1 // Locate the insertion point for x in a to maintain sorted order. The

     2 // arguments lo and hi may be used to specify a subset of the array which should

     3 // be considered; by default the entire array is used. If x is already present

     4 // in a, the insertion point will be before (to the left of) any existing

     5 // entries. The return value is suitable for use as the first argument to

     6 // `array.splice` assuming that a is already sorted.

     7 //

     8 // The returned insertion point i partitions the array a into two halves so that

     9 // all v < x for v in a[lo:i] for the left side and all v >= x for v in a[i:hi]

    10 // for the right side.

    11 d3.bisectLeft = function(a, x, lo, hi) {

    12   if (arguments.length < 3) lo = 0;

    13   if (arguments.length < 4) hi = a.length;

    14   while (lo < hi) {

    15     var mid = (lo + hi) >> 1;

    16     if (a[mid] < x) lo = mid + 1;

    17     else hi = mid;

    18   }

    19   return lo;

    20 };

    21 

    22 // Similar to bisectLeft, but returns an insertion point which comes after (to

    23 // the right of) any existing entries of x in a.

    24 //

    25 // The returned insertion point i partitions the array into two halves so that

    26 // all v <= x for v in a[lo:i] for the left side and all v > x for v in a[i:hi]

    27 // for the right side.

    28 d3.bisect =

    29 d3.bisectRight = function(a, x, lo, hi) {

    30   if (arguments.length < 3) lo = 0;

    31   if (arguments.length < 4) hi = a.length;

    32   while (lo < hi) {

    33     var mid = (lo + hi) >> 1;

    34     if (x < a[mid]) hi = mid;

    35     else lo = mid + 1;

    36   }

    37   return lo;

    38 };