1 /**
  2  * Returns a {@link pv.Nest} operator for the specified array. This is a
  3  * convenience factory method, equivalent to <tt>new pv.Nest(array)</tt>.
  4  *
  5  * @see pv.Nest
  6  * @param {array} array an array of elements to nest.
  7  * @returns {pv.Nest} a nest operator for the specified array.
  8  */
  9 pv.nest = function(array) {
 10   return new pv.Nest(array);
 11 };
 12 
 13 /**
 14  * Constructs a nest operator for the specified array. This constructor should
 15  * not be invoked directly; use {@link pv.nest} instead.
 16  *
 17  * @class Represents a {@link Nest} operator for the specified array. Nesting
 18  * allows elements in an array to be grouped into a hierarchical tree
 19  * structure. The levels in the tree are specified by <i>key</i> functions. The
 20  * leaf nodes of the tree can be sorted by value, while the internal nodes can
 21  * be sorted by key. Finally, the tree can be returned either has a
 22  * multidimensional array via {@link #entries}, or as a hierarchical map via
 23  * {@link #map}. The {@link #rollup} routine similarly returns a map, collapsing
 24  * the elements in each leaf node using a summary function.
 25  *
 26  * <p>For example, consider the following tabular data structure of Barley
 27  * yields, from various sites in Minnesota during 1931-2:
 28  *
 29  * <pre>{ yield: 27.00, variety: "Manchuria", year: 1931, site: "University Farm" },
 30  * { yield: 48.87, variety: "Manchuria", year: 1931, site: "Waseca" },
 31  * { yield: 27.43, variety: "Manchuria", year: 1931, site: "Morris" }, ...</pre>
 32  *
 33  * To facilitate visualization, it may be useful to nest the elements first by
 34  * year, and then by variety, as follows:
 35  *
 36  * <pre>var nest = pv.nest(yields)
 37  *     .key(function(d) d.year)
 38  *     .key(function(d) d.variety)
 39  *     .entries();</pre>
 40  *
 41  * This returns a nested array. Each element of the outer array is a key-values
 42  * pair, listing the values for each distinct key:
 43  *
 44  * <pre>{ key: 1931, values: [
 45  *   { key: "Manchuria", values: [
 46  *       { yield: 27.00, variety: "Manchuria", year: 1931, site: "University Farm" },
 47  *       { yield: 48.87, variety: "Manchuria", year: 1931, site: "Waseca" },
 48  *       { yield: 27.43, variety: "Manchuria", year: 1931, site: "Morris" },
 49  *       ...
 50  *     ] },
 51  *   { key: "Glabron", values: [
 52  *       { yield: 43.07, variety: "Glabron", year: 1931, site: "University Farm" },
 53  *       { yield: 55.20, variety: "Glabron", year: 1931, site: "Waseca" },
 54  *       ...
 55  *     ] },
 56  *   ] },
 57  * { key: 1932, values: ... }</pre>
 58  *
 59  * Further details, including sorting and rollup, is provided below on the
 60  * corresponding methods.
 61  *
 62  * @param {array} array an array of elements to nest.
 63  */
 64 pv.Nest = function(array) {
 65   this.array = array;
 66   this.keys = [];
 67 };
 68 
 69 /**
 70  * Nests using the specified key function. Multiple keys may be added to the
 71  * nest; the array elements will be nested in the order keys are specified.
 72  *
 73  * @param {function} key a key function; must return a string or suitable map
 74  * key.
 75  * @returns {pv.Nest} this.
 76  */
 77 pv.Nest.prototype.key = function(key) {
 78   this.keys.push(key);
 79   return this;
 80 };
 81 
 82 /**
 83  * Sorts the previously-added keys. The natural sort order is used by default
 84  * (see {@link pv.naturalOrder}); if an alternative order is desired,
 85  * <tt>order</tt> should be a comparator function. If this method is not called
 86  * (i.e., keys are <i>unsorted</i>), keys will appear in the order they appear
 87  * in the underlying elements array. For example,
 88  *
 89  * <pre>pv.nest(yields)
 90  *     .key(function(d) d.year)
 91  *     .key(function(d) d.variety)
 92  *     .sortKeys()
 93  *     .entries()</pre>
 94  *
 95  * groups yield data by year, then variety, and sorts the variety groups
 96  * lexicographically (since the variety attribute is a string).
 97  *
 98  * <p>Key sort order is only used in conjunction with {@link #entries}, which
 99  * returns an array of key-values pairs. If the nest is used to construct a
100  * {@link #map} instead, keys are unsorted.
101  *
102  * @param {function} [order] an optional comparator function.
103  * @returns {pv.Nest} this.
104  */
105 pv.Nest.prototype.sortKeys = function(order) {
106   this.keys[this.keys.length - 1].order = order || pv.naturalOrder;
107   return this;
108 };
109 
110 /**
111  * Sorts the leaf values. The natural sort order is used by default (see
112  * {@link pv.naturalOrder}); if an alternative order is desired, <tt>order</tt>
113  * should be a comparator function. If this method is not called (i.e., values
114  * are <i>unsorted</i>), values will appear in the order they appear in the
115  * underlying elements array. For example,
116  *
117  * <pre>pv.nest(yields)
118  *     .key(function(d) d.year)
119  *     .key(function(d) d.variety)
120  *     .sortValues(function(a, b) a.yield - b.yield)
121  *     .entries()</pre>
122  *
123  * groups yield data by year, then variety, and sorts the values for each
124  * variety group by yield.
125  *
126  * <p>Value sort order, unlike keys, applies to both {@link #entries} and
127  * {@link #map}. It has no effect on {@link #rollup}.
128  *
129  * @param {function} [order] an optional comparator function.
130  * @returns {pv.Nest} this.
131  */
132 pv.Nest.prototype.sortValues = function(order) {
133   this.order = order || pv.naturalOrder;
134   return this;
135 };
136 
137 /**
138  * Returns a hierarchical map of values. Each key adds one level to the
139  * hierarchy. With only a single key, the returned map will have a key for each
140  * distinct value of the key function; the correspond value with be an array of
141  * elements with that key value. If a second key is added, this will be a nested
142  * map. For example:
143  *
144  * <pre>pv.nest(yields)
145  *     .key(function(d) d.variety)
146  *     .key(function(d) d.site)
147  *     .map()</pre>
148  *
149  * returns a map <tt>m</tt> such that <tt>m[variety][site]</tt> is an array, a subset of
150  * <tt>yields</tt>, with each element having the given variety and site.
151  *
152  * @returns a hierarchical map of values.
153  */
154 pv.Nest.prototype.map = function() {
155   var map = {}, values = [];
156 
157   /* Build the map. */
158   for (var i, j = 0; j < this.array.length; j++) {
159     var x = this.array[j];
160     var m = map;
161     for (i = 0; i < this.keys.length - 1; i++) {
162       var k = this.keys[i](x);
163       if (!m[k]) m[k] = {};
164       m = m[k];
165     }
166     k = this.keys[i](x);
167     if (!m[k]) {
168       var a = [];
169       values.push(a);
170       m[k] = a;
171     }
172     m[k].push(x);
173   }
174 
175   /* Sort each leaf array. */
176   if (this.order) {
177     for (var i = 0; i < values.length; i++) {
178       values[i].sort(this.order);
179     }
180   }
181 
182   return map;
183 };
184 
185 /**
186  * Returns a hierarchical nested array. This method is similar to
187  * {@link pv.entries}, but works recursively on the entire hierarchy. Rather
188  * than returning a map like {@link #map}, this method returns a nested
189  * array. Each element of the array has a <tt>key</tt> and <tt>values</tt>
190  * field. For leaf nodes, the <tt>values</tt> array will be a subset of the
191  * underlying elements array; for non-leaf nodes, the <tt>values</tt> array will
192  * contain more key-values pairs.
193  *
194  * <p>For an example usage, see the {@link Nest} constructor.
195  *
196  * @returns a hierarchical nested array.
197  */
198 pv.Nest.prototype.entries = function() {
199 
200   /** Recursively extracts the entries for the given map. */
201   function entries(map) {
202     var array = [];
203     for (var k in map) {
204       var v = map[k];
205       array.push({ key: k, values: (v instanceof Array) ? v : entries(v) });
206     };
207     return array;
208   }
209 
210   /** Recursively sorts the values for the given key-values array. */
211   function sort(array, i) {
212     var o = this.keys[i].order;
213     if (o) array.sort(function(a, b) { return o(a.key, b.key); });
214     if (++i < this.keys.length) {
215       for (var j = 0; j < array.length; j++) {
216         sort.call(this, array[j].values, i);
217       }
218     }
219     return array;
220   }
221 
222   return sort.call(this, entries(this.map()), 0);
223 };
224 
225 /**
226  * Returns a rollup map. The behavior of this method is the same as
227  * {@link #map}, except that the leaf values are replaced with the return value
228  * of the specified rollup function <tt>f</tt>. For example,
229  *
230  * <pre>pv.nest(yields)
231  *      .key(function(d) d.site)
232  *      .rollup(function(v) pv.median(v, function(d) d.yield))</pre>
233  *
234  * first groups yield data by site, and then returns a map from site to median
235  * yield for the given site.
236  *
237  * @see #map
238  * @param {function} f a rollup function.
239  * @returns a hierarchical map, with the leaf values computed by <tt>f</tt>.
240  */
241 pv.Nest.prototype.rollup = function(f) {
242 
243   /** Recursively descends to the leaf nodes (arrays) and does rollup. */
244   function rollup(map) {
245     for (var key in map) {
246       var value = map[key];
247       if (value instanceof Array) {
248         map[key] = f(value);
249       } else {
250         rollup(value);
251       }
252     }
253     return map;
254   }
255 
256   return rollup(this.map());
257 };
258