11dd2f7b04ff398119a639b1af75ba78de867c79
[rails.git] / vendor / assets / iD / iD.js
1 (function(exports) {
2
3   var bootstrap = (typeof exports.bootstrap === "object") ?
4     exports.bootstrap :
5     (exports.bootstrap = {});
6
7   bootstrap.tooltip = function() {
8
9     var tooltip = function(selection) {
10         selection.each(setup);
11       },
12       animation = d3.functor(false),
13       html = d3.functor(false),
14       title = function() {
15         var title = this.getAttribute("data-original-title");
16         if (title) {
17           return title;
18         } else {
19           title = this.getAttribute("title");
20           this.removeAttribute("title");
21           this.setAttribute("data-original-title", title);
22         }
23         return title;
24       },
25       over = "mouseenter.tooltip",
26       out = "mouseleave.tooltip",
27       placements = "top left bottom right".split(" "),
28       placement = d3.functor("top");
29
30     tooltip.title = function(_) {
31       if (arguments.length) {
32         title = d3.functor(_);
33         return tooltip;
34       } else {
35         return title;
36       }
37     };
38
39     tooltip.html = function(_) {
40       if (arguments.length) {
41         html = d3.functor(_);
42         return tooltip;
43       } else {
44         return html;
45       }
46     };
47
48     tooltip.placement = function(_) {
49       if (arguments.length) {
50         placement = d3.functor(_);
51         return tooltip;
52       } else {
53         return placement;
54       }
55     };
56
57     tooltip.show = function(selection) {
58       selection.each(show);
59     };
60
61     tooltip.hide = function(selection) {
62       selection.each(hide);
63     };
64
65     tooltip.toggle = function(selection) {
66       selection.each(toggle);
67     };
68
69     tooltip.destroy = function(selection) {
70       selection
71         .on(over, null)
72         .on(out, null)
73         .attr("title", function() {
74           return this.getAttribute("data-original-title") || this.getAttribute("title");
75         })
76         .attr("data-original-title", null)
77         .select(".tooltip")
78         .remove();
79     };
80
81     function setup() {
82       var root = d3.select(this),
83           animate = animation.apply(this, arguments),
84           tip = root.append("div")
85             .attr("class", "tooltip");
86
87       if (animate) {
88         tip.classed("fade", true);
89       }
90
91       // TODO "inside" checks?
92
93       tip.append("div")
94         .attr("class", "tooltip-arrow");
95       tip.append("div")
96         .attr("class", "tooltip-inner");
97
98       var place = placement.apply(this, arguments);
99       tip.classed(place, true);
100
101       root.on(over, show);
102       root.on(out, hide);
103     }
104
105     function show() {
106       var root = d3.select(this),
107           content = title.apply(this, arguments),
108           tip = root.select(".tooltip")
109             .classed("in", true),
110           markup = html.apply(this, arguments),
111           innercontent = tip.select(".tooltip-inner")[markup ? "html" : "text"](content),
112           place = placement.apply(this, arguments),
113           outer = getPosition(root.node()),
114           inner = getPosition(tip.node()),
115           pos;
116
117       switch (place) {
118         case "top":
119           pos = {x: outer.x + (outer.w - inner.w) / 2, y: outer.y - inner.h};
120           break;
121         case "right":
122           pos = {x: outer.x + outer.w, y: outer.y + (outer.h - inner.h) / 2};
123           break;
124         case "left":
125           pos = {x: outer.x - inner.w, y: outer.y + (outer.h - inner.h) / 2};
126           break;
127         case "bottom":
128           pos = {x: Math.max(0, outer.x + (outer.w - inner.w) / 2), y: outer.y + outer.h};
129           break;
130       }
131
132       tip.style(pos ?
133         {left: ~~pos.x + "px", top: ~~pos.y + "px"} :
134         {left: null, top: null});
135
136       this.tooltipVisible = true;
137     }
138
139     function hide() {
140       d3.select(this).select(".tooltip")
141         .classed("in", false);
142
143       this.tooltipVisible = false;
144     }
145
146     function toggle() {
147       if (this.tooltipVisible) {
148         hide.apply(this, arguments);
149       } else {
150         show.apply(this, arguments);
151       }
152     }
153
154     return tooltip;
155   };
156
157   function getPosition(node) {
158     var mode = d3.select(node).style('position');
159     if (mode === 'absolute' || mode === 'static') {
160       return {
161         x: node.offsetLeft,
162         y: node.offsetTop,
163         w: node.offsetWidth,
164         h: node.offsetHeight
165       };
166     } else {
167       return {
168         x: 0,
169         y: 0,
170         w: node.offsetWidth,
171         h: node.offsetHeight
172       };
173     }
174   }
175
176 })(this);
177 d3 = (function(){
178   var d3 = {version: "3.1.4"}; // semver
179 d3.ascending = function(a, b) {
180   return a < b ? -1 : a > b ? 1 : a >= b ? 0 : NaN;
181 };
182 d3.descending = function(a, b) {
183   return b < a ? -1 : b > a ? 1 : b >= a ? 0 : NaN;
184 };
185 d3.min = function(array, f) {
186   var i = -1,
187       n = array.length,
188       a,
189       b;
190   if (arguments.length === 1) {
191     while (++i < n && ((a = array[i]) == null || a != a)) a = undefined;
192     while (++i < n) if ((b = array[i]) != null && a > b) a = b;
193   } else {
194     while (++i < n && ((a = f.call(array, array[i], i)) == null || a != a)) a = undefined;
195     while (++i < n) if ((b = f.call(array, array[i], i)) != null && a > b) a = b;
196   }
197   return a;
198 };
199 d3.max = function(array, f) {
200   var i = -1,
201       n = array.length,
202       a,
203       b;
204   if (arguments.length === 1) {
205     while (++i < n && ((a = array[i]) == null || a != a)) a = undefined;
206     while (++i < n) if ((b = array[i]) != null && b > a) a = b;
207   } else {
208     while (++i < n && ((a = f.call(array, array[i], i)) == null || a != a)) a = undefined;
209     while (++i < n) if ((b = f.call(array, array[i], i)) != null && b > a) a = b;
210   }
211   return a;
212 };
213 d3.extent = function(array, f) {
214   var i = -1,
215       n = array.length,
216       a,
217       b,
218       c;
219   if (arguments.length === 1) {
220     while (++i < n && ((a = c = array[i]) == null || a != a)) a = c = undefined;
221     while (++i < n) if ((b = array[i]) != null) {
222       if (a > b) a = b;
223       if (c < b) c = b;
224     }
225   } else {
226     while (++i < n && ((a = c = f.call(array, array[i], i)) == null || a != a)) a = undefined;
227     while (++i < n) if ((b = f.call(array, array[i], i)) != null) {
228       if (a > b) a = b;
229       if (c < b) c = b;
230     }
231   }
232   return [a, c];
233 };
234 d3.sum = function(array, f) {
235   var s = 0,
236       n = array.length,
237       a,
238       i = -1;
239
240   if (arguments.length === 1) {
241     while (++i < n) if (!isNaN(a = +array[i])) s += a;
242   } else {
243     while (++i < n) if (!isNaN(a = +f.call(array, array[i], i))) s += a;
244   }
245
246   return s;
247 };
248 function d3_number(x) {
249   return x != null && !isNaN(x);
250 }
251
252 d3.mean = function(array, f) {
253   var n = array.length,
254       a,
255       m = 0,
256       i = -1,
257       j = 0;
258   if (arguments.length === 1) {
259     while (++i < n) if (d3_number(a = array[i])) m += (a - m) / ++j;
260   } else {
261     while (++i < n) if (d3_number(a = f.call(array, array[i], i))) m += (a - m) / ++j;
262   }
263   return j ? m : undefined;
264 };
265 // R-7 per <http://en.wikipedia.org/wiki/Quantile>
266 d3.quantile = function(values, p) {
267   var H = (values.length - 1) * p + 1,
268       h = Math.floor(H),
269       v = +values[h - 1],
270       e = H - h;
271   return e ? v + e * (values[h] - v) : v;
272 };
273
274 d3.median = function(array, f) {
275   if (arguments.length > 1) array = array.map(f);
276   array = array.filter(d3_number);
277   return array.length ? d3.quantile(array.sort(d3.ascending), .5) : undefined;
278 };
279 d3.bisector = function(f) {
280   return {
281     left: function(a, x, lo, hi) {
282       if (arguments.length < 3) lo = 0;
283       if (arguments.length < 4) hi = a.length;
284       while (lo < hi) {
285         var mid = lo + hi >>> 1;
286         if (f.call(a, a[mid], mid) < x) lo = mid + 1;
287         else hi = mid;
288       }
289       return lo;
290     },
291     right: function(a, x, lo, hi) {
292       if (arguments.length < 3) lo = 0;
293       if (arguments.length < 4) hi = a.length;
294       while (lo < hi) {
295         var mid = lo + hi >>> 1;
296         if (x < f.call(a, a[mid], mid)) hi = mid;
297         else lo = mid + 1;
298       }
299       return lo;
300     }
301   };
302 };
303
304 var d3_bisector = d3.bisector(function(d) { return d; });
305 d3.bisectLeft = d3_bisector.left;
306 d3.bisect = d3.bisectRight = d3_bisector.right;
307 d3.shuffle = function(array) {
308   var m = array.length, t, i;
309   while (m) {
310     i = Math.random() * m-- | 0;
311     t = array[m], array[m] = array[i], array[i] = t;
312   }
313   return array;
314 };
315 d3.permute = function(array, indexes) {
316   var permutes = [],
317       i = -1,
318       n = indexes.length;
319   while (++i < n) permutes[i] = array[indexes[i]];
320   return permutes;
321 };
322
323 d3.zip = function() {
324   if (!(n = arguments.length)) return [];
325   for (var i = -1, m = d3.min(arguments, d3_zipLength), zips = new Array(m); ++i < m;) {
326     for (var j = -1, n, zip = zips[i] = new Array(n); ++j < n;) {
327       zip[j] = arguments[j][i];
328     }
329   }
330   return zips;
331 };
332
333 function d3_zipLength(d) {
334   return d.length;
335 }
336
337 d3.transpose = function(matrix) {
338   return d3.zip.apply(d3, matrix);
339 };
340 d3.keys = function(map) {
341   var keys = [];
342   for (var key in map) keys.push(key);
343   return keys;
344 };
345 d3.values = function(map) {
346   var values = [];
347   for (var key in map) values.push(map[key]);
348   return values;
349 };
350 d3.entries = function(map) {
351   var entries = [];
352   for (var key in map) entries.push({key: key, value: map[key]});
353   return entries;
354 };
355 d3.merge = function(arrays) {
356   return Array.prototype.concat.apply([], arrays);
357 };
358 d3.range = function(start, stop, step) {
359   if (arguments.length < 3) {
360     step = 1;
361     if (arguments.length < 2) {
362       stop = start;
363       start = 0;
364     }
365   }
366   if ((stop - start) / step === Infinity) throw new Error("infinite range");
367   var range = [],
368        k = d3_range_integerScale(Math.abs(step)),
369        i = -1,
370        j;
371   start *= k, stop *= k, step *= k;
372   if (step < 0) while ((j = start + step * ++i) > stop) range.push(j / k);
373   else while ((j = start + step * ++i) < stop) range.push(j / k);
374   return range;
375 };
376
377 function d3_range_integerScale(x) {
378   var k = 1;
379   while (x * k % 1) k *= 10;
380   return k;
381 }
382 function d3_class(ctor, properties) {
383   try {
384     for (var key in properties) {
385       Object.defineProperty(ctor.prototype, key, {
386         value: properties[key],
387         enumerable: false
388       });
389     }
390   } catch (e) {
391     ctor.prototype = properties;
392   }
393 }
394
395 d3.map = function(object) {
396   var map = new d3_Map;
397   for (var key in object) map.set(key, object[key]);
398   return map;
399 };
400
401 function d3_Map() {}
402
403 d3_class(d3_Map, {
404   has: function(key) {
405     return d3_map_prefix + key in this;
406   },
407   get: function(key) {
408     return this[d3_map_prefix + key];
409   },
410   set: function(key, value) {
411     return this[d3_map_prefix + key] = value;
412   },
413   remove: function(key) {
414     key = d3_map_prefix + key;
415     return key in this && delete this[key];
416   },
417   keys: function() {
418     var keys = [];
419     this.forEach(function(key) { keys.push(key); });
420     return keys;
421   },
422   values: function() {
423     var values = [];
424     this.forEach(function(key, value) { values.push(value); });
425     return values;
426   },
427   entries: function() {
428     var entries = [];
429     this.forEach(function(key, value) { entries.push({key: key, value: value}); });
430     return entries;
431   },
432   forEach: function(f) {
433     for (var key in this) {
434       if (key.charCodeAt(0) === d3_map_prefixCode) {
435         f.call(this, key.substring(1), this[key]);
436       }
437     }
438   }
439 });
440
441 var d3_map_prefix = "\0", // prevent collision with built-ins
442     d3_map_prefixCode = d3_map_prefix.charCodeAt(0);
443
444 d3.nest = function() {
445   var nest = {},
446       keys = [],
447       sortKeys = [],
448       sortValues,
449       rollup;
450
451   function map(mapType, array, depth) {
452     if (depth >= keys.length) return rollup
453         ? rollup.call(nest, array) : (sortValues
454         ? array.sort(sortValues)
455         : array);
456
457     var i = -1,
458         n = array.length,
459         key = keys[depth++],
460         keyValue,
461         object,
462         setter,
463         valuesByKey = new d3_Map,
464         values;
465
466     while (++i < n) {
467       if (values = valuesByKey.get(keyValue = key(object = array[i]))) {
468         values.push(object);
469       } else {
470         valuesByKey.set(keyValue, [object]);
471       }
472     }
473
474     if (mapType) {
475       object = mapType();
476       setter = function(keyValue, values) {
477         object.set(keyValue, map(mapType, values, depth));
478       };
479     } else {
480       object = {};
481       setter = function(keyValue, values) {
482         object[keyValue] = map(mapType, values, depth);
483       };
484     }
485
486     valuesByKey.forEach(setter);
487     return object;
488   }
489
490   function entries(map, depth) {
491     if (depth >= keys.length) return map;
492
493     var array = [],
494         sortKey = sortKeys[depth++];
495
496     map.forEach(function(key, keyMap) {
497       array.push({key: key, values: entries(keyMap, depth)});
498     });
499
500     return sortKey
501         ? array.sort(function(a, b) { return sortKey(a.key, b.key); })
502         : array;
503   }
504
505   nest.map = function(array, mapType) {
506     return map(mapType, array, 0);
507   };
508
509   nest.entries = function(array) {
510     return entries(map(d3.map, array, 0), 0);
511   };
512
513   nest.key = function(d) {
514     keys.push(d);
515     return nest;
516   };
517
518   // Specifies the order for the most-recently specified key.
519   // Note: only applies to entries. Map keys are unordered!
520   nest.sortKeys = function(order) {
521     sortKeys[keys.length - 1] = order;
522     return nest;
523   };
524
525   // Specifies the order for leaf values.
526   // Applies to both maps and entries array.
527   nest.sortValues = function(order) {
528     sortValues = order;
529     return nest;
530   };
531
532   nest.rollup = function(f) {
533     rollup = f;
534     return nest;
535   };
536
537   return nest;
538 };
539
540 d3.set = function(array) {
541   var set = new d3_Set();
542   if (array) for (var i = 0; i < array.length; i++) set.add(array[i]);
543   return set;
544 };
545
546 function d3_Set() {}
547
548 d3_class(d3_Set, {
549   has: function(value) {
550     return d3_map_prefix + value in this;
551   },
552   add: function(value) {
553     this[d3_map_prefix + value] = true;
554     return value;
555   },
556   remove: function(value) {
557     value = d3_map_prefix + value;
558     return value in this && delete this[value];
559   },
560   values: function() {
561     var values = [];
562     this.forEach(function(value) {
563       values.push(value);
564     });
565     return values;
566   },
567   forEach: function(f) {
568     for (var value in this) {
569       if (value.charCodeAt(0) === d3_map_prefixCode) {
570         f.call(this, value.substring(1));
571       }
572     }
573   }
574 });
575 d3.behavior = {};
576 var d3_document = document,
577     d3_window = window;
578 // Copies a variable number of methods from source to target.
579 d3.rebind = function(target, source) {
580   var i = 1, n = arguments.length, method;
581   while (++i < n) target[method = arguments[i]] = d3_rebind(target, source, source[method]);
582   return target;
583 };
584
585 // Method is assumed to be a standard D3 getter-setter:
586 // If passed with no arguments, gets the value.
587 // If passed with arguments, sets the value and returns the target.
588 function d3_rebind(target, source, method) {
589   return function() {
590     var value = method.apply(source, arguments);
591     return value === source ? target : value;
592   };
593 }
594
595 d3.dispatch = function() {
596   var dispatch = new d3_dispatch,
597       i = -1,
598       n = arguments.length;
599   while (++i < n) dispatch[arguments[i]] = d3_dispatch_event(dispatch);
600   return dispatch;
601 };
602
603 function d3_dispatch() {}
604
605 d3_dispatch.prototype.on = function(type, listener) {
606   var i = type.indexOf("."),
607       name = "";
608
609   // Extract optional namespace, e.g., "click.foo"
610   if (i >= 0) {
611     name = type.substring(i + 1);
612     type = type.substring(0, i);
613   }
614
615   if (type) return arguments.length < 2
616       ? this[type].on(name)
617       : this[type].on(name, listener);
618
619   if (arguments.length === 2) {
620     if (listener == null) for (type in this) {
621       if (this.hasOwnProperty(type)) this[type].on(name, null);
622     }
623     return this;
624   }
625 };
626
627 function d3_dispatch_event(dispatch) {
628   var listeners = [],
629       listenerByName = new d3_Map;
630
631   function event() {
632     var z = listeners, // defensive reference
633         i = -1,
634         n = z.length,
635         l;
636     while (++i < n) if (l = z[i].on) l.apply(this, arguments);
637     return dispatch;
638   }
639
640   event.on = function(name, listener) {
641     var l = listenerByName.get(name),
642         i;
643
644     // return the current listener, if any
645     if (arguments.length < 2) return l && l.on;
646
647     // remove the old listener, if any (with copy-on-write)
648     if (l) {
649       l.on = null;
650       listeners = listeners.slice(0, i = listeners.indexOf(l)).concat(listeners.slice(i + 1));
651       listenerByName.remove(name);
652     }
653
654     // add the new listener, if any
655     if (listener) listeners.push(listenerByName.set(name, {on: listener}));
656
657     return dispatch;
658   };
659
660   return event;
661 }
662
663 d3.event = null;
664
665 function d3_eventCancel() {
666   d3.event.stopPropagation();
667   d3.event.preventDefault();
668 }
669
670 function d3_eventSource() {
671   var e = d3.event, s;
672   while (s = e.sourceEvent) e = s;
673   return e;
674 }
675
676 // Like d3.dispatch, but for custom events abstracting native UI events. These
677 // events have a target component (such as a brush), a target element (such as
678 // the svg:g element containing the brush) and the standard arguments `d` (the
679 // target element's data) and `i` (the selection index of the target element).
680 function d3_eventDispatch(target) {
681   var dispatch = new d3_dispatch,
682       i = 0,
683       n = arguments.length;
684
685   while (++i < n) dispatch[arguments[i]] = d3_dispatch_event(dispatch);
686
687   // Creates a dispatch context for the specified `thiz` (typically, the target
688   // DOM element that received the source event) and `argumentz` (typically, the
689   // data `d` and index `i` of the target element). The returned function can be
690   // used to dispatch an event to any registered listeners; the function takes a
691   // single argument as input, being the event to dispatch. The event must have
692   // a "type" attribute which corresponds to a type registered in the
693   // constructor. This context will automatically populate the "sourceEvent" and
694   // "target" attributes of the event, as well as setting the `d3.event` global
695   // for the duration of the notification.
696   dispatch.of = function(thiz, argumentz) {
697     return function(e1) {
698       try {
699         var e0 =
700         e1.sourceEvent = d3.event;
701         e1.target = target;
702         d3.event = e1;
703         dispatch[e1.type].apply(thiz, argumentz);
704       } finally {
705         d3.event = e0;
706       }
707     };
708   };
709
710   return dispatch;
711 }
712
713 d3.mouse = function(container) {
714   return d3_mousePoint(container, d3_eventSource());
715 };
716
717 // https://bugs.webkit.org/show_bug.cgi?id=44083
718 var d3_mouse_bug44083 = /WebKit/.test(d3_window.navigator.userAgent) ? -1 : 0;
719
720 function d3_mousePoint(container, e) {
721   var svg = container.ownerSVGElement || container;
722   if (svg.createSVGPoint) {
723     var point = svg.createSVGPoint();
724     if (d3_mouse_bug44083 < 0 && (d3_window.scrollX || d3_window.scrollY)) {
725       svg = d3.select(d3_document.body).append("svg")
726           .style("position", "absolute")
727           .style("top", 0)
728           .style("left", 0);
729       var ctm = svg[0][0].getScreenCTM();
730       d3_mouse_bug44083 = !(ctm.f || ctm.e);
731       svg.remove();
732     }
733     if (d3_mouse_bug44083) {
734       point.x = e.pageX;
735       point.y = e.pageY;
736     } else {
737       point.x = e.clientX;
738       point.y = e.clientY;
739     }
740     point = point.matrixTransform(container.getScreenCTM().inverse());
741     return [point.x, point.y];
742   }
743   var rect = container.getBoundingClientRect();
744   return [e.clientX - rect.left - container.clientLeft, e.clientY - rect.top - container.clientTop];
745 };
746
747 var d3_array = d3_arraySlice; // conversion for NodeLists
748
749 function d3_arrayCopy(pseudoarray) {
750   var i = -1, n = pseudoarray.length, array = [];
751   while (++i < n) array.push(pseudoarray[i]);
752   return array;
753 }
754
755 function d3_arraySlice(pseudoarray) {
756   return Array.prototype.slice.call(pseudoarray);
757 }
758
759 try {
760   d3_array(d3_document.documentElement.childNodes)[0].nodeType;
761 } catch(e) {
762   d3_array = d3_arrayCopy;
763 }
764
765 var d3_arraySubclass = [].__proto__?
766
767 // Until ECMAScript supports array subclassing, prototype injection works well.
768 function(array, prototype) {
769   array.__proto__ = prototype;
770 }:
771
772 // And if your browser doesn't support __proto__, we'll use direct extension.
773 function(array, prototype) {
774   for (var property in prototype) array[property] = prototype[property];
775 };
776
777 d3.touches = function(container, touches) {
778   if (arguments.length < 2) touches = d3_eventSource().touches;
779   return touches ? d3_array(touches).map(function(touch) {
780     var point = d3_mousePoint(container, touch);
781     point.identifier = touch.identifier;
782     return point;
783   }) : [];
784 };
785
786 function d3_selection(groups) {
787   d3_arraySubclass(groups, d3_selectionPrototype);
788   return groups;
789 }
790
791 var d3_select = function(s, n) { return n.querySelector(s); },
792     d3_selectAll = function(s, n) { return n.querySelectorAll(s); },
793     d3_selectRoot = d3_document.documentElement,
794     d3_selectMatcher = d3_selectRoot.matchesSelector || d3_selectRoot.webkitMatchesSelector || d3_selectRoot.mozMatchesSelector || d3_selectRoot.msMatchesSelector || d3_selectRoot.oMatchesSelector,
795     d3_selectMatches = function(n, s) { return d3_selectMatcher.call(n, s); };
796
797 // Prefer Sizzle, if available.
798 if (typeof Sizzle === "function") {
799   d3_select = function(s, n) { return Sizzle(s, n)[0] || null; };
800   d3_selectAll = function(s, n) { return Sizzle.uniqueSort(Sizzle(s, n)); };
801   d3_selectMatches = Sizzle.matchesSelector;
802 }
803
804 var d3_selectionPrototype = [];
805
806 d3.selection = function() {
807   return d3_selectionRoot;
808 };
809
810 d3.selection.prototype = d3_selectionPrototype;
811
812
813 d3_selectionPrototype.select = function(selector) {
814   var subgroups = [],
815       subgroup,
816       subnode,
817       group,
818       node;
819
820   if (typeof selector !== "function") selector = d3_selection_selector(selector);
821
822   for (var j = -1, m = this.length; ++j < m;) {
823     subgroups.push(subgroup = []);
824     subgroup.parentNode = (group = this[j]).parentNode;
825     for (var i = -1, n = group.length; ++i < n;) {
826       if (node = group[i]) {
827         subgroup.push(subnode = selector.call(node, node.__data__, i));
828         if (subnode && "__data__" in node) subnode.__data__ = node.__data__;
829       } else {
830         subgroup.push(null);
831       }
832     }
833   }
834
835   return d3_selection(subgroups);
836 };
837
838 function d3_selection_selector(selector) {
839   return function() {
840     return d3_select(selector, this);
841   };
842 }
843
844 d3_selectionPrototype.selectAll = function(selector) {
845   var subgroups = [],
846       subgroup,
847       node;
848
849   if (typeof selector !== "function") selector = d3_selection_selectorAll(selector);
850
851   for (var j = -1, m = this.length; ++j < m;) {
852     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
853       if (node = group[i]) {
854         subgroups.push(subgroup = d3_array(selector.call(node, node.__data__, i)));
855         subgroup.parentNode = node;
856       }
857     }
858   }
859
860   return d3_selection(subgroups);
861 };
862
863 function d3_selection_selectorAll(selector) {
864   return function() {
865     return d3_selectAll(selector, this);
866   };
867 }
868 var d3_nsPrefix = {
869   svg: "http://www.w3.org/2000/svg",
870   xhtml: "http://www.w3.org/1999/xhtml",
871   xlink: "http://www.w3.org/1999/xlink",
872   xml: "http://www.w3.org/XML/1998/namespace",
873   xmlns: "http://www.w3.org/2000/xmlns/"
874 };
875
876 d3.ns = {
877   prefix: d3_nsPrefix,
878   qualify: function(name) {
879     var i = name.indexOf(":"),
880         prefix = name;
881     if (i >= 0) {
882       prefix = name.substring(0, i);
883       name = name.substring(i + 1);
884     }
885     return d3_nsPrefix.hasOwnProperty(prefix)
886         ? {space: d3_nsPrefix[prefix], local: name}
887         : name;
888   }
889 };
890
891 d3_selectionPrototype.attr = function(name, value) {
892   if (arguments.length < 2) {
893
894     // For attr(string), return the attribute value for the first node.
895     if (typeof name === "string") {
896       var node = this.node();
897       name = d3.ns.qualify(name);
898       return name.local
899           ? node.getAttributeNS(name.space, name.local)
900           : node.getAttribute(name);
901     }
902
903     // For attr(object), the object specifies the names and values of the
904     // attributes to set or remove. The values may be functions that are
905     // evaluated for each element.
906     for (value in name) this.each(d3_selection_attr(value, name[value]));
907     return this;
908   }
909
910   return this.each(d3_selection_attr(name, value));
911 };
912
913 function d3_selection_attr(name, value) {
914   name = d3.ns.qualify(name);
915
916   // For attr(string, null), remove the attribute with the specified name.
917   function attrNull() {
918     this.removeAttribute(name);
919   }
920   function attrNullNS() {
921     this.removeAttributeNS(name.space, name.local);
922   }
923
924   // For attr(string, string), set the attribute with the specified name.
925   function attrConstant() {
926     this.setAttribute(name, value);
927   }
928   function attrConstantNS() {
929     this.setAttributeNS(name.space, name.local, value);
930   }
931
932   // For attr(string, function), evaluate the function for each element, and set
933   // or remove the attribute as appropriate.
934   function attrFunction() {
935     var x = value.apply(this, arguments);
936     if (x == null) this.removeAttribute(name);
937     else this.setAttribute(name, x);
938   }
939   function attrFunctionNS() {
940     var x = value.apply(this, arguments);
941     if (x == null) this.removeAttributeNS(name.space, name.local);
942     else this.setAttributeNS(name.space, name.local, x);
943   }
944
945   return value == null
946       ? (name.local ? attrNullNS : attrNull) : (typeof value === "function"
947       ? (name.local ? attrFunctionNS : attrFunction)
948       : (name.local ? attrConstantNS : attrConstant));
949 }
950 function d3_collapse(s) {
951   return s.trim().replace(/\s+/g, " ");
952 }
953 d3.requote = function(s) {
954   return s.replace(d3_requote_re, "\\$&");
955 };
956
957 var d3_requote_re = /[\\\^\$\*\+\?\|\[\]\(\)\.\{\}]/g;
958
959 d3_selectionPrototype.classed = function(name, value) {
960   if (arguments.length < 2) {
961
962     // For classed(string), return true only if the first node has the specified
963     // class or classes. Note that even if the browser supports DOMTokenList, it
964     // probably doesn't support it on SVG elements (which can be animated).
965     if (typeof name === "string") {
966       var node = this.node(),
967           n = (name = name.trim().split(/^|\s+/g)).length,
968           i = -1;
969       if (value = node.classList) {
970         while (++i < n) if (!value.contains(name[i])) return false;
971       } else {
972         value = node.getAttribute("class");
973         while (++i < n) if (!d3_selection_classedRe(name[i]).test(value)) return false;
974       }
975       return true;
976     }
977
978     // For classed(object), the object specifies the names of classes to add or
979     // remove. The values may be functions that are evaluated for each element.
980     for (value in name) this.each(d3_selection_classed(value, name[value]));
981     return this;
982   }
983
984   // Otherwise, both a name and a value are specified, and are handled as below.
985   return this.each(d3_selection_classed(name, value));
986 };
987
988 function d3_selection_classedRe(name) {
989   return new RegExp("(?:^|\\s+)" + d3.requote(name) + "(?:\\s+|$)", "g");
990 }
991
992 // Multiple class names are allowed (e.g., "foo bar").
993 function d3_selection_classed(name, value) {
994   name = name.trim().split(/\s+/).map(d3_selection_classedName);
995   var n = name.length;
996
997   function classedConstant() {
998     var i = -1;
999     while (++i < n) name[i](this, value);
1000   }
1001
1002   // When the value is a function, the function is still evaluated only once per
1003   // element even if there are multiple class names.
1004   function classedFunction() {
1005     var i = -1, x = value.apply(this, arguments);
1006     while (++i < n) name[i](this, x);
1007   }
1008
1009   return typeof value === "function"
1010       ? classedFunction
1011       : classedConstant;
1012 }
1013
1014 function d3_selection_classedName(name) {
1015   var re = d3_selection_classedRe(name);
1016   return function(node, value) {
1017     if (c = node.classList) return value ? c.add(name) : c.remove(name);
1018     var c = node.getAttribute("class") || "";
1019     if (value) {
1020       re.lastIndex = 0;
1021       if (!re.test(c)) node.setAttribute("class", d3_collapse(c + " " + name));
1022     } else {
1023       node.setAttribute("class", d3_collapse(c.replace(re, " ")));
1024     }
1025   };
1026 }
1027
1028 d3_selectionPrototype.style = function(name, value, priority) {
1029   var n = arguments.length;
1030   if (n < 3) {
1031
1032     // For style(object) or style(object, string), the object specifies the
1033     // names and values of the attributes to set or remove. The values may be
1034     // functions that are evaluated for each element. The optional string
1035     // specifies the priority.
1036     if (typeof name !== "string") {
1037       if (n < 2) value = "";
1038       for (priority in name) this.each(d3_selection_style(priority, name[priority], value));
1039       return this;
1040     }
1041
1042     // For style(string), return the computed style value for the first node.
1043     if (n < 2) return d3_window.getComputedStyle(this.node(), null).getPropertyValue(name);
1044
1045     // For style(string, string) or style(string, function), use the default
1046     // priority. The priority is ignored for style(string, null).
1047     priority = "";
1048   }
1049
1050   // Otherwise, a name, value and priority are specified, and handled as below.
1051   return this.each(d3_selection_style(name, value, priority));
1052 };
1053
1054 function d3_selection_style(name, value, priority) {
1055
1056   // For style(name, null) or style(name, null, priority), remove the style
1057   // property with the specified name. The priority is ignored.
1058   function styleNull() {
1059     this.style.removeProperty(name);
1060   }
1061
1062   // For style(name, string) or style(name, string, priority), set the style
1063   // property with the specified name, using the specified priority.
1064   function styleConstant() {
1065     this.style.setProperty(name, value, priority);
1066   }
1067
1068   // For style(name, function) or style(name, function, priority), evaluate the
1069   // function for each element, and set or remove the style property as
1070   // appropriate. When setting, use the specified priority.
1071   function styleFunction() {
1072     var x = value.apply(this, arguments);
1073     if (x == null) this.style.removeProperty(name);
1074     else this.style.setProperty(name, x, priority);
1075   }
1076
1077   return value == null
1078       ? styleNull : (typeof value === "function"
1079       ? styleFunction : styleConstant);
1080 }
1081
1082 d3_selectionPrototype.property = function(name, value) {
1083   if (arguments.length < 2) {
1084
1085     // For property(string), return the property value for the first node.
1086     if (typeof name === "string") return this.node()[name];
1087
1088     // For property(object), the object specifies the names and values of the
1089     // properties to set or remove. The values may be functions that are
1090     // evaluated for each element.
1091     for (value in name) this.each(d3_selection_property(value, name[value]));
1092     return this;
1093   }
1094
1095   // Otherwise, both a name and a value are specified, and are handled as below.
1096   return this.each(d3_selection_property(name, value));
1097 };
1098
1099 function d3_selection_property(name, value) {
1100
1101   // For property(name, null), remove the property with the specified name.
1102   function propertyNull() {
1103     delete this[name];
1104   }
1105
1106   // For property(name, string), set the property with the specified name.
1107   function propertyConstant() {
1108     this[name] = value;
1109   }
1110
1111   // For property(name, function), evaluate the function for each element, and
1112   // set or remove the property as appropriate.
1113   function propertyFunction() {
1114     var x = value.apply(this, arguments);
1115     if (x == null) delete this[name];
1116     else this[name] = x;
1117   }
1118
1119   return value == null
1120       ? propertyNull : (typeof value === "function"
1121       ? propertyFunction : propertyConstant);
1122 }
1123
1124 d3_selectionPrototype.text = function(value) {
1125   return arguments.length
1126       ? this.each(typeof value === "function"
1127       ? function() { var v = value.apply(this, arguments); this.textContent = v == null ? "" : v; } : value == null
1128       ? function() { this.textContent = ""; }
1129       : function() { this.textContent = value; })
1130       : this.node().textContent;
1131 };
1132
1133 d3_selectionPrototype.html = function(value) {
1134   return arguments.length
1135       ? this.each(typeof value === "function"
1136       ? function() { var v = value.apply(this, arguments); this.innerHTML = v == null ? "" : v; } : value == null
1137       ? function() { this.innerHTML = ""; }
1138       : function() { this.innerHTML = value; })
1139       : this.node().innerHTML;
1140 };
1141
1142 // TODO append(node)?
1143 // TODO append(function)?
1144 d3_selectionPrototype.append = function(name) {
1145   name = d3.ns.qualify(name);
1146
1147   function append() {
1148     return this.appendChild(d3_document.createElementNS(this.namespaceURI, name));
1149   }
1150
1151   function appendNS() {
1152     return this.appendChild(d3_document.createElementNS(name.space, name.local));
1153   }
1154
1155   return this.select(name.local ? appendNS : append);
1156 };
1157
1158 d3_selectionPrototype.insert = function(name, before) {
1159   name = d3.ns.qualify(name);
1160
1161   if (typeof before !== "function") before = d3_selection_selector(before);
1162
1163   function insert(d, i) {
1164     return this.insertBefore(
1165         d3_document.createElementNS(this.namespaceURI, name),
1166         before.call(this, d, i));
1167   }
1168
1169   function insertNS(d, i) {
1170     return this.insertBefore(
1171         d3_document.createElementNS(name.space, name.local),
1172         before.call(this, d, i));
1173   }
1174
1175   return this.select(name.local ? insertNS : insert);
1176 };
1177
1178 // TODO remove(selector)?
1179 // TODO remove(node)?
1180 // TODO remove(function)?
1181 d3_selectionPrototype.remove = function() {
1182   return this.each(function() {
1183     var parent = this.parentNode;
1184     if (parent) parent.removeChild(this);
1185   });
1186 };
1187
1188 d3_selectionPrototype.data = function(value, key) {
1189   var i = -1,
1190       n = this.length,
1191       group,
1192       node;
1193
1194   // If no value is specified, return the first value.
1195   if (!arguments.length) {
1196     value = new Array(n = (group = this[0]).length);
1197     while (++i < n) {
1198       if (node = group[i]) {
1199         value[i] = node.__data__;
1200       }
1201     }
1202     return value;
1203   }
1204
1205   function bind(group, groupData) {
1206     var i,
1207         n = group.length,
1208         m = groupData.length,
1209         n0 = Math.min(n, m),
1210         updateNodes = new Array(m),
1211         enterNodes = new Array(m),
1212         exitNodes = new Array(n),
1213         node,
1214         nodeData;
1215
1216     if (key) {
1217       var nodeByKeyValue = new d3_Map,
1218           dataByKeyValue = new d3_Map,
1219           keyValues = [],
1220           keyValue;
1221
1222       for (i = -1; ++i < n;) {
1223         keyValue = key.call(node = group[i], node.__data__, i);
1224         if (nodeByKeyValue.has(keyValue)) {
1225           exitNodes[i] = node; // duplicate selection key
1226         } else {
1227           nodeByKeyValue.set(keyValue, node);
1228         }
1229         keyValues.push(keyValue);
1230       }
1231
1232       for (i = -1; ++i < m;) {
1233         keyValue = key.call(groupData, nodeData = groupData[i], i);
1234         if (node = nodeByKeyValue.get(keyValue)) {
1235           updateNodes[i] = node;
1236           node.__data__ = nodeData;
1237         } else if (!dataByKeyValue.has(keyValue)) { // no duplicate data key
1238           enterNodes[i] = d3_selection_dataNode(nodeData);
1239         }
1240         dataByKeyValue.set(keyValue, nodeData);
1241         nodeByKeyValue.remove(keyValue);
1242       }
1243
1244       for (i = -1; ++i < n;) {
1245         if (nodeByKeyValue.has(keyValues[i])) {
1246           exitNodes[i] = group[i];
1247         }
1248       }
1249     } else {
1250       for (i = -1; ++i < n0;) {
1251         node = group[i];
1252         nodeData = groupData[i];
1253         if (node) {
1254           node.__data__ = nodeData;
1255           updateNodes[i] = node;
1256         } else {
1257           enterNodes[i] = d3_selection_dataNode(nodeData);
1258         }
1259       }
1260       for (; i < m; ++i) {
1261         enterNodes[i] = d3_selection_dataNode(groupData[i]);
1262       }
1263       for (; i < n; ++i) {
1264         exitNodes[i] = group[i];
1265       }
1266     }
1267
1268     enterNodes.update
1269         = updateNodes;
1270
1271     enterNodes.parentNode
1272         = updateNodes.parentNode
1273         = exitNodes.parentNode
1274         = group.parentNode;
1275
1276     enter.push(enterNodes);
1277     update.push(updateNodes);
1278     exit.push(exitNodes);
1279   }
1280
1281   var enter = d3_selection_enter([]),
1282       update = d3_selection([]),
1283       exit = d3_selection([]);
1284
1285   if (typeof value === "function") {
1286     while (++i < n) {
1287       bind(group = this[i], value.call(group, group.parentNode.__data__, i));
1288     }
1289   } else {
1290     while (++i < n) {
1291       bind(group = this[i], value);
1292     }
1293   }
1294
1295   update.enter = function() { return enter; };
1296   update.exit = function() { return exit; };
1297   return update;
1298 };
1299
1300 function d3_selection_dataNode(data) {
1301   return {__data__: data};
1302 }
1303
1304 d3_selectionPrototype.datum = function(value) {
1305   return arguments.length
1306       ? this.property("__data__", value)
1307       : this.property("__data__");
1308 };
1309
1310 d3_selectionPrototype.filter = function(filter) {
1311   var subgroups = [],
1312       subgroup,
1313       group,
1314       node;
1315
1316   if (typeof filter !== "function") filter = d3_selection_filter(filter);
1317
1318   for (var j = 0, m = this.length; j < m; j++) {
1319     subgroups.push(subgroup = []);
1320     subgroup.parentNode = (group = this[j]).parentNode;
1321     for (var i = 0, n = group.length; i < n; i++) {
1322       if ((node = group[i]) && filter.call(node, node.__data__, i)) {
1323         subgroup.push(node);
1324       }
1325     }
1326   }
1327
1328   return d3_selection(subgroups);
1329 };
1330
1331 function d3_selection_filter(selector) {
1332   return function() {
1333     return d3_selectMatches(this, selector);
1334   };
1335 }
1336
1337 d3_selectionPrototype.order = function() {
1338   for (var j = -1, m = this.length; ++j < m;) {
1339     for (var group = this[j], i = group.length - 1, next = group[i], node; --i >= 0;) {
1340       if (node = group[i]) {
1341         if (next && next !== node.nextSibling) next.parentNode.insertBefore(node, next);
1342         next = node;
1343       }
1344     }
1345   }
1346   return this;
1347 };
1348
1349 d3_selectionPrototype.sort = function(comparator) {
1350   comparator = d3_selection_sortComparator.apply(this, arguments);
1351   for (var j = -1, m = this.length; ++j < m;) this[j].sort(comparator);
1352   return this.order();
1353 };
1354
1355 function d3_selection_sortComparator(comparator) {
1356   if (!arguments.length) comparator = d3.ascending;
1357   return function(a, b) {
1358     return (!a - !b) || comparator(a.__data__, b.__data__);
1359   };
1360 }
1361 function d3_noop() {}
1362
1363 d3_selectionPrototype.on = function(type, listener, capture) {
1364   var n = arguments.length;
1365   if (n < 3) {
1366
1367     // For on(object) or on(object, boolean), the object specifies the event
1368     // types and listeners to add or remove. The optional boolean specifies
1369     // whether the listener captures events.
1370     if (typeof type !== "string") {
1371       if (n < 2) listener = false;
1372       for (capture in type) this.each(d3_selection_on(capture, type[capture], listener));
1373       return this;
1374     }
1375
1376     // For on(string), return the listener for the first node.
1377     if (n < 2) return (n = this.node()["__on" + type]) && n._;
1378
1379     // For on(string, function), use the default capture.
1380     capture = false;
1381   }
1382
1383   // Otherwise, a type, listener and capture are specified, and handled as below.
1384   return this.each(d3_selection_on(type, listener, capture));
1385 };
1386
1387 function d3_selection_on(type, listener, capture) {
1388   var name = "__on" + type,
1389       i = type.indexOf("."),
1390       wrap = d3_selection_onListener;
1391
1392   if (i > 0) type = type.substring(0, i);
1393   var filter = d3_selection_onFilters.get(type);
1394   if (filter) type = filter, wrap = d3_selection_onFilter;
1395
1396   function onRemove() {
1397     var l = this[name];
1398     if (l) {
1399       this.removeEventListener(type, l, l.$);
1400       delete this[name];
1401     }
1402   }
1403
1404   function onAdd() {
1405     var l = wrap(listener, d3_array(arguments));
1406     if (typeof Raven !== 'undefined') l = Raven.wrap(l);
1407     onRemove.call(this);
1408     this.addEventListener(type, this[name] = l, l.$ = capture);
1409     l._ = listener;
1410   }
1411
1412   function removeAll() {
1413     var re = new RegExp("^__on([^.]+)" + d3.requote(type) + "$"),
1414         match;
1415     for (var name in this) {
1416       if (match = name.match(re)) {
1417         var l = this[name];
1418         this.removeEventListener(match[1], l, l.$);
1419         delete this[name];
1420       }
1421     }
1422   }
1423
1424   return i
1425       ? listener ? onAdd : onRemove
1426       : listener ? d3_noop : removeAll;
1427 }
1428
1429 var d3_selection_onFilters = d3.map({
1430   mouseenter: "mouseover",
1431   mouseleave: "mouseout"
1432 });
1433
1434 d3_selection_onFilters.forEach(function(k) {
1435   if ("on" + k in d3_document) d3_selection_onFilters.remove(k);
1436 });
1437
1438 function d3_selection_onListener(listener, argumentz) {
1439   return function(e) {
1440     var o = d3.event; // Events can be reentrant (e.g., focus).
1441     d3.event = e;
1442     argumentz[0] = this.__data__;
1443     try {
1444       listener.apply(this, argumentz);
1445     } finally {
1446       d3.event = o;
1447     }
1448   };
1449 }
1450
1451 function d3_selection_onFilter(listener, argumentz) {
1452   var l = d3_selection_onListener(listener, argumentz);
1453   return function(e) {
1454     var target = this, related = e.relatedTarget;
1455     if (!related || (related !== target && !(related.compareDocumentPosition(target) & 8))) {
1456       l.call(target, e);
1457     }
1458   };
1459 }
1460
1461 d3_selectionPrototype.each = function(callback) {
1462   return d3_selection_each(this, function(node, i, j) {
1463     callback.call(node, node.__data__, i, j);
1464   });
1465 };
1466
1467 function d3_selection_each(groups, callback) {
1468   for (var j = 0, m = groups.length; j < m; j++) {
1469     for (var group = groups[j], i = 0, n = group.length, node; i < n; i++) {
1470       if (node = group[i]) callback(node, i, j);
1471     }
1472   }
1473   return groups;
1474 }
1475
1476 d3_selectionPrototype.call = function(callback) {
1477   var args = d3_array(arguments);
1478   callback.apply(args[0] = this, args);
1479   return this;
1480 };
1481
1482 d3_selectionPrototype.empty = function() {
1483   return !this.node();
1484 };
1485
1486 d3_selectionPrototype.node = function() {
1487   for (var j = 0, m = this.length; j < m; j++) {
1488     for (var group = this[j], i = 0, n = group.length; i < n; i++) {
1489       var node = group[i];
1490       if (node) return node;
1491     }
1492   }
1493   return null;
1494 };
1495
1496 function d3_selection_enter(selection) {
1497   d3_arraySubclass(selection, d3_selection_enterPrototype);
1498   return selection;
1499 }
1500
1501 var d3_selection_enterPrototype = [];
1502
1503 d3.selection.enter = d3_selection_enter;
1504 d3.selection.enter.prototype = d3_selection_enterPrototype;
1505
1506 d3_selection_enterPrototype.append = d3_selectionPrototype.append;
1507 d3_selection_enterPrototype.insert = d3_selectionPrototype.insert;
1508 d3_selection_enterPrototype.empty = d3_selectionPrototype.empty;
1509 d3_selection_enterPrototype.node = d3_selectionPrototype.node;
1510
1511
1512 d3_selection_enterPrototype.select = function(selector) {
1513   var subgroups = [],
1514       subgroup,
1515       subnode,
1516       upgroup,
1517       group,
1518       node;
1519
1520   for (var j = -1, m = this.length; ++j < m;) {
1521     upgroup = (group = this[j]).update;
1522     subgroups.push(subgroup = []);
1523     subgroup.parentNode = group.parentNode;
1524     for (var i = -1, n = group.length; ++i < n;) {
1525       if (node = group[i]) {
1526         subgroup.push(upgroup[i] = subnode = selector.call(group.parentNode, node.__data__, i));
1527         subnode.__data__ = node.__data__;
1528       } else {
1529         subgroup.push(null);
1530       }
1531     }
1532   }
1533
1534   return d3_selection(subgroups);
1535 };
1536
1537 d3_selectionPrototype.transition = function() {
1538   var id = d3_transitionInheritId || ++d3_transitionId,
1539       subgroups = [],
1540       subgroup,
1541       node,
1542       transition = Object.create(d3_transitionInherit);
1543
1544   transition.time = Date.now();
1545
1546   for (var j = -1, m = this.length; ++j < m;) {
1547     subgroups.push(subgroup = []);
1548     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
1549       if (node = group[i]) d3_transitionNode(node, i, id, transition);
1550       subgroup.push(node);
1551     }
1552   }
1553
1554   return d3_transition(subgroups, id);
1555 };
1556
1557 var d3_selectionRoot = d3_selection([[d3_document]]);
1558
1559 d3_selectionRoot[0].parentNode = d3_selectRoot;
1560
1561 // TODO fast singleton implementation!
1562 // TODO select(function)
1563 d3.select = function(selector) {
1564   return typeof selector === "string"
1565       ? d3_selectionRoot.select(selector)
1566       : d3_selection([[selector]]); // assume node
1567 };
1568
1569 // TODO selectAll(function)
1570 d3.selectAll = function(selector) {
1571   return typeof selector === "string"
1572       ? d3_selectionRoot.selectAll(selector)
1573       : d3_selection([d3_array(selector)]); // assume node[]
1574 };
1575
1576 d3.behavior.zoom = function() {
1577   var translate = [0, 0],
1578       translate0, // translate when we started zooming (to avoid drift)
1579       scale = 1,
1580       scale0, // scale when we started touching
1581       scaleExtent = d3_behavior_zoomInfinity,
1582       event = d3_eventDispatch(zoom, "zoom"),
1583       x0,
1584       x1,
1585       y0,
1586       y1,
1587       touchtime; // time of last touchstart (to detect double-tap)
1588
1589   function zoom() {
1590     this.on("mousedown.zoom", mousedown)
1591         .on("mousemove.zoom", mousemove)
1592         .on(d3_behavior_zoomWheel + ".zoom", mousewheel)
1593         .on("dblclick.zoom", dblclick)
1594         .on("touchstart.zoom", touchstart)
1595         .on("touchmove.zoom", touchmove)
1596         .on("touchend.zoom", touchstart);
1597   }
1598
1599   zoom.translate = function(x) {
1600     if (!arguments.length) return translate;
1601     translate = x.map(Number);
1602     rescale();
1603     return zoom;
1604   };
1605
1606   zoom.scale = function(x) {
1607     if (!arguments.length) return scale;
1608     scale = +x;
1609     rescale();
1610     return zoom;
1611   };
1612
1613   zoom.scaleExtent = function(x) {
1614     if (!arguments.length) return scaleExtent;
1615     scaleExtent = x == null ? d3_behavior_zoomInfinity : x.map(Number);
1616     return zoom;
1617   };
1618
1619   zoom.x = function(z) {
1620     if (!arguments.length) return x1;
1621     x1 = z;
1622     x0 = z.copy();
1623     translate = [0, 0];
1624     scale = 1;
1625     return zoom;
1626   };
1627
1628   zoom.y = function(z) {
1629     if (!arguments.length) return y1;
1630     y1 = z;
1631     y0 = z.copy();
1632     translate = [0, 0];
1633     scale = 1;
1634     return zoom;
1635   };
1636
1637   function location(p) {
1638     return [(p[0] - translate[0]) / scale, (p[1] - translate[1]) / scale];
1639   }
1640
1641   function point(l) {
1642     return [l[0] * scale + translate[0], l[1] * scale + translate[1]];
1643   }
1644
1645   function scaleTo(s) {
1646     scale = Math.max(scaleExtent[0], Math.min(scaleExtent[1], s));
1647   }
1648
1649   function translateTo(p, l) {
1650     l = point(l);
1651     translate[0] += p[0] - l[0];
1652     translate[1] += p[1] - l[1];
1653   }
1654
1655   function rescale() {
1656     if (x1) x1.domain(x0.range().map(function(x) { return (x - translate[0]) / scale; }).map(x0.invert));
1657     if (y1) y1.domain(y0.range().map(function(y) { return (y - translate[1]) / scale; }).map(y0.invert));
1658   }
1659
1660   function dispatch(event) {
1661     rescale();
1662     d3.event.preventDefault();
1663     event({type: "zoom", scale: scale, translate: translate});
1664   }
1665
1666   function mousedown() {
1667     var target = this,
1668         event_ = event.of(target, arguments),
1669         eventTarget = d3.event.target,
1670         moved = 0,
1671         w = d3.select(d3_window).on("mousemove.zoom", mousemove).on("mouseup.zoom", mouseup),
1672         l = location(d3.mouse(target));
1673
1674     d3_window.focus();
1675     d3_eventCancel();
1676
1677     function mousemove() {
1678       moved = 1;
1679       translateTo(d3.mouse(target), l);
1680       dispatch(event_);
1681     }
1682
1683     function mouseup() {
1684       if (moved) d3_eventCancel();
1685       w.on("mousemove.zoom", null).on("mouseup.zoom", null);
1686       if (moved && d3.event.target === eventTarget) {
1687           w.on("click.zoom", click, true);
1688           window.setTimeout(function() {
1689               // Remove click block if click didn't fire
1690               w.on("click.zoom", null);
1691           }, 0);
1692       }
1693     }
1694
1695     function click() {
1696       d3_eventCancel();
1697       w.on("click.zoom", null);
1698     }
1699   }
1700
1701   function mousewheel() {
1702     if (!translate0) translate0 = location(d3.mouse(this));
1703     scaleTo(Math.pow(2, d3_behavior_zoomDelta() * .002) * scale);
1704     translateTo(d3.mouse(this), translate0);
1705     dispatch(event.of(this, arguments));
1706   }
1707
1708   function mousemove() {
1709     translate0 = null;
1710   }
1711
1712   function dblclick() {
1713     var p = d3.mouse(this), l = location(p), k = Math.log(scale) / Math.LN2;
1714     scaleTo(Math.pow(2, d3.event.shiftKey ? Math.ceil(k) - 1 : Math.floor(k) + 1));
1715     translateTo(p, l);
1716     dispatch(event.of(this, arguments));
1717   }
1718
1719   function touchstart() {
1720     var touches = d3.touches(this),
1721         now = Date.now();
1722
1723     scale0 = scale;
1724     translate0 = {};
1725     touches.forEach(function(t) { translate0[t.identifier] = location(t); });
1726     d3_eventCancel();
1727
1728     if (touches.length === 1) {
1729       if (now - touchtime < 500) { // dbltap
1730         var p = touches[0], l = location(touches[0]);
1731         scaleTo(scale * 2);
1732         translateTo(p, l);
1733         dispatch(event.of(this, arguments));
1734       }
1735       touchtime = now;
1736     }
1737   }
1738
1739   function touchmove() {
1740     var touches = d3.touches(this),
1741         p0 = touches[0],
1742         l0 = translate0[p0.identifier];
1743     if (p1 = touches[1]) {
1744       var p1, l1 = translate0[p1.identifier];
1745       p0 = [(p0[0] + p1[0]) / 2, (p0[1] + p1[1]) / 2];
1746       l0 = [(l0[0] + l1[0]) / 2, (l0[1] + l1[1]) / 2];
1747       scaleTo(d3.event.scale * scale0);
1748     }
1749     translateTo(p0, l0);
1750     touchtime = null;
1751     dispatch(event.of(this, arguments));
1752   }
1753
1754   return d3.rebind(zoom, event, "on");
1755 };
1756
1757 var d3_behavior_zoomInfinity = [0, Infinity]; // default scale extent
1758
1759 // https://developer.mozilla.org/en-US/docs/Mozilla_event_reference/wheel
1760 var d3_behavior_zoomDelta, d3_behavior_zoomWheel
1761     = "onwheel" in d3_document ? (d3_behavior_zoomDelta = function() { return -d3.event.deltaY * (d3.event.deltaMode ? 120 : 1); }, "wheel")
1762     : "onmousewheel" in d3_document ? (d3_behavior_zoomDelta = function() { return d3.event.wheelDelta; }, "mousewheel")
1763     : (d3_behavior_zoomDelta = function() { return -d3.event.detail; }, "MozMousePixelScroll");
1764 function d3_functor(v) {
1765   return typeof v === "function" ? v : function() { return v; };
1766 }
1767
1768 d3.functor = d3_functor;
1769
1770 var d3_timer_id = 0,
1771     d3_timer_byId = {},
1772     d3_timer_queue = null,
1773     d3_timer_interval, // is an interval (or frame) active?
1774     d3_timer_timeout; // is a timeout active?
1775
1776 // The timer will continue to fire until callback returns true.
1777 d3.timer = function(callback, delay, then) {
1778   if (arguments.length < 3) {
1779     if (arguments.length < 2) delay = 0;
1780     else if (!isFinite(delay)) return;
1781     then = Date.now();
1782   }
1783
1784   // If the callback's already in the queue, update it.
1785   var timer = d3_timer_byId[callback.id];
1786   if (timer && timer.callback === callback) {
1787     timer.then = then;
1788     timer.delay = delay;
1789   }
1790
1791   // Otherwise, add the callback to the queue.
1792   else d3_timer_byId[callback.id = ++d3_timer_id] = d3_timer_queue = {
1793     callback: callback,
1794     then: then,
1795     delay: delay,
1796     next: d3_timer_queue
1797   };
1798
1799   // Start animatin'!
1800   if (!d3_timer_interval) {
1801     d3_timer_timeout = clearTimeout(d3_timer_timeout);
1802     d3_timer_interval = 1;
1803     d3_timer_frame(d3_timer_step);
1804   }
1805 };
1806
1807 function d3_timer_step() {
1808   var elapsed,
1809       now = Date.now(),
1810       t1 = d3_timer_queue;
1811
1812   while (t1) {
1813     elapsed = now - t1.then;
1814     if (elapsed >= t1.delay) t1.flush = t1.callback(elapsed);
1815     t1 = t1.next;
1816   }
1817
1818   var delay = d3_timer_flush() - now;
1819   if (delay > 24) {
1820     if (isFinite(delay)) {
1821       clearTimeout(d3_timer_timeout);
1822       d3_timer_timeout = setTimeout(d3_timer_step, delay);
1823     }
1824     d3_timer_interval = 0;
1825   } else {
1826     d3_timer_interval = 1;
1827     d3_timer_frame(d3_timer_step);
1828   }
1829 }
1830
1831 d3.timer.flush = function() {
1832   var elapsed,
1833       now = Date.now(),
1834       t1 = d3_timer_queue;
1835
1836   while (t1) {
1837     elapsed = now - t1.then;
1838     if (!t1.delay) t1.flush = t1.callback(elapsed);
1839     t1 = t1.next;
1840   }
1841
1842   d3_timer_flush();
1843 };
1844
1845 // Flush after callbacks to avoid concurrent queue modification.
1846 function d3_timer_flush() {
1847   var t0 = null,
1848       t1 = d3_timer_queue,
1849       then = Infinity;
1850   while (t1) {
1851     if (t1.flush) {
1852       delete d3_timer_byId[t1.callback.id];
1853       t1 = t0 ? t0.next = t1.next : d3_timer_queue = t1.next;
1854     } else {
1855       then = Math.min(then, t1.then + t1.delay);
1856       t1 = (t0 = t1).next;
1857     }
1858   }
1859   return then;
1860 }
1861
1862 var d3_timer_frame = d3_window.requestAnimationFrame
1863     || d3_window.webkitRequestAnimationFrame
1864     || d3_window.mozRequestAnimationFrame
1865     || d3_window.oRequestAnimationFrame
1866     || d3_window.msRequestAnimationFrame
1867     || function(callback) { setTimeout(callback, 17); };
1868 var π = Math.PI,
1869     ε = 1e-6,
1870     d3_radians = π / 180,
1871     d3_degrees = 180 / π;
1872
1873 function d3_sgn(x) {
1874   return x > 0 ? 1 : x < 0 ? -1 : 0;
1875 }
1876
1877 function d3_acos(x) {
1878   return Math.acos(Math.max(-1, Math.min(1, x)));
1879 }
1880
1881 function d3_asin(x) {
1882   return x > 1 ? π / 2 : x < -1 ? -π / 2 : Math.asin(x);
1883 }
1884
1885 function d3_sinh(x) {
1886   return (Math.exp(x) - Math.exp(-x)) / 2;
1887 }
1888
1889 function d3_cosh(x) {
1890   return (Math.exp(x) + Math.exp(-x)) / 2;
1891 }
1892
1893 function d3_haversin(x) {
1894   return (x = Math.sin(x / 2)) * x;
1895 }
1896 d3.geo = {};
1897 function d3_identity(d) {
1898   return d;
1899 }
1900 function d3_true() {
1901   return true;
1902 }
1903
1904 function d3_geo_spherical(cartesian) {
1905   return [
1906     Math.atan2(cartesian[1], cartesian[0]),
1907     Math.asin(Math.max(-1, Math.min(1, cartesian[2])))
1908   ];
1909 }
1910
1911 function d3_geo_sphericalEqual(a, b) {
1912   return Math.abs(a[0] - b[0]) < ε && Math.abs(a[1] - b[1]) < ε;
1913 }
1914
1915 // General spherical polygon clipping algorithm: takes a polygon, cuts it into
1916 // visible line segments and rejoins the segments by interpolating along the
1917 // clip edge.
1918 function d3_geo_clipPolygon(segments, compare, inside, interpolate, listener) {
1919   var subject = [],
1920       clip = [];
1921
1922   segments.forEach(function(segment) {
1923     if ((n = segment.length - 1) <= 0) return;
1924     var n, p0 = segment[0], p1 = segment[n];
1925
1926     // If the first and last points of a segment are coincident, then treat as
1927     // a closed ring.
1928     // TODO if all rings are closed, then the winding order of the exterior
1929     // ring should be checked.
1930     if (d3_geo_sphericalEqual(p0, p1)) {
1931       listener.lineStart();
1932       for (var i = 0; i < n; ++i) listener.point((p0 = segment[i])[0], p0[1]);
1933       listener.lineEnd();
1934       return;
1935     }
1936
1937     var a = {point: p0, points: segment, other: null, visited: false, entry: true, subject: true},
1938         b = {point: p0, points: [p0], other: a, visited: false, entry: false, subject: false};
1939     a.other = b;
1940     subject.push(a);
1941     clip.push(b);
1942     a = {point: p1, points: [p1], other: null, visited: false, entry: false, subject: true};
1943     b = {point: p1, points: [p1], other: a, visited: false, entry: true, subject: false};
1944     a.other = b;
1945     subject.push(a);
1946     clip.push(b);
1947   });
1948   clip.sort(compare);
1949   d3_geo_clipPolygonLinkCircular(subject);
1950   d3_geo_clipPolygonLinkCircular(clip);
1951   if (!subject.length) return;
1952
1953   if (inside) for (var i = 1, e = !inside(clip[0].point), n = clip.length; i < n; ++i) {
1954     clip[i].entry = (e = !e);
1955   }
1956
1957   var start = subject[0],
1958       current,
1959       points,
1960       point;
1961   while (1) {
1962     // Find first unvisited intersection.
1963     current = start;
1964     while (current.visited) if ((current = current.next) === start) return;
1965     points = current.points;
1966     listener.lineStart();
1967     do {
1968       current.visited = current.other.visited = true;
1969       if (current.entry) {
1970         if (current.subject) {
1971           for (var i = 0; i < points.length; i++) listener.point((point = points[i])[0], point[1]);
1972         } else {
1973           interpolate(current.point, current.next.point, 1, listener);
1974         }
1975         current = current.next;
1976       } else {
1977         if (current.subject) {
1978           points = current.prev.points;
1979           for (var i = points.length; --i >= 0;) listener.point((point = points[i])[0], point[1]);
1980         } else {
1981           interpolate(current.point, current.prev.point, -1, listener);
1982         }
1983         current = current.prev;
1984       }
1985       current = current.other;
1986       points = current.points;
1987     } while (!current.visited);
1988     listener.lineEnd();
1989   }
1990 }
1991
1992 function d3_geo_clipPolygonLinkCircular(array) {
1993   if (!(n = array.length)) return;
1994   var n,
1995       i = 0,
1996       a = array[0],
1997       b;
1998   while (++i < n) {
1999     a.next = b = array[i];
2000     b.prev = a;
2001     a = b;
2002   }
2003   a.next = b = array[0];
2004   b.prev = a;
2005 }
2006
2007 function d3_geo_clip(pointVisible, clipLine, interpolate) {
2008   return function(listener) {
2009     var line = clipLine(listener);
2010
2011     var clip = {
2012       point: point,
2013       lineStart: lineStart,
2014       lineEnd: lineEnd,
2015       polygonStart: function() {
2016         clip.point = pointRing;
2017         clip.lineStart = ringStart;
2018         clip.lineEnd = ringEnd;
2019         invisible = false;
2020         invisibleArea = visibleArea = 0;
2021         segments = [];
2022         listener.polygonStart();
2023       },
2024       polygonEnd: function() {
2025         clip.point = point;
2026         clip.lineStart = lineStart;
2027         clip.lineEnd = lineEnd;
2028
2029         segments = d3.merge(segments);
2030         if (segments.length) {
2031           d3_geo_clipPolygon(segments, d3_geo_clipSort, null, interpolate, listener);
2032         } else if (visibleArea < -ε || invisible && invisibleArea < -ε) {
2033           listener.lineStart();
2034           interpolate(null, null, 1, listener);
2035           listener.lineEnd();
2036         }
2037         listener.polygonEnd();
2038         segments = null;
2039       },
2040       sphere: function() {
2041         listener.polygonStart();
2042         listener.lineStart();
2043         interpolate(null, null, 1, listener);
2044         listener.lineEnd();
2045         listener.polygonEnd();
2046       }
2047     };
2048
2049     function point(λ, φ) { if (pointVisible(λ, φ)) listener.point(λ, φ); }
2050     function pointLine(λ, φ) { line.point(λ, φ); }
2051     function lineStart() { clip.point = pointLine; line.lineStart(); }
2052     function lineEnd() { clip.point = point; line.lineEnd(); }
2053
2054     var segments,
2055         visibleArea,
2056         invisibleArea,
2057         invisible;
2058
2059     var buffer = d3_geo_clipBufferListener(),
2060         ringListener = clipLine(buffer),
2061         ring;
2062
2063     function pointRing(λ, φ) {
2064       ringListener.point(λ, φ);
2065       ring.push([λ, φ]);
2066     }
2067
2068     function ringStart() {
2069       ringListener.lineStart();
2070       ring = [];
2071     }
2072
2073     function ringEnd() {
2074       pointRing(ring[0][0], ring[0][1]);
2075       ringListener.lineEnd();
2076
2077       var clean = ringListener.clean(),
2078           ringSegments = buffer.buffer(),
2079           segment,
2080           n = ringSegments.length;
2081
2082       // TODO compute on-the-fly?
2083       if (!n) {
2084         invisible = true;
2085         invisibleArea += d3_geo_clipAreaRing(ring, -1);
2086         ring = null;
2087         return;
2088       }
2089       ring = null;
2090
2091       // No intersections.
2092       // TODO compute on-the-fly?
2093       if (clean & 1) {
2094         segment = ringSegments[0];
2095         visibleArea += d3_geo_clipAreaRing(segment, 1);
2096         var n = segment.length - 1,
2097             i = -1,
2098             point;
2099         listener.lineStart();
2100         while (++i < n) listener.point((point = segment[i])[0], point[1]);
2101         listener.lineEnd();
2102         return;
2103       }
2104
2105       // Rejoin connected segments.
2106       // TODO reuse bufferListener.rejoin()?
2107       if (n > 1 && clean & 2) ringSegments.push(ringSegments.pop().concat(ringSegments.shift()));
2108
2109       segments.push(ringSegments.filter(d3_geo_clipSegmentLength1));
2110     }
2111
2112     return clip;
2113   };
2114 }
2115
2116 function d3_geo_clipSegmentLength1(segment) {
2117   return segment.length > 1;
2118 }
2119
2120 function d3_geo_clipBufferListener() {
2121   var lines = [],
2122       line;
2123   return {
2124     lineStart: function() { lines.push(line = []); },
2125     point: function(λ, φ) { line.push([λ, φ]); },
2126     lineEnd: d3_noop,
2127     buffer: function() {
2128       var buffer = lines;
2129       lines = [];
2130       line = null;
2131       return buffer;
2132     },
2133     rejoin: function() {
2134       if (lines.length > 1) lines.push(lines.pop().concat(lines.shift()));
2135     }
2136   };
2137 }
2138
2139 // Approximate polygon ring area (×2, since we only need the sign).
2140 // For an invisible polygon ring, we rotate longitudinally by 180°.
2141 // The invisible parameter should be 1, or -1 to rotate longitudinally.
2142 // Based on Robert. G. Chamberlain and William H. Duquette,
2143 // “Some Algorithms for Polygons on a Sphere”,
2144 // http://trs-new.jpl.nasa.gov/dspace/handle/2014/40409
2145 function d3_geo_clipAreaRing(ring, invisible) {
2146   if (!(n = ring.length)) return 0;
2147   var n,
2148       i = 0,
2149       area = 0,
2150       p = ring[0],
2151       λ = p[0],
2152       φ = p[1],
2153       cosφ = Math.cos(φ),
2154       x0 = Math.atan2(invisible * Math.sin(λ) * cosφ, Math.sin(φ)),
2155       y0 = 1 - invisible * Math.cos(λ) * cosφ,
2156       x1 = x0,
2157       x, // λ'; λ rotated to south pole.
2158       y; // φ' = 1 + sin(φ); φ rotated to south pole.
2159   while (++i < n) {
2160     p = ring[i];
2161     cosφ = Math.cos(φ = p[1]);
2162     x = Math.atan2(invisible * Math.sin(λ = p[0]) * cosφ, Math.sin(φ));
2163     y = 1 - invisible * Math.cos(λ) * cosφ;
2164
2165     // If both the current point and the previous point are at the north pole,
2166     // skip this point.
2167     if (Math.abs(y0 - 2) < ε && Math.abs(y - 2) < ε) continue;
2168
2169     // If this or the previous point is at the south pole, or if this segment
2170     // goes through the south pole, the area is 0.
2171     if (Math.abs(y) < ε || Math.abs(y0) < ε) {}
2172
2173     // If this segment goes through either pole…
2174     else if (Math.abs(Math.abs(x - x0) - π) < ε) {
2175       // For the north pole, compute lune area.
2176       if (y + y0 > 2) area += 4 * (x - x0);
2177       // For the south pole, the area is zero.
2178     }
2179
2180     // If the previous point is at the north pole, then compute lune area.
2181     else if (Math.abs(y0 - 2) < ε) area += 4 * (x - x1);
2182
2183     // Otherwise, the spherical triangle area is approximately
2184     // δλ * (1 + sinφ0 + 1 + sinφ) / 2.
2185     else area += ((3 * π + x - x0) % (2 * π) - π) * (y0 + y);
2186
2187     x1 = x0, x0 = x, y0 = y;
2188   }
2189   return area;
2190 }
2191
2192 // Intersection points are sorted along the clip edge. For both antimeridian
2193 // cutting and circle clipping, the same comparison is used.
2194 function d3_geo_clipSort(a, b) {
2195   return ((a = a.point)[0] < 0 ? a[1] - π / 2 - ε : π / 2 - a[1])
2196        - ((b = b.point)[0] < 0 ? b[1] - π / 2 - ε : π / 2 - b[1]);
2197 }
2198
2199 var d3_geo_clipAntimeridian = d3_geo_clip(d3_true, d3_geo_clipAntimeridianLine, d3_geo_clipAntimeridianInterpolate);
2200
2201 // Takes a line and cuts into visible segments. Return values:
2202 //   0: there were intersections or the line was empty.
2203 //   1: no intersections.
2204 //   2: there were intersections, and the first and last segments should be
2205 //      rejoined.
2206 function d3_geo_clipAntimeridianLine(listener) {
2207   var λ0 = NaN,
2208       φ0 = NaN,
2209       sλ0 = NaN,
2210       clean; // no intersections
2211
2212   return {
2213     lineStart: function() {
2214       listener.lineStart();
2215       clean = 1;
2216     },
2217     point: function(λ1, φ1) {
2218       var sλ1 = λ1 > 0 ? π : -π,
2219           dλ = Math.abs(λ1 - λ0);
2220       if (Math.abs(dλ - π) < ε) { // line crosses a pole
2221         listener.point(λ0, φ0 = (φ0 + φ1) / 2 > 0 ? π / 2 : -π / 2);
2222         listener.point(sλ0, φ0);
2223         listener.lineEnd();
2224         listener.lineStart();
2225         listener.point(sλ1, φ0);
2226         listener.point( λ1, φ0);
2227         clean = 0;
2228       } else if (sλ0 !== sλ1 && dλ >= π) { // line crosses antimeridian
2229         // handle degeneracies
2230         if (Math.abs(λ0 - sλ0) < ε) λ0 -= sλ0 * ε;
2231         if (Math.abs(λ1 - sλ1) < ε) λ1 -= sλ1 * ε;
2232         φ0 = d3_geo_clipAntimeridianIntersect(λ0, φ0, λ1, φ1);
2233         listener.point(sλ0, φ0);
2234         listener.lineEnd();
2235         listener.lineStart();
2236         listener.point(sλ1, φ0);
2237         clean = 0;
2238       }
2239       listener.point(λ0 = λ1, φ0 = φ1);
2240       sλ0 = sλ1;
2241     },
2242     lineEnd: function() {
2243       listener.lineEnd();
2244       λ0 = φ0 = NaN;
2245     },
2246     // if there are intersections, we always rejoin the first and last segments.
2247     clean: function() { return 2 - clean; }
2248   };
2249 }
2250
2251 function d3_geo_clipAntimeridianIntersect(λ0, φ0, λ1, φ1) {
2252   var cosφ0,
2253       cosφ1,
2254       sinλ0_λ1 = Math.sin(λ0 - λ1);
2255   return Math.abs(sinλ0_λ1) > ε
2256       ? Math.atan((Math.sin(φ0) * (cosφ1 = Math.cos(φ1)) * Math.sin(λ1)
2257                  - Math.sin(φ1) * (cosφ0 = Math.cos(φ0)) * Math.sin(λ0))
2258                  / (cosφ0 * cosφ1 * sinλ0_λ1))
2259       : (φ0 + φ1) / 2;
2260 }
2261
2262 function d3_geo_clipAntimeridianInterpolate(from, to, direction, listener) {
2263   var φ;
2264   if (from == null) {
2265     φ = direction * π / 2;
2266     listener.point(-π,  φ);
2267     listener.point( 0,  φ);
2268     listener.point( π,  φ);
2269     listener.point( π,  0);
2270     listener.point( π, -φ);
2271     listener.point( 0, -φ);
2272     listener.point(-π, -φ);
2273     listener.point(-π,  0);
2274     listener.point(-π,  φ);
2275   } else if (Math.abs(from[0] - to[0]) > ε) {
2276     var s = (from[0] < to[0] ? 1 : -1) * π;
2277     φ = direction * s / 2;
2278     listener.point(-s, φ);
2279     listener.point( 0, φ);
2280     listener.point( s, φ);
2281   } else {
2282     listener.point(to[0], to[1]);
2283   }
2284 }
2285 // TODO
2286 // cross and scale return new vectors,
2287 // whereas add and normalize operate in-place
2288
2289 function d3_geo_cartesian(spherical) {
2290   var λ = spherical[0],
2291       φ = spherical[1],
2292       cosφ = Math.cos(φ);
2293   return [
2294     cosφ * Math.cos(λ),
2295     cosφ * Math.sin(λ),
2296     Math.sin(φ)
2297   ];
2298 }
2299
2300 function d3_geo_cartesianDot(a, b) {
2301   return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
2302 }
2303
2304 function d3_geo_cartesianCross(a, b) {
2305   return [
2306     a[1] * b[2] - a[2] * b[1],
2307     a[2] * b[0] - a[0] * b[2],
2308     a[0] * b[1] - a[1] * b[0]
2309   ];
2310 }
2311
2312 function d3_geo_cartesianAdd(a, b) {
2313   a[0] += b[0];
2314   a[1] += b[1];
2315   a[2] += b[2];
2316 }
2317
2318 function d3_geo_cartesianScale(vector, k) {
2319   return [
2320     vector[0] * k,
2321     vector[1] * k,
2322     vector[2] * k
2323   ];
2324 }
2325
2326 function d3_geo_cartesianNormalize(d) {
2327   var l = Math.sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]);
2328   d[0] /= l;
2329   d[1] /= l;
2330   d[2] /= l;
2331 }
2332
2333 function d3_geo_equirectangular(λ, φ) {
2334   return [λ, φ];
2335 }
2336
2337 (d3.geo.equirectangular = function() {
2338   return d3_geo_projection(d3_geo_equirectangular);
2339 }).raw = d3_geo_equirectangular.invert = d3_geo_equirectangular;
2340
2341 d3.geo.rotation = function(rotate) {
2342   rotate = d3_geo_rotation(rotate[0] % 360 * d3_radians, rotate[1] * d3_radians, rotate.length > 2 ? rotate[2] * d3_radians : 0);
2343
2344   function forward(coordinates) {
2345     coordinates = rotate(coordinates[0] * d3_radians, coordinates[1] * d3_radians);
2346     return coordinates[0] *= d3_degrees, coordinates[1] *= d3_degrees, coordinates;
2347   }
2348
2349   forward.invert = function(coordinates) {
2350     coordinates = rotate.invert(coordinates[0] * d3_radians, coordinates[1] * d3_radians);
2351     return coordinates[0] *= d3_degrees, coordinates[1] *= d3_degrees, coordinates;
2352   };
2353
2354   return forward;
2355 };
2356
2357 // Note: |δλ| must be < 2π
2358 function d3_geo_rotation(δλ, δφ, δγ) {
2359   return δλ ? (δφ || δγ ? d3_geo_compose(d3_geo_rotationλ(δλ), d3_geo_rotationφγ(δφ, δγ))
2360     : d3_geo_rotationλ(δλ))
2361     : (δφ || δγ ? d3_geo_rotationφγ(δφ, δγ)
2362     : d3_geo_equirectangular);
2363 }
2364
2365 function d3_geo_forwardRotationλ(δλ) {
2366   return function(λ, φ) {
2367     return λ += δλ, [λ > π ? λ - 2 * π : λ < -π ? λ + 2 * π : λ, φ];
2368   };
2369 }
2370
2371 function d3_geo_rotationλ(δλ) {
2372   var rotation = d3_geo_forwardRotationλ(δλ);
2373   rotation.invert = d3_geo_forwardRotationλ(-δλ);
2374   return rotation;
2375 }
2376
2377 function d3_geo_rotationφγ(δφ, δγ) {
2378   var cosδφ = Math.cos(δφ),
2379       sinδφ = Math.sin(δφ),
2380       cosδγ = Math.cos(δγ),
2381       sinδγ = Math.sin(δγ);
2382
2383   function rotation(λ, φ) {
2384     var cosφ = Math.cos(φ),
2385         x = Math.cos(λ) * cosφ,
2386         y = Math.sin(λ) * cosφ,
2387         z = Math.sin(φ),
2388         k = z * cosδφ + x * sinδφ;
2389     return [
2390       Math.atan2(y * cosδγ - k * sinδγ, x * cosδφ - z * sinδφ),
2391       Math.asin(Math.max(-1, Math.min(1, k * cosδγ + y * sinδγ)))
2392     ];
2393   }
2394
2395   rotation.invert = function(λ, φ) {
2396     var cosφ = Math.cos(φ),
2397         x = Math.cos(λ) * cosφ,
2398         y = Math.sin(λ) * cosφ,
2399         z = Math.sin(φ),
2400         k = z * cosδγ - y * sinδγ;
2401     return [
2402       Math.atan2(y * cosδγ + z * sinδγ, x * cosδφ + k * sinδφ),
2403       Math.asin(Math.max(-1, Math.min(1, k * cosδφ - x * sinδφ)))
2404     ];
2405   };
2406
2407   return rotation;
2408 }
2409
2410 d3.geo.circle = function() {
2411   var origin = [0, 0],
2412       angle,
2413       precision = 6,
2414       interpolate;
2415
2416   function circle() {
2417     var center = typeof origin === "function" ? origin.apply(this, arguments) : origin,
2418         rotate = d3_geo_rotation(-center[0] * d3_radians, -center[1] * d3_radians, 0).invert,
2419         ring = [];
2420
2421     interpolate(null, null, 1, {
2422       point: function(x, y) {
2423         ring.push(x = rotate(x, y));
2424         x[0] *= d3_degrees, x[1] *= d3_degrees;
2425       }
2426     });
2427
2428     return {type: "Polygon", coordinates: [ring]};
2429   }
2430
2431   circle.origin = function(x) {
2432     if (!arguments.length) return origin;
2433     origin = x;
2434     return circle;
2435   };
2436
2437   circle.angle = function(x) {
2438     if (!arguments.length) return angle;
2439     interpolate = d3_geo_circleInterpolate((angle = +x) * d3_radians, precision * d3_radians);
2440     return circle;
2441   };
2442
2443   circle.precision = function(_) {
2444     if (!arguments.length) return precision;
2445     interpolate = d3_geo_circleInterpolate(angle * d3_radians, (precision = +_) * d3_radians);
2446     return circle;
2447   };
2448
2449   return circle.angle(90);
2450 };
2451
2452 // Interpolates along a circle centered at [0°, 0°], with a given radius and
2453 // precision.
2454 function d3_geo_circleInterpolate(radius, precision) {
2455   var cr = Math.cos(radius),
2456       sr = Math.sin(radius);
2457   return function(from, to, direction, listener) {
2458     if (from != null) {
2459       from = d3_geo_circleAngle(cr, from);
2460       to = d3_geo_circleAngle(cr, to);
2461       if (direction > 0 ? from < to: from > to) from += direction * 2 * π;
2462     } else {
2463       from = radius + direction * 2 * π;
2464       to = radius;
2465     }
2466     var point;
2467     for (var step = direction * precision, t = from; direction > 0 ? t > to : t < to; t -= step) {
2468       listener.point((point = d3_geo_spherical([
2469         cr,
2470         -sr * Math.cos(t),
2471         -sr * Math.sin(t)
2472       ]))[0], point[1]);
2473     }
2474   };
2475 }
2476
2477 // Signed angle of a cartesian point relative to [cr, 0, 0].
2478 function d3_geo_circleAngle(cr, point) {
2479   var a = d3_geo_cartesian(point);
2480   a[0] -= cr;
2481   d3_geo_cartesianNormalize(a);
2482   var angle = d3_acos(-a[1]);
2483   return ((-a[2] < 0 ? -angle : angle) + 2 * Math.PI - ε) % (2 * Math.PI);
2484 }
2485
2486 // Clip features against a small circle centered at [0°, 0°].
2487 function d3_geo_clipCircle(radius) {
2488   var cr = Math.cos(radius),
2489       smallRadius = cr > 0,
2490       notHemisphere = Math.abs(cr) > ε, // TODO optimise for this common case
2491       interpolate = d3_geo_circleInterpolate(radius, 6 * d3_radians);
2492
2493   return d3_geo_clip(visible, clipLine, interpolate);
2494
2495   function visible(λ, φ) {
2496     return Math.cos(λ) * Math.cos(φ) > cr;
2497   }
2498
2499   // Takes a line and cuts into visible segments. Return values used for
2500   // polygon clipping:
2501   //   0: there were intersections or the line was empty.
2502   //   1: no intersections.
2503   //   2: there were intersections, and the first and last segments should be
2504   //      rejoined.
2505   function clipLine(listener) {
2506     var point0, // previous point
2507         c0, // code for previous point
2508         v0, // visibility of previous point
2509         v00, // visibility of first point
2510         clean; // no intersections
2511     return {
2512       lineStart: function() {
2513         v00 = v0 = false;
2514         clean = 1;
2515       },
2516       point: function(λ, φ) {
2517         var point1 = [λ, φ],
2518             point2,
2519             v = visible(λ, φ),
2520             c = smallRadius
2521               ? v ? 0 : code(λ, φ)
2522               : v ? code(λ + (λ < 0 ? π : -π), φ) : 0;
2523         if (!point0 && (v00 = v0 = v)) listener.lineStart();
2524         // Handle degeneracies.
2525         // TODO ignore if not clipping polygons.
2526         if (v !== v0) {
2527           point2 = intersect(point0, point1);
2528           if (d3_geo_sphericalEqual(point0, point2) || d3_geo_sphericalEqual(point1, point2)) {
2529             point1[0] += ε;
2530             point1[1] += ε;
2531             v = visible(point1[0], point1[1]);
2532           }
2533         }
2534         if (v !== v0) {
2535           clean = 0;
2536           if (v) {
2537             // outside going in
2538             listener.lineStart();
2539             point2 = intersect(point1, point0);
2540             listener.point(point2[0], point2[1]);
2541           } else {
2542             // inside going out
2543             point2 = intersect(point0, point1);
2544             listener.point(point2[0], point2[1]);
2545             listener.lineEnd();
2546           }
2547           point0 = point2;
2548         } else if (notHemisphere && point0 && smallRadius ^ v) {
2549           var t;
2550           // If the codes for two points are different, or are both zero,
2551           // and there this segment intersects with the small circle.
2552           if (!(c & c0) && (t = intersect(point1, point0, true))) {
2553             clean = 0;
2554             if (smallRadius) {
2555               listener.lineStart();
2556               listener.point(t[0][0], t[0][1]);
2557               listener.point(t[1][0], t[1][1]);
2558               listener.lineEnd();
2559             } else {
2560               listener.point(t[1][0], t[1][1]);
2561               listener.lineEnd();
2562               listener.lineStart();
2563               listener.point(t[0][0], t[0][1]);
2564             }
2565           }
2566         }
2567         if (v && (!point0 || !d3_geo_sphericalEqual(point0, point1))) {
2568           listener.point(point1[0], point1[1]);
2569         }
2570         point0 = point1, v0 = v, c0 = c;
2571       },
2572       lineEnd: function() {
2573         if (v0) listener.lineEnd();
2574         point0 = null;
2575       },
2576       // Rejoin first and last segments if there were intersections and the first
2577       // and last points were visible.
2578       clean: function() { return clean | ((v00 && v0) << 1); }
2579     };
2580   }
2581
2582   // Intersects the great circle between a and b with the clip circle.
2583   function intersect(a, b, two) {
2584     var pa = d3_geo_cartesian(a),
2585         pb = d3_geo_cartesian(b);
2586
2587     // We have two planes, n1.p = d1 and n2.p = d2.
2588     // Find intersection line p(t) = c1 n1 + c2 n2 + t (n1 ⨯ n2).
2589     var n1 = [1, 0, 0], // normal
2590         n2 = d3_geo_cartesianCross(pa, pb),
2591         n2n2 = d3_geo_cartesianDot(n2, n2),
2592         n1n2 = n2[0], // d3_geo_cartesianDot(n1, n2),
2593         determinant = n2n2 - n1n2 * n1n2;
2594
2595     // Two polar points.
2596     if (!determinant) return !two && a;
2597
2598     var c1 =  cr * n2n2 / determinant,
2599         c2 = -cr * n1n2 / determinant,
2600         n1xn2 = d3_geo_cartesianCross(n1, n2),
2601         A = d3_geo_cartesianScale(n1, c1),
2602         B = d3_geo_cartesianScale(n2, c2);
2603     d3_geo_cartesianAdd(A, B);
2604
2605     // Solve |p(t)|^2 = 1.
2606     var u = n1xn2,
2607         w = d3_geo_cartesianDot(A, u),
2608         uu = d3_geo_cartesianDot(u, u),
2609         t2 = w * w - uu * (d3_geo_cartesianDot(A, A) - 1);
2610
2611     if (t2 < 0) return;
2612
2613     var t = Math.sqrt(t2),
2614         q = d3_geo_cartesianScale(u, (-w - t) / uu);
2615     d3_geo_cartesianAdd(q, A);
2616     q = d3_geo_spherical(q);
2617     if (!two) return q;
2618
2619     // Two intersection points.
2620     var λ0 = a[0],
2621         λ1 = b[0],
2622         φ0 = a[1],
2623         φ1 = b[1],
2624         z;
2625     if (λ1 < λ0) z = λ0, λ0 = λ1, λ1 = z;
2626     var δλ = λ1 - λ0,
2627         polar = Math.abs(δλ - π) < ε,
2628         meridian = polar || δλ < ε;
2629
2630     if (!polar && φ1 < φ0) z = φ0, φ0 = φ1, φ1 = z;
2631
2632     // Check that the first point is between a and b.
2633     if (meridian
2634         ? polar
2635           ? φ0 + φ1 > 0 ^ q[1] < (Math.abs(q[0] - λ0) < ε ? φ0 : φ1)
2636           : φ0 <= q[1] && q[1] <= φ1
2637         : δλ > π ^ (λ0 <= q[0] && q[0] <= λ1)) {
2638       var q1 = d3_geo_cartesianScale(u, (-w + t) / uu);
2639       d3_geo_cartesianAdd(q1, A);
2640       return [q, d3_geo_spherical(q1)];
2641     }
2642   }
2643
2644   // Generates a 4-bit vector representing the location of a point relative to
2645   // the small circle's bounding box.
2646   function code(λ, φ) {
2647     var r = smallRadius ? radius : π - radius,
2648         code = 0;
2649     if (λ < -r) code |= 1; // left
2650     else if (λ > r) code |= 2; // right
2651     if (φ < -r) code |= 4; // below
2652     else if (φ > r) code |= 8; // above
2653     return code;
2654   }
2655 }
2656
2657 var d3_geo_clipViewMAX = 1e9;
2658
2659 function d3_geo_clipView(x0, y0, x1, y1) {
2660   return function(listener) {
2661     var listener_ = listener,
2662         bufferListener = d3_geo_clipBufferListener(),
2663         segments,
2664         polygon,
2665         ring;
2666
2667     var clip = {
2668       point: point,
2669       lineStart: lineStart,
2670       lineEnd: lineEnd,
2671       polygonStart: function() {
2672         listener = bufferListener;
2673         segments = [];
2674         polygon = [];
2675       },
2676       polygonEnd: function() {
2677         listener = listener_;
2678         if ((segments = d3.merge(segments)).length) {
2679           listener.polygonStart();
2680           d3_geo_clipPolygon(segments, compare, inside, interpolate, listener);
2681           listener.polygonEnd();
2682         } else if (insidePolygon([x0, y0])) {
2683           listener.polygonStart(), listener.lineStart();
2684           interpolate(null, null, 1, listener);
2685           listener.lineEnd(), listener.polygonEnd();
2686         }
2687         segments = polygon = ring = null;
2688       }
2689     };
2690
2691     function inside(point) {
2692       var a = corner(point, -1),
2693           i = insidePolygon([a === 0 || a === 3 ? x0 : x1, a > 1 ? y1 : y0]);
2694       return i;
2695     }
2696
2697     function insidePolygon(p) {
2698       var wn = 0, // the winding number counter
2699           n = polygon.length,
2700           y = p[1];
2701
2702       for (var i = 0; i < n; ++i) {
2703         for (var j = 1, v = polygon[i], m = v.length, a = v[0]; j < m; ++j) {
2704           b = v[j];
2705           if (a[1] <= y) {
2706             if (b[1] >  y && isLeft(a, b, p) > 0) ++wn;
2707           } else {
2708             if (b[1] <= y && isLeft(a, b, p) < 0) --wn;
2709           }
2710           a = b;
2711         }
2712       }
2713       return wn !== 0;
2714     }
2715
2716     function isLeft(a, b, c) {
2717       return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]);
2718     }
2719
2720     function interpolate(from, to, direction, listener) {
2721       var a = 0, a1 = 0;
2722       if (from == null ||
2723           (a = corner(from, direction)) !== (a1 = corner(to, direction)) ||
2724           comparePoints(from, to) < 0 ^ direction > 0) {
2725         do {
2726           listener.point(a === 0 || a === 3 ? x0 : x1, a > 1 ? y1 : y0);
2727         } while ((a = (a + direction + 4) % 4) !== a1);
2728       } else {
2729         listener.point(to[0], to[1]);
2730       }
2731     }
2732
2733     function visible(x, y) {
2734       return x0 <= x && x <= x1 && y0 <= y && y <= y1;
2735     }
2736
2737     function point(x, y) {
2738       if (visible(x, y)) listener.point(x, y);
2739     }
2740
2741     var x__, y__, v__, // first point
2742         x_, y_, v_, // previous point
2743         first;
2744
2745     function lineStart() {
2746       clip.point = linePoint;
2747       if (polygon) polygon.push(ring = []);
2748       first = true;
2749       v_ = false;
2750       x_ = y_ = NaN;
2751     }
2752
2753     function lineEnd() {
2754       // TODO rather than special-case polygons, simply handle them separately.
2755       // Ideally, coincident intersection points should be jittered to avoid
2756       // clipping issues.
2757       if (segments) {
2758         linePoint(x__, y__);
2759         if (v__ && v_) bufferListener.rejoin();
2760         segments.push(bufferListener.buffer());
2761       }
2762       clip.point = point;
2763       if (v_) listener.lineEnd();
2764     }
2765
2766     function linePoint(x, y) {
2767       x = Math.max(-d3_geo_clipViewMAX, Math.min(d3_geo_clipViewMAX, x));
2768       y = Math.max(-d3_geo_clipViewMAX, Math.min(d3_geo_clipViewMAX, y));
2769       var v = visible(x, y);
2770       if (polygon) ring.push([x, y]);
2771       if (first) {
2772         x__ = x, y__ = y, v__ = v;
2773         first = false;
2774         if (v) {
2775           listener.lineStart();
2776           listener.point(x, y);
2777         }
2778       } else {
2779         if (v && v_) listener.point(x, y);
2780         else {
2781           var a = [x_, y_],
2782               b = [x, y];
2783           if (clipLine(a, b)) {
2784             if (!v_) {
2785               listener.lineStart();
2786               listener.point(a[0], a[1]);
2787             }
2788             listener.point(b[0], b[1]);
2789             if (!v) listener.lineEnd();
2790           } else {
2791             listener.lineStart();
2792             listener.point(x, y);
2793           }
2794         }
2795       }
2796       x_ = x, y_ = y, v_ = v;
2797     }
2798
2799     return clip;
2800   };
2801
2802   function corner(p, direction) {
2803     return Math.abs(p[0] - x0) < ε ? direction > 0 ? 0 : 3
2804         : Math.abs(p[0] - x1) < ε ? direction > 0 ? 2 : 1
2805         : Math.abs(p[1] - y0) < ε ? direction > 0 ? 1 : 0
2806         : direction > 0 ? 3 : 2; // Math.abs(p[1] - y1) < ε
2807   }
2808
2809   function compare(a, b) {
2810     return comparePoints(a.point, b.point);
2811   }
2812
2813   function comparePoints(a, b) {
2814     var ca = corner(a, 1),
2815         cb = corner(b, 1);
2816     return ca !== cb ? ca - cb
2817         : ca === 0 ? b[1] - a[1]
2818         : ca === 1 ? a[0] - b[0]
2819         : ca === 2 ? a[1] - b[1]
2820         : b[0] - a[0];
2821   }
2822
2823   // Liang–Barsky line clipping.
2824   function clipLine(a, b) {
2825     var dx = b[0] - a[0],
2826         dy = b[1] - a[1],
2827         t = [0, 1];
2828
2829     if (Math.abs(dx) < ε && Math.abs(dy) < ε) return x0 <= a[0] && a[0] <= x1 && y0 <= a[1] && a[1] <= y1;
2830
2831     if (d3_geo_clipViewT(x0 - a[0],  dx, t) &&
2832         d3_geo_clipViewT(a[0] - x1, -dx, t) &&
2833         d3_geo_clipViewT(y0 - a[1],  dy, t) &&
2834         d3_geo_clipViewT(a[1] - y1, -dy, t)) {
2835       if (t[1] < 1) {
2836         b[0] = a[0] + t[1] * dx;
2837         b[1] = a[1] + t[1] * dy;
2838       }
2839       if (t[0] > 0) {
2840         a[0] += t[0] * dx;
2841         a[1] += t[0] * dy;
2842       }
2843       return true;
2844     }
2845
2846     return false;
2847   }
2848 }
2849
2850 function d3_geo_clipViewT(num, denominator, t) {
2851   if (Math.abs(denominator) < ε) return num <= 0;
2852
2853   var u = num / denominator;
2854
2855   if (denominator > 0) {
2856     if (u > t[1]) return false;
2857     if (u > t[0]) t[0] = u;
2858   } else {
2859     if (u < t[0]) return false;
2860     if (u < t[1]) t[1] = u;
2861   }
2862   return true;
2863 }
2864 function d3_geo_compose(a, b) {
2865
2866   function compose(x, y) {
2867     return x = a(x, y), b(x[0], x[1]);
2868   }
2869
2870   if (a.invert && b.invert) compose.invert = function(x, y) {
2871     return x = b.invert(x, y), x && a.invert(x[0], x[1]);
2872   };
2873
2874   return compose;
2875 }
2876
2877 d3.geo.stream = function(object, listener) {
2878   if (d3_geo_streamObjectType.hasOwnProperty(object.type)) {
2879     d3_geo_streamObjectType[object.type](object, listener);
2880   } else {
2881     d3_geo_streamGeometry(object, listener);
2882   }
2883 };
2884
2885 function d3_geo_streamGeometry(geometry, listener) {
2886   if (d3_geo_streamGeometryType.hasOwnProperty(geometry.type)) {
2887     d3_geo_streamGeometryType[geometry.type](geometry, listener);
2888   }
2889 }
2890
2891 var d3_geo_streamObjectType = {
2892   Feature: function(feature, listener) {
2893     d3_geo_streamGeometry(feature.geometry, listener);
2894   },
2895   FeatureCollection: function(object, listener) {
2896     var features = object.features, i = -1, n = features.length;
2897     while (++i < n) d3_geo_streamGeometry(features[i].geometry, listener);
2898   }
2899 };
2900
2901 var d3_geo_streamGeometryType = {
2902   Sphere: function(object, listener) {
2903     listener.sphere();
2904   },
2905   Point: function(object, listener) {
2906     var coordinate = object.coordinates;
2907     listener.point(coordinate[0], coordinate[1]);
2908   },
2909   MultiPoint: function(object, listener) {
2910     var coordinates = object.coordinates, i = -1, n = coordinates.length, coordinate;
2911     while (++i < n) coordinate = coordinates[i], listener.point(coordinate[0], coordinate[1]);
2912   },
2913   LineString: function(object, listener) {
2914     d3_geo_streamLine(object.coordinates, listener, 0);
2915   },
2916   MultiLineString: function(object, listener) {
2917     var coordinates = object.coordinates, i = -1, n = coordinates.length;
2918     while (++i < n) d3_geo_streamLine(coordinates[i], listener, 0);
2919   },
2920   Polygon: function(object, listener) {
2921     d3_geo_streamPolygon(object.coordinates, listener);
2922   },
2923   MultiPolygon: function(object, listener) {
2924     var coordinates = object.coordinates, i = -1, n = coordinates.length;
2925     while (++i < n) d3_geo_streamPolygon(coordinates[i], listener);
2926   },
2927   GeometryCollection: function(object, listener) {
2928     var geometries = object.geometries, i = -1, n = geometries.length;
2929     while (++i < n) d3_geo_streamGeometry(geometries[i], listener);
2930   }
2931 };
2932
2933 function d3_geo_streamLine(coordinates, listener, closed) {
2934   var i = -1, n = coordinates.length - closed, coordinate;
2935   listener.lineStart();
2936   while (++i < n) coordinate = coordinates[i], listener.point(coordinate[0], coordinate[1]);
2937   listener.lineEnd();
2938 }
2939
2940 function d3_geo_streamPolygon(coordinates, listener) {
2941   var i = -1, n = coordinates.length;
2942   listener.polygonStart();
2943   while (++i < n) d3_geo_streamLine(coordinates[i], listener, 1);
2944   listener.polygonEnd();
2945 }
2946
2947 function d3_geo_resample(project) {
2948   var δ2 = .5, // precision, px²
2949       maxDepth = 16;
2950
2951   function resample(stream) {
2952     var λ0, x0, y0, a0, b0, c0; // previous point
2953
2954     var resample = {
2955       point: point,
2956       lineStart: lineStart,
2957       lineEnd: lineEnd,
2958       polygonStart: function() { stream.polygonStart(); resample.lineStart = polygonLineStart; },
2959       polygonEnd: function() { stream.polygonEnd(); resample.lineStart = lineStart; }
2960     };
2961
2962     function point(x, y) {
2963       x = project(x, y);
2964       stream.point(x[0], x[1]);
2965     }
2966
2967     function lineStart() {
2968       x0 = NaN;
2969       resample.point = linePoint;
2970       stream.lineStart();
2971     }
2972
2973     function linePoint(λ, φ) {
2974       var c = d3_geo_cartesian([λ, φ]), p = project(λ, φ);
2975       resampleLineTo(x0, y0, λ0, a0, b0, c0, x0 = p[0], y0 = p[1], λ0 = λ, a0 = c[0], b0 = c[1], c0 = c[2], maxDepth, stream);
2976       stream.point(x0, y0);
2977     }
2978
2979     function lineEnd() {
2980       resample.point = point;
2981       stream.lineEnd();
2982     }
2983
2984     function polygonLineStart() {
2985       var λ00, φ00, x00, y00, a00, b00, c00; // first point
2986
2987       lineStart();
2988
2989       resample.point = function(λ, φ) {
2990         linePoint(λ00 = λ, φ00 = φ), x00 = x0, y00 = y0, a00 = a0, b00 = b0, c00 = c0;
2991         resample.point = linePoint;
2992       };
2993
2994       resample.lineEnd = function() {
2995         resampleLineTo(x0, y0, λ0, a0, b0, c0, x00, y00, λ00, a00, b00, c00, maxDepth, stream);
2996         resample.lineEnd = lineEnd;
2997         lineEnd();
2998       };
2999     }
3000
3001     return resample;
3002   }
3003
3004   function resampleLineTo(x0, y0, λ0, a0, b0, c0, x1, y1, λ1, a1, b1, c1, depth, stream) {
3005     var dx = x1 - x0,
3006         dy = y1 - y0,
3007         d2 = dx * dx + dy * dy;
3008     if (d2 > 4 * δ2 && depth--) {
3009       var a = a0 + a1,
3010           b = b0 + b1,
3011           c = c0 + c1,
3012           m = Math.sqrt(a * a + b * b + c * c),
3013           φ2 = Math.asin(c /= m),
3014           λ2 = Math.abs(Math.abs(c) - 1) < ε ? (λ0 + λ1) / 2 : Math.atan2(b, a),
3015           p = project(λ2, φ2),
3016           x2 = p[0],
3017           y2 = p[1],
3018           dx2 = x2 - x0,
3019           dy2 = y2 - y0,
3020           dz = dy * dx2 - dx * dy2;
3021       if (dz * dz / d2 > δ2 || Math.abs((dx * dx2 + dy * dy2) / d2 - .5) > .3) {
3022         resampleLineTo(x0, y0, λ0, a0, b0, c0, x2, y2, λ2, a /= m, b /= m, c, depth, stream);
3023         stream.point(x2, y2);
3024         resampleLineTo(x2, y2, λ2, a, b, c, x1, y1, λ1, a1, b1, c1, depth, stream);
3025       }
3026     }
3027   }
3028
3029   resample.precision = function(_) {
3030     if (!arguments.length) return Math.sqrt(δ2);
3031     maxDepth = (δ2 = _ * _) > 0 && 16;
3032     return resample;
3033   };
3034
3035   return resample;
3036 }
3037
3038 d3.geo.projection = d3_geo_projection;
3039 d3.geo.projectionMutator = d3_geo_projectionMutator;
3040
3041 function d3_geo_projection(project) {
3042   return d3_geo_projectionMutator(function() { return project; })();
3043 }
3044
3045 function d3_geo_projectionMutator(projectAt) {
3046   var project,
3047       rotate,
3048       projectRotate,
3049       projectResample = d3_geo_resample(function(x, y) { x = project(x, y); return [x[0] * k + δx, δy - x[1] * k]; }),
3050       k = 150, // scale
3051       x = 480, y = 250, // translate
3052       λ = 0, φ = 0, // center
3053       δλ = 0, δφ = 0, δγ = 0, // rotate
3054       δx, δy, // center
3055       preclip = d3_geo_clipAntimeridian,
3056       postclip = d3_identity,
3057       clipAngle = null,
3058       clipExtent = null;
3059
3060   function projection(point) {
3061     point = projectRotate(point[0] * d3_radians, point[1] * d3_radians);
3062     return [point[0] * k + δx, δy - point[1] * k];
3063   }
3064
3065   function invert(point) {
3066     point = projectRotate.invert((point[0] - δx) / k, (δy - point[1]) / k);
3067     return point && [point[0] * d3_degrees, point[1] * d3_degrees];
3068   }
3069
3070   projection.stream = function(stream) {
3071     return d3_geo_projectionRadiansRotate(rotate, preclip(projectResample(postclip(stream))));
3072   };
3073
3074   projection.clipAngle = function(_) {
3075     if (!arguments.length) return clipAngle;
3076     preclip = _ == null ? (clipAngle = _, d3_geo_clipAntimeridian) : d3_geo_clipCircle((clipAngle = +_) * d3_radians);
3077     return projection;
3078   };
3079
3080   projection.clipExtent = function(_) {
3081     if (!arguments.length) return clipExtent;
3082     clipExtent = _;
3083     postclip = _ == null ? d3_identity : d3_geo_clipView(_[0][0], _[0][1], _[1][0], _[1][1]);
3084     return projection;
3085   };
3086
3087   projection.scale = function(_) {
3088     if (!arguments.length) return k;
3089     k = +_;
3090     return reset();
3091   };
3092
3093   projection.translate = function(_) {
3094     if (!arguments.length) return [x, y];
3095     x = +_[0];
3096     y = +_[1];
3097     return reset();
3098   };
3099
3100   projection.center = function(_) {
3101     if (!arguments.length) return [λ * d3_degrees, φ * d3_degrees];
3102     λ = _[0] % 360 * d3_radians;
3103     φ = _[1] % 360 * d3_radians;
3104     return reset();
3105   };
3106
3107   projection.rotate = function(_) {
3108     if (!arguments.length) return [δλ * d3_degrees, δφ * d3_degrees, δγ * d3_degrees];
3109     δλ = _[0] % 360 * d3_radians;
3110     δφ = _[1] % 360 * d3_radians;
3111     δγ = _.length > 2 ? _[2] % 360 * d3_radians : 0;
3112     return reset();
3113   };
3114
3115   d3.rebind(projection, projectResample, "precision");
3116
3117   function reset() {
3118     projectRotate = d3_geo_compose(rotate = d3_geo_rotation(δλ, δφ, δγ), project);
3119     var center = project(λ, φ);
3120     δx = x - center[0] * k;
3121     δy = y + center[1] * k;
3122     return projection;
3123   }
3124
3125   return function() {
3126     project = projectAt.apply(this, arguments);
3127     projection.invert = project.invert && invert;
3128     return reset();
3129   };
3130 }
3131
3132 function d3_geo_projectionRadiansRotate(rotate, stream) {
3133   return {
3134     point: function(x, y) {
3135       y = rotate(x * d3_radians, y * d3_radians), x = y[0];
3136       stream.point(x > π ? x - 2 * π : x < -π ? x + 2 * π : x, y[1]);
3137     },
3138     sphere: function() { stream.sphere(); },
3139     lineStart: function() { stream.lineStart(); },
3140     lineEnd: function() { stream.lineEnd(); },
3141     polygonStart: function() { stream.polygonStart(); },
3142     polygonEnd: function() { stream.polygonEnd(); }
3143   };
3144 }
3145
3146 function d3_geo_mercator(λ, φ) {
3147   return [λ, Math.log(Math.tan(π / 4 + φ / 2))];
3148 }
3149
3150 d3_geo_mercator.invert = function(x, y) {
3151   return [x, 2 * Math.atan(Math.exp(y)) - π / 2];
3152 };
3153
3154 function d3_geo_mercatorProjection(project) {
3155   var m = d3_geo_projection(project),
3156       scale = m.scale,
3157       translate = m.translate,
3158       clipExtent = m.clipExtent,
3159       clipAuto;
3160
3161   m.scale = function() {
3162     var v = scale.apply(m, arguments);
3163     return v === m ? (clipAuto ? m.clipExtent(null) : m) : v;
3164   };
3165
3166   m.translate = function() {
3167     var v = translate.apply(m, arguments);
3168     return v === m ? (clipAuto ? m.clipExtent(null) : m) : v;
3169   };
3170
3171   m.clipExtent = function(_) {
3172     var v = clipExtent.apply(m, arguments);
3173     if (v === m) {
3174       if (clipAuto = _ == null) {
3175         var k = π * scale(), t = translate();
3176         clipExtent([[t[0] - k, t[1] - k], [t[0] + k, t[1] + k]]);
3177       }
3178     } else if (clipAuto) {
3179       v = null;
3180     }
3181     return v;
3182   };
3183
3184   return m.clipExtent(null);
3185 }
3186
3187 (d3.geo.mercator = function() {
3188   return d3_geo_mercatorProjection(d3_geo_mercator);
3189 }).raw = d3_geo_mercator;
3190
3191 function d3_geo_conic(projectAt) {
3192   var φ0 = 0,
3193       φ1 = π / 3,
3194       m = d3_geo_projectionMutator(projectAt),
3195       p = m(φ0, φ1);
3196
3197   p.parallels = function(_) {
3198     if (!arguments.length) return [φ0 / π * 180, φ1 / π * 180];
3199     return m(φ0 = _[0] * π / 180, φ1 = _[1] * π / 180);
3200   };
3201
3202   return p;
3203 }
3204
3205 function d3_geo_conicEqualArea(φ0, φ1) {
3206   var sinφ0 = Math.sin(φ0),
3207       n = (sinφ0 + Math.sin(φ1)) / 2,
3208       C = 1 + sinφ0 * (2 * n - sinφ0),
3209       ρ0 = Math.sqrt(C) / n;
3210
3211   function forward(λ, φ) {
3212     var ρ = Math.sqrt(C - 2 * n * Math.sin(φ)) / n;
3213     return [
3214       ρ * Math.sin(λ *= n),
3215       ρ0 - ρ * Math.cos(λ)
3216     ];
3217   }
3218
3219   forward.invert = function(x, y) {
3220     var ρ0_y = ρ0 - y;
3221     return [
3222       Math.atan2(x, ρ0_y) / n,
3223       Math.asin((C - (x * x + ρ0_y * ρ0_y) * n * n) / (2 * n))
3224     ];
3225   };
3226
3227   return forward;
3228 }
3229
3230 (d3.geo.conicEqualArea = function() {
3231   return d3_geo_conic(d3_geo_conicEqualArea);
3232 }).raw = d3_geo_conicEqualArea;
3233
3234 // A composite projection for the United States, 960×500. The set of standard
3235 // parallels for each region comes from USGS, which is published here:
3236 // http://egsc.usgs.gov/isb/pubs/MapProjections/projections.html#albers
3237 d3.geo.albersUsa = function() {
3238   var lower48 = d3.geo.conicEqualArea()
3239       .rotate([98, 0])
3240       .center([0, 38])
3241       .parallels([29.5, 45.5]);
3242
3243   var alaska = d3.geo.conicEqualArea()
3244       .rotate([160, 0])
3245       .center([0, 60])
3246       .parallels([55, 65]);
3247
3248   var hawaii = d3.geo.conicEqualArea()
3249       .rotate([160, 0])
3250       .center([0, 20])
3251       .parallels([8, 18]);
3252
3253   var puertoRico = d3.geo.conicEqualArea()
3254       .rotate([60, 0])
3255       .center([0, 10])
3256       .parallels([8, 18]);
3257
3258   var alaskaInvert,
3259       hawaiiInvert,
3260       puertoRicoInvert;
3261
3262   function albersUsa(coordinates) {
3263     return projection(coordinates)(coordinates);
3264   }
3265
3266   function projection(point) {
3267     var lon = point[0],
3268         lat = point[1];
3269     return lat > 50 ? alaska
3270         : lon < -140 ? hawaii
3271         : lat < 21 ? puertoRico
3272         : lower48;
3273   }
3274
3275   albersUsa.invert = function(coordinates) {
3276     return alaskaInvert(coordinates) || hawaiiInvert(coordinates) || puertoRicoInvert(coordinates) || lower48.invert(coordinates);
3277   };
3278
3279   albersUsa.scale = function(x) {
3280     if (!arguments.length) return lower48.scale();
3281     lower48.scale(x);
3282     alaska.scale(x * .6);
3283     hawaii.scale(x);
3284     puertoRico.scale(x * 1.5);
3285     return albersUsa.translate(lower48.translate());
3286   };
3287
3288   albersUsa.translate = function(x) {
3289     if (!arguments.length) return lower48.translate();
3290     var dz = lower48.scale(),
3291         dx = x[0],
3292         dy = x[1];
3293     lower48.translate(x);
3294     alaska.translate([dx - .40 * dz, dy + .17 * dz]);
3295     hawaii.translate([dx - .19 * dz, dy + .20 * dz]);
3296     puertoRico.translate([dx + .58 * dz, dy + .43 * dz]);
3297
3298     alaskaInvert = d3_geo_albersUsaInvert(alaska, [[-180, 50], [-130, 72]]);
3299     hawaiiInvert = d3_geo_albersUsaInvert(hawaii, [[-164, 18], [-154, 24]]);
3300     puertoRicoInvert = d3_geo_albersUsaInvert(puertoRico, [[-67.5, 17.5], [-65, 19]]);
3301
3302     return albersUsa;
3303   };
3304
3305   return albersUsa.scale(1000);
3306 };
3307
3308 function d3_geo_albersUsaInvert(projection, extent) {
3309   var a = projection(extent[0]),
3310       b = projection([.5 * (extent[0][0] + extent[1][0]), extent[0][1]]),
3311       c = projection([extent[1][0], extent[0][1]]),
3312       d = projection(extent[1]);
3313
3314   var dya = b[1]- a[1],
3315       dxa = b[0]- a[0],
3316       dyb = c[1]- b[1],
3317       dxb = c[0]- b[0];
3318
3319   var ma = dya / dxa,
3320       mb = dyb / dxb;
3321
3322   // Find center of circle going through points [a, b, c].
3323   var cx = .5 * (ma * mb * (a[1] - c[1]) + mb * (a[0] + b[0]) - ma * (b[0] + c[0])) / (mb - ma),
3324       cy = (.5 * (a[0] + b[0]) - cx) / ma + .5 * (a[1] + b[1]);
3325
3326   // Radial distance² from center.
3327   var dx0 = d[0] - cx,
3328       dy0 = d[1] - cy,
3329       dx1 = a[0] - cx,
3330       dy1 = a[1] - cy,
3331       r0 = dx0 * dx0 + dy0 * dy0,
3332       r1 = dx1 * dx1 + dy1 * dy1;
3333
3334   // Angular extent.
3335   var a0 = Math.atan2(dy0, dx0),
3336       a1 = Math.atan2(dy1, dx1);
3337
3338   return function(coordinates) {
3339     var dx = coordinates[0] - cx,
3340         dy = coordinates[1] - cy,
3341         r = dx * dx + dy * dy,
3342         a = Math.atan2(dy, dx);
3343     if (r0 < r && r < r1 && a0 < a && a < a1) return projection.invert(coordinates);
3344   };
3345 }
3346
3347 d3.geo.area = function(object) {
3348   d3_geo_areaSum = 0;
3349   d3.geo.stream(object, d3_geo_area);
3350   return d3_geo_areaSum;
3351 };
3352
3353 var d3_geo_areaSum,
3354     d3_geo_areaRingU,
3355     d3_geo_areaRingV;
3356
3357 var d3_geo_area = {
3358   sphere: function() { d3_geo_areaSum += 4 * π; },
3359   point: d3_noop,
3360   lineStart: d3_noop,
3361   lineEnd: d3_noop,
3362
3363   // Only count area for polygon rings.
3364   polygonStart: function() {
3365     d3_geo_areaRingU = 1, d3_geo_areaRingV = 0;
3366     d3_geo_area.lineStart = d3_geo_areaRingStart;
3367   },
3368   polygonEnd: function() {
3369     var area = 2 * Math.atan2(d3_geo_areaRingV, d3_geo_areaRingU);
3370     d3_geo_areaSum += area < 0 ? 4 * π + area : area;
3371     d3_geo_area.lineStart = d3_geo_area.lineEnd = d3_geo_area.point = d3_noop;
3372   }
3373 };
3374
3375 function d3_geo_areaRingStart() {
3376   var λ00, φ00, λ0, cosφ0, sinφ0; // start point and two previous points
3377
3378   // For the first point, …
3379   d3_geo_area.point = function(λ, φ) {
3380     d3_geo_area.point = nextPoint;
3381     λ0 = (λ00 = λ) * d3_radians, cosφ0 = Math.cos(φ = (φ00 = φ) * d3_radians / 2 + π / 4), sinφ0 = Math.sin(φ);
3382   };
3383
3384   // For subsequent points, …
3385   function nextPoint(λ, φ) {
3386     λ *= d3_radians;
3387     φ = φ * d3_radians / 2 + π / 4; // half the angular distance from south pole
3388
3389     // Spherical excess E for a spherical triangle with vertices: south pole,
3390     // previous point, current point.  Uses a formula derived from Cagnoli’s
3391     // theorem.  See Todhunter, Spherical Trig. (1871), Sec. 103, Eq. (2).
3392     var dλ = λ - λ0,
3393         cosφ = Math.cos(φ),
3394         sinφ = Math.sin(φ),
3395         k = sinφ0 * sinφ,
3396         u0 = d3_geo_areaRingU,
3397         v0 = d3_geo_areaRingV,
3398         u = cosφ0 * cosφ + k * Math.cos(dλ),
3399         v = k * Math.sin(dλ);
3400     // ∑ arg(z) = arg(∏ z), where z = u + iv.
3401     d3_geo_areaRingU = u0 * u - v0 * v;
3402     d3_geo_areaRingV = v0 * u + u0 * v;
3403
3404     // Advance the previous points.
3405     λ0 = λ, cosφ0 = cosφ, sinφ0 = sinφ;
3406   }
3407
3408   // For the last point, return to the start.
3409   d3_geo_area.lineEnd = function() {
3410     nextPoint(λ00, φ00);
3411   };
3412 }
3413
3414 d3.geo.bounds = d3_geo_bounds(d3_identity);
3415
3416 function d3_geo_bounds(projectStream) {
3417   var x0, y0, x1, y1;
3418
3419   var bound = {
3420     point: boundPoint,
3421     lineStart: d3_noop,
3422     lineEnd: d3_noop,
3423
3424     // While inside a polygon, ignore points in holes.
3425     polygonStart: function() { bound.lineEnd = boundPolygonLineEnd; },
3426     polygonEnd: function() { bound.point = boundPoint; }
3427   };
3428
3429   function boundPoint(x, y) {
3430     if (x < x0) x0 = x;
3431     if (x > x1) x1 = x;
3432     if (y < y0) y0 = y;
3433     if (y > y1) y1 = y;
3434   }
3435
3436   function boundPolygonLineEnd() {
3437     bound.point = bound.lineEnd = d3_noop;
3438   }
3439
3440   return function(feature) {
3441     y1 = x1 = -(x0 = y0 = Infinity);
3442     d3.geo.stream(feature, projectStream(bound));
3443     return [[x0, y0], [x1, y1]];
3444   };
3445 }
3446
3447 d3.geo.centroid = function(object) {
3448   d3_geo_centroidDimension = d3_geo_centroidW = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3449   d3.geo.stream(object, d3_geo_centroid);
3450   var m;
3451   if (d3_geo_centroidW &&
3452       Math.abs(m = Math.sqrt(d3_geo_centroidX * d3_geo_centroidX + d3_geo_centroidY * d3_geo_centroidY + d3_geo_centroidZ * d3_geo_centroidZ)) > ε) {
3453     return [
3454       Math.atan2(d3_geo_centroidY, d3_geo_centroidX) * d3_degrees,
3455       Math.asin(Math.max(-1, Math.min(1, d3_geo_centroidZ / m))) * d3_degrees
3456     ];
3457   }
3458 };
3459
3460 var d3_geo_centroidDimension,
3461     d3_geo_centroidW,
3462     d3_geo_centroidX,
3463     d3_geo_centroidY,
3464     d3_geo_centroidZ;
3465
3466 var d3_geo_centroid = {
3467   sphere: function() {
3468     if (d3_geo_centroidDimension < 2) {
3469       d3_geo_centroidDimension = 2;
3470       d3_geo_centroidW = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3471     }
3472   },
3473   point: d3_geo_centroidPoint,
3474   lineStart: d3_geo_centroidLineStart,
3475   lineEnd: d3_geo_centroidLineEnd,
3476   polygonStart: function() {
3477     if (d3_geo_centroidDimension < 2) {
3478       d3_geo_centroidDimension = 2;
3479       d3_geo_centroidW = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3480     }
3481     d3_geo_centroid.lineStart = d3_geo_centroidRingStart;
3482   },
3483   polygonEnd: function() {
3484     d3_geo_centroid.lineStart = d3_geo_centroidLineStart;
3485   }
3486 };
3487
3488 // Arithmetic mean of Cartesian vectors.
3489 function d3_geo_centroidPoint(λ, φ) {
3490   if (d3_geo_centroidDimension) return;
3491   ++d3_geo_centroidW;
3492   λ *= d3_radians;
3493   var cosφ = Math.cos(φ *= d3_radians);
3494   d3_geo_centroidX += (cosφ * Math.cos(λ) - d3_geo_centroidX) / d3_geo_centroidW;
3495   d3_geo_centroidY += (cosφ * Math.sin(λ) - d3_geo_centroidY) / d3_geo_centroidW;
3496   d3_geo_centroidZ += (Math.sin(φ) - d3_geo_centroidZ) / d3_geo_centroidW;
3497 }
3498
3499 function d3_geo_centroidRingStart() {
3500   var λ00, φ00; // first point
3501
3502   d3_geo_centroidDimension = 1;
3503   d3_geo_centroidLineStart();
3504   d3_geo_centroidDimension = 2;
3505
3506   var linePoint = d3_geo_centroid.point;
3507   d3_geo_centroid.point = function(λ, φ) {
3508     linePoint(λ00 = λ, φ00 = φ);
3509   };
3510   d3_geo_centroid.lineEnd = function() {
3511     d3_geo_centroid.point(λ00, φ00);
3512     d3_geo_centroidLineEnd();
3513     d3_geo_centroid.lineEnd = d3_geo_centroidLineEnd;
3514   };
3515 }
3516
3517 function d3_geo_centroidLineStart() {
3518   var x0, y0, z0; // previous point
3519
3520   if (d3_geo_centroidDimension > 1) return;
3521   if (d3_geo_centroidDimension < 1) {
3522     d3_geo_centroidDimension = 1;
3523     d3_geo_centroidW = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3524   }
3525
3526   d3_geo_centroid.point = function(λ, φ) {
3527     λ *= d3_radians;
3528     var cosφ = Math.cos(φ *= d3_radians);
3529     x0 = cosφ * Math.cos(λ);
3530     y0 = cosφ * Math.sin(λ);
3531     z0 = Math.sin(φ);
3532     d3_geo_centroid.point = nextPoint;
3533   };
3534
3535   function nextPoint(λ, φ) {
3536     λ *= d3_radians;
3537     var cosφ = Math.cos(φ *= d3_radians),
3538         x = cosφ * Math.cos(λ),
3539         y = cosφ * Math.sin(λ),
3540         z = Math.sin(φ),
3541         w = Math.atan2(
3542           Math.sqrt((w = y0 * z - z0 * y) * w + (w = z0 * x - x0 * z) * w + (w = x0 * y - y0 * x) * w),
3543           x0 * x + y0 * y + z0 * z);
3544     d3_geo_centroidW += w;
3545     d3_geo_centroidX += w * (x0 + (x0 = x));
3546     d3_geo_centroidY += w * (y0 + (y0 = y));
3547     d3_geo_centroidZ += w * (z0 + (z0 = z));
3548   }
3549 }
3550
3551 function d3_geo_centroidLineEnd() {
3552   d3_geo_centroid.point = d3_geo_centroidPoint;
3553 }
3554
3555 // TODO Unify this code with d3.geom.polygon area?
3556
3557 var d3_geo_pathAreaSum, d3_geo_pathAreaPolygon, d3_geo_pathArea = {
3558   point: d3_noop,
3559   lineStart: d3_noop,
3560   lineEnd: d3_noop,
3561
3562   // Only count area for polygon rings.
3563   polygonStart: function() {
3564     d3_geo_pathAreaPolygon = 0;
3565     d3_geo_pathArea.lineStart = d3_geo_pathAreaRingStart;
3566   },
3567   polygonEnd: function() {
3568     d3_geo_pathArea.lineStart = d3_geo_pathArea.lineEnd = d3_geo_pathArea.point = d3_noop;
3569     d3_geo_pathAreaSum += Math.abs(d3_geo_pathAreaPolygon / 2);
3570   }
3571 };
3572
3573 function d3_geo_pathAreaRingStart() {
3574   var x00, y00, x0, y0;
3575
3576   // For the first point, …
3577   d3_geo_pathArea.point = function(x, y) {
3578     d3_geo_pathArea.point = nextPoint;
3579     x00 = x0 = x, y00 = y0 = y;
3580   };
3581
3582   // For subsequent points, …
3583   function nextPoint(x, y) {
3584     d3_geo_pathAreaPolygon += y0 * x - x0 * y;
3585     x0 = x, y0 = y;
3586   }
3587
3588   // For the last point, return to the start.
3589   d3_geo_pathArea.lineEnd = function() {
3590     nextPoint(x00, y00);
3591   };
3592 }
3593 function d3_geo_pathBuffer() {
3594   var pointCircle = d3_geo_pathCircle(4.5),
3595       buffer = [];
3596
3597   var stream = {
3598     point: point,
3599
3600     // While inside a line, override point to moveTo then lineTo.
3601     lineStart: function() { stream.point = pointLineStart; },
3602     lineEnd: lineEnd,
3603
3604     // While inside a polygon, override lineEnd to closePath.
3605     polygonStart: function() { stream.lineEnd = lineEndPolygon; },
3606     polygonEnd: function() { stream.lineEnd = lineEnd; stream.point = point; },
3607
3608     pointRadius: function(_) {
3609       pointCircle = d3_geo_pathCircle(_);
3610       return stream;
3611     },
3612
3613     result: function() {
3614       if (buffer.length) {
3615         var result = buffer.join("");
3616         buffer = [];
3617         return result;
3618       }
3619     }
3620   };
3621
3622   function point(x, y) {
3623     buffer.push("M", x, ",", y, pointCircle);
3624   }
3625
3626   function pointLineStart(x, y) {
3627     buffer.push("M", x, ",", y);
3628     stream.point = pointLine;
3629   }
3630
3631   function pointLine(x, y) {
3632     buffer.push("L", x, ",", y);
3633   }
3634
3635   function lineEnd() {
3636     stream.point = point;
3637   }
3638
3639   function lineEndPolygon() {
3640     buffer.push("Z");
3641   }
3642
3643   return stream;
3644 }
3645
3646 // TODO Unify this code with d3.geom.polygon centroid?
3647 // TODO Enforce positive area for exterior, negative area for interior?
3648
3649 var d3_geo_pathCentroid = {
3650   point: d3_geo_pathCentroidPoint,
3651
3652   // For lines, weight by length.
3653   lineStart: d3_geo_pathCentroidLineStart,
3654   lineEnd: d3_geo_pathCentroidLineEnd,
3655
3656   // For polygons, weight by area.
3657   polygonStart: function() {
3658     d3_geo_pathCentroid.lineStart = d3_geo_pathCentroidRingStart;
3659   },
3660   polygonEnd: function() {
3661     d3_geo_pathCentroid.point = d3_geo_pathCentroidPoint;
3662     d3_geo_pathCentroid.lineStart = d3_geo_pathCentroidLineStart;
3663     d3_geo_pathCentroid.lineEnd = d3_geo_pathCentroidLineEnd;
3664   }
3665 };
3666
3667 function d3_geo_pathCentroidPoint(x, y) {
3668   if (d3_geo_centroidDimension) return;
3669   d3_geo_centroidX += x;
3670   d3_geo_centroidY += y;
3671   ++d3_geo_centroidZ;
3672 }
3673
3674 function d3_geo_pathCentroidLineStart() {
3675   var x0, y0;
3676
3677   if (d3_geo_centroidDimension !== 1) {
3678     if (d3_geo_centroidDimension < 1) {
3679       d3_geo_centroidDimension = 1;
3680       d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3681     } else return;
3682   }
3683
3684   d3_geo_pathCentroid.point = function(x, y) {
3685     d3_geo_pathCentroid.point = nextPoint;
3686     x0 = x, y0 = y;
3687   };
3688
3689   function nextPoint(x, y) {
3690     var dx = x - x0, dy = y - y0, z = Math.sqrt(dx * dx + dy * dy);
3691     d3_geo_centroidX += z * (x0 + x) / 2;
3692     d3_geo_centroidY += z * (y0 + y) / 2;
3693     d3_geo_centroidZ += z;
3694     x0 = x, y0 = y;
3695   }
3696 }
3697
3698 function d3_geo_pathCentroidLineEnd() {
3699   d3_geo_pathCentroid.point = d3_geo_pathCentroidPoint;
3700 }
3701
3702 function d3_geo_pathCentroidRingStart() {
3703   var x00, y00, x0, y0;
3704
3705   if (d3_geo_centroidDimension < 2) {
3706     d3_geo_centroidDimension = 2;
3707     d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3708   }
3709
3710   // For the first point, …
3711   d3_geo_pathCentroid.point = function(x, y) {
3712     d3_geo_pathCentroid.point = nextPoint;
3713     x00 = x0 = x, y00 = y0 = y;
3714   };
3715
3716   // For subsequent points, …
3717   function nextPoint(x, y) {
3718     var z = y0 * x - x0 * y;
3719     d3_geo_centroidX += z * (x0 + x);
3720     d3_geo_centroidY += z * (y0 + y);
3721     d3_geo_centroidZ += z * 3;
3722     x0 = x, y0 = y;
3723   }
3724
3725   // For the last point, return to the start.
3726   d3_geo_pathCentroid.lineEnd = function() {
3727     nextPoint(x00, y00);
3728   };
3729 }
3730
3731 function d3_geo_pathContext(context) {
3732   var pointRadius = 4.5;
3733
3734   var stream = {
3735     point: point,
3736
3737     // While inside a line, override point to moveTo then lineTo.
3738     lineStart: function() { stream.point = pointLineStart; },
3739     lineEnd: lineEnd,
3740
3741     // While inside a polygon, override lineEnd to closePath.
3742     polygonStart: function() { stream.lineEnd = lineEndPolygon; },
3743     polygonEnd: function() { stream.lineEnd = lineEnd; stream.point = point; },
3744
3745     pointRadius: function(_) {
3746       pointRadius = _;
3747       return stream;
3748     },
3749
3750     result: d3_noop
3751   };
3752
3753   function point(x, y) {
3754     context.moveTo(x, y);
3755     context.arc(x, y, pointRadius, 0, 2 * π);
3756   }
3757
3758   function pointLineStart(x, y) {
3759     context.moveTo(x, y);
3760     stream.point = pointLine;
3761   }
3762
3763   function pointLine(x, y) {
3764     context.lineTo(x, y);
3765   }
3766
3767   function lineEnd() {
3768     stream.point = point;
3769   }
3770
3771   function lineEndPolygon() {
3772     context.closePath();
3773   }
3774
3775   return stream;
3776 }
3777
3778 d3.geo.path = function() {
3779   var pointRadius = 4.5,
3780       projection,
3781       context,
3782       projectStream,
3783       contextStream;
3784
3785   function path(object) {
3786     if (object) d3.geo.stream(object, projectStream(
3787         contextStream.pointRadius(typeof pointRadius === "function"
3788             ? +pointRadius.apply(this, arguments)
3789             : pointRadius)));
3790     return contextStream.result();
3791   }
3792
3793   path.area = function(object) {
3794     d3_geo_pathAreaSum = 0;
3795     d3.geo.stream(object, projectStream(d3_geo_pathArea));
3796     return d3_geo_pathAreaSum;
3797   };
3798
3799   path.centroid = function(object) {
3800     d3_geo_centroidDimension = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3801     d3.geo.stream(object, projectStream(d3_geo_pathCentroid));
3802     return d3_geo_centroidZ ? [d3_geo_centroidX / d3_geo_centroidZ, d3_geo_centroidY / d3_geo_centroidZ] : undefined;
3803   };
3804
3805   path.bounds = function(object) {
3806     return d3_geo_bounds(projectStream)(object);
3807   };
3808
3809   path.projection = function(_) {
3810     if (!arguments.length) return projection;
3811     projectStream = (projection = _) ? _.stream || d3_geo_pathProjectStream(_) : d3_identity;
3812     return path;
3813   };
3814
3815   path.context = function(_) {
3816     if (!arguments.length) return context;
3817     contextStream = (context = _) == null ? new d3_geo_pathBuffer : new d3_geo_pathContext(_);
3818     return path;
3819   };
3820
3821   path.pointRadius = function(_) {
3822     if (!arguments.length) return pointRadius;
3823     pointRadius = typeof _ === "function" ? _ : +_;
3824     return path;
3825   };
3826
3827   return path.projection(d3.geo.albersUsa()).context(null);
3828 };
3829
3830 function d3_geo_pathCircle(radius) {
3831   return "m0," + radius
3832       + "a" + radius + "," + radius + " 0 1,1 0," + (-2 * radius)
3833       + "a" + radius + "," + radius + " 0 1,1 0," + (+2 * radius)
3834       + "z";
3835 }
3836
3837 function d3_geo_pathProjectStream(project) {
3838   var resample = d3_geo_resample(function(λ, φ) { return project([λ * d3_degrees, φ * d3_degrees]); });
3839   return function(stream) {
3840     stream = resample(stream);
3841     return {
3842       point: function(λ, φ) { stream.point(λ * d3_radians, φ * d3_radians); },
3843       sphere: function() { stream.sphere(); },
3844       lineStart: function() { stream.lineStart(); },
3845       lineEnd: function() { stream.lineEnd(); },
3846       polygonStart: function() { stream.polygonStart(); },
3847       polygonEnd: function() { stream.polygonEnd(); }
3848     };
3849   };
3850 }
3851 d3.geom = {};
3852
3853 d3.geom.polygon = function(coordinates) {
3854
3855   coordinates.area = function() {
3856     var i = 0,
3857         n = coordinates.length,
3858         area = coordinates[n - 1][1] * coordinates[0][0] - coordinates[n - 1][0] * coordinates[0][1];
3859     while (++i < n) {
3860       area += coordinates[i - 1][1] * coordinates[i][0] - coordinates[i - 1][0] * coordinates[i][1];
3861     }
3862     return area * .5;
3863   };
3864
3865   coordinates.centroid = function(k) {
3866     var i = -1,
3867         n = coordinates.length,
3868         x = 0,
3869         y = 0,
3870         a,
3871         b = coordinates[n - 1],
3872         c;
3873     if (!arguments.length) k = -1 / (6 * coordinates.area());
3874     while (++i < n) {
3875       a = b;
3876       b = coordinates[i];
3877       c = a[0] * b[1] - b[0] * a[1];
3878       x += (a[0] + b[0]) * c;
3879       y += (a[1] + b[1]) * c;
3880     }
3881     return [x * k, y * k];
3882   };
3883
3884   // The Sutherland-Hodgman clipping algorithm.
3885   // Note: requires the clip polygon to be counterclockwise and convex.
3886   coordinates.clip = function(subject) {
3887     var input,
3888         i = -1,
3889         n = coordinates.length,
3890         j,
3891         m,
3892         a = coordinates[n - 1],
3893         b,
3894         c,
3895         d;
3896     while (++i < n) {
3897       input = subject.slice();
3898       subject.length = 0;
3899       b = coordinates[i];
3900       c = input[(m = input.length) - 1];
3901       j = -1;
3902       while (++j < m) {
3903         d = input[j];
3904         if (d3_geom_polygonInside(d, a, b)) {
3905           if (!d3_geom_polygonInside(c, a, b)) {
3906             subject.push(d3_geom_polygonIntersect(c, d, a, b));
3907           }
3908           subject.push(d);
3909         } else if (d3_geom_polygonInside(c, a, b)) {
3910           subject.push(d3_geom_polygonIntersect(c, d, a, b));
3911         }
3912         c = d;
3913       }
3914       a = b;
3915     }
3916     return subject;
3917   };
3918
3919   return coordinates;
3920 };
3921
3922 function d3_geom_polygonInside(p, a, b) {
3923   return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
3924 }
3925
3926 // Intersect two infinite lines cd and ab.
3927 function d3_geom_polygonIntersect(c, d, a, b) {
3928   var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3,
3929       y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3,
3930       ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
3931   return [x1 + ua * x21, y1 + ua * y21];
3932 }
3933
3934 var d3_ease_default = function() { return d3_identity; };
3935
3936 var d3_ease = d3.map({
3937   linear: d3_ease_default,
3938   poly: d3_ease_poly,
3939   quad: function() { return d3_ease_quad; },
3940   cubic: function() { return d3_ease_cubic; },
3941   sin: function() { return d3_ease_sin; },
3942   exp: function() { return d3_ease_exp; },
3943   circle: function() { return d3_ease_circle; },
3944   elastic: d3_ease_elastic,
3945   back: d3_ease_back,
3946   bounce: function() { return d3_ease_bounce; }
3947 });
3948
3949 var d3_ease_mode = d3.map({
3950   "in": d3_identity,
3951   "out": d3_ease_reverse,
3952   "in-out": d3_ease_reflect,
3953   "out-in": function(f) { return d3_ease_reflect(d3_ease_reverse(f)); }
3954 });
3955
3956 d3.ease = function(name) {
3957   var i = name.indexOf("-"),
3958       t = i >= 0 ? name.substring(0, i) : name,
3959       m = i >= 0 ? name.substring(i + 1) : "in";
3960   t = d3_ease.get(t) || d3_ease_default;
3961   m = d3_ease_mode.get(m) || d3_identity;
3962   return d3_ease_clamp(m(t.apply(null, Array.prototype.slice.call(arguments, 1))));
3963 };
3964
3965 function d3_ease_clamp(f) {
3966   return function(t) {
3967     return t <= 0 ? 0 : t >= 1 ? 1 : f(t);
3968   };
3969 }
3970
3971 function d3_ease_reverse(f) {
3972   return function(t) {
3973     return 1 - f(1 - t);
3974   };
3975 }
3976
3977 function d3_ease_reflect(f) {
3978   return function(t) {
3979     return .5 * (t < .5 ? f(2 * t) : (2 - f(2 - 2 * t)));
3980   };
3981 }
3982
3983 function d3_ease_quad(t) {
3984   return t * t;
3985 }
3986
3987 function d3_ease_cubic(t) {
3988   return t * t * t;
3989 }
3990
3991 // Optimized clamp(reflect(poly(3))).
3992 function d3_ease_cubicInOut(t) {
3993   if (t <= 0) return 0;
3994   if (t >= 1) return 1;
3995   var t2 = t * t, t3 = t2 * t;
3996   return 4 * (t < .5 ? t3 : 3 * (t - t2) + t3 - .75);
3997 }
3998
3999 function d3_ease_poly(e) {
4000   return function(t) {
4001     return Math.pow(t, e);
4002   };
4003 }
4004
4005 function d3_ease_sin(t) {
4006   return 1 - Math.cos(t * π / 2);
4007 }
4008
4009 function d3_ease_exp(t) {
4010   return Math.pow(2, 10 * (t - 1));
4011 }
4012
4013 function d3_ease_circle(t) {
4014   return 1 - Math.sqrt(1 - t * t);
4015 }
4016
4017 function d3_ease_elastic(a, p) {
4018   var s;
4019   if (arguments.length < 2) p = 0.45;
4020   if (arguments.length) s = p / (2 * π) * Math.asin(1 / a);
4021   else a = 1, s = p / 4;
4022   return function(t) {
4023     return 1 + a * Math.pow(2, 10 * -t) * Math.sin((t - s) * 2 * π / p);
4024   };
4025 }
4026
4027 function d3_ease_back(s) {
4028   if (!s) s = 1.70158;
4029   return function(t) {
4030     return t * t * ((s + 1) * t - s);
4031   };
4032 }
4033
4034 function d3_ease_bounce(t) {
4035   return t < 1 / 2.75 ? 7.5625 * t * t
4036       : t < 2 / 2.75 ? 7.5625 * (t -= 1.5 / 2.75) * t + .75
4037       : t < 2.5 / 2.75 ? 7.5625 * (t -= 2.25 / 2.75) * t + .9375
4038       : 7.5625 * (t -= 2.625 / 2.75) * t + .984375;
4039 }
4040
4041 function d3_transition(groups, id) {
4042   d3_arraySubclass(groups, d3_transitionPrototype);
4043
4044   groups.id = id; // Note: read-only!
4045
4046   return groups;
4047 }
4048
4049 var d3_transitionPrototype = [],
4050     d3_transitionId = 0,
4051     d3_transitionInheritId,
4052     d3_transitionInherit = {ease: d3_ease_cubicInOut, delay: 0, duration: 250};
4053
4054 d3_transitionPrototype.call = d3_selectionPrototype.call;
4055 d3_transitionPrototype.empty = d3_selectionPrototype.empty;
4056 d3_transitionPrototype.node = d3_selectionPrototype.node;
4057
4058 d3.transition = function(selection) {
4059   return arguments.length
4060       ? (d3_transitionInheritId ? selection.transition() : selection)
4061       : d3_selectionRoot.transition();
4062 };
4063
4064 d3.transition.prototype = d3_transitionPrototype;
4065
4066
4067 d3_transitionPrototype.select = function(selector) {
4068   var id = this.id,
4069       subgroups = [],
4070       subgroup,
4071       subnode,
4072       node;
4073
4074   if (typeof selector !== "function") selector = d3_selection_selector(selector);
4075
4076   for (var j = -1, m = this.length; ++j < m;) {
4077     subgroups.push(subgroup = []);
4078     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
4079       if ((node = group[i]) && (subnode = selector.call(node, node.__data__, i))) {
4080         if ("__data__" in node) subnode.__data__ = node.__data__;
4081         d3_transitionNode(subnode, i, id, node.__transition__[id]);
4082         subgroup.push(subnode);
4083       } else {
4084         subgroup.push(null);
4085       }
4086     }
4087   }
4088
4089   return d3_transition(subgroups, id);
4090 };
4091
4092 d3_transitionPrototype.selectAll = function(selector) {
4093   var id = this.id,
4094       subgroups = [],
4095       subgroup,
4096       subnodes,
4097       node,
4098       subnode,
4099       transition;
4100
4101   if (typeof selector !== "function") selector = d3_selection_selectorAll(selector);
4102
4103   for (var j = -1, m = this.length; ++j < m;) {
4104     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
4105       if (node = group[i]) {
4106         transition = node.__transition__[id];
4107         subnodes = selector.call(node, node.__data__, i);
4108         subgroups.push(subgroup = []);
4109         for (var k = -1, o = subnodes.length; ++k < o;) {
4110           d3_transitionNode(subnode = subnodes[k], k, id, transition);
4111           subgroup.push(subnode);
4112         }
4113       }
4114     }
4115   }
4116
4117   return d3_transition(subgroups, id);
4118 };
4119
4120 d3_transitionPrototype.filter = function(filter) {
4121   var subgroups = [],
4122       subgroup,
4123       group,
4124       node;
4125
4126   if (typeof filter !== "function") filter = d3_selection_filter(filter);
4127
4128   for (var j = 0, m = this.length; j < m; j++) {
4129     subgroups.push(subgroup = []);
4130     for (var group = this[j], i = 0, n = group.length; i < n; i++) {
4131       if ((node = group[i]) && filter.call(node, node.__data__, i)) {
4132         subgroup.push(node);
4133       }
4134     }
4135   }
4136
4137   return d3_transition(subgroups, this.id, this.time).ease(this.ease());
4138 };
4139 function d3_Color() {}
4140
4141 d3_Color.prototype.toString = function() {
4142   return this.rgb() + "";
4143 };
4144
4145 d3.hsl = function(h, s, l) {
4146   return arguments.length === 1
4147       ? (h instanceof d3_Hsl ? d3_hsl(h.h, h.s, h.l)
4148       : d3_rgb_parse("" + h, d3_rgb_hsl, d3_hsl))
4149       : d3_hsl(+h, +s, +l);
4150 };
4151
4152 function d3_hsl(h, s, l) {
4153   return new d3_Hsl(h, s, l);
4154 }
4155
4156 function d3_Hsl(h, s, l) {
4157   this.h = h;
4158   this.s = s;
4159   this.l = l;
4160 }
4161
4162 var d3_hslPrototype = d3_Hsl.prototype = new d3_Color;
4163
4164 d3_hslPrototype.brighter = function(k) {
4165   k = Math.pow(0.7, arguments.length ? k : 1);
4166   return d3_hsl(this.h, this.s, this.l / k);
4167 };
4168
4169 d3_hslPrototype.darker = function(k) {
4170   k = Math.pow(0.7, arguments.length ? k : 1);
4171   return d3_hsl(this.h, this.s, k * this.l);
4172 };
4173
4174 d3_hslPrototype.rgb = function() {
4175   return d3_hsl_rgb(this.h, this.s, this.l);
4176 };
4177
4178 function d3_hsl_rgb(h, s, l) {
4179   var m1,
4180       m2;
4181
4182   /* Some simple corrections for h, s and l. */
4183   h = h % 360; if (h < 0) h += 360;
4184   s = s < 0 ? 0 : s > 1 ? 1 : s;
4185   l = l < 0 ? 0 : l > 1 ? 1 : l;
4186
4187   /* From FvD 13.37, CSS Color Module Level 3 */
4188   m2 = l <= .5 ? l * (1 + s) : l + s - l * s;
4189   m1 = 2 * l - m2;
4190
4191   function v(h) {
4192     if (h > 360) h -= 360;
4193     else if (h < 0) h += 360;
4194     if (h < 60) return m1 + (m2 - m1) * h / 60;
4195     if (h < 180) return m2;
4196     if (h < 240) return m1 + (m2 - m1) * (240 - h) / 60;
4197     return m1;
4198   }
4199
4200   function vv(h) {
4201     return Math.round(v(h) * 255);
4202   }
4203
4204   return d3_rgb(vv(h + 120), vv(h), vv(h - 120));
4205 }
4206
4207 d3.hcl = function(h, c, l) {
4208   return arguments.length === 1
4209       ? (h instanceof d3_Hcl ? d3_hcl(h.h, h.c, h.l)
4210       : (h instanceof d3_Lab ? d3_lab_hcl(h.l, h.a, h.b)
4211       : d3_lab_hcl((h = d3_rgb_lab((h = d3.rgb(h)).r, h.g, h.b)).l, h.a, h.b)))
4212       : d3_hcl(+h, +c, +l);
4213 };
4214
4215 function d3_hcl(h, c, l) {
4216   return new d3_Hcl(h, c, l);
4217 }
4218
4219 function d3_Hcl(h, c, l) {
4220   this.h = h;
4221   this.c = c;
4222   this.l = l;
4223 }
4224
4225 var d3_hclPrototype = d3_Hcl.prototype = new d3_Color;
4226
4227 d3_hclPrototype.brighter = function(k) {
4228   return d3_hcl(this.h, this.c, Math.min(100, this.l + d3_lab_K * (arguments.length ? k : 1)));
4229 };
4230
4231 d3_hclPrototype.darker = function(k) {
4232   return d3_hcl(this.h, this.c, Math.max(0, this.l - d3_lab_K * (arguments.length ? k : 1)));
4233 };
4234
4235 d3_hclPrototype.rgb = function() {
4236   return d3_hcl_lab(this.h, this.c, this.l).rgb();
4237 };
4238
4239 function d3_hcl_lab(h, c, l) {
4240   return d3_lab(l, Math.cos(h *= d3_radians) * c, Math.sin(h) * c);
4241 }
4242
4243 d3.lab = function(l, a, b) {
4244   return arguments.length === 1
4245       ? (l instanceof d3_Lab ? d3_lab(l.l, l.a, l.b)
4246       : (l instanceof d3_Hcl ? d3_hcl_lab(l.l, l.c, l.h)
4247       : d3_rgb_lab((l = d3.rgb(l)).r, l.g, l.b)))
4248       : d3_lab(+l, +a, +b);
4249 };
4250
4251 function d3_lab(l, a, b) {
4252   return new d3_Lab(l, a, b);
4253 }
4254
4255 function d3_Lab(l, a, b) {
4256   this.l = l;
4257   this.a = a;
4258   this.b = b;
4259 }
4260
4261 // Corresponds roughly to RGB brighter/darker
4262 var d3_lab_K = 18;
4263
4264 // D65 standard referent
4265 var d3_lab_X = 0.950470,
4266     d3_lab_Y = 1,
4267     d3_lab_Z = 1.088830;
4268
4269 var d3_labPrototype = d3_Lab.prototype = new d3_Color;
4270
4271 d3_labPrototype.brighter = function(k) {
4272   return d3_lab(Math.min(100, this.l + d3_lab_K * (arguments.length ? k : 1)), this.a, this.b);
4273 };
4274
4275 d3_labPrototype.darker = function(k) {
4276   return d3_lab(Math.max(0, this.l - d3_lab_K * (arguments.length ? k : 1)), this.a, this.b);
4277 };
4278
4279 d3_labPrototype.rgb = function() {
4280   return d3_lab_rgb(this.l, this.a, this.b);
4281 };
4282
4283 function d3_lab_rgb(l, a, b) {
4284   var y = (l + 16) / 116,
4285       x = y + a / 500,
4286       z = y - b / 200;
4287   x = d3_lab_xyz(x) * d3_lab_X;
4288   y = d3_lab_xyz(y) * d3_lab_Y;
4289   z = d3_lab_xyz(z) * d3_lab_Z;
4290   return d3_rgb(
4291     d3_xyz_rgb( 3.2404542 * x - 1.5371385 * y - 0.4985314 * z),
4292     d3_xyz_rgb(-0.9692660 * x + 1.8760108 * y + 0.0415560 * z),
4293     d3_xyz_rgb( 0.0556434 * x - 0.2040259 * y + 1.0572252 * z)
4294   );
4295 }
4296
4297 function d3_lab_hcl(l, a, b) {
4298   return d3_hcl(Math.atan2(b, a) * d3_degrees, Math.sqrt(a * a + b * b), l);
4299 }
4300
4301 function d3_lab_xyz(x) {
4302   return x > 0.206893034 ? x * x * x : (x - 4 / 29) / 7.787037;
4303 }
4304 function d3_xyz_lab(x) {
4305   return x > 0.008856 ? Math.pow(x, 1 / 3) : 7.787037 * x + 4 / 29;
4306 }
4307
4308 function d3_xyz_rgb(r) {
4309   return Math.round(255 * (r <= 0.00304 ? 12.92 * r : 1.055 * Math.pow(r, 1 / 2.4) - 0.055));
4310 }
4311
4312 d3.rgb = function(r, g, b) {
4313   return arguments.length === 1
4314       ? (r instanceof d3_Rgb ? d3_rgb(r.r, r.g, r.b)
4315       : d3_rgb_parse("" + r, d3_rgb, d3_hsl_rgb))
4316       : d3_rgb(~~r, ~~g, ~~b);
4317 };
4318
4319 function d3_rgb(r, g, b) {
4320   return new d3_Rgb(r, g, b);
4321 }
4322
4323 function d3_Rgb(r, g, b) {
4324   this.r = r;
4325   this.g = g;
4326   this.b = b;
4327 }
4328
4329 var d3_rgbPrototype = d3_Rgb.prototype = new d3_Color;
4330
4331 d3_rgbPrototype.brighter = function(k) {
4332   k = Math.pow(0.7, arguments.length ? k : 1);
4333   var r = this.r,
4334       g = this.g,
4335       b = this.b,
4336       i = 30;
4337   if (!r && !g && !b) return d3_rgb(i, i, i);
4338   if (r && r < i) r = i;
4339   if (g && g < i) g = i;
4340   if (b && b < i) b = i;
4341   return d3_rgb(
4342       Math.min(255, Math.floor(r / k)),
4343       Math.min(255, Math.floor(g / k)),
4344       Math.min(255, Math.floor(b / k)));
4345 };
4346
4347 d3_rgbPrototype.darker = function(k) {
4348   k = Math.pow(0.7, arguments.length ? k : 1);
4349   return d3_rgb(
4350       Math.floor(k * this.r),
4351       Math.floor(k * this.g),
4352       Math.floor(k * this.b));
4353 };
4354
4355 d3_rgbPrototype.hsl = function() {
4356   return d3_rgb_hsl(this.r, this.g, this.b);
4357 };
4358
4359 d3_rgbPrototype.toString = function() {
4360   return "#" + d3_rgb_hex(this.r) + d3_rgb_hex(this.g) + d3_rgb_hex(this.b);
4361 };
4362
4363 function d3_rgb_hex(v) {
4364   return v < 0x10
4365       ? "0" + Math.max(0, v).toString(16)
4366       : Math.min(255, v).toString(16);
4367 }
4368
4369 function d3_rgb_parse(format, rgb, hsl) {
4370   var r = 0, // red channel; int in [0, 255]
4371       g = 0, // green channel; int in [0, 255]
4372       b = 0, // blue channel; int in [0, 255]
4373       m1, // CSS color specification match
4374       m2, // CSS color specification type (e.g., rgb)
4375       name;
4376
4377   /* Handle hsl, rgb. */
4378   m1 = /([a-z]+)\((.*)\)/i.exec(format);
4379   if (m1) {
4380     m2 = m1[2].split(",");
4381     switch (m1[1]) {
4382       case "hsl": {
4383         return hsl(
4384           parseFloat(m2[0]), // degrees
4385           parseFloat(m2[1]) / 100, // percentage
4386           parseFloat(m2[2]) / 100 // percentage
4387         );
4388       }
4389       case "rgb": {
4390         return rgb(
4391           d3_rgb_parseNumber(m2[0]),
4392           d3_rgb_parseNumber(m2[1]),
4393           d3_rgb_parseNumber(m2[2])
4394         );
4395       }
4396     }
4397   }
4398
4399   /* Named colors. */
4400   if (name = d3_rgb_names.get(format)) return rgb(name.r, name.g, name.b);
4401
4402   /* Hexadecimal colors: #rgb and #rrggbb. */
4403   if (format != null && format.charAt(0) === "#") {
4404     if (format.length === 4) {
4405       r = format.charAt(1); r += r;
4406       g = format.charAt(2); g += g;
4407       b = format.charAt(3); b += b;
4408     } else if (format.length === 7) {
4409       r = format.substring(1, 3);
4410       g = format.substring(3, 5);
4411       b = format.substring(5, 7);
4412     }
4413     r = parseInt(r, 16);
4414     g = parseInt(g, 16);
4415     b = parseInt(b, 16);
4416   }
4417
4418   return rgb(r, g, b);
4419 }
4420
4421 function d3_rgb_hsl(r, g, b) {
4422   var min = Math.min(r /= 255, g /= 255, b /= 255),
4423       max = Math.max(r, g, b),
4424       d = max - min,
4425       h,
4426       s,
4427       l = (max + min) / 2;
4428   if (d) {
4429     s = l < .5 ? d / (max + min) : d / (2 - max - min);
4430     if (r == max) h = (g - b) / d + (g < b ? 6 : 0);
4431     else if (g == max) h = (b - r) / d + 2;
4432     else h = (r - g) / d + 4;
4433     h *= 60;
4434   } else {
4435     s = h = 0;
4436   }
4437   return d3_hsl(h, s, l);
4438 }
4439
4440 function d3_rgb_lab(r, g, b) {
4441   r = d3_rgb_xyz(r);
4442   g = d3_rgb_xyz(g);
4443   b = d3_rgb_xyz(b);
4444   var x = d3_xyz_lab((0.4124564 * r + 0.3575761 * g + 0.1804375 * b) / d3_lab_X),
4445       y = d3_xyz_lab((0.2126729 * r + 0.7151522 * g + 0.0721750 * b) / d3_lab_Y),
4446       z = d3_xyz_lab((0.0193339 * r + 0.1191920 * g + 0.9503041 * b) / d3_lab_Z);
4447   return d3_lab(116 * y - 16, 500 * (x - y), 200 * (y - z));
4448 }
4449
4450 function d3_rgb_xyz(r) {
4451   return (r /= 255) <= 0.04045 ? r / 12.92 : Math.pow((r + 0.055) / 1.055, 2.4);
4452 }
4453
4454 function d3_rgb_parseNumber(c) { // either integer or percentage
4455   var f = parseFloat(c);
4456   return c.charAt(c.length - 1) === "%" ? Math.round(f * 2.55) : f;
4457 }
4458
4459 var d3_rgb_names = d3.map({
4460   aliceblue: "#f0f8ff",
4461   antiquewhite: "#faebd7",
4462   aqua: "#00ffff",
4463   aquamarine: "#7fffd4",
4464   azure: "#f0ffff",
4465   beige: "#f5f5dc",
4466   bisque: "#ffe4c4",
4467   black: "#000000",
4468   blanchedalmond: "#ffebcd",
4469   blue: "#0000ff",
4470   blueviolet: "#8a2be2",
4471   brown: "#a52a2a",
4472   burlywood: "#deb887",
4473   cadetblue: "#5f9ea0",
4474   chartreuse: "#7fff00",
4475   chocolate: "#d2691e",
4476   coral: "#ff7f50",
4477   cornflowerblue: "#6495ed",
4478   cornsilk: "#fff8dc",
4479   crimson: "#dc143c",
4480   cyan: "#00ffff",
4481   darkblue: "#00008b",
4482   darkcyan: "#008b8b",
4483   darkgoldenrod: "#b8860b",
4484   darkgray: "#a9a9a9",
4485   darkgreen: "#006400",
4486   darkgrey: "#a9a9a9",
4487   darkkhaki: "#bdb76b",
4488   darkmagenta: "#8b008b",
4489   darkolivegreen: "#556b2f",
4490   darkorange: "#ff8c00",
4491   darkorchid: "#9932cc",
4492   darkred: "#8b0000",
4493   darksalmon: "#e9967a",
4494   darkseagreen: "#8fbc8f",
4495   darkslateblue: "#483d8b",
4496   darkslategray: "#2f4f4f",
4497   darkslategrey: "#2f4f4f",
4498   darkturquoise: "#00ced1",
4499   darkviolet: "#9400d3",
4500   deeppink: "#ff1493",
4501   deepskyblue: "#00bfff",
4502   dimgray: "#696969",
4503   dimgrey: "#696969",
4504   dodgerblue: "#1e90ff",
4505   firebrick: "#b22222",
4506   floralwhite: "#fffaf0",
4507   forestgreen: "#228b22",
4508   fuchsia: "#ff00ff",
4509   gainsboro: "#dcdcdc",
4510   ghostwhite: "#f8f8ff",
4511   gold: "#ffd700",
4512   goldenrod: "#daa520",
4513   gray: "#808080",
4514   green: "#008000",
4515   greenyellow: "#adff2f",
4516   grey: "#808080",
4517   honeydew: "#f0fff0",
4518   hotpink: "#ff69b4",
4519   indianred: "#cd5c5c",
4520   indigo: "#4b0082",
4521   ivory: "#fffff0",
4522   khaki: "#f0e68c",
4523   lavender: "#e6e6fa",
4524   lavenderblush: "#fff0f5",
4525   lawngreen: "#7cfc00",
4526   lemonchiffon: "#fffacd",
4527   lightblue: "#add8e6",
4528   lightcoral: "#f08080",
4529   lightcyan: "#e0ffff",
4530   lightgoldenrodyellow: "#fafad2",
4531   lightgray: "#d3d3d3",
4532   lightgreen: "#90ee90",
4533   lightgrey: "#d3d3d3",
4534   lightpink: "#ffb6c1",
4535   lightsalmon: "#ffa07a",
4536   lightseagreen: "#20b2aa",
4537   lightskyblue: "#87cefa",
4538   lightslategray: "#778899",
4539   lightslategrey: "#778899",
4540   lightsteelblue: "#b0c4de",
4541   lightyellow: "#ffffe0",
4542   lime: "#00ff00",
4543   limegreen: "#32cd32",
4544   linen: "#faf0e6",
4545   magenta: "#ff00ff",
4546   maroon: "#800000",
4547   mediumaquamarine: "#66cdaa",
4548   mediumblue: "#0000cd",
4549   mediumorchid: "#ba55d3",
4550   mediumpurple: "#9370db",
4551   mediumseagreen: "#3cb371",
4552   mediumslateblue: "#7b68ee",
4553   mediumspringgreen: "#00fa9a",
4554   mediumturquoise: "#48d1cc",
4555   mediumvioletred: "#c71585",
4556   midnightblue: "#191970",
4557   mintcream: "#f5fffa",
4558   mistyrose: "#ffe4e1",
4559   moccasin: "#ffe4b5",
4560   navajowhite: "#ffdead",
4561   navy: "#000080",
4562   oldlace: "#fdf5e6",
4563   olive: "#808000",
4564   olivedrab: "#6b8e23",
4565   orange: "#ffa500",
4566   orangered: "#ff4500",
4567   orchid: "#da70d6",
4568   palegoldenrod: "#eee8aa",
4569   palegreen: "#98fb98",
4570   paleturquoise: "#afeeee",
4571   palevioletred: "#db7093",
4572   papayawhip: "#ffefd5",
4573   peachpuff: "#ffdab9",
4574   peru: "#cd853f",
4575   pink: "#ffc0cb",
4576   plum: "#dda0dd",
4577   powderblue: "#b0e0e6",
4578   purple: "#800080",
4579   red: "#ff0000",
4580   rosybrown: "#bc8f8f",
4581   royalblue: "#4169e1",
4582   saddlebrown: "#8b4513",
4583   salmon: "#fa8072",
4584   sandybrown: "#f4a460",
4585   seagreen: "#2e8b57",
4586   seashell: "#fff5ee",
4587   sienna: "#a0522d",
4588   silver: "#c0c0c0",
4589   skyblue: "#87ceeb",
4590   slateblue: "#6a5acd",
4591   slategray: "#708090",
4592   slategrey: "#708090",
4593   snow: "#fffafa",
4594   springgreen: "#00ff7f",
4595   steelblue: "#4682b4",
4596   tan: "#d2b48c",
4597   teal: "#008080",
4598   thistle: "#d8bfd8",
4599   tomato: "#ff6347",
4600   turquoise: "#40e0d0",
4601   violet: "#ee82ee",
4602   wheat: "#f5deb3",
4603   white: "#ffffff",
4604   whitesmoke: "#f5f5f5",
4605   yellow: "#ffff00",
4606   yellowgreen: "#9acd32"
4607 });
4608
4609 d3_rgb_names.forEach(function(key, value) {
4610   d3_rgb_names.set(key, d3_rgb_parse(value, d3_rgb, d3_hsl_rgb));
4611 });
4612
4613 d3.interpolateRgb = d3_interpolateRgb;
4614
4615 function d3_interpolateRgb(a, b) {
4616   a = d3.rgb(a);
4617   b = d3.rgb(b);
4618   var ar = a.r,
4619       ag = a.g,
4620       ab = a.b,
4621       br = b.r - ar,
4622       bg = b.g - ag,
4623       bb = b.b - ab;
4624   return function(t) {
4625     return "#"
4626         + d3_rgb_hex(Math.round(ar + br * t))
4627         + d3_rgb_hex(Math.round(ag + bg * t))
4628         + d3_rgb_hex(Math.round(ab + bb * t));
4629   };
4630 }
4631
4632 d3.transform = function(string) {
4633   var g = d3_document.createElementNS(d3.ns.prefix.svg, "g");
4634   return (d3.transform = function(string) {
4635     g.setAttribute("transform", string);
4636     var t = g.transform.baseVal.consolidate();
4637     return new d3_transform(t ? t.matrix : d3_transformIdentity);
4638   })(string);
4639 };
4640
4641 // Compute x-scale and normalize the first row.
4642 // Compute shear and make second row orthogonal to first.
4643 // Compute y-scale and normalize the second row.
4644 // Finally, compute the rotation.
4645 function d3_transform(m) {
4646   var r0 = [m.a, m.b],
4647       r1 = [m.c, m.d],
4648       kx = d3_transformNormalize(r0),
4649       kz = d3_transformDot(r0, r1),
4650       ky = d3_transformNormalize(d3_transformCombine(r1, r0, -kz)) || 0;
4651   if (r0[0] * r1[1] < r1[0] * r0[1]) {
4652     r0[0] *= -1;
4653     r0[1] *= -1;
4654     kx *= -1;
4655     kz *= -1;
4656   }
4657   this.rotate = (kx ? Math.atan2(r0[1], r0[0]) : Math.atan2(-r1[0], r1[1])) * d3_degrees;
4658   this.translate = [m.e, m.f];
4659   this.scale = [kx, ky];
4660   this.skew = ky ? Math.atan2(kz, ky) * d3_degrees : 0;
4661 };
4662
4663 d3_transform.prototype.toString = function() {
4664   return "translate(" + this.translate
4665       + ")rotate(" + this.rotate
4666       + ")skewX(" + this.skew
4667       + ")scale(" + this.scale
4668       + ")";
4669 };
4670
4671 function d3_transformDot(a, b) {
4672   return a[0] * b[0] + a[1] * b[1];
4673 }
4674
4675 function d3_transformNormalize(a) {
4676   var k = Math.sqrt(d3_transformDot(a, a));
4677   if (k) {
4678     a[0] /= k;
4679     a[1] /= k;
4680   }
4681   return k;
4682 }
4683
4684 function d3_transformCombine(a, b, k) {
4685   a[0] += k * b[0];
4686   a[1] += k * b[1];
4687   return a;
4688 }
4689
4690 var d3_transformIdentity = {a: 1, b: 0, c: 0, d: 1, e: 0, f: 0};
4691 d3.interpolateNumber = d3_interpolateNumber;
4692
4693 function d3_interpolateNumber(a, b) {
4694   b -= a;
4695   return function(t) { return a + b * t; };
4696 }
4697
4698 d3.interpolateTransform = d3_interpolateTransform;
4699
4700 function d3_interpolateTransform(a, b) {
4701   var s = [], // string constants and placeholders
4702       q = [], // number interpolators
4703       n,
4704       A = d3.transform(a),
4705       B = d3.transform(b),
4706       ta = A.translate,
4707       tb = B.translate,
4708       ra = A.rotate,
4709       rb = B.rotate,
4710       wa = A.skew,
4711       wb = B.skew,
4712       ka = A.scale,
4713       kb = B.scale;
4714
4715   if (ta[0] != tb[0] || ta[1] != tb[1]) {
4716     s.push("translate(", null, ",", null, ")");
4717     q.push({i: 1, x: d3_interpolateNumber(ta[0], tb[0])}, {i: 3, x: d3_interpolateNumber(ta[1], tb[1])});
4718   } else if (tb[0] || tb[1]) {
4719     s.push("translate(" + tb + ")");
4720   } else {
4721     s.push("");
4722   }
4723
4724   if (ra != rb) {
4725     if (ra - rb > 180) rb += 360; else if (rb - ra > 180) ra += 360; // shortest path
4726     q.push({i: s.push(s.pop() + "rotate(", null, ")") - 2, x: d3_interpolateNumber(ra, rb)});
4727   } else if (rb) {
4728     s.push(s.pop() + "rotate(" + rb + ")");
4729   }
4730
4731   if (wa != wb) {
4732     q.push({i: s.push(s.pop() + "skewX(", null, ")") - 2, x: d3_interpolateNumber(wa, wb)});
4733   } else if (wb) {
4734     s.push(s.pop() + "skewX(" + wb + ")");
4735   }
4736
4737   if (ka[0] != kb[0] || ka[1] != kb[1]) {
4738     n = s.push(s.pop() + "scale(", null, ",", null, ")");
4739     q.push({i: n - 4, x: d3_interpolateNumber(ka[0], kb[0])}, {i: n - 2, x: d3_interpolateNumber(ka[1], kb[1])});
4740   } else if (kb[0] != 1 || kb[1] != 1) {
4741     s.push(s.pop() + "scale(" + kb + ")");
4742   }
4743
4744   n = q.length;
4745   return function(t) {
4746     var i = -1, o;
4747     while (++i < n) s[(o = q[i]).i] = o.x(t);
4748     return s.join("");
4749   };
4750 }
4751
4752 d3.interpolateObject = d3_interpolateObject;
4753
4754 function d3_interpolateObject(a, b) {
4755   var i = {},
4756       c = {},
4757       k;
4758   for (k in a) {
4759     if (k in b) {
4760       i[k] = d3_interpolateByName(k)(a[k], b[k]);
4761     } else {
4762       c[k] = a[k];
4763     }
4764   }
4765   for (k in b) {
4766     if (!(k in a)) {
4767       c[k] = b[k];
4768     }
4769   }
4770   return function(t) {
4771     for (k in i) c[k] = i[k](t);
4772     return c;
4773   };
4774 }
4775
4776 d3.interpolateArray = d3_interpolateArray;
4777
4778 function d3_interpolateArray(a, b) {
4779   var x = [],
4780       c = [],
4781       na = a.length,
4782       nb = b.length,
4783       n0 = Math.min(a.length, b.length),
4784       i;
4785   for (i = 0; i < n0; ++i) x.push(d3_interpolate(a[i], b[i]));
4786   for (; i < na; ++i) c[i] = a[i];
4787   for (; i < nb; ++i) c[i] = b[i];
4788   return function(t) {
4789     for (i = 0; i < n0; ++i) c[i] = x[i](t);
4790     return c;
4791   };
4792 }
4793
4794 d3.interpolateString = d3_interpolateString;
4795
4796 function d3_interpolateString(a, b) {
4797   var m, // current match
4798       i, // current index
4799       j, // current index (for coalescing)
4800       s0 = 0, // start index of current string prefix
4801       s1 = 0, // end index of current string prefix
4802       s = [], // string constants and placeholders
4803       q = [], // number interpolators
4804       n, // q.length
4805       o;
4806
4807   // Reset our regular expression!
4808   d3_interpolate_number.lastIndex = 0;
4809
4810   // Find all numbers in b.
4811   for (i = 0; m = d3_interpolate_number.exec(b); ++i) {
4812     if (m.index) s.push(b.substring(s0, s1 = m.index));
4813     q.push({i: s.length, x: m[0]});
4814     s.push(null);
4815     s0 = d3_interpolate_number.lastIndex;
4816   }
4817   if (s0 < b.length) s.push(b.substring(s0));
4818
4819   // Find all numbers in a.
4820   for (i = 0, n = q.length; (m = d3_interpolate_number.exec(a)) && i < n; ++i) {
4821     o = q[i];
4822     if (o.x == m[0]) { // The numbers match, so coalesce.
4823       if (o.i) {
4824         if (s[o.i + 1] == null) { // This match is followed by another number.
4825           s[o.i - 1] += o.x;
4826           s.splice(o.i, 1);
4827           for (j = i + 1; j < n; ++j) q[j].i--;
4828         } else { // This match is followed by a string, so coalesce twice.
4829           s[o.i - 1] += o.x + s[o.i + 1];
4830           s.splice(o.i, 2);
4831           for (j = i + 1; j < n; ++j) q[j].i -= 2;
4832         }
4833       } else {
4834           if (s[o.i + 1] == null) { // This match is followed by another number.
4835           s[o.i] = o.x;
4836         } else { // This match is followed by a string, so coalesce twice.
4837           s[o.i] = o.x + s[o.i + 1];
4838           s.splice(o.i + 1, 1);
4839           for (j = i + 1; j < n; ++j) q[j].i--;
4840         }
4841       }
4842       q.splice(i, 1);
4843       n--;
4844       i--;
4845     } else {
4846       o.x = d3_interpolateNumber(parseFloat(m[0]), parseFloat(o.x));
4847     }
4848   }
4849
4850   // Remove any numbers in b not found in a.
4851   while (i < n) {
4852     o = q.pop();
4853     if (s[o.i + 1] == null) { // This match is followed by another number.
4854       s[o.i] = o.x;
4855     } else { // This match is followed by a string, so coalesce twice.
4856       s[o.i] = o.x + s[o.i + 1];
4857       s.splice(o.i + 1, 1);
4858     }
4859     n--;
4860   }
4861
4862   // Special optimization for only a single match.
4863   if (s.length === 1) {
4864     return s[0] == null ? q[0].x : function() { return b; };
4865   }
4866
4867   // Otherwise, interpolate each of the numbers and rejoin the string.
4868   return function(t) {
4869     for (i = 0; i < n; ++i) s[(o = q[i]).i] = o.x(t);
4870     return s.join("");
4871   };
4872 }
4873