1 /**
  2  * The top-level Protovis namespace. All public methods and fields should be
  3  * registered on this object. Note that core Protovis source is surrounded by an
  4  * anonymous function, so any other declared globals will not be visible outside
  5  * of core methods. This also allows multiple versions of Protovis to coexist,
  6  * since each version will see their own <tt>pv</tt> namespace.
  7  *
  8  * @namespace The top-level Protovis namespace, <tt>pv</tt>.
  9  */
 10 var pv = {};
 11 
 12 /**
 13  * @private Returns a prototype object suitable for extending the given class
 14  * <tt>f</tt>. Rather than constructing a new instance of <tt>f</tt> to serve as
 15  * the prototype (which unnecessarily runs the constructor on the created
 16  * prototype object, potentially polluting it), an anonymous function is
 17  * generated internally that shares the same prototype:
 18  *
 19  * <pre>function g() {}
 20  * g.prototype = f.prototype;
 21  * return new g();</pre>
 22  *
 23  * For more details, see Douglas Crockford's essay on prototypal inheritance.
 24  *
 25  * @param {function} f a constructor.
 26  * @returns a suitable prototype object.
 27  * @see Douglas Crockford's essay on <a
 28  * href="http://javascript.crockford.com/prototypal.html">prototypal
 29  * inheritance</a>.
 30  */
 31 pv.extend = function(f) {
 32   function g() {}
 33   g.prototype = f.prototype || f;
 34   return new g();
 35 };
 36 
 37 try {
 38   eval("pv.parse = function(x) x;"); // native support
 39 } catch (e) {
 40 
 41 /**
 42  * @private Parses a Protovis specification, which may use JavaScript 1.8
 43  * function expresses, replacing those function expressions with proper
 44  * functions such that the code can be run by a JavaScript 1.6 interpreter. This
 45  * hack only supports function expressions (using clumsy regular expressions, no
 46  * less), and not other JavaScript 1.8 features such as let expressions.
 47  *
 48  * @param {string} s a Protovis specification (i.e., a string of JavaScript 1.8
 49  * source code).
 50  * @returns {string} a conformant JavaScript 1.6 source code.
 51  */
 52   pv.parse = function(js) { // hacky regex support
 53     var re = new RegExp("function(\\s+\\w+)?\\([^)]*\\)\\s*", "mg"), m, i = 0;
 54     var s = "";
 55     while (m = re.exec(js)) {
 56       var j = m.index + m[0].length;
 57       if (js.charAt(j--) != '{') {
 58         s += js.substring(i, j) + "{return ";
 59         i = j;
 60         for (var p = 0; p >= 0 && j < js.length; j++) {
 61           var c = js.charAt(j);
 62           switch (c) {
 63             case '"': case '\'': {
 64               while (++j < js.length && (d = js.charAt(j)) != c) {
 65                 if (d == '\\') j++;
 66               }
 67               break;
 68             }
 69             case '[': case '(': p++; break;
 70             case ']': case ')': p--; break;
 71             case ';':
 72             case ',': if (p == 0) p--; break;
 73           }
 74         }
 75         s += pv.parse(js.substring(i, --j)) + ";}";
 76         i = j;
 77       }
 78       re.lastIndex = j;
 79     }
 80     s += js.substring(i);
 81     return s;
 82   };
 83 }
 84 
 85 /**
 86  * Returns the passed-in argument, <tt>x</tt>; the identity function. This method
 87  * is provided for convenience since it is used as the default behavior for a
 88  * number of property functions.
 89  *
 90  * @param x a value.
 91  * @returns the value <tt>x</tt>.
 92  */
 93 pv.identity = function(x) { return x; };
 94 
 95 /**
 96  * Returns <tt>this.index</tt>. This method is provided for convenience for use
 97  * with scales. For example, to color bars by their index, say:
 98  *
 99  * <pre>.fillStyle(pv.Colors.category10().by(pv.index))</pre>
100  *
101  * This method is equivalent to <tt>function() this.index</tt>, but more
102  * succinct. Note that the <tt>index</tt> property is also supported for
103  * accessor functions with {@link pv.max}, {@link pv.min} and other array
104  * utility methods.
105  *
106  * @see pv.Scale
107  * @see pv.Mark#index
108  */
109 pv.index = function() { return this.index; };
110 
111 /**
112  * Returns <tt>this.childIndex</tt>. This method is provided for convenience for
113  * use with scales. For example, to color bars by their child index, say:
114  *
115  * <pre>.fillStyle(pv.Colors.category10().by(pv.child))</pre>
116  *
117  * This method is equivalent to <tt>function() this.childIndex</tt>, but more
118  * succinct.
119  *
120  * @see pv.Scale
121  * @see pv.Mark#childIndex
122  */
123 pv.child = function() { return this.childIndex; };
124 
125 /**
126  * Returns <tt>this.parent.index</tt>. This method is provided for convenience
127  * for use with scales. This method is provided for convenience for use with
128  * scales. For example, to color bars by their parent index, say:
129  *
130  * <pre>.fillStyle(pv.Colors.category10().by(pv.parent))</pre>
131  *
132  * Tthis method is equivalent to <tt>function() this.parent.index</tt>, but more
133  * succinct.
134  *
135  * @see pv.Scale
136  * @see pv.Mark#index
137  */
138 pv.parent = function() { return this.parent.index; };
139 
140 /**
141  * Returns an array of numbers, starting at <tt>start</tt>, incrementing by
142  * <tt>step</tt>, until <tt>stop</tt> is reached. The stop value is exclusive. If
143  * only a single argument is specified, this value is interpeted as the
144  * <i>stop</i> value, with the <i>start</i> value as zero. If only two arguments
145  * are specified, the step value is implied to be one.
146  *
147  * <p>The method is modeled after the built-in <tt>range</tt> method from
148  * Python. See the Python documentation for more details.
149  *
150  * @see <a href="http://docs.python.org/library/functions.html#range">Python range</a>
151  * @param {number} [start] the start value.
152  * @param {number} stop the stop value.
153  * @param {number} [step] the step value.
154  * @returns {number[]} an array of numbers.
155  */
156 pv.range = function(start, stop, step) {
157   if (arguments.length == 1) {
158     stop = start;
159     start = 0;
160   }
161   if (step == undefined) step = 1;
162   else if (!step) throw new Error("step must be non-zero");
163   var array = [], i = 0, j;
164   if (step < 0) {
165     while ((j = start + step * i++) > stop) {
166       array.push(j);
167     }
168   } else {
169     while ((j = start + step * i++) < stop) {
170       array.push(j);
171     }
172   }
173   return array;
174 };
175 
176 /**
177  * Returns a random number in the range [<tt>min</tt>, <tt>max</tt>) that is a
178  * multiple of <tt>step</tt>. More specifically, the returned number is of the
179  * form <tt>min</tt> + <i>n</i> * <tt>step</tt>, where <i>n</i> is a nonnegative
180  * integer. If <tt>step</tt> is not specified, it defaults to 1, returning a
181  * random integer if <tt>min</tt> is also an integer.
182  *
183  * @param min {number} minimum value.
184  * @param [max] {number} maximum value.
185  * @param [step] {numbeR} step value.
186  */
187 pv.random = function(min, max, step) {
188   if (arguments.length == 1) {
189     max = min;
190     min = 0;
191   }
192   if (step == undefined) {
193     step = 1;
194   }
195   return step
196       ? (Math.floor(Math.random() * (max - min) / step) * step + min)
197       : (Math.random() * (max - min) + min);
198 };
199 
200 /**
201  * Concatenates the specified array with itself <i>n</i> times. For example,
202  * <tt>pv.repeat([1, 2])</tt> returns [1, 2, 1, 2].
203  *
204  * @param {array} a an array.
205  * @param {number} [n] the number of times to repeat; defaults to two.
206  * @returns {array} an array that repeats the specified array.
207  */
208 pv.repeat = function(array, n) {
209   if (arguments.length == 1) n = 2;
210   return pv.blend(pv.range(n).map(function() { return array; }));
211 };
212 
213 /**
214  * Given two arrays <tt>a</tt> and <tt>b</tt>, <style
215  * type="text/css">sub{line-height:0}</style> returns an array of all possible
216  * pairs of elements [a<sub>i</sub>, b<sub>j</sub>]. The outer loop is on array
217  * <i>a</i>, while the inner loop is on <i>b</i>, such that the order of
218  * returned elements is [a<sub>0</sub>, b<sub>0</sub>], [a<sub>0</sub>,
219  * b<sub>1</sub>], ... [a<sub>0</sub>, b<sub>m</sub>], [a<sub>1</sub>,
220  * b<sub>0</sub>], [a<sub>1</sub>, b<sub>1</sub>], ... [a<sub>1</sub>,
221  * b<sub>m</sub>], ... [a<sub>n</sub>, b<sub>m</sub>]. If either array is empty,
222  * an empty array is returned.
223  *
224  * @param {array} a an array.
225  * @param {array} b an array.
226  * @returns {array} an array of pairs of elements in <tt>a</tt> and <tt>b</tt>.
227  */
228 pv.cross = function(a, b) {
229   var array = [];
230   for (var i = 0, n = a.length, m = b.length; i < n; i++) {
231     for (var j = 0, x = a[i]; j < m; j++) {
232       array.push([x, b[j]]);
233     }
234   }
235   return array;
236 };
237 
238 /**
239  * Given the specified array of arrays, concatenates the arrays into a single
240  * array. If the individual arrays are explicitly known, an alternative to blend
241  * is to use JavaScript's <tt>concat</tt> method directly. These two equivalent
242  * expressions:<ul>
243  *
244  * <li><tt>pv.blend([[1, 2, 3], ["a", "b", "c"]])</tt>
245  * <li><tt>[1, 2, 3].concat(["a", "b", "c"])</tt>
246  *
247  * </ul>return [1, 2, 3, "a", "b", "c"].
248  *
249  * @param {array[]} arrays an array of arrays.
250  * @returns {array} an array containing all the elements of each array in
251  * <tt>arrays</tt>.
252  */
253 pv.blend = function(arrays) {
254   return Array.prototype.concat.apply([], arrays);
255 };
256 
257 /**
258  * Given the specified array of arrays, <style
259  * type="text/css">sub{line-height:0}</style> transposes each element
260  * array<sub>ij</sub> with array<sub>ji</sub>. If the array has dimensions
261  * <i>n</i>×<i>m</i>, it will have dimensions <i>m</i>×<i>n</i>
262  * after this method returns. This method transposes the elements of the array
263  * in place, mutating the array, and returning a reference to the array.
264  *
265  * @param {array[]} arrays an array of arrays.
266  * @returns {array[]} the passed-in array, after transposing the elements.
267  */
268 pv.transpose = function(arrays) {
269   var n = arrays.length, m = pv.max(arrays, function(d) { return d.length; });
270 
271   if (m > n) {
272     arrays.length = m;
273     for (var i = n; i < m; i++) {
274       arrays[i] = new Array(n);
275     }
276     for (var i = 0; i < n; i++) {
277       for (var j = i + 1; j < m; j++) {
278         var t = arrays[i][j];
279         arrays[i][j] = arrays[j][i];
280         arrays[j][i] = t;
281       }
282     }
283   } else {
284     for (var i = 0; i < m; i++) {
285       arrays[i].length = n;
286     }
287     for (var i = 0; i < n; i++) {
288       for (var j = 0; j < i; j++) {
289         var t = arrays[i][j];
290         arrays[i][j] = arrays[j][i];
291         arrays[j][i] = t;
292       }
293     }
294   }
295 
296   arrays.length = m;
297   for (var i = 0; i < m; i++) {
298     arrays[i].length = n;
299   }
300 
301   return arrays;
302 };
303 
304 /**
305  * Returns all of the property names (keys) of the specified object (a map). The
306  * order of the returned array is not defined.
307  *
308  * @param map an object.
309  * @returns {string[]} an array of strings corresponding to the keys.
310  * @see #entries
311  */
312 pv.keys = function(map) {
313   var array = [];
314   for (var key in map) {
315     array.push(key);
316   }
317   return array;
318 };
319 
320 /**
321  * Returns all of the entries (key-value pairs) of the specified object (a
322  * map). The order of the returned array is not defined. Each key-value pair is
323  * represented as an object with <tt>key</tt> and <tt>value</tt> attributes,
324  * e.g., <tt>{key: "foo", value: 42}</tt>.
325  *
326  * @param map an object.
327  * @returns {array} an array of key-value pairs corresponding to the keys.
328  */
329 pv.entries = function(map) {
330   var array = [];
331   for (var key in map) {
332     array.push({ key: key, value: map[key] });
333   }
334   return array;
335 };
336 
337 /**
338  * Returns all of the values (attribute values) of the specified object (a
339  * map). The order of the returned array is not defined.
340  *
341  * @param map an object.
342  * @returns {array} an array of objects corresponding to the values.
343  * @see #entries
344  */
345 pv.values = function(map) {
346   var array = [];
347   for (var key in map) {
348     array.push(map[key]);
349   }
350   return array;
351 };
352 
353 /**
354  * @private A private variant of Array.prototype.map that supports the index
355  * property.
356  */
357 function map(array, f) {
358   var o = {};
359   return f
360       ? array.map(function(d, i) { o.index = i; return f.call(o, d); })
361       : array.slice();
362 };
363 
364 /**
365  * Returns a normalized copy of the specified array, such that the sum of the
366  * returned elements sum to one. If the specified array is not an array of
367  * numbers, an optional accessor function <tt>f</tt> can be specified to map the
368  * elements to numbers. For example, if <tt>array</tt> is an array of objects,
369  * and each object has a numeric property "foo", the expression
370  *
371  * <pre>pv.normalize(array, function(d) d.foo)</pre>
372  *
373  * returns a normalized array on the "foo" property. If an accessor function is
374  * not specified, the identity function is used. Accessor functions can refer to
375  * <tt>this.index</tt>.
376  *
377  * @param {array} array an array of objects, or numbers.
378  * @param {function} [f] an optional accessor function.
379  * @returns {number[]} an array of numbers that sums to one.
380  */
381 pv.normalize = function(array, f) {
382   var norm = map(array, f), sum = pv.sum(norm);
383   for (var i = 0; i < norm.length; i++) norm[i] /= sum;
384   return norm;
385 };
386 
387 /**
388  * Returns the sum of the specified array. If the specified array is not an
389  * array of numbers, an optional accessor function <tt>f</tt> can be specified
390  * to map the elements to numbers. See {@link #normalize} for an example.
391  * Accessor functions can refer to <tt>this.index</tt>.
392  *
393  * @param {array} array an array of objects, or numbers.
394  * @param {function} [f] an optional accessor function.
395  * @returns {number} the sum of the specified array.
396  */
397 pv.sum = function(array, f) {
398   var o = {};
399   return array.reduce(f
400       ? function(p, d, i) { o.index = i; return p + f.call(o, d); }
401       : function(p, d) { return p + d; }, 0);
402 };
403 
404 /**
405  * Returns the maximum value of the specified array. If the specified array is
406  * not an array of numbers, an optional accessor function <tt>f</tt> can be
407  * specified to map the elements to numbers. See {@link #normalize} for an
408  * example. Accessor functions can refer to <tt>this.index</tt>.
409  *
410  * @param {array} array an array of objects, or numbers.
411  * @param {function} [f] an optional accessor function.
412  * @returns {number} the maximum value of the specified array.
413  */
414 pv.max = function(array, f) {
415   if (f == pv.index) return array.length - 1;
416   return Math.max.apply(null, f ? map(array, f) : array);
417 };
418 
419 /**
420  * Returns the index of the maximum value of the specified array. If the
421  * specified array is not an array of numbers, an optional accessor function
422  * <tt>f</tt> can be specified to map the elements to numbers. See
423  * {@link #normalize} for an example. Accessor functions can refer to
424  * <tt>this.index</tt>.
425  *
426  * @param {array} array an array of objects, or numbers.
427  * @param {function} [f] an optional accessor function.
428  * @returns {number} the index of the maximum value of the specified array.
429  */
430 pv.max.index = function(array, f) {
431   if (f == pv.index) return array.length - 1;
432   if (!f) f = pv.identity;
433   var maxi = -1, maxx = -Infinity, o = {};
434   for (var i = 0; i < array.length; i++) {
435     o.index = i;
436     var x = f.call(o, array[i]);
437     if (x > maxx) {
438       maxx = x;
439       maxi = i;
440     }
441   }
442   return maxi;
443 }
444 
445 /**
446  * Returns the minimum value of the specified array of numbers. If the specified
447  * array is not an array of numbers, an optional accessor function <tt>f</tt>
448  * can be specified to map the elements to numbers. See {@link #normalize} for
449  * an example. Accessor functions can refer to <tt>this.index</tt>.
450  *
451  * @param {array} array an array of objects, or numbers.
452  * @param {function} [f] an optional accessor function.
453  * @returns {number} the minimum value of the specified array.
454  */
455 pv.min = function(array, f) {
456   if (f == pv.index) return 0;
457   return Math.min.apply(null, f ? map(array, f) : array);
458 };
459 
460 /**
461  * Returns the index of the minimum value of the specified array. If the
462  * specified array is not an array of numbers, an optional accessor function
463  * <tt>f</tt> can be specified to map the elements to numbers. See
464  * {@link #normalize} for an example. Accessor functions can refer to
465  * <tt>this.index</tt>.
466  *
467  * @param {array} array an array of objects, or numbers.
468  * @param {function} [f] an optional accessor function.
469  * @returns {number} the index of the minimum value of the specified array.
470  */
471 pv.min.index = function(array, f) {
472   if (f == pv.index) return 0;
473   if (!f) f = pv.identity;
474   var mini = -1, minx = Infinity, o = {};
475   for (var i = 0; i < array.length; i++) {
476     o.index = i;
477     var x = f.call(o, array[i]);
478     if (x < minx) {
479       minx = x;
480       mini = i;
481     }
482   }
483   return mini;
484 }
485 
486 /**
487  * Returns the arithmetic mean, or average, of the specified array. If the
488  * specified array is not an array of numbers, an optional accessor function
489  * <tt>f</tt> can be specified to map the elements to numbers. See
490  * {@link #normalize} for an example. Accessor functions can refer to
491  * <tt>this.index</tt>.
492  *
493  * @param {array} array an array of objects, or numbers.
494  * @param {function} [f] an optional accessor function.
495  * @returns {number} the mean of the specified array.
496  */
497 pv.mean = function(array, f) {
498   return pv.sum(array, f) / array.length;
499 };
500 
501 /**
502  * Returns the median of the specified array. If the specified array is not an
503  * array of numbers, an optional accessor function <tt>f</tt> can be specified
504  * to map the elements to numbers. See {@link #normalize} for an example.
505  * Accessor functions can refer to <tt>this.index</tt>.
506  *
507  * @param {array} array an array of objects, or numbers.
508  * @param {function} [f] an optional accessor function.
509  * @returns {number} the median of the specified array.
510  */
511 pv.median = function(array, f) {
512   if (f == pv.index) return (array.length - 1) / 2;
513   array = map(array, f).sort(pv.naturalOrder);
514   if (array.length % 2) return array[Math.floor(array.length / 2)];
515   var i = array.length / 2;
516   return (array[i - 1] + array[i]) / 2;
517 };
518 
519 /**
520  * Returns a map constructed from the specified <tt>keys</tt>, using the
521  * function <tt>f</tt> to compute the value for each key. The single argument to
522  * the value function is the key. The callback is invoked only for indexes of
523  * the array which have assigned values; it is not invoked for indexes which
524  * have been deleted or which have never been assigned values.
525  *
526  * <p>For example, this expression creates a map from strings to string length:
527  *
528  * <pre>pv.dict(["one", "three", "seventeen"], function(s) s.length)</pre>
529  *
530  * The returned value is <tt>{one: 3, three: 5, seventeen: 9}</tt>. Accessor
531  * functions can refer to <tt>this.index</tt>.
532  *
533  * @param {array} keys an array.
534  * @param {function} f a value function.
535  * @returns a map from keys to values.
536  */
537 pv.dict = function(keys, f) {
538   var m = {}, o = {};
539   for (var i = 0; i < keys.length; i++) {
540     if (i in keys) {
541       var k = keys[i];
542       o.index = i;
543       m[k] = f.call(o, k);
544     }
545   }
546   return m;
547 };
548 
549 /**
550  * Returns a permutation of the specified array, using the specified array of
551  * indexes. The returned array contains the corresponding element in
552  * <tt>array</tt> for each index in <tt>indexes</tt>, in order. For example,
553  *
554  * <pre>pv.permute(["a", "b", "c"], [1, 2, 0])</pre>
555  *
556  * returns <tt>["b", "c", "a"]</tt>. It is acceptable for the array of indexes
557  * to be a different length from the array of elements, and for indexes to be
558  * duplicated or omitted. The optional accessor function <tt>f</tt> can be used
559  * to perform a simultaneous mapping of the array elements. Accessor functions
560  * can refer to <tt>this.index</tt>.
561  *
562  * @param {array} array an array.
563  * @param {number[]} indexes an array of indexes into <tt>array</tt>.
564  * @param {function} [f] an optional accessor function.
565  * @returns {array} an array of elements from <tt>array</tt>; a permutation.
566  */
567 pv.permute = function(array, indexes, f) {
568   if (!f) f = pv.identity;
569   var p = new Array(indexes.length), o = {};
570   indexes.forEach(function(j, i) { o.index = j; p[i] = f.call(o, array[j]); });
571   return p;
572 };
573 
574 /**
575  * Returns a map from key to index for the specified <tt>keys</tt> array. For
576  * example,
577  *
578  * <pre>pv.numerate(["a", "b", "c"])</pre>
579  *
580  * returns <tt>{a: 0, b: 1, c: 2}</tt>. Note that since JavaScript maps only
581  * support string keys, <tt>keys</tt> must contain strings, or other values that
582  * naturally map to distinct string values. Alternatively, an optional accessor
583  * function <tt>f</tt> can be specified to compute the string key for the given
584  * element. Accessor functions can refer to <tt>this.index</tt>.
585  *
586  * @param {array} keys an array, usually of string keys.
587  * @param {function} [f] an optional key function.
588  * @returns a map from key to index.
589  */
590 pv.numerate = function(keys, f) {
591   if (!f) f = pv.identity;
592   var map = {}, o = {};
593   keys.forEach(function(x, i) { o.index = i; map[f.call(o, x)] = i; });
594   return map;
595 };
596 
597 /**
598  * The comparator function for natural order. This can be used in conjunction with
599  * the built-in array <tt>sort</tt> method to sort elements by their natural
600  * order, ascending. Note that if no comparator function is specified to the
601  * built-in <tt>sort</tt> method, the default order is lexicographic, <i>not</i>
602  * natural!
603  *
604  * @see <a
605  * href="http://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort">Array.sort</a>.
606  * @param a an element to compare.
607  * @param b an element to compare.
608  * @returns {number} negative if a < b; positive if a > b; otherwise 0.
609  */
610 pv.naturalOrder = function(a, b) {
611   return (a < b) ? -1 : ((a > b) ? 1 : 0);
612 };
613 
614 /**
615  * The comparator function for reverse natural order. This can be used in
616  * conjunction with the built-in array <tt>sort</tt> method to sort elements by
617  * their natural order, descending. Note that if no comparator function is
618  * specified to the built-in <tt>sort</tt> method, the default order is
619  * lexicographic, <i>not</i> natural!
620  *
621  * @see #naturalOrder
622  * @param a an element to compare.
623  * @param b an element to compare.
624  * @returns {number} negative if a < b; positive if a > b; otherwise 0.
625  */
626 pv.reverseOrder = function(b, a) {
627   return (a < b) ? -1 : ((a > b) ? 1 : 0);
628 };
629 
630 /**
631  * @private Computes the value of the specified CSS property <tt>p</tt> on the
632  * specified element <tt>e</tt>.
633  *
634  * @param {string} p the name of the CSS property.
635  * @param e the element on which to compute the CSS property.
636  */
637 pv.css = function(e, p) {
638   return window.getComputedStyle
639       ? window.getComputedStyle(e, null).getPropertyValue(p)
640       : e.currentStyle[p];
641 };
642 
643 /**
644  * Namespace constants for SVG, XMLNS, and XLINK.
645  *
646  * @namespace Namespace constants for SVG, XMLNS, and XLINK.
647  */
648 pv.ns = {
649   /**
650    * The SVG namespace, "http://www.w3.org/2000/svg".
651    *
652    * @type string
653    * @constant
654    */
655   svg: "http://www.w3.org/2000/svg",
656 
657   /**
658    * The XMLNS namespace, "http://www.w3.org/2000/xmlns".
659    *
660    * @type string
661    * @constant
662    */
663   xmlns: "http://www.w3.org/2000/xmlns",
664 
665   /**
666    * The XLINK namespace, "http://www.w3.org/1999/xlink".
667    *
668    * @type string
669    * @constant
670    */
671   xlink: "http://www.w3.org/1999/xlink"
672 };
673 
674 /**
675  * Protovis major and minor version numbers.
676  *
677  * @namespace Protovis major and minor version numbers.
678  */
679 pv.version = {
680   /**
681    * The major version number.
682    *
683    * @type number
684    * @constant
685    */
686   major: 3,
687 
688   /**
689    * The minor version number.
690    *
691    * @type number
692    * @constant
693    */
694   minor: 0
695 };
696 
697 /**
698  * @private Reports the specified error to the JavaScript console. Mozilla only
699  * allows logging to the console for privileged code; if the console is
700  * unavailable, the alert dialog box is used instead.
701  *
702  * @param e the exception that triggered the error.
703  */
704 pv.error = function(e) {
705   (typeof console == "undefined") ? alert(e) : console.error(e);
706 };
707 
708 /**
709  * @private Registers the specified listener for events of the specified type on
710  * the specified target. For standards-compliant browsers, this method uses
711  * <tt>addEventListener</tt>; for Internet Explorer, <tt>attachEvent</tt>.
712  *
713  * @param target a DOM element.
714  * @param {string} type the type of event, such as "click".
715  * @param {function} the listener callback function.
716  */
717 pv.listen = function(target, type, listener) {
718   return target.addEventListener
719     ? target.addEventListener(type, listener, false)
720     : target.attachEvent("on" + type, listener);
721 };
722 
723 /**
724  * Returns the logarithm with a given base value.
725  *
726  * @param {number} x the number for which to compute the logarithm.
727  * @param {number} b the base of the logarithm.
728  * @returns {number} the logarithm value.
729  */
730 pv.log = function(x, b) {
731   return Math.log(x) / Math.log(b);
732 };
733 
734 /**
735  * Computes a zero-symmetric logarithm. Computes the logarithm of the absolute
736  * value of the input, and determines the sign of the output according to the
737  * sign of the input value.
738  *
739  * @param {number} x the number for which to compute the logarithm.
740  * @param {number} b the base of the logarithm.
741  * @returns {number} the symmetric log value.
742  */
743 pv.logSymmetric = function(x, b) {
744   return (x == 0) ? 0 : ((x < 0) ? -pv.log(-x, b) : pv.log(x, b));
745 };
746 
747 /**
748  * Computes a zero-symmetric logarithm, with adjustment to values between zero
749  * and the logarithm base. This adjustment introduces distortion for values less
750  * than the base number, but enables simultaneous plotting of log-transformed
751  * data involving both positive and negative numbers.
752  *
753  * @param {number} x the number for which to compute the logarithm.
754  * @param {number} b the base of the logarithm.
755  * @returns {number} the adjusted, symmetric log value.
756  */
757 pv.logAdjusted = function(x, b) {
758   var negative = x < 0;
759   if (x < b) x += (b - x) / b;
760   return negative ? -pv.log(x, b) : pv.log(x, b);
761 };
762 
763 /**
764  * Rounds an input value down according to its logarithm. The method takes the
765  * floor of the logarithm of the value and then uses the resulting value as an
766  * exponent for the base value.
767  *
768  * @param {number} x the number for which to compute the logarithm floor.
769  * @param {number} b the base of the logarithm.
770  * @return {number} the rounded-by-logarithm value.
771  */
772 pv.logFloor = function(x, b) {
773   return (x > 0)
774       ? Math.pow(b, Math.floor(pv.log(x, b)))
775       : -Math.pow(b, -Math.floor(-pv.log(-x, b)));
776 };
777 
778 /**
779  * Rounds an input value up according to its logarithm. The method takes the
780  * ceiling of the logarithm of the value and then uses the resulting value as an
781  * exponent for the base value.
782  *
783  * @param {number} x the number for which to compute the logarithm ceiling.
784  * @param {number} b the base of the logarithm.
785  * @return {number} the rounded-by-logarithm value.
786  */
787 pv.logCeil = function(x, b) {
788   return (x > 0)
789       ? Math.pow(b, Math.ceil(pv.log(x, b)))
790       : -Math.pow(b, -Math.ceil(-pv.log(-x, b)));
791 };
792 
793 /**
794  * Searches the specified array of numbers for the specified value using the
795  * binary search algorithm. The array must be sorted (as by the <tt>sort</tt>
796  * method) prior to making this call. If it is not sorted, the results are
797  * undefined. If the array contains multiple elements with the specified value,
798  * there is no guarantee which one will be found.
799  *
800  * <p>The <i>insertion point</i> is defined as the point at which the value
801  * would be inserted into the array: the index of the first element greater than
802  * the value, or <tt>array.length</tt>, if all elements in the array are less
803  * than the specified value. Note that this guarantees that the return value
804  * will be nonnegative if and only if the value is found.
805  *
806  * @param {number[]} array the array to be searched.
807  * @param {number} value the value to be searched for.
808  * @returns the index of the search value, if it is contained in the array;
809  * otherwise, (-(<i>insertion point</i>) - 1).
810  */
811 pv.search = function(array, value) {
812   var low = 0, high = array.length - 1;
813   while (low <= high) {
814     var mid = (low + high) >> 1, midValue = array[mid];
815     if (midValue < value) low = mid + 1;
816     else if (midValue > value) high = mid - 1;
817     else return mid;
818   }
819   return -low - 1;
820 };
821