protected function unravelIndex($index)
    {
        $a = 0;
        $b = $this->L-1;
        $y = 0;
        while ($b-$a > 1) {
            // the middle row in the interval [a,b]
            $y = (int) (($a+$b)/2);
            // the candidate index aka how many points until this row
            $i = $y*($y-1)/2;

            // if we need an offset les then the wanted y will be in the offset [a,y]
            if ($i > $index) {
                $b = $y;
            } else {
            // else it will be in the offset [y,b]
                $a = $y;
            }
        }
        // we have finished searching it is either a or b
        $x = $index - $i;

        // this means that it is b and we have a
        if ($y <= $x) {
            $y++;
            $x = $index - $y*($y-1)/2;
        } elseif ($x < 0) {
        // this means that it is a and we have b
            $y--;
            $x = $index - $y*($y-1)/2;
        }

        return array(
            (int) $y,
            (int) $x
        );
    }
protected function unravelIndex($index)
    {
        $a = 0;
        $b = $this->L-1;
        $y = 0;
        while ($b-$a > 1) {
            // the middle row in the interval [a,b]
            $y = (int) (($a+$b)/2);
            // the candidate index aka how many points until this row
            $i = $y*($y-1)/2;

            // if we need an offset les then the wanted y will be in the offset [a,y]
            if ($i > $index) {
                $b = $y;
            } else {
            // else it will be in the offset [y,b]
                $a = $y;
            }
        }
        // we have finished searching it is either a or b
        $x = $index - $i;

        // this means that it is b and we have a
        if ($y <= $x) {
            $y++;
            $x = $index - $y*($y-1)/2;
        } elseif ($x < 0) {
        // this means that it is a and we have b
            $y--;
            $x = $index - $y*($y-1)/2;
        }

        return array(
            (int) $y,
            (int) $x
        );
    }
protected function unravelIndex ( $ index ) { $ a = 0 ; $ b = $ this -> L - 1 ; $ y = 0 ; while ( $ b - $ a > 1 ) { // the middle row in the interval [a,b] $ y = ( int ) ( ( $ a + $ b ) / 2 ) ; // the candidate index aka how many points until this row $ i = $ y * ( $ y - 1 ) / 2 ; // if we need an offset les then the wanted y will be in the offset [a,y] if ( $ i > $ index ) { $ b = $ y ; } else { // else it will be in the offset [y,b] $ a = $ y ; } } // we have finished searching it is either a or b $ x = $ index - $ i ; // this means that it is b and we have a if ( $ y <= $ x ) { $ y ++ ; $ x = $ index - $ y * ( $ y - 1 ) / 2 ; } elseif ( $ x < 0 ) { // this means that it is a and we have b $ y -- ; $ x = $ index - $ y * ( $ y - 1 ) / 2 ; } return array ( ( int ) $ y , ( int ) $ x ) ; }
Use binary search to unravel the index to its coordinates x,y
return them in the order y,x . This operation is to be done only
once per merge so it doesn't add much overhead.

Note: y will always be larger than x

@param  integer $index The index to be unraveled
@return array   An array containing (y,x)
Use binary search to unravel the index to its coordinates x y return them in the order y x . This operation is to be done only once per merge so it doesn t add much overhead .