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 rank16 implementation.

rank16 is a ranking structure using just 12.6% additional space and providing fast ranking. It is the natural ranking structure for 128-bit processors.

 
 
 public class Rank16 extends AbstractRank implements Rank {
 	private static final boolean ASSERTS = false;
 	private static final long serialVersionUID = 1L;
 	private static final int BLOCK_LENGTH = 1024;
 	
 	protected transient long[] bits;
 	protected final long[] superCount;
 	protected final short[] count;
 	protected final int numWords;
 	protected final long numOnes;
 	protected final long lastOne;
 	protected final BitVector bitVector;
 	
 	public Rank16long[] bitslong length ) {
 		this( LongArrayBitVector.wrapbitslength ) );
 	}
 		
 	public Rank16final BitVector bitVector ) {
 		this. = bitVector;
 		this. = bitVector.bits();
 		 = (int)( ( bitVector.length() + . - 1 ) / . );
 
 		final int numSuperCounts = (int)( ( bitVector.length() +  - 1 ) /  );
 		final int numCounts = (  + 1 ) / 2;
 		// Init rank/select structure
 		 = new shortnumCounts ];
 		 = new longnumSuperCounts ];
 
 		long c = 0, l = -1;
 		forint i = 0; i < i++ ) {
 			if ( i %  == 0 ) i /  ] = c;
 			if ( i % 2 == 0 ) i / 2 ] = (short)( c - i /  ] );
 			c += Long.bitCounti ] );
 			if ( i ] != 0 ) l = i * 64L + Fast.mostSignificantBiti ] );
 		}
 		
 		 = c;
 		 = l;
 	}
 	
 	
 	public long ranklong pos ) {
 		if (  ) assert pos >= 0;
 		if (  ) assert pos <= .length();
 		// This test can be eliminated if there is always an additional word at the end of the bit array.
 		if ( pos >  ) return ;
 		
 		final int word = (int)( pos / . );
 		final int block = word / ;
 		final int offset = word / 2;
         
 		return word % 2 == 0 ?
 				block ] + ( offset ] & 0xFFFF ) + Long.bitCountword ] & ( ( 1L << pos % 64 ) - 1 ) ) :
 				block ] + ( offset ] & 0xFFFF ) + Long.bitCountword - 1 ] ) + Long.bitCountword ] & ( 1L << pos % 64 ) - 1 );
 	}
 
 	public long numBits() {
 		return . * (long). + . * (long).;
 	}
 
 	public long count() {
 		return ;
 	}
	public long ranklong fromlong to ) {
		return rankto ) - rankfrom );
	}
	public long lastOne() {
		return ;
	}
	private void readObjectfinal ObjectInputStream s ) throws IOExceptionClassNotFoundException {
	}
	public BitVector bitVector() {
		return ;
	}
New to GrepCode? Check out our FAQ X