1 /**
  2  * @private A private variant of Array.prototype.map that supports the index
  3  * property.
  4  */
  5 pv.map = function(array, f) {
  6   var o = {};
  7   return f
  8       ? array.map(function(d, i) { o.index = i; return f.call(o, d); })
  9       : array.slice();
 10 };
 11 
 12 /**
 13  * Concatenates the specified array with itself <i>n</i> times. For example,
 14  * <tt>pv.repeat([1, 2])</tt> returns [1, 2, 1, 2].
 15  *
 16  * @param {array} a an array.
 17  * @param {number} [n] the number of times to repeat; defaults to two.
 18  * @returns {array} an array that repeats the specified array.
 19  */
 20 pv.repeat = function(array, n) {
 21   if (arguments.length == 1) n = 2;
 22   return pv.blend(pv.range(n).map(function() { return array; }));
 23 };
 24 
 25 /**
 26  * Given two arrays <tt>a</tt> and <tt>b</tt>, <style
 27  * type="text/css">sub{line-height:0}</style> returns an array of all possible
 28  * pairs of elements [a<sub>i</sub>, b<sub>j</sub>]. The outer loop is on array
 29  * <i>a</i>, while the inner loop is on <i>b</i>, such that the order of
 30  * returned elements is [a<sub>0</sub>, b<sub>0</sub>], [a<sub>0</sub>,
 31  * b<sub>1</sub>], ... [a<sub>0</sub>, b<sub>m</sub>], [a<sub>1</sub>,
 32  * b<sub>0</sub>], [a<sub>1</sub>, b<sub>1</sub>], ... [a<sub>1</sub>,
 33  * b<sub>m</sub>], ... [a<sub>n</sub>, b<sub>m</sub>]. If either array is empty,
 34  * an empty array is returned.
 35  *
 36  * @param {array} a an array.
 37  * @param {array} b an array.
 38  * @returns {array} an array of pairs of elements in <tt>a</tt> and <tt>b</tt>.
 39  */
 40 pv.cross = function(a, b) {
 41   var array = [];
 42   for (var i = 0, n = a.length, m = b.length; i < n; i++) {
 43     for (var j = 0, x = a[i]; j < m; j++) {
 44       array.push([x, b[j]]);
 45     }
 46   }
 47   return array;
 48 };
 49 
 50 /**
 51  * Given the specified array of arrays, concatenates the arrays into a single
 52  * array. If the individual arrays are explicitly known, an alternative to blend
 53  * is to use JavaScript's <tt>concat</tt> method directly. These two equivalent
 54  * expressions:<ul>
 55  *
 56  * <li><tt>pv.blend([[1, 2, 3], ["a", "b", "c"]])</tt>
 57  * <li><tt>[1, 2, 3].concat(["a", "b", "c"])</tt>
 58  *
 59  * </ul>return [1, 2, 3, "a", "b", "c"].
 60  *
 61  * @param {array[]} arrays an array of arrays.
 62  * @returns {array} an array containing all the elements of each array in
 63  * <tt>arrays</tt>.
 64  */
 65 pv.blend = function(arrays) {
 66   return Array.prototype.concat.apply([], arrays);
 67 };
 68 
 69 /**
 70  * Given the specified array of arrays, <style
 71  * type="text/css">sub{line-height:0}</style> transposes each element
 72  * array<sub>ij</sub> with array<sub>ji</sub>. If the array has dimensions
 73  * <i>n</i>×<i>m</i>, it will have dimensions <i>m</i>×<i>n</i>
 74  * after this method returns. This method transposes the elements of the array
 75  * in place, mutating the array, and returning a reference to the array.
 76  *
 77  * @param {array[]} arrays an array of arrays.
 78  * @returns {array[]} the passed-in array, after transposing the elements.
 79  */
 80 pv.transpose = function(arrays) {
 81   var n = arrays.length, m = pv.max(arrays, function(d) { return d.length; });
 82 
 83   if (m > n) {
 84     arrays.length = m;
 85     for (var i = n; i < m; i++) {
 86       arrays[i] = new Array(n);
 87     }
 88     for (var i = 0; i < n; i++) {
 89       for (var j = i + 1; j < m; j++) {
 90         var t = arrays[i][j];
 91         arrays[i][j] = arrays[j][i];
 92         arrays[j][i] = t;
 93       }
 94     }
 95   } else {
 96     for (var i = 0; i < m; i++) {
 97       arrays[i].length = n;
 98     }
 99     for (var i = 0; i < n; i++) {
100       for (var j = 0; j < i; j++) {
101         var t = arrays[i][j];
102         arrays[i][j] = arrays[j][i];
103         arrays[j][i] = t;
104       }
105     }
106   }
107 
108   arrays.length = m;
109   for (var i = 0; i < m; i++) {
110     arrays[i].length = n;
111   }
112 
113   return arrays;
114 };
115 
116 /**
117  * Returns a normalized copy of the specified array, such that the sum of the
118  * returned elements sum to one. If the specified array is not an array of
119  * numbers, an optional accessor function <tt>f</tt> can be specified to map the
120  * elements to numbers. For example, if <tt>array</tt> is an array of objects,
121  * and each object has a numeric property "foo", the expression
122  *
123  * <pre>pv.normalize(array, function(d) d.foo)</pre>
124  *
125  * returns a normalized array on the "foo" property. If an accessor function is
126  * not specified, the identity function is used. Accessor functions can refer to
127  * <tt>this.index</tt>.
128  *
129  * @param {array} array an array of objects, or numbers.
130  * @param {function} [f] an optional accessor function.
131  * @returns {number[]} an array of numbers that sums to one.
132  */
133 pv.normalize = function(array, f) {
134   var norm = pv.map(array, f), sum = pv.sum(norm);
135   for (var i = 0; i < norm.length; i++) norm[i] /= sum;
136   return norm;
137 };
138 
139 /**
140  * Returns a permutation of the specified array, using the specified array of
141  * indexes. The returned array contains the corresponding element in
142  * <tt>array</tt> for each index in <tt>indexes</tt>, in order. For example,
143  *
144  * <pre>pv.permute(["a", "b", "c"], [1, 2, 0])</pre>
145  *
146  * returns <tt>["b", "c", "a"]</tt>. It is acceptable for the array of indexes
147  * to be a different length from the array of elements, and for indexes to be
148  * duplicated or omitted. The optional accessor function <tt>f</tt> can be used
149  * to perform a simultaneous mapping of the array elements. Accessor functions
150  * can refer to <tt>this.index</tt>.
151  *
152  * @param {array} array an array.
153  * @param {number[]} indexes an array of indexes into <tt>array</tt>.
154  * @param {function} [f] an optional accessor function.
155  * @returns {array} an array of elements from <tt>array</tt>; a permutation.
156  */
157 pv.permute = function(array, indexes, f) {
158   if (!f) f = pv.identity;
159   var p = new Array(indexes.length), o = {};
160   indexes.forEach(function(j, i) { o.index = j; p[i] = f.call(o, array[j]); });
161   return p;
162 };
163 
164 /**
165  * Returns a map from key to index for the specified <tt>keys</tt> array. For
166  * example,
167  *
168  * <pre>pv.numerate(["a", "b", "c"])</pre>
169  *
170  * returns <tt>{a: 0, b: 1, c: 2}</tt>. Note that since JavaScript maps only
171  * support string keys, <tt>keys</tt> must contain strings, or other values that
172  * naturally map to distinct string values. Alternatively, an optional accessor
173  * function <tt>f</tt> can be specified to compute the string key for the given
174  * element. Accessor functions can refer to <tt>this.index</tt>.
175  *
176  * @param {array} keys an array, usually of string keys.
177  * @param {function} [f] an optional key function.
178  * @returns a map from key to index.
179  */
180 pv.numerate = function(keys, f) {
181   if (!f) f = pv.identity;
182   var map = {}, o = {};
183   keys.forEach(function(x, i) { o.index = i; map[f.call(o, x)] = i; });
184   return map;
185 };
186 
187 /**
188  * Returns the unique elements in the specified array, in the order they appear.
189  * Note that since JavaScript maps only support string keys, <tt>array</tt> must
190  * contain strings, or other values that naturally map to distinct string
191  * values. Alternatively, an optional accessor function <tt>f</tt> can be
192  * specified to compute the string key for the given element. Accessor functions
193  * can refer to <tt>this.index</tt>.
194  *
195  * @param {array} array an array, usually of string keys.
196  * @param {function} [f] an optional key function.
197  * @returns {array} the unique values.
198  */
199 pv.uniq = function(array, f) {
200   if (!f) f = pv.identity;
201   var map = {}, keys = [], o = {}, y;
202   array.forEach(function(x, i) {
203     o.index = i;
204     y = f.call(o, x);
205     if (!(y in map)) map[y] = keys.push(y);
206   });
207   return keys;
208 };
209 
210 /**
211  * The comparator function for natural order. This can be used in conjunction with
212  * the built-in array <tt>sort</tt> method to sort elements by their natural
213  * order, ascending. Note that if no comparator function is specified to the
214  * built-in <tt>sort</tt> method, the default order is lexicographic, <i>not</i>
215  * natural!
216  *
217  * @see <a
218  * href="http://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort">Array.sort</a>.
219  * @param a an element to compare.
220  * @param b an element to compare.
221  * @returns {number} negative if a < b; positive if a > b; otherwise 0.
222  */
223 pv.naturalOrder = function(a, b) {
224   return (a < b) ? -1 : ((a > b) ? 1 : 0);
225 };
226 
227 /**
228  * The comparator function for reverse natural order. This can be used in
229  * conjunction with the built-in array <tt>sort</tt> method to sort elements by
230  * their natural order, descending. Note that if no comparator function is
231  * specified to the built-in <tt>sort</tt> method, the default order is
232  * lexicographic, <i>not</i> natural!
233  *
234  * @see #naturalOrder
235  * @param a an element to compare.
236  * @param b an element to compare.
237  * @returns {number} negative if a < b; positive if a > b; otherwise 0.
238  */
239 pv.reverseOrder = function(b, a) {
240   return (a < b) ? -1 : ((a > b) ? 1 : 0);
241 };
242 
243 /**
244  * Searches the specified array of numbers for the specified value using the
245  * binary search algorithm. The array must be sorted (as by the <tt>sort</tt>
246  * method) prior to making this call. If it is not sorted, the results are
247  * undefined. If the array contains multiple elements with the specified value,
248  * there is no guarantee which one will be found.
249  *
250  * <p>The <i>insertion point</i> is defined as the point at which the value
251  * would be inserted into the array: the index of the first element greater than
252  * the value, or <tt>array.length</tt>, if all elements in the array are less
253  * than the specified value. Note that this guarantees that the return value
254  * will be nonnegative if and only if the value is found.
255  *
256  * @param {number[]} array the array to be searched.
257  * @param {number} value the value to be searched for.
258  * @returns the index of the search value, if it is contained in the array;
259  * otherwise, (-(<i>insertion point</i>) - 1).
260  * @param {function} [f] an optional key function.
261  */
262 pv.search = function(array, value, f) {
263   if (!f) f = pv.identity;
264   var low = 0, high = array.length - 1;
265   while (low <= high) {
266     var mid = (low + high) >> 1, midValue = f(array[mid]);
267     if (midValue < value) low = mid + 1;
268     else if (midValue > value) high = mid - 1;
269     else return mid;
270   }
271   return -low - 1;
272 };
273 
274 pv.search.index = function(array, value, f) {
275   var i = pv.search(array, value, f);
276   return (i < 0) ? (-i - 1) : i;
277 };
278