crossFilter.js

(function (exports) {
    crossfilter.version = "1.3.7";
    function crossfilter_identity(d) {
        return d;
    }
    crossfilter.permute = permute;

    function permute(array, index) {
        for (var i = 0, n = index.length, copy = new Array(n); i < n; ++i) {
            copy[i] = array[index[i]];
        }
        return copy;
    }
    var bisect = crossfilter.bisect = bisect_by(crossfilter_identity);

    bisect.by = bisect_by;

    function bisect_by(f) {

        // Locate the insertion point for x in a to maintain sorted order. The
        // arguments lo and hi may be used to specify a subset of the array which
        // should be considered; by default the entire array is used. If x is already
        // present in a, the insertion point will be before (to the left of) any
        // existing entries. The return value is suitable for use as the first
        // argument to `array.splice` assuming that a is already sorted.
        //
        // The returned insertion point i partitions the array a into two halves so
        // that all v < x for v in a[lo:i] for the left side and all v >= x for v in
        // a[i:hi] for the right side.
        function bisectLeft(a, x, lo, hi) {
            while (lo < hi) {
                var mid = lo + hi >>> 1;
                if (f(a[mid]) < x)
                    lo = mid + 1;
                else
                    hi = mid;
            }
            return lo;
        }

        // Similar to bisectLeft, but returns an insertion point which comes after (to
        // the right of) any existing entries of x in a.
        //
        // The returned insertion point i partitions the array into two halves so that
        // all v <= x for v in a[lo:i] for the left side and all v > x for v in
        // a[i:hi] for the right side.
        function bisectRight(a, x, lo, hi) {
            while (lo < hi) {
                var mid = lo + hi >>> 1;
                if (x < f(a[mid]))
                    hi = mid;
                else
                    lo = mid + 1;
            }
            return lo;
        }

        bisectRight.right = bisectRight;
        bisectRight.left = bisectLeft;
        return bisectRight;
    }
    var heap = crossfilter.heap = heap_by(crossfilter_identity);

    heap.by = heap_by;

    function heap_by(f) {

        // Builds a binary heap within the specified array a[lo:hi]. The heap has the
        // property such that the parent a[lo+i] is always less than or equal to its
        // two children: a[lo+2*i+1] and a[lo+2*i+2].
        function heap(a, lo, hi) {
            var n = hi - lo,
                    i = (n >>> 1) + 1;
            while (--i > 0)
                sift(a, i, n, lo);
            return a;
        }

        // Sorts the specified array a[lo:hi] in descending order, assuming it is
        // already a heap.
        function sort(a, lo, hi) {
            var n = hi - lo,
                    t;
            while (--n > 0)
                t = a[lo], a[lo] = a[lo + n], a[lo + n] = t, sift(a, 1, n, lo);
            return a;
        }

        // Sifts the element a[lo+i-1] down the heap, where the heap is the contiguous
        // slice of array a[lo:lo+n]. This method can also be used to update the heap
        // incrementally, without incurring the full cost of reconstructing the heap.
        function sift(a, i, n, lo) {
            var d = a[--lo + i],
                    x = f(d),
                    child;
            while ((child = i << 1) <= n) {
                if (child < n && f(a[lo + child]) > f(a[lo + child + 1]))
                    child++;
                if (x <= f(a[lo + child]))
                    break;
                a[lo + i] = a[lo + child];
                i = child;
            }
            a[lo + i] = d;
        }

        heap.sort = sort;
        return heap;
    }
    var heapselect = crossfilter.heapselect = heapselect_by(crossfilter_identity);

    heapselect.by = heapselect_by;

    function heapselect_by(f) {
        var heap = heap_by(f);

        // Returns a new array containing the top k elements in the array a[lo:hi].
        // The returned array is not sorted, but maintains the heap property. If k is
        // greater than hi - lo, then fewer than k elements will be returned. The
        // order of elements in a is unchanged by this operation.
        function heapselect(a, lo, hi, k) {
            var queue = new Array(k = Math.min(hi - lo, k)),
                    min,
                    i,
                    x,
                    d;

            for (i = 0; i < k; ++i)
                queue[i] = a[lo++];
            heap(queue, 0, k);

            if (lo < hi) {
                min = f(queue[0]);
                do {
                    if (x = f(d = a[lo]) > min) {
                        queue[0] = d;
                        min = f(heap(queue, 0, k)[0]);
                    }
                } while (++lo < hi);
            }

            return queue;
        }

        return heapselect;
    }
    var insertionsort = crossfilter.insertionsort = insertionsort_by(crossfilter_identity);

    insertionsort.by = insertionsort_by;

    function insertionsort_by(f) {

        function insertionsort(a, lo, hi) {
            for (var i = lo + 1; i < hi; ++i) {
                for (var j = i, t = a[i], x = f(t); j > lo && f(a[j - 1]) > x; --j) {
                    a[j] = a[j - 1];
                }
                a[j] = t;
            }
            return a;
        }

        return insertionsort;
    }
// Algorithm designed by Vladimir Yaroslavskiy.
// Implementation based on the Dart project; see lib/dart/LICENSE for details.

    var quicksort = crossfilter.quicksort = quicksort_by(crossfilter_identity);

    quicksort.by = quicksort_by;

    function quicksort_by(f) {
        var insertionsort = insertionsort_by(f);

        function sort(a, lo, hi) {
            return (hi - lo < quicksort_sizeThreshold
                    ? insertionsort
                    : quicksort)(a, lo, hi);
        }

        function quicksort(a, lo, hi) {
            // Compute the two pivots by looking at 5 elements.
            var sixth = (hi - lo) / 6 | 0,
                    i1 = lo + sixth,
                    i5 = hi - 1 - sixth,
                    i3 = lo + hi - 1 >> 1, // The midpoint.
                    i2 = i3 - sixth,
                    i4 = i3 + sixth;

            var e1 = a[i1], x1 = f(e1),
                    e2 = a[i2], x2 = f(e2),
                    e3 = a[i3], x3 = f(e3),
                    e4 = a[i4], x4 = f(e4),
                    e5 = a[i5], x5 = f(e5);

            var t;

            // Sort the selected 5 elements using a sorting network.
            if (x1 > x2)
                t = e1, e1 = e2, e2 = t, t = x1, x1 = x2, x2 = t;
            if (x4 > x5)
                t = e4, e4 = e5, e5 = t, t = x4, x4 = x5, x5 = t;
            if (x1 > x3)
                t = e1, e1 = e3, e3 = t, t = x1, x1 = x3, x3 = t;
            if (x2 > x3)
                t = e2, e2 = e3, e3 = t, t = x2, x2 = x3, x3 = t;
            if (x1 > x4)
                t = e1, e1 = e4, e4 = t, t = x1, x1 = x4, x4 = t;
            if (x3 > x4)
                t = e3, e3 = e4, e4 = t, t = x3, x3 = x4, x4 = t;
            if (x2 > x5)
                t = e2, e2 = e5, e5 = t, t = x2, x2 = x5, x5 = t;
            if (x2 > x3)
                t = e2, e2 = e3, e3 = t, t = x2, x2 = x3, x3 = t;
            if (x4 > x5)
                t = e4, e4 = e5, e5 = t, t = x4, x4 = x5, x5 = t;

            var pivot1 = e2, pivotValue1 = x2,
                    pivot2 = e4, pivotValue2 = x4;

            // e2 and e4 have been saved in the pivot variables. They will be written
            // back, once the partitioning is finished.
            a[i1] = e1;
            a[i2] = a[lo];
            a[i3] = e3;
            a[i4] = a[hi - 1];
            a[i5] = e5;

            var less = lo + 1, // First element in the middle partition.
                    great = hi - 2;  // Last element in the middle partition.

            // Note that for value comparison, <, <=, >= and > coerce to a primitive via
            // Object.prototype.valueOf; == and === do not, so in order to be consistent
            // with natural order (such as for Date objects), we must do two compares.
            var pivotsEqual = pivotValue1 <= pivotValue2 && pivotValue1 >= pivotValue2;
            if (pivotsEqual) {

                // Degenerated case where the partitioning becomes a dutch national flag
                // problem.
                //
                // [ |  < pivot  | == pivot | unpartitioned | > pivot  | ]
                //  ^             ^          ^             ^            ^
                // left         less         k           great         right
                //
                // a[left] and a[right] are undefined and are filled after the
                // partitioning.
                //
                // Invariants:
                //   1) for x in ]left, less[ : x < pivot.
                //   2) for x in [less, k[ : x == pivot.
                //   3) for x in ]great, right[ : x > pivot.
                for (var k = less; k <= great; ++k) {
                    var ek = a[k], xk = f(ek);
                    if (xk < pivotValue1) {
                        if (k !== less) {
                            a[k] = a[less];
                            a[less] = ek;
                        }
                        ++less;
                    } else if (xk > pivotValue1) {

                        // Find the first element <= pivot in the range [k - 1, great] and
                        // put [:ek:] there. We know that such an element must exist:
                        // When k == less, then el3 (which is equal to pivot) lies in the
                        // interval. Otherwise a[k - 1] == pivot and the search stops at k-1.
                        // Note that in the latter case invariant 2 will be violated for a
                        // short amount of time. The invariant will be restored when the
                        // pivots are put into their final positions.
                        while (true) {
                            var greatValue = f(a[great]);
                            if (greatValue > pivotValue1) {
                                great--;
                                // This is the only location in the while-loop where a new
                                // iteration is started.
                                continue;
                            } else if (greatValue < pivotValue1) {
                                // Triple exchange.
                                a[k] = a[less];
                                a[less++] = a[great];
                                a[great--] = ek;
                                break;
                            } else {
                                a[k] = a[great];
                                a[great--] = ek;
                                // Note: if great < k then we will exit the outer loop and fix
                                // invariant 2 (which we just violated).
                                break;
                            }
                        }
                    }
                }
            } else {

                // We partition the list into three parts:
                //  1. < pivot1
                //  2. >= pivot1 && <= pivot2
                //  3. > pivot2
                //
                // During the loop we have:
                // [ | < pivot1 | >= pivot1 && <= pivot2 | unpartitioned  | > pivot2  | ]
                //  ^            ^                        ^              ^             ^
                // left         less                     k              great        right
                //
                // a[left] and a[right] are undefined and are filled after the
                // partitioning.
                //
                // Invariants:
                //   1. for x in ]left, less[ : x < pivot1
                //   2. for x in [less, k[ : pivot1 <= x && x <= pivot2
                //   3. for x in ]great, right[ : x > pivot2
                for (var k = less; k <= great; k++) {
                    var ek = a[k], xk = f(ek);
                    if (xk < pivotValue1) {
                        if (k !== less) {
                            a[k] = a[less];
                            a[less] = ek;
                        }
                        ++less;
                    } else {
                        if (xk > pivotValue2) {
                            while (true) {
                                var greatValue = f(a[great]);
                                if (greatValue > pivotValue2) {
                                    great--;
                                    if (great < k)
                                        break;
                                    // This is the only location inside the loop where a new
                                    // iteration is started.
                                    continue;
                                } else {
                                    // a[great] <= pivot2.
                                    if (greatValue < pivotValue1) {
                                        // Triple exchange.
                                        a[k] = a[less];
                                        a[less++] = a[great];
                                        a[great--] = ek;
                                    } else {
                                        // a[great] >= pivot1.
                                        a[k] = a[great];
                                        a[great--] = ek;
                                    }
                                    break;
                                }
                            }
                        }
                    }
                }
            }

            // Move pivots into their final positions.
            // We shrunk the list from both sides (a[left] and a[right] have
            // meaningless values in them) and now we move elements from the first
            // and third partition into these locations so that we can store the
            // pivots.
            a[lo] = a[less - 1];
            a[less - 1] = pivot1;
            a[hi - 1] = a[great + 1];
            a[great + 1] = pivot2;

            // The list is now partitioned into three partitions:
            // [ < pivot1   | >= pivot1 && <= pivot2   |  > pivot2   ]
            //  ^            ^                        ^             ^
            // left         less                     great        right

            // Recursive descent. (Don't include the pivot values.)
            sort(a, lo, less - 1);
            sort(a, great + 2, hi);

            if (pivotsEqual) {
                // All elements in the second partition are equal to the pivot. No
                // need to sort them.
                return a;
            }

            // In theory it should be enough to call _doSort recursively on the second
            // partition.
            // The Android source however removes the pivot elements from the recursive
            // call if the second partition is too large (more than 2/3 of the list).
            if (less < i1 && great > i5) {
                var lessValue, greatValue;
                while ((lessValue = f(a[less])) <= pivotValue1 && lessValue >= pivotValue1)
                    ++less;
                while ((greatValue = f(a[great])) <= pivotValue2 && greatValue >= pivotValue2)
                    --great;

                // Copy paste of the previous 3-way partitioning with adaptions.
                //
                // We partition the list into three parts:
                //  1. == pivot1
                //  2. > pivot1 && < pivot2
                //  3. == pivot2
                //
                // During the loop we have:
                // [ == pivot1 | > pivot1 && < pivot2 | unpartitioned  | == pivot2 ]
                //              ^                      ^              ^
                //            less                     k              great
                //
                // Invariants:
                //   1. for x in [ *, less[ : x == pivot1
                //   2. for x in [less, k[ : pivot1 < x && x < pivot2
                //   3. for x in ]great, * ] : x == pivot2
                for (var k = less; k <= great; k++) {
                    var ek = a[k], xk = f(ek);
                    if (xk <= pivotValue1 && xk >= pivotValue1) {
                        if (k !== less) {
                            a[k] = a[less];
                            a[less] = ek;
                        }
                        less++;
                    } else {
                        if (xk <= pivotValue2 && xk >= pivotValue2) {
                            while (true) {
                                var greatValue = f(a[great]);
                                if (greatValue <= pivotValue2 && greatValue >= pivotValue2) {
                                    great--;
                                    if (great < k)
                                        break;
                                    // This is the only location inside the loop where a new
                                    // iteration is started.
                                    continue;
                                } else {
                                    // a[great] < pivot2.
                                    if (greatValue < pivotValue1) {
                                        // Triple exchange.
                                        a[k] = a[less];
                                        a[less++] = a[great];
                                        a[great--] = ek;
                                    } else {
                                        // a[great] == pivot1.
                                        a[k] = a[great];
                                        a[great--] = ek;
                                    }
                                    break;
                                }
                            }
                        }
                    }
                }
            }

            // The second partition has now been cleared of pivot elements and looks
            // as follows:
            // [  *  |  > pivot1 && < pivot2  | * ]
            //        ^                      ^
            //       less                  great
            // Sort the second partition using recursive descent.

            // The second partition looks as follows:
            // [  *  |  >= pivot1 && <= pivot2  | * ]
            //        ^                        ^
            //       less                    great
            // Simply sort it by recursive descent.

            return sort(a, less, great + 1);
        }

        return sort;
    }

    var quicksort_sizeThreshold = 32;
    var crossfilter_array8 = crossfilter_arrayUntyped,
            crossfilter_array16 = crossfilter_arrayUntyped,
            crossfilter_array32 = crossfilter_arrayUntyped,
            crossfilter_arrayLengthen = crossfilter_arrayLengthenUntyped,
            crossfilter_arrayWiden = crossfilter_arrayWidenUntyped;

    if (typeof Uint8Array !== "undefined") {
        crossfilter_array8 = function (n) {
            return new Uint8Array(n);
        };
        crossfilter_array16 = function (n) {
            return new Uint16Array(n);
        };
        crossfilter_array32 = function (n) {
            return new Uint32Array(n);
        };

        crossfilter_arrayLengthen = function (array, length) {
            if (array.length >= length)
                return array;
            var copy = new array.constructor(length);
            copy.set(array);
            return copy;
        };

        crossfilter_arrayWiden = function (array, width) {
            var copy;
            switch (width) {
                case 16:
                    copy = crossfilter_array16(array.length);
                    break;
                case 32:
                    copy = crossfilter_array32(array.length);
                    break;
                default:
                    throw new Error("invalid array width!");
            }
            copy.set(array);
            return copy;
        };
    }

    function crossfilter_arrayUntyped(n) {
        var array = new Array(n), i = -1;
        while (++i < n)
            array[i] = 0;
        return array;
    }

    function crossfilter_arrayLengthenUntyped(array, length) {
        var n = array.length;
        while (n < length)
            array[n++] = 0;
        return array;
    }

    function crossfilter_arrayWidenUntyped(array, width) {
        if (width > 32)
            throw new Error("invalid array width!");
        return array;
    }
    function crossfilter_filterExact(bisect, value) {
        return function (values) {
            var n = values.length;
            return [bisect.left(values, value, 0, n), bisect.right(values, value, 0, n)];
        };
    }

    function crossfilter_filterRange(bisect, range) {
        var min = range[0],
                max = range[1];
        return function (values) {
            var n = values.length;
            return [bisect.left(values, min, 0, n), bisect.left(values, max, 0, n)];
        };
    }

    function crossfilter_filterAll(values) {
        return [0, values.length];
    }
    function crossfilter_null() {
        return null;
    }
    function crossfilter_zero() {
        return 0;
    }
    function crossfilter_reduceIncrement(p) {
        return p + 1;
    }

    function crossfilter_reduceDecrement(p) {
        return p - 1;
    }

    function crossfilter_reduceAdd(f) {
        return function (p, v) {
            return p + +f(v);
        };
    }

    function crossfilter_reduceSubtract(f) {
        return function (p, v) {
            return p - f(v);
        };
    }
    exports.crossfilter = crossfilter;

    function crossfilter() {
        var crossfilter = {
            add: add,
            remove: removeData,
            dimension: dimension,
            groupAll: groupAll,
            size: size
        };

        var data = [], // the records
                n = 0, // the number of records; data.length
                m = 0, // a bit mask representing which dimensions are in use
                M = 8, // number of dimensions that can fit in `filters`
                filters = crossfilter_array8(0), // M bits per record; 1 is filtered out
                filterListeners = [], // when the filters change
                dataListeners = [], // when data is added
                removeDataListeners = []; // when data is removed

        // Adds the specified new records to this crossfilter.
        function add(newData) {
            var n0 = n,
                    n1 = newData.length;

            // If there's actually new data to add…
            // Merge the new data into the existing data.
            // Lengthen the filter bitset to handle the new records.
            // Notify listeners (dimensions and groups) that new data is available.
            if (n1) {
                data = data.concat(newData);
                filters = crossfilter_arrayLengthen(filters, n += n1);
                dataListeners.forEach(function (l) {
                    l(newData, n0, n1);
                });
            }

            return crossfilter;
        }

        // Removes all records that match the current filters.
        function removeData() {
            var newIndex = crossfilter_index(n, n),
                    removed = [];
            for (var i = 0, j = 0; i < n; ++i) {
                if (filters[i])
                    newIndex[i] = j++;
                else
                    removed.push(i);
            }

            // Remove all matching records from groups.
            filterListeners.forEach(function (l) {
                l(0, [], removed);
            });

            // Update indexes.
            removeDataListeners.forEach(function (l) {
                l(newIndex);
            });

            // Remove old filters and data by overwriting.
            for (var i = 0, j = 0, k; i < n; ++i) {
                if (k = filters[i]) {
                    if (i !== j)
                        filters[j] = k, data[j] = data[i];
                    ++j;
                }
            }
            data.length = j;
            while (n > j)
                filters[--n] = 0;
        }

        // Adds a new dimension with the specified value accessor function.
        function dimension(value) {
            var dimension = {
                filter: filter,
                filterExact: filterExact,
                filterRange: filterRange,
                filterFunction: filterFunction,
                filterAll: filterAll,
                top: top,
                bottom: bottom,
                group: group,
                groupAll: groupAll,
                dispose: dispose,
                remove: dispose // for backwards-compatibility
            };

            var one = ~m & -~m, // lowest unset bit as mask, e.g., 00001000
                    zero = ~one, // inverted one, e.g., 11110111
                    values, // sorted, cached array
                    index, // value rank ↦ object id
                    newValues, // temporary array storing newly-added values
                    newIndex, // temporary array storing newly-added index
                    sort = quicksort_by(function (i) {
                        return newValues[i];
                    }),
                    refilter = crossfilter_filterAll, // for recomputing filter
                    refilterFunction, // the custom filter function in use
                    indexListeners = [], // when data is added
                    dimensionGroups = [],
                    lo0 = 0,
                    hi0 = 0;

            // Updating a dimension is a two-stage process. First, we must update the
            // associated filters for the newly-added records. Once all dimensions have
            // updated their filters, the groups are notified to update.
            dataListeners.unshift(preAdd);
            dataListeners.push(postAdd);

            removeDataListeners.push(removeData);

            // Incorporate any existing data into this dimension, and make sure that the
            // filter bitset is wide enough to handle the new dimension.
            m |= one;
            if (M >= 32 ? !one : m & (1 << M) - 1) {
                filters = crossfilter_arrayWiden(filters, M <<= 1);
            }
            preAdd(data, 0, n);
            postAdd(data, 0, n);

            // Incorporates the specified new records into this dimension.
            // This function is responsible for updating filters, values, and index.
            function preAdd(newData, n0, n1) {

                // Permute new values into natural order using a sorted index.
                newValues = newData.map(value);
                newIndex = sort(crossfilter_range(n1), 0, n1);
                newValues = permute(newValues, newIndex);

                // Bisect newValues to determine which new records are selected.
                var bounds = refilter(newValues), lo1 = bounds[0], hi1 = bounds[1], i;
                if (refilterFunction) {
                    for (i = 0; i < n1; ++i) {
                        if (!refilterFunction(newValues[i], i))
                            filters[newIndex[i] + n0] |= one;
                    }
                } else {
                    for (i = 0; i < lo1; ++i)
                        filters[newIndex[i] + n0] |= one;
                    for (i = hi1; i < n1; ++i)
                        filters[newIndex[i] + n0] |= one;
                }

                // If this dimension previously had no data, then we don't need to do the
                // more expensive merge operation; use the new values and index as-is.
                if (!n0) {
                    values = newValues;
                    index = newIndex;
                    lo0 = lo1;
                    hi0 = hi1;
                    return;
                }

                var oldValues = values,
                        oldIndex = index,
                        i0 = 0,
                        i1 = 0;

                // Otherwise, create new arrays into which to merge new and old.
                values = new Array(n);
                index = crossfilter_index(n, n);

                // Merge the old and new sorted values, and old and new index.
                for (i = 0; i0 < n0 && i1 < n1; ++i) {
                    if (oldValues[i0] < newValues[i1]) {
                        values[i] = oldValues[i0];
                        index[i] = oldIndex[i0++];
                    } else {
                        values[i] = newValues[i1];
                        index[i] = newIndex[i1++] + n0;
                    }
                }

                // Add any remaining old values.
                for (; i0 < n0; ++i0, ++i) {
                    values[i] = oldValues[i0];
                    index[i] = oldIndex[i0];
                }

                // Add any remaining new values.
                for (; i1 < n1; ++i1, ++i) {
                    values[i] = newValues[i1];
                    index[i] = newIndex[i1] + n0;
                }

                // Bisect again to recompute lo0 and hi0.
                bounds = refilter(values), lo0 = bounds[0], hi0 = bounds[1];
            }

            // When all filters have updated, notify index listeners of the new values.
            function postAdd(newData, n0, n1) {
                indexListeners.forEach(function (l) {
                    l(newValues, newIndex, n0, n1);
                });
                newValues = newIndex = null;
            }

            function removeData(reIndex) {
                for (var i = 0, j = 0, k; i < n; ++i) {
                    if (filters[k = index[i]]) {
                        if (i !== j)
                            values[j] = values[i];
                        index[j] = reIndex[k];
                        ++j;
                    }
                }
                values.length = j;
                while (j < n)
                    index[j++] = 0;

                // Bisect again to recompute lo0 and hi0.
                var bounds = refilter(values);
                lo0 = bounds[0], hi0 = bounds[1];
            }

            // Updates the selected values based on the specified bounds [lo, hi].
            // This implementation is used by all the public filter methods.
            function filterIndexBounds(bounds) {
                var lo1 = bounds[0],
                        hi1 = bounds[1];

                if (refilterFunction) {
                    refilterFunction = null;
                    filterIndexFunction(function (d, i) {
                        return lo1 <= i && i < hi1;
                    });
                    lo0 = lo1;
                    hi0 = hi1;
                    return dimension;
                }

                var i,
                        j,
                        k,
                        added = [],
                        removed = [];

                // Fast incremental update based on previous lo index.
                if (lo1 < lo0) {
                    for (i = lo1, j = Math.min(lo0, hi1); i < j; ++i) {
                        filters[k = index[i]] ^= one;
                        added.push(k);
                    }
                } else if (lo1 > lo0) {
                    for (i = lo0, j = Math.min(lo1, hi0); i < j; ++i) {
                        filters[k = index[i]] ^= one;
                        removed.push(k);
                    }
                }

                // Fast incremental update based on previous hi index.
                if (hi1 > hi0) {
                    for (i = Math.max(lo1, hi0), j = hi1; i < j; ++i) {
                        filters[k = index[i]] ^= one;
                        added.push(k);
                    }
                } else if (hi1 < hi0) {
                    for (i = Math.max(lo0, hi1), j = hi0; i < j; ++i) {
                        filters[k = index[i]] ^= one;
                        removed.push(k);
                    }
                }

                lo0 = lo1;
                hi0 = hi1;
                filterListeners.forEach(function (l) {
                    l(one, added, removed);
                });
                return dimension;
            }

            // Filters this dimension using the specified range, value, or null.
            // If the range is null, this is equivalent to filterAll.
            // If the range is an array, this is equivalent to filterRange.
            // Otherwise, this is equivalent to filterExact.
            function filter(range) {
                return range == null
                        ? filterAll() : Array.isArray(range)
                        ? filterRange(range) : typeof range === "function"
                        ? filterFunction(range)
                        : filterExact(range);
            }

            // Filters this dimension to select the exact value.
            function filterExact(value) {
                return filterIndexBounds((refilter = crossfilter_filterExact(bisect, value))(values));
            }

            // Filters this dimension to select the specified range [lo, hi].
            // The lower bound is inclusive, and the upper bound is exclusive.
            function filterRange(range) {
                return filterIndexBounds((refilter = crossfilter_filterRange(bisect, range))(values));
            }

            // Clears any filters on this dimension.
            function filterAll() {
                return filterIndexBounds((refilter = crossfilter_filterAll)(values));
            }

            // Filters this dimension using an arbitrary function.
            function filterFunction(f) {
                refilter = crossfilter_filterAll;

                filterIndexFunction(refilterFunction = f);

                lo0 = 0;
                hi0 = n;

                return dimension;
            }

            function filterIndexFunction(f) {
                var i,
                        k,
                        x,
                        added = [],
                        removed = [];

                for (i = 0; i < n; ++i) {
                    if (!(filters[k = index[i]] & one) ^ (x = f(values[i], i))) {
                        if (x)
                            filters[k] &= zero, added.push(k);
                        else
                            filters[k] |= one, removed.push(k);
                    }
                }
                filterListeners.forEach(function (l) {
                    l(one, added, removed);
                });
            }

            // Returns the top K selected records based on this dimension's order.
            // Note: observes this dimension's filter, unlike group and groupAll.
            function top(k) {
                var array = [],
                        i = hi0,
                        j;

                while (--i >= lo0 && k > 0) {
                    if (!filters[j = index[i]]) {
                        array.push(data[j]);
                        --k;
                    }
                }

                return array;
            }

            // Returns the bottom K selected records based on this dimension's order.
            // Note: observes this dimension's filter, unlike group and groupAll.
            function bottom(k) {
                var array = [],
                        i = lo0,
                        j;

                while (i < hi0 && k > 0) {
                    if (!filters[j = index[i]]) {
                        array.push(data[j]);
                        --k;
                    }
                    i++;
                }

                return array;
            }

            // Adds a new group to this dimension, using the specified key function.
            function group(key) {
                var group = {
                    top: top,
                    all: all,
                    reduce: reduce,
                    reduceCount: reduceCount,
                    reduceSum: reduceSum,
                    order: order,
                    orderNatural: orderNatural,
                    size: size,
                    dispose: dispose,
                    remove: dispose // for backwards-compatibility
                };

                // Ensure that this group will be removed when the dimension is removed.
                dimensionGroups.push(group);

                var groups, // array of {key, value}
                        groupIndex, // object id ↦ group id
                        groupWidth = 8,
                        groupCapacity = crossfilter_capacity(groupWidth),
                        k = 0, // cardinality
                        select,
                        heap,
                        reduceAdd,
                        reduceRemove,
                        reduceInitial,
                        update = crossfilter_null,
                        reset = crossfilter_null,
                        resetNeeded = true;

                if (arguments.length < 1)
                    key = crossfilter_identity;

                // The group listens to the crossfilter for when any dimension changes, so
                // that it can update the associated reduce values. It must also listen to
                // the parent dimension for when data is added, and compute new keys.
                filterListeners.push(update);
                indexListeners.push(add);
                removeDataListeners.push(removeData);

                // Incorporate any existing data into the grouping.
                add(values, index, 0, n);

                // Incorporates the specified new values into this group.
                // This function is responsible for updating groups and groupIndex.
                function add(newValues, newIndex, n0, n1) {
                    var oldGroups = groups,
                            reIndex = crossfilter_index(k, groupCapacity),
                            add = reduceAdd,
                            initial = reduceInitial,
                            k0 = k, // old cardinality
                            i0 = 0, // index of old group
                            i1 = 0, // index of new record
                            j, // object id
                            g0, // old group
                            x0, // old key
                            x1, // new key
                            g, // group to add
                            x; // key of group to add

                    // If a reset is needed, we don't need to update the reduce values.
                    if (resetNeeded)
                        add = initial = crossfilter_null;

                    // Reset the new groups (k is a lower bound).
                    // Also, make sure that groupIndex exists and is long enough.
                    groups = new Array(k), k = 0;
                    groupIndex = k0 > 1 ? crossfilter_arrayLengthen(groupIndex, n) : crossfilter_index(n, groupCapacity);

                    // Get the first old key (x0 of g0), if it exists.
                    if (k0)
                        x0 = (g0 = oldGroups[0]).key;

                    // Find the first new key (x1), skipping NaN keys.
                    while (i1 < n1 && !((x1 = key(newValues[i1])) >= x1))
                        ++i1;

                    // While new keys remain…
                    while (i1 < n1) {

                        // Determine the lesser of the two current keys; new and old.
                        // If there are no old keys remaining, then always add the new key.
                        if (g0 && x0 <= x1) {
                            g = g0, x = x0;

                            // Record the new index of the old group.
                            reIndex[i0] = k;

                            // Retrieve the next old key.
                            if (g0 = oldGroups[++i0])
                                x0 = g0.key;
                        } else {
                            g = {key: x1, value: initial()}, x = x1;
                        }

                        // Add the lesser group.
                        groups[k] = g;

                        // Add any selected records belonging to the added group, while
                        // advancing the new key and populating the associated group index.
                        while (!(x1 > x)) {
                            groupIndex[j = newIndex[i1] + n0] = k;
                            if (!(filters[j] & zero))
                                g.value = add(g.value, data[j]);
                            if (++i1 >= n1)
                                break;
                            x1 = key(newValues[i1]);
                        }

                        groupIncrement();
                    }

                    // Add any remaining old groups that were greater than all new keys.
                    // No incremental reduce is needed; these groups have no new records.
                    // Also record the new index of the old group.
                    while (i0 < k0) {
                        groups[reIndex[i0] = k] = oldGroups[i0++];
                        groupIncrement();
                    }

                    // If we added any new groups before any old groups,
                    // update the group index of all the old records.
                    if (k > i0)
                        for (i0 = 0; i0 < n0; ++i0) {
                            groupIndex[i0] = reIndex[groupIndex[i0]];
                        }

                    // Modify the update and reset behavior based on the cardinality.
                    // If the cardinality is less than or equal to one, then the groupIndex
                    // is not needed. If the cardinality is zero, then there are no records
                    // and therefore no groups to update or reset. Note that we also must
                    // change the registered listener to point to the new method.
                    j = filterListeners.indexOf(update);
                    if (k > 1) {
                        update = updateMany;
                        reset = resetMany;
                    } else {
                        if (k === 1) {
                            update = updateOne;
                            reset = resetOne;
                        } else {
                            update = crossfilter_null;
                            reset = crossfilter_null;
                        }
                        groupIndex = null;
                    }
                    filterListeners[j] = update;

                    // Count the number of added groups,
                    // and widen the group index as needed.
                    function groupIncrement() {
                        if (++k === groupCapacity) {
                            reIndex = crossfilter_arrayWiden(reIndex, groupWidth <<= 1);
                            groupIndex = crossfilter_arrayWiden(groupIndex, groupWidth);
                            groupCapacity = crossfilter_capacity(groupWidth);
                        }
                    }
                }

                function removeData() {
                    if (k > 1) {
                        var oldK = k,
                                oldGroups = groups,
                                seenGroups = crossfilter_index(oldK, oldK);

                        // Filter out non-matches by copying matching group index entries to
                        // the beginning of the array.
                        for (var i = 0, j = 0; i < n; ++i) {
                            if (filters[i]) {
                                seenGroups[groupIndex[j] = groupIndex[i]] = 1;
                                ++j;
                            }
                        }

                        // Reassemble groups including only those groups that were referred
                        // to by matching group index entries.  Note the new group index in
                        // seenGroups.
                        groups = [], k = 0;
                        for (i = 0; i < oldK; ++i) {
                            if (seenGroups[i]) {
                                seenGroups[i] = k++;
                                groups.push(oldGroups[i]);
                            }
                        }

                        if (k > 1) {
                            // Reindex the group index using seenGroups to find the new index.
                            for (var i = 0; i < j; ++i)
                                groupIndex[i] = seenGroups[groupIndex[i]];
                        } else {
                            groupIndex = null;
                        }
                        filterListeners[filterListeners.indexOf(update)] = k > 1
                                ? (reset = resetMany, update = updateMany)
                                : k === 1 ? (reset = resetOne, update = updateOne)
                                : reset = update = crossfilter_null;
                    } else if (k === 1) {
                        for (var i = 0; i < n; ++i)
                            if (filters[i])
                                return;
                        groups = [], k = 0;
                        filterListeners[filterListeners.indexOf(update)] =
                                update = reset = crossfilter_null;
                    }
                }

                // Reduces the specified selected or deselected records.
                // This function is only used when the cardinality is greater than 1.
                function updateMany(filterOne, added, removed) {
                    if (filterOne === one || resetNeeded)
                        return;

                    var i,
                            k,
                            n,
                            g;

                    // Add the added values.
                    for (i = 0, n = added.length; i < n; ++i) {
                        if (!(filters[k = added[i]] & zero)) {
                            g = groups[groupIndex[k]];
                            g.value = reduceAdd(g.value, data[k]);
                        }
                    }

                    // Remove the removed values.
                    for (i = 0, n = removed.length; i < n; ++i) {
                        if ((filters[k = removed[i]] & zero) === filterOne) {
                            g = groups[groupIndex[k]];
                            g.value = reduceRemove(g.value, data[k]);
                        }
                    }
                }

                // Reduces the specified selected or deselected records.
                // This function is only used when the cardinality is 1.
                function updateOne(filterOne, added, removed) {
                    if (filterOne === one || resetNeeded)
                        return;

                    var i,
                            k,
                            n,
                            g = groups[0];

                    // Add the added values.
                    for (i = 0, n = added.length; i < n; ++i) {
                        if (!(filters[k = added[i]] & zero)) {
                            g.value = reduceAdd(g.value, data[k]);
                        }
                    }

                    // Remove the removed values.
                    for (i = 0, n = removed.length; i < n; ++i) {
                        if ((filters[k = removed[i]] & zero) === filterOne) {
                            g.value = reduceRemove(g.value, data[k]);
                        }
                    }
                }

                // Recomputes the group reduce values from scratch.
                // This function is only used when the cardinality is greater than 1.
                function resetMany() {
                    var i,
                            g;

                    // Reset all group values.
                    for (i = 0; i < k; ++i) {
                        groups[i].value = reduceInitial();
                    }

                    // Add any selected records.
                    for (i = 0; i < n; ++i) {
                        if (!(filters[i] & zero)) {
                            g = groups[groupIndex[i]];
                            g.value = reduceAdd(g.value, data[i]);
                        }
                    }
                }

                // Recomputes the group reduce values from scratch.
                // This function is only used when the cardinality is 1.
                function resetOne() {
                    var i,
                            g = groups[0];

                    // Reset the singleton group values.
                    g.value = reduceInitial();

                    // Add any selected records.
                    for (i = 0; i < n; ++i) {
                        if (!(filters[i] & zero)) {
                            g.value = reduceAdd(g.value, data[i]);
                        }
                    }
                }

                // Returns the array of group values, in the dimension's natural order.
                function all() {
                    if (resetNeeded)
                        reset(), resetNeeded = false;
                    return groups;
                }

                // Returns a new array containing the top K group values, in reduce order.
                function top(k) {
                    var top = select(all(), 0, groups.length, k);
                    return heap.sort(top, 0, top.length);
                }

                // Sets the reduce behavior for this group to use the specified functions.
                // This method lazily recomputes the reduce values, waiting until needed.
                function reduce(add, remove, initial) {
                    reduceAdd = add;
                    reduceRemove = remove;
                    reduceInitial = initial;
                    resetNeeded = true;
                    return group;
                }

                // A convenience method for reducing by count.
                function reduceCount() {
                    return reduce(crossfilter_reduceIncrement, crossfilter_reduceDecrement, crossfilter_zero);
                }

                // A convenience method for reducing by sum(value).
                function reduceSum(value) {
                    return reduce(crossfilter_reduceAdd(value), crossfilter_reduceSubtract(value), crossfilter_zero);
                }

                // Sets the reduce order, using the specified accessor.
                function order(value) {
                    select = heapselect_by(valueOf);
                    heap = heap_by(valueOf);
                    function valueOf(d) {
                        return value(d.value);
                    }
                    return group;
                }

                // A convenience method for natural ordering by reduce value.
                function orderNatural() {
                    return order(crossfilter_identity);
                }

                // Returns the cardinality of this group, irrespective of any filters.
                function size() {
                    return k;
                }

                // Removes this group and associated event listeners.
                function dispose() {
                    var i = filterListeners.indexOf(update);
                    if (i >= 0)
                        filterListeners.splice(i, 1);
                    i = indexListeners.indexOf(add);
                    if (i >= 0)
                        indexListeners.splice(i, 1);
                    i = removeDataListeners.indexOf(removeData);
                    if (i >= 0)
                        removeDataListeners.splice(i, 1);
                    return group;
                }

                return reduceCount().orderNatural();
            }

            // A convenience function for generating a singleton group.
            function groupAll() {
                var g = group(crossfilter_null), all = g.all;
                delete g.all;
                delete g.top;
                delete g.order;
                delete g.orderNatural;
                delete g.size;
                g.value = function () {
                    return all()[0].value;
                };
                return g;
            }

            // Removes this dimension and associated groups and event listeners.
            function dispose() {
                dimensionGroups.forEach(function (group) {
                    group.dispose();
                });
                var i = dataListeners.indexOf(preAdd);
                if (i >= 0)
                    dataListeners.splice(i, 1);
                i = dataListeners.indexOf(postAdd);
                if (i >= 0)
                    dataListeners.splice(i, 1);
                i = removeDataListeners.indexOf(removeData);
                if (i >= 0)
                    removeDataListeners.splice(i, 1);
                for (i = 0; i < n; ++i)
                    filters[i] &= zero;
                m &= zero;
                return dimension;
            }

            return dimension;
        }

        // A convenience method for groupAll on a dummy dimension.
        // This implementation can be optimized since it always has cardinality 1.
        function groupAll() {
            var group = {
                reduce: reduce,
                reduceCount: reduceCount,
                reduceSum: reduceSum,
                value: value,
                dispose: dispose,
                remove: dispose // for backwards-compatibility
            };

            var reduceValue,
                    reduceAdd,
                    reduceRemove,
                    reduceInitial,
                    resetNeeded = true;

            // The group listens to the crossfilter for when any dimension changes, so
            // that it can update the reduce value. It must also listen to the parent
            // dimension for when data is added.
            filterListeners.push(update);
            dataListeners.push(add);

            // For consistency; actually a no-op since resetNeeded is true.
            add(data, 0, n);

            // Incorporates the specified new values into this group.
            function add(newData, n0) {
                var i;

                if (resetNeeded)
                    return;

                // Add the added values.
                for (i = n0; i < n; ++i) {
                    if (!filters[i]) {
                        reduceValue = reduceAdd(reduceValue, data[i]);
                    }
                }
            }

            // Reduces the specified selected or deselected records.
            function update(filterOne, added, removed) {
                var i,
                        k,
                        n;

                if (resetNeeded)
                    return;

                // Add the added values.
                for (i = 0, n = added.length; i < n; ++i) {
                    if (!filters[k = added[i]]) {
                        reduceValue = reduceAdd(reduceValue, data[k]);
                    }
                }

                // Remove the removed values.
                for (i = 0, n = removed.length; i < n; ++i) {
                    if (filters[k = removed[i]] === filterOne) {
                        reduceValue = reduceRemove(reduceValue, data[k]);
                    }
                }
            }

            // Recomputes the group reduce value from scratch.
            function reset() {
                var i;

                reduceValue = reduceInitial();

                for (i = 0; i < n; ++i) {
                    if (!filters[i]) {
                        reduceValue = reduceAdd(reduceValue, data[i]);
                    }
                }
            }

            // Sets the reduce behavior for this group to use the specified functions.
            // This method lazily recomputes the reduce value, waiting until needed.
            function reduce(add, remove, initial) {
                reduceAdd = add;
                reduceRemove = remove;
                reduceInitial = initial;
                resetNeeded = true;
                return group;
            }

            // A convenience method for reducing by count.
            function reduceCount() {
                return reduce(crossfilter_reduceIncrement, crossfilter_reduceDecrement, crossfilter_zero);
            }

            // A convenience method for reducing by sum(value).
            function reduceSum(value) {
                return reduce(crossfilter_reduceAdd(value), crossfilter_reduceSubtract(value), crossfilter_zero);
            }

            // Returns the computed reduce value.
            function value() {
                if (resetNeeded)
                    reset(), resetNeeded = false;
                return reduceValue;
            }

            // Removes this group and associated event listeners.
            function dispose() {
                var i = filterListeners.indexOf(update);
                if (i >= 0)
                    filterListeners.splice(i);
                i = dataListeners.indexOf(add);
                if (i >= 0)
                    dataListeners.splice(i);
                return group;
            }

            return reduceCount();
        }

        // Returns the number of records in this crossfilter, irrespective of any filters.
        function size() {
            return n;
        }

        return arguments.length
                ? add(arguments[0])
                : crossfilter;
    }

// Returns an array of size n, big enough to store ids up to m.
    function crossfilter_index(n, m) {
        return (m < 0x101
                ? crossfilter_array8 : m < 0x10001
                ? crossfilter_array16
                : crossfilter_array32)(n);
    }

// Constructs a new array of size n, with sequential values from 0 to n - 1.
    function crossfilter_range(n) {
        var range = crossfilter_index(n, n);
        for (var i = -1; ++i < n; )
            range[i] = i;
        return range;
    }

    function crossfilter_capacity(w) {
        return w === 8
                ? 0x100 : w === 16
                ? 0x10000
                : 0x100000000;
    }
})(typeof exports !== 'undefined' && exports || this);