private static void mergeBins ( int mergedBinCount , float [ ] mergedPositions , long [ ] mergedBins , float [ ] deltas , int numMerge , int [ ] next , int [ ] prev ) { // repeatedly search for two closest bins, merge them and update the corresponding deltas // maintain index to the last valid bin int lastValidIndex = mergedBinCount - 1 ; // initialize prev / next lookup arrays for ( int i = 0 ; i < mergedBinCount ; ++ i ) { next [ i ] = i + 1 ; } for ( int i = 0 ; i < mergedBinCount ; ++ i ) { prev [ i ] = i - 1 ; } // initialize min-heap of deltas and the reverse index into the heap int heapSize = mergedBinCount - 1 ; int [ ] heap = new int [ heapSize ] ; int [ ] reverseIndex = new int [ heapSize ] ; for ( int i = 0 ; i < heapSize ; ++ i ) { heap [ i ] = i ; } for ( int i = 0 ; i < heapSize ; ++ i ) { reverseIndex [ i ] = i ; } heapify ( heap , reverseIndex , heapSize , deltas ) ; { int i = 0 ; while ( i < numMerge ) { // find the smallest delta within the range used for bins // pick minimum delta index using min-heap int currentIndex = heap [ 0 ] ; final int nextIndex = next [ currentIndex ] ; final int prevIndex = prev [ currentIndex ] ; final long k0 = mergedBins [ currentIndex ] & COUNT_BITS ; final long k1 = mergedBins [ nextIndex ] & COUNT_BITS ; final float m0 = mergedPositions [ currentIndex ] ; final float m1 = mergedPositions [ nextIndex ] ; final float d1 = deltas [ nextIndex ] ; final long sum = k0 + k1 ; final float w = ( float ) k0 / ( float ) sum ; // merge bin at given position with the next bin final float mm0 = ( m0 - m1 ) * w + m1 ; mergedPositions [ currentIndex ] = mm0 ; mergedBins [ currentIndex ] = sum | APPROX_FLAG_BIT ; // update deltas and min-heap if ( nextIndex == lastValidIndex ) { // merged bin is the last => remove the current bin delta from the heap heapSize = heapDelete ( heap , reverseIndex , heapSize , reverseIndex [ currentIndex ] , deltas ) ; } else { // merged bin is not the last => remove the merged bin delta from the heap heapSize = heapDelete ( heap , reverseIndex , heapSize , reverseIndex [ nextIndex ] , deltas ) ; // updated current delta deltas [ currentIndex ] = m1 - mm0 + d1 ; // updated delta is necessarily larger than existing one, therefore we only need to push it down the heap siftDown ( heap , reverseIndex , reverseIndex [ currentIndex ] , heapSize - 1 , deltas ) ; } if ( prevIndex >= 0 ) { // current bin is not the first, therefore update the previous bin delta deltas [ prevIndex ] = mm0 - mergedPositions [ prevIndex ] ; // updated previous bin delta is necessarily larger than its existing value => push down the heap siftDown ( heap , reverseIndex , reverseIndex [ prevIndex ] , heapSize - 1 , deltas ) ; } // update last valid index if we merged the last bin if ( nextIndex == lastValidIndex ) { lastValidIndex = currentIndex ; } next [ currentIndex ] = next [ nextIndex ] ; if ( nextIndex < lastValidIndex ) { prev [ next [ nextIndex ] ] = currentIndex ; } ++ i ; } } }
mergeBins performs the given number of bin merge operations on the given histogram