1 /**
  2  * Returns a {@link pv.Flatten} operator for the specified map. This is a
  3  * convenience factory method, equivalent to <tt>new pv.Flatten(map)</tt>.
  4  *
  5  * @see pv.Flatten
  6  * @param map a map to flatten.
  7  * @returns {pv.Flatten} a flatten operator for the specified map.
  8  */
  9 pv.flatten = function(map) {
 10   return new pv.Flatten(map);
 11 };
 12 
 13 /**
 14  * Constructs a flatten operator for the specified map. This constructor should
 15  * not be invoked directly; use {@link pv.flatten} instead.
 16  *
 17  * @class Represents a flatten operator for the specified array. Flattening
 18  * allows hierarchical maps to be flattened into an array. The levels in the
 19  * input tree are specified by <i>key</i> functions.
 20  *
 21  * <p>For example, consider the following hierarchical data structure of Barley
 22  * yields, from various sites in Minnesota during 1931-2:
 23  *
 24  * <pre>{ 1931: {
 25  *     Manchuria: {
 26  *       "University Farm": 27.00,
 27  *       "Waseca": 48.87,
 28  *       "Morris": 27.43,
 29  *       ... },
 30  *     Glabron: {
 31  *       "University Farm": 43.07,
 32  *       "Waseca": 55.20,
 33  *       ... } },
 34  *   1932: {
 35  *     ... } }</pre>
 36  *
 37  * To facilitate visualization, it may be useful to flatten the tree into a
 38  * tabular array:
 39  *
 40  * <pre>var array = pv.flatten(yields)
 41  *     .key("year")
 42  *     .key("variety")
 43  *     .key("site")
 44  *     .key("yield")
 45  *     .array();</pre>
 46  *
 47  * This returns an array of object elements. Each element in the array has
 48  * attributes corresponding to this flatten operator's keys:
 49  *
 50  * <pre>{ site: "University Farm", variety: "Manchuria", year: 1931, yield: 27 },
 51  * { site: "Waseca", variety: "Manchuria", year: 1931, yield: 48.87 },
 52  * { site: "Morris", variety: "Manchuria", year: 1931, yield: 27.43 },
 53  * { site: "University Farm", variety: "Glabron", year: 1931, yield: 43.07 },
 54  * { site: "Waseca", variety: "Glabron", year: 1931, yield: 55.2 }, ...</pre>
 55  *
 56  * <p>The flatten operator is roughly the inverse of the {@link pv.Nest} and
 57  * {@link pv.Tree} operators.
 58  *
 59  * @param map a map to flatten.
 60  */
 61 pv.Flatten = function(map) {
 62   this.map = map;
 63   this.keys = [];
 64 };
 65 
 66 /**
 67  * Flattens using the specified key function. Multiple keys may be added to the
 68  * flatten; the tiers of the underlying tree must correspond to the specified
 69  * keys, in order. The order of the returned array is undefined; however, you
 70  * can easily sort it.
 71  *
 72  * @param {string} key the key name.
 73  * @param {function} [f] an optional value map function.
 74  * @returns {pv.Nest} this.
 75  */
 76 pv.Flatten.prototype.key = function(key, f) {
 77   this.keys.push({name: key, value: f});
 78   delete this.$leaf;
 79   return this;
 80 };
 81 
 82 /**
 83  * Flattens using the specified leaf function. This is an alternative to
 84  * specifying an explicit set of keys; the tiers of the underlying tree will be
 85  * determined dynamically by recursing on the values, and the resulting keys
 86  * will be stored in the entries <tt>keys</tt> attribute. The leaf function must
 87  * return true for leaves, and false for internal nodes.
 88  *
 89  * @param {function} f a leaf function.
 90  * @returns {pv.Nest} this.
 91  */
 92 pv.Flatten.prototype.leaf = function(f) {
 93   this.keys.length = 0;
 94   this.$leaf = f;
 95   return this;
 96 };
 97 
 98 /**
 99  * Returns the flattened array. Each entry in the array is an object; each
100  * object has attributes corresponding to this flatten operator's keys.
101  *
102  * @returns an array of elements from the flattened map.
103  */
104 pv.Flatten.prototype.array = function() {
105   var entries = [], stack = [], keys = this.keys, leaf = this.$leaf;
106 
107   /* Recursively visit using the leaf function. */
108   if (leaf) {
109     function recurse(value, i) {
110       if (leaf(value)) {
111         entries.push({keys: stack.slice(), value: value});
112       } else {
113         for (var key in value) {
114           stack.push(key);
115           recurse(value[key], i + 1);
116           stack.pop();
117         }
118       }
119     }
120     recurse(this.map, 0);
121     return entries;
122   }
123 
124   /* Recursively visits the specified value. */
125   function visit(value, i) {
126     if (i < keys.length - 1) {
127       for (var key in value) {
128         stack.push(key);
129         visit(value[key], i + 1);
130         stack.pop();
131       }
132     } else {
133       entries.push(stack.concat(value));
134     }
135   }
136 
137   visit(this.map, 0);
138   return entries.map(function(stack) {
139       var m = {};
140       for (var i = 0; i < keys.length; i++) {
141         var k = keys[i], v = stack[i];
142         m[k.name] = k.value ? k.value.call(null, v) : v;
143       }
144       return m;
145     });
146 };
147