Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package it.unimi.dsi.sux4j.bits;
  
  
  /*		 
   * Sux4J: Succinct data structures for Java
   *
   * Copyright (C) 2008-2014 Sebastiano Vigna 
   *
   *  This library is free software; you can redistribute it and/or modify it
  *  under the terms of the GNU Lesser General Public License as published by the Free
  *  Software Foundation; either version 3 of the License, or (at your option)
  *  any later version.
  *
  *  This library is distributed in the hope that it will be useful, but
  *  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  *  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
  *  for more details.
  *
  *  You should have received a copy of the GNU Lesser General Public License
  *  along with this program; if not, see <http://www.gnu.org/licenses/>.
  *
  */
 
 
 
A hinted binary-search select implementation.

Instances of this class perform selection using a hinted binary search over an underlying Rank9 instance. We use 12.5% additional space for a small inventory.

 
 
 public class HintedBsearchSelect implements Select {
 	@SuppressWarnings("unused")
 	private static final boolean ASSERTS = false;
 	private static final long serialVersionUID = 1L;
 
 	private static final long ONES_STEP_9 = 1L << 0 | 1L << 9 | 1L << 18 | 1L << 27 | 1L << 36 | 1L << 45 | 1L << 54;
 	private static final long MSBS_STEP_9 = 0x100L * ;
 
 	private final int[] inventory;
 	private final int onesPerInventory;
 	private final int log2OnesPerInventory;
 	private final long numOnes;
 	private final int numWords;
 	private transient long[] bits;
 	private final long[] count;
 	private final Rank9 rank9;
 
 	public HintedBsearchSelectfinal Rank9 rank9 ) {
 		this. = rank9;
 		 = rank9.numOnes;
 		 = rank9.numWords;
 		 = rank9.bits;
 		 = rank9.count;
 		
 		 = rank9.bitVector.length() == 0 ? 0 : Fast.mostSignificantBit( (  * 16 * 64 + rank9.bitVector.length() - 1 ) / rank9.bitVector.length() );
 		final int inventorySize = (int)( (  +  - 1 ) /  );
 
 		 = new intinventorySize + 1 ];
 		long d = 0;
 		final long mask =  - 1;
 		forint i = 0; i < i++ )
 			forint j = 0; j < 64; j++ )
 				if ( ( i ] & 1L << j ) != 0 ) {
 					if ( ( d & mask ) == 0 ) [ (int)( d >>  ) ] = ( i / 8 ) * 2;
 					d++;
 				}
 
 		inventorySize ] = (  / 8 ) * 2;
 	}
 	
 	public long selectlong rank ) {
 		if ( rank >=  ) return -1;
 		
 		final long[] count = this.;
 		final int[] inventory = this.;
 		final int inventoryIndexLeft = (int)( rank >>>  );
 		int blockLeft = inventoryinventoryIndexLeft ];
 		int blockRight = inventoryinventoryIndexLeft + 1 ];
 
 		if ( rank >= countblockRight ] ) {
 			blockRight = ( blockLeft = blockRight ) + 2;
 		}
 		else {
 			int blockMiddle;
 
 			whileblockRight - blockLeft > 2 ) {
 				blockMiddle = ( blockRight + blockLeft ) / 2 & ~1;
 				if ( rank >= countblockMiddle ] ) blockLeft = blockMiddle;
 				else blockRight = blockMiddle;
 			}
 		}
		final long rankInBlock = rank - countblockLeft ];     
		final long rankInBlockStep9 = rankInBlock * ;
		final long subcounts = countblockLeft + 1 ];
		final long offsetInBlock = ( ( ( ( ( ( ( rankInBlockStep9 |  ) - ( subcounts & ~ ) ) | ( subcounts ^ rankInBlockStep9 ) ) ^ ( subcounts & ~rankInBlockStep9 ) ) &  ) >>> 8 ) *  >>> 54 & 0x7 );
		final long word = blockLeft * 4 + offsetInBlock;
		final long rankInWord = rankInBlock - ( subcounts >>> ( offsetInBlock - 1 & 7 ) * 9 & 0x1FF );
        return word * 64L + Fast.select[ (int)word ], (int)rankInWord );
	}
	public long numBits() {
		return .numBits() + . * (long).;
	}
	private void readObjectfinal ObjectInputStream s ) throws IOExceptionClassNotFoundException {
	}
	public BitVector bitVector() {
		return .bitVector();
	}
New to GrepCode? Check out our FAQ X