2 crossfilter.version = "1.0.3";
3 function crossfilter_identity(d) {
6 crossfilter.permute = permute;
8 function permute(array, index) {
9 for (var i = 0, n = index.length, copy = new Array(n); i < n; ++i) {
10 copy[i] = array[index[i]];
14 var bisect = crossfilter.bisect = bisect_by(crossfilter_identity);
16 bisect.by = bisect_by;
18 function bisect_by(f) {
20 // Locate the insertion point for x in a to maintain sorted order. The
21 // arguments lo and hi may be used to specify a subset of the array which
22 // should be considered; by default the entire array is used. If x is already
23 // present in a, the insertion point will be before (to the left of) any
24 // existing entries. The return value is suitable for use as the first
25 // argument to `array.splice` assuming that a is already sorted.
27 // The returned insertion point i partitions the array a into two halves so
28 // that all v < x for v in a[lo:i] for the left side and all v >= x for v in
29 // a[i:hi] for the right side.
30 function bisectLeft(a, x, lo, hi) {
32 var mid = lo + hi >> 1;
33 if (f(a[mid]) < x) lo = mid + 1;
39 // Similar to bisectLeft, but returns an insertion point which comes after (to
40 // the right of) any existing entries of x in a.
42 // The returned insertion point i partitions the array into two halves so that
43 // all v <= x for v in a[lo:i] for the left side and all v > x for v in
44 // a[i:hi] for the right side.
45 function bisectRight(a, x, lo, hi) {
47 var mid = lo + hi >> 1;
48 if (x < f(a[mid])) hi = mid;
54 bisectRight.right = bisectRight;
55 bisectRight.left = bisectLeft;
58 var heap = crossfilter.heap = heap_by(crossfilter_identity);
64 // Builds a binary heap within the specified array a[lo:hi]. The heap has the
65 // property such that the parent a[lo+i] is always less than or equal to its
66 // two children: a[lo+2*i+1] and a[lo+2*i+2].
67 function heap(a, lo, hi) {
70 while (--i > 0) sift(a, i, n, lo);
74 // Sorts the specified array a[lo:hi] in descending order, assuming it is
76 function sort(a, lo, hi) {
79 while (--n > 0) t = a[lo], a[lo] = a[lo + n], a[lo + n] = t, sift(a, 1, n, lo);
83 // Sifts the element a[lo+i-1] down the heap, where the heap is the contiguous
84 // slice of array a[lo:lo+n]. This method can also be used to update the heap
85 // incrementally, without incurring the full cost of reconstructing the heap.
86 function sift(a, i, n, lo) {
90 while ((child = i << 1) <= n) {
91 if (child < n && f(a[lo + child]) > f(a[lo + child + 1])) child++;
92 if (x <= f(a[lo + child])) break;
93 a[lo + i] = a[lo + child];
102 var heapselect = crossfilter.heapselect = heapselect_by(crossfilter_identity);
104 heapselect.by = heapselect_by;
106 function heapselect_by(f) {
107 var heap = heap_by(f);
109 // Returns a new array containing the top k elements in the array a[lo:hi].
110 // The returned array is not sorted, but maintains the heap property. If k is
111 // greater than hi - lo, then fewer than k elements will be returned. The
112 // order of elements in a is unchanged by this operation.
113 function heapselect(a, lo, hi, k) {
114 var queue = new Array(k = Math.min(hi - lo, k)),
120 for (i = 0; i < k; ++i) queue[i] = a[lo++];
126 if (x = f(d = a[lo]) > min) {
128 min = f(heap(queue, 0, k)[0]);
138 var insertionsort = crossfilter.insertionsort = insertionsort_by(crossfilter_identity);
140 insertionsort.by = insertionsort_by;
142 function insertionsort_by(f) {
144 function insertionsort(a, lo, hi) {
145 for (var i = lo + 1; i < hi; ++i) {
146 for (var j = i, t = a[i], x = f(t); j > lo && f(a[j - 1]) > x; --j) {
154 return insertionsort;
156 // Algorithm designed by Vladimir Yaroslavskiy.
157 // Implementation based on the Dart project; see lib/dart/LICENSE for details.
159 var quicksort = crossfilter.quicksort = quicksort_by(crossfilter_identity);
161 quicksort.by = quicksort_by;
163 function quicksort_by(f) {
164 var insertionsort = insertionsort_by(f);
166 function sort(a, lo, hi) {
167 return (hi - lo < quicksort_sizeThreshold
169 : quicksort)(a, lo, hi);
172 function quicksort(a, lo, hi) {
174 // Compute the two pivots by looking at 5 elements.
175 var sixth = (hi - lo) / 6 | 0,
178 i3 = lo + hi - 1 >> 1, // The midpoint.
182 var e1 = a[i1], x1 = f(e1),
183 e2 = a[i2], x2 = f(e2),
184 e3 = a[i3], x3 = f(e3),
185 e4 = a[i4], x4 = f(e4),
186 e5 = a[i5], x5 = f(e5);
190 // Sort the selected 5 elements using a sorting network.
191 if (x1 > x2) t = e1, e1 = e2, e2 = t, t = x1, x1 = x2, x2 = t;
192 if (x4 > x5) t = e4, e4 = e5, e5 = t, t = x4, x4 = x5, x5 = t;
193 if (x1 > x3) t = e1, e1 = e3, e3 = t, t = x1, x1 = x3, x3 = t;
194 if (x2 > x3) t = e2, e2 = e3, e3 = t, t = x2, x2 = x3, x3 = t;
195 if (x1 > x4) t = e1, e1 = e4, e4 = t, t = x1, x1 = x4, x4 = t;
196 if (x3 > x4) t = e3, e3 = e4, e4 = t, t = x3, x3 = x4, x4 = t;
197 if (x2 > x5) t = e2, e2 = e5, e5 = t, t = x2, x2 = x5, x5 = t;
198 if (x2 > x3) t = e2, e2 = e3, e3 = t, t = x2, x2 = x3, x3 = t;
199 if (x4 > x5) t = e4, e4 = e5, e5 = t, t = x4, x4 = x5, x5 = t;
201 var pivot1 = e2, pivotValue1 = x2,
202 pivot2 = e4, pivotValue2 = x4;
204 // e2 and e4 have been saved in the pivot variables. They will be written
205 // back, once the partitioning is finished.
212 var less = lo + 1, // First element in the middle partition.
213 great = hi - 2; // Last element in the middle partition.
215 // Note that for value comparison, <, <=, >= and > coerce to a primitive via
216 // Object.prototype.valueOf; == and === do not, so in order to be consistent
217 // with natural order (such as for Date objects), we must do two compares.
218 var pivotsEqual = pivotValue1 <= pivotValue2 && pivotValue1 >= pivotValue2;
221 // Degenerated case where the partitioning becomes a dutch national flag
224 // [ | < pivot | == pivot | unpartitioned | > pivot | ]
226 // left less k great right
228 // a[left] and a[right] are undefined and are filled after the
232 // 1) for x in ]left, less[ : x < pivot.
233 // 2) for x in [less, k[ : x == pivot.
234 // 3) for x in ]great, right[ : x > pivot.
235 for (var k = less; k <= great; ++k) {
236 var ek = a[k], xk = f(ek);
237 if (xk < pivotValue1) {
243 } else if (xk > pivotValue1) {
245 // Find the first element <= pivot in the range [k - 1, great] and
246 // put [:ek:] there. We know that such an element must exist:
247 // When k == less, then el3 (which is equal to pivot) lies in the
248 // interval. Otherwise a[k - 1] == pivot and the search stops at k-1.
249 // Note that in the latter case invariant 2 will be violated for a
250 // short amount of time. The invariant will be restored when the
251 // pivots are put into their final positions.
253 var greatValue = f(a[great]);
254 if (greatValue > pivotValue1) {
256 // This is the only location in the while-loop where a new
257 // iteration is started.
259 } else if (greatValue < pivotValue1) {
262 a[less++] = a[great];
268 // Note: if great < k then we will exit the outer loop and fix
269 // invariant 2 (which we just violated).
277 // We partition the list into three parts:
279 // 2. >= pivot1 && <= pivot2
282 // During the loop we have:
283 // [ | < pivot1 | >= pivot1 && <= pivot2 | unpartitioned | > pivot2 | ]
285 // left less k great right
287 // a[left] and a[right] are undefined and are filled after the
291 // 1. for x in ]left, less[ : x < pivot1
292 // 2. for x in [less, k[ : pivot1 <= x && x <= pivot2
293 // 3. for x in ]great, right[ : x > pivot2
294 for (var k = less; k <= great; k++) {
295 var ek = a[k], xk = f(ek);
296 if (xk < pivotValue1) {
303 if (xk > pivotValue2) {
305 var greatValue = f(a[great]);
306 if (greatValue > pivotValue2) {
308 if (great < k) break;
309 // This is the only location inside the loop where a new
310 // iteration is started.
313 // a[great] <= pivot2.
314 if (greatValue < pivotValue1) {
317 a[less++] = a[great];
320 // a[great] >= pivot1.
332 // Move pivots into their final positions.
333 // We shrunk the list from both sides (a[left] and a[right] have
334 // meaningless values in them) and now we move elements from the first
335 // and third partition into these locations so that we can store the
338 a[less - 1] = pivot1;
339 a[hi - 1] = a[great + 1];
340 a[great + 1] = pivot2;
342 // The list is now partitioned into three partitions:
343 // [ < pivot1 | >= pivot1 && <= pivot2 | > pivot2 ]
345 // left less great right
347 // Recursive descent. (Don't include the pivot values.)
348 sort(a, lo, less - 1);
349 sort(a, great + 2, hi);
352 // All elements in the second partition are equal to the pivot. No
353 // need to sort them.
357 // In theory it should be enough to call _doSort recursively on the second
359 // The Android source however removes the pivot elements from the recursive
360 // call if the second partition is too large (more than 2/3 of the list).
361 if (less < i1 && great > i5) {
362 var lessValue, greatValue;
363 while ((lessValue = f(a[less])) <= pivotValue1 && lessValue >= pivotValue1) ++less;
364 while ((greatValue = f(a[great])) <= pivotValue2 && greatValue >= pivotValue2) --great;
366 // Copy paste of the previous 3-way partitioning with adaptions.
368 // We partition the list into three parts:
370 // 2. > pivot1 && < pivot2
373 // During the loop we have:
374 // [ == pivot1 | > pivot1 && < pivot2 | unpartitioned | == pivot2 ]
379 // 1. for x in [ *, less[ : x == pivot1
380 // 2. for x in [less, k[ : pivot1 < x && x < pivot2
381 // 3. for x in ]great, * ] : x == pivot2
382 for (var k = less; k <= great; k++) {
383 var ek = a[k], xk = f(ek);
384 if (xk <= pivotValue1 && xk >= pivotValue1) {
391 if (xk <= pivotValue2 && xk >= pivotValue2) {
393 var greatValue = f(a[great]);
394 if (greatValue <= pivotValue2 && greatValue >= pivotValue2) {
396 if (great < k) break;
397 // This is the only location inside the loop where a new
398 // iteration is started.
401 // a[great] < pivot2.
402 if (greatValue < pivotValue1) {
405 a[less++] = a[great];
408 // a[great] == pivot1.
420 // The second partition has now been cleared of pivot elements and looks
422 // [ * | > pivot1 && < pivot2 | * ]
425 // Sort the second partition using recursive descent.
427 // The second partition looks as follows:
428 // [ * | >= pivot1 && <= pivot2 | * ]
431 // Simply sort it by recursive descent.
433 return sort(a, less, great + 1);
439 var quicksort_sizeThreshold = 32;
440 var crossfilter_array8 = crossfilter_arrayUntyped,
441 crossfilter_array16 = crossfilter_arrayUntyped,
442 crossfilter_array32 = crossfilter_arrayUntyped,
443 crossfilter_arrayLengthen = crossfilter_identity,
444 crossfilter_arrayWiden = crossfilter_identity;
446 if (typeof Uint8Array !== "undefined") {
447 crossfilter_array8 = function(n) { return new Uint8Array(n); };
448 crossfilter_array16 = function(n) { return new Uint16Array(n); };
449 crossfilter_array32 = function(n) { return new Uint32Array(n); };
451 crossfilter_arrayLengthen = function(array, length) {
452 var copy = new array.constructor(length);
457 crossfilter_arrayWiden = function(array, width) {
460 case 16: copy = crossfilter_array16(array.length); break;
461 case 32: copy = crossfilter_array32(array.length); break;
462 default: throw new Error("invalid array width!");
469 function crossfilter_arrayUntyped(n) {
472 function crossfilter_filterExact(bisect, value) {
473 return function(values) {
474 var n = values.length;
475 return [bisect.left(values, value, 0, n), bisect.right(values, value, 0, n)];
479 function crossfilter_filterRange(bisect, range) {
482 return function(values) {
483 var n = values.length;
484 return [bisect.left(values, min, 0, n), bisect.left(values, max, 0, n)];
488 function crossfilter_filterAll(values) {
489 return [0, values.length];
491 function crossfilter_null() {
494 function crossfilter_zero() {
497 function crossfilter_reduceIncrement(p) {
501 function crossfilter_reduceDecrement(p) {
505 function crossfilter_reduceAdd(f) {
506 return function(p, v) {
511 function crossfilter_reduceSubtract(f) {
512 return function(p, v) {
516 exports.crossfilter = crossfilter;
518 function crossfilter() {
521 dimension: dimension,
526 var data = [], // the records
527 n = 0, // the number of records; data.length
528 m = 0, // number of dimensions in use
529 M = 8, // number of dimensions that can fit in `filters`
530 filters = crossfilter_array8(0), // M bits per record; 1 is filtered out
531 filterListeners = [], // when the filters change
532 dataListeners = []; // when data is added
534 // Adds the specified new records to this crossfilter.
535 function add(newData) {
539 // If there's actually new data to add…
540 // Merge the new data into the existing data.
541 // Lengthen the filter bitset to handle the new records.
542 // Notify listeners (dimensions and groups) that new data is available.
544 data = data.concat(newData);
545 filters = crossfilter_arrayLengthen(filters, n += n1);
546 dataListeners.forEach(function(l) { l(newData, n0, n1); });
552 // Adds a new dimension with the specified value accessor function.
553 function dimension(value) {
556 filterExact: filterExact,
557 filterRange: filterRange,
558 filterAll: filterAll,
564 var one = 1 << m++, // bit mask, e.g., 00001000
565 zero = ~one, // inverted one, e.g., 11110111
566 values, // sorted, cached array
567 index, // value rank ↦ object id
568 newValues, // temporary array storing newly-added values
569 newIndex, // temporary array storing newly-added index
570 sort = quicksort_by(function(i) { return newValues[i]; }),
571 refilter = crossfilter_filterAll, // for recomputing filter
572 indexListeners = [], // when data is added
576 // Updating a dimension is a two-stage process. First, we must update the
577 // associated filters for the newly-added records. Once all dimensions have
578 // updated their filters, the groups are notified to update.
579 dataListeners.unshift(preAdd);
580 dataListeners.push(postAdd);
582 // Incorporate any existing data into this dimension, and make sure that the
583 // filter bitset is wide enough to handle the new dimension.
584 if (m > M) filters = crossfilter_arrayWiden(filters, M <<= 1);
588 // Incorporates the specified new records into this dimension.
589 // This function is responsible for updating filters, values, and index.
590 function preAdd(newData, n0, n1) {
592 // Permute new values into natural order using a sorted index.
593 newValues = newData.map(value);
594 newIndex = sort(crossfilter_range(n1), 0, n1);
595 newValues = permute(newValues, newIndex);
597 // Bisect newValues to determine which new records are selected.
598 var bounds = refilter(newValues), lo1 = bounds[0], hi1 = bounds[1], i;
599 for (i = 0; i < lo1; ++i) filters[newIndex[i] + n0] |= one;
600 for (i = hi1; i < n1; ++i) filters[newIndex[i] + n0] |= one;
602 // If this dimension previously had no data, then we don't need to do the
603 // more expensive merge operation; use the new values and index as-is.
612 var oldValues = values,
617 // Otherwise, create new arrays into which to merge new and old.
618 values = new Array(n);
619 index = crossfilter_index(n, n);
621 // Merge the old and new sorted values, and old and new index.
622 for (i = 0; i0 < n0 && i1 < n1; ++i) {
623 if (oldValues[i0] < newValues[i1]) {
624 values[i] = oldValues[i0];
625 index[i] = oldIndex[i0++];
627 values[i] = newValues[i1];
628 index[i] = newIndex[i1++] + n0;
632 // Add any remaining old values.
633 for (; i0 < n0; ++i0, ++i) {
634 values[i] = oldValues[i0];
635 index[i] = oldIndex[i0];
638 // Add any remaining new values.
639 for (; i1 < n1; ++i1, ++i) {
640 values[i] = newValues[i1];
641 index[i] = newIndex[i1] + n0;
644 // Bisect again to recompute lo0 and hi0.
645 bounds = refilter(values), lo0 = bounds[0], hi0 = bounds[1];
648 // When all filters have updated, notify index listeners of the new values.
649 function postAdd(newData, n0, n1) {
650 indexListeners.forEach(function(l) { l(newValues, newIndex, n0, n1); });
651 newValues = newIndex = null;
654 // Updates the selected values based on the specified bounds [lo, hi].
655 // This implementation is used by all the public filter methods.
656 function filterIndex(bounds) {
665 // Fast incremental update based on previous lo index.
667 for (i = lo1, j = Math.min(lo0, hi1); i < j; ++i) {
668 filters[k = index[i]] ^= one;
671 } else if (lo1 > lo0) {
672 for (i = lo0, j = Math.min(lo1, hi0); i < j; ++i) {
673 filters[k = index[i]] ^= one;
678 // Fast incremental update based on previous hi index.
680 for (i = Math.max(lo1, hi0), j = hi1; i < j; ++i) {
681 filters[k = index[i]] ^= one;
684 } else if (hi1 < hi0) {
685 for (i = Math.max(lo0, hi1), j = hi0; i < j; ++i) {
686 filters[k = index[i]] ^= one;
693 filterListeners.forEach(function(l) { l(one, added, removed); });
697 // Filters this dimension using the specified range, value, or null.
698 // If the range is null, this is equivalent to filterAll.
699 // If the range is an array, this is equivalent to filterRange.
700 // Otherwise, this is equivalent to filterExact.
701 function filter(range) {
703 ? filterAll() : Array.isArray(range)
705 : filterExact(range);
708 // Filters this dimension to select the exact value.
709 function filterExact(value) {
710 return filterIndex((refilter = crossfilter_filterExact(bisect, value))(values));
713 // Filters this dimension to select the specified range [lo, hi].
714 // The lower bound is inclusive, and the upper bound is exclusive.
715 function filterRange(range) {
716 return filterIndex((refilter = crossfilter_filterRange(bisect, range))(values));
719 // Clears any filters on this dimension.
720 function filterAll() {
721 return filterIndex((refilter = crossfilter_filterAll)(values));
724 // Returns the top K selected records, based on this dimension's order.
725 // Note: observes this dimension's filter, unlike group and groupAll.
731 while (--i >= lo0 && k > 0) {
732 if (!filters[j = index[i]]) {
741 // Adds a new group to this dimension, using the specified key function.
742 function group(key) {
747 reduceCount: reduceCount,
748 reduceSum: reduceSum,
750 orderNatural: orderNatural,
754 var groups, // array of {key, value}
755 groupIndex, // object id ↦ group id
757 groupCapacity = crossfilter_capacity(groupWidth),
758 k = 0, // cardinality
764 update = crossfilter_null,
765 reset = crossfilter_null,
768 if (arguments.length < 1) key = crossfilter_identity;
770 // The group listens to the crossfilter for when any dimension changes, so
771 // that it can update the associated reduce values. It must also listen to
772 // the parent dimension for when data is added, and compute new keys.
773 filterListeners.push(update);
774 indexListeners.push(add);
776 // Incorporate any existing data into the grouping.
777 add(values, index, 0, n);
779 // Incorporates the specified new values into this group.
780 // This function is responsible for updating groups and groupIndex.
781 function add(newValues, newIndex, n0, n1) {
782 var oldGroups = groups,
783 reIndex = crossfilter_index(k, groupCapacity),
785 initial = reduceInitial,
786 k0 = k, // old cardinality
787 i0 = 0, // index of old group
788 i1 = 0, // index of new record
794 x; // key of group to add
796 // If a reset is needed, we don't need to update the reduce values.
797 if (resetNeeded) add = initial = crossfilter_null;
799 // Reset the new groups (k is a lower bound).
800 // Also, make sure that groupIndex exists and is long enough.
801 groups = new Array(k), k = 0;
802 groupIndex = k0 > 1 ? crossfilter_arrayLengthen(groupIndex, n) : crossfilter_index(n, groupCapacity);
804 // Get the first old key (x0 of g0), if it exists.
805 if (k0) x0 = (g0 = oldGroups[0]).key;
807 // Find the first new key (x1), skipping NaN keys.
808 while (i1 < n1 && !((x1 = key(newValues[i1])) >= x1)) ++i1;
810 // While new keys remain…
813 // Determine the lesser of the two current keys; new and old.
814 // If there are no old keys remaining, then always add the new key.
815 if (g0 && x0 <= x1) {
818 // Record the new index of the old group.
821 // Retrieve the next old key.
822 if (g0 = oldGroups[++i0]) x0 = g0.key;
824 g = {key: x1, value: initial()}, x = x1;
827 // Add the lesser group.
830 // Add any selected records belonging to the added group, while
831 // advancing the new key and populating the associated group index.
833 groupIndex[j = newIndex[i1] + n0] = k;
834 if (!(filters[j] & zero)) g.value = add(g.value, data[j]);
835 if (++i1 >= n1) break;
836 x1 = key(newValues[i1]);
842 // Add any remaining old groups that were greater than all new keys.
843 // No incremental reduce is needed; these groups have no new records.
844 // Also record the new index of the old group.
846 groups[reIndex[i0] = k] = oldGroups[i0++];
850 // If we added any new groups before any old groups,
851 // update the group index of all the old records.
852 if (k > i0) for (i0 = 0; i0 < n0; ++i0) {
853 groupIndex[i0] = reIndex[groupIndex[i0]];
856 // Modify the update and reset behavior based on the cardinality.
857 // If the cardinality is less than or equal to one, then the groupIndex
858 // is not needed. If the cardinality is zero, then there are no records
859 // and therefore no groups to update or reset. Note that we also must
860 // change the registered listener to point to the new method.
861 j = filterListeners.indexOf(update);
870 update = crossfilter_null;
871 reset = crossfilter_null;
875 filterListeners[j] = update;
877 // Count the number of added groups,
878 // and widen the group index as needed.
879 function groupIncrement() {
880 if (++k === groupCapacity) {
881 reIndex = crossfilter_arrayWiden(reIndex, groupWidth <<= 1);
882 groupIndex = crossfilter_arrayWiden(groupIndex, groupWidth);
883 groupCapacity = crossfilter_capacity(groupWidth);
888 // Reduces the specified selected or deselected records.
889 // This function is only used when the cardinality is greater than 1.
890 function updateMany(filterOne, added, removed) {
891 if (filterOne === one || resetNeeded) return;
898 // Add the added values.
899 for (i = 0, n = added.length; i < n; ++i) {
900 if (!(filters[k = added[i]] & zero)) {
901 g = groups[groupIndex[k]];
902 g.value = reduceAdd(g.value, data[k]);
906 // Remove the removed values.
907 for (i = 0, n = removed.length; i < n; ++i) {
908 if ((filters[k = removed[i]] & zero) === filterOne) {
909 g = groups[groupIndex[k]];
910 g.value = reduceRemove(g.value, data[k]);
915 // Reduces the specified selected or deselected records.
916 // This function is only used when the cardinality is 1.
917 function updateOne(filterOne, added, removed) {
918 if (filterOne === one || resetNeeded) return;
925 // Add the added values.
926 for (i = 0, n = added.length; i < n; ++i) {
927 if (!(filters[k = added[i]] & zero)) {
928 g.value = reduceAdd(g.value, data[k]);
932 // Remove the removed values.
933 for (i = 0, n = removed.length; i < n; ++i) {
934 if ((filters[k = removed[i]] & zero) === filterOne) {
935 g.value = reduceRemove(g.value, data[k]);
940 // Recomputes the group reduce values from scratch.
941 // This function is only used when the cardinality is greater than 1.
942 function resetMany() {
946 // Reset all group values.
947 for (i = 0; i < k; ++i) {
948 groups[i].value = reduceInitial();
951 // Add any selected records.
952 for (i = 0; i < n; ++i) {
953 if (!(filters[i] & zero)) {
954 g = groups[groupIndex[i]];
955 g.value = reduceAdd(g.value, data[i]);
960 // Recomputes the group reduce values from scratch.
961 // This function is only used when the cardinality is 1.
962 function resetOne() {
966 // Reset the singleton group values.
967 g.value = reduceInitial();
969 // Add any selected records.
970 for (i = 0; i < n; ++i) {
971 if (!(filters[i] & zero)) {
972 g.value = reduceAdd(g.value, data[i]);
977 // Returns the array of group values, in the dimension's natural order.
979 if (resetNeeded) reset(), resetNeeded = false;
983 // Returns a new array containing the top K group values, in reduce order.
985 var top = select(all(), 0, groups.length, k);
986 return heap.sort(top, 0, top.length);
989 // Sets the reduce behavior for this group to use the specified functions.
990 // This method lazily recomputes the reduce values, waiting until needed.
991 function reduce(add, remove, initial) {
993 reduceRemove = remove;
994 reduceInitial = initial;
999 // A convenience method for reducing by count.
1000 function reduceCount() {
1001 return reduce(crossfilter_reduceIncrement, crossfilter_reduceDecrement, crossfilter_zero);
1004 // A convenience method for reducing by sum(value).
1005 function reduceSum(value) {
1006 return reduce(crossfilter_reduceAdd(value), crossfilter_reduceSubtract(value), crossfilter_zero);
1009 // Sets the reduce order, using the specified accessor.
1010 function order(value) {
1011 select = heapselect_by(valueOf);
1012 heap = heap_by(valueOf);
1013 function valueOf(d) { return value(d.value); }
1017 // A convenience method for natural ordering by reduce value.
1018 function orderNatural() {
1019 return order(crossfilter_identity);
1022 // Returns the cardinality of this group, irrespective of any filters.
1027 return reduceCount().orderNatural();
1030 // A convenience function for generating a singleton group.
1031 function groupAll() {
1032 var g = group(crossfilter_null), all = g.all;
1036 delete g.orderNatural;
1038 g.value = function() { return all()[0].value; };
1045 // A convenience method for groupAll on a dummy dimension.
1046 // This implementation can be optimized since it is always cardinality 1.
1047 function groupAll() {
1050 reduceCount: reduceCount,
1051 reduceSum: reduceSum,
1061 // The group listens to the crossfilter for when any dimension changes, so
1062 // that it can update the reduce value. It must also listen to the parent
1063 // dimension for when data is added.
1064 filterListeners.push(update);
1065 dataListeners.push(add);
1067 // For consistency; actually a no-op since resetNeeded is true.
1070 // Incorporates the specified new values into this group.
1071 function add(newData, n0, n1) {
1074 if (resetNeeded) return;
1076 // Add the added values.
1077 for (i = n0; i < n; ++i) {
1079 reduceValue = reduceAdd(reduceValue, data[i]);
1084 // Reduces the specified selected or deselected records.
1085 function update(filterOne, added, removed) {
1090 if (resetNeeded) return;
1092 // Add the added values.
1093 for (i = 0, n = added.length; i < n; ++i) {
1094 if (!filters[k = added[i]]) {
1095 reduceValue = reduceAdd(reduceValue, data[k]);
1099 // Remove the removed values.
1100 for (i = 0, n = removed.length; i < n; ++i) {
1101 if (filters[k = removed[i]] === filterOne) {
1102 reduceValue = reduceRemove(reduceValue, data[k]);
1107 // Recomputes the group reduce value from scratch.
1111 reduceValue = reduceInitial();
1113 for (i = 0; i < n; ++i) {
1115 reduceValue = reduceAdd(reduceValue, data[i]);
1120 // Sets the reduce behavior for this group to use the specified functions.
1121 // This method lazily recomputes the reduce value, waiting until needed.
1122 function reduce(add, remove, initial) {
1124 reduceRemove = remove;
1125 reduceInitial = initial;
1130 // A convenience method for reducing by count.
1131 function reduceCount() {
1132 return reduce(crossfilter_reduceIncrement, crossfilter_reduceDecrement, crossfilter_zero);
1135 // A convenience method for reducing by sum(value).
1136 function reduceSum(value) {
1137 return reduce(crossfilter_reduceAdd(value), crossfilter_reduceSubtract(value), crossfilter_zero);
1140 // Returns the computed reduce value.
1142 if (resetNeeded) reset(), resetNeeded = false;
1146 return reduceCount();
1149 // Returns the number of records in this crossfilter, irrespective of any filters.
1154 return arguments.length
1159 // Returns an array of size n, big enough to store ids up to m.
1160 function crossfilter_index(n, m) {
1162 ? crossfilter_array8 : m < 0x10001
1163 ? crossfilter_array16
1164 : crossfilter_array32)(n);
1167 // Constructs a new array of size n, with sequential values from 0 to n - 1.
1168 function crossfilter_range(n) {
1169 var range = crossfilter_index(n, n);
1170 for (var i = -1; ++i < n;) range[i] = i;
1174 function crossfilter_capacity(w) {