private void preComputeCardinalities ( ) { if ( ! cumulatedCardinalitiesCacheIsValid ) { int nbBuckets = highLowContainer . size ( ) ; // Ensure the cache size is the right one if ( highToCumulatedCardinality == null || highToCumulatedCardinality . length != nbBuckets ) { highToCumulatedCardinality = new int [ nbBuckets ] ; } // Ensure the cache content is valid if ( highToCumulatedCardinality . length >= 1 ) { // As we compute the cumulated cardinalities, the first index is an edge case highToCumulatedCardinality [ 0 ] = highLowContainer . getContainerAtIndex ( 0 ) . getCardinality ( ) ; for ( int i = 1 ; i < highToCumulatedCardinality . length ; i ++ ) { highToCumulatedCardinality [ i ] = highToCumulatedCardinality [ i - 1 ] + highLowContainer . getContainerAtIndex ( i ) . getCardinality ( ) ; } } cumulatedCardinalitiesCacheIsValid = true ; } }
On any . rank or . select operation we pre - compute all cumulated cardinalities . It will enable using a binary - search to spot the relevant underlying bucket . We may prefer to cache cardinality only up - to the selected rank but it would lead to a more complex implementation