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 select implementation for sparse bit arrays based on the Elias–Fano representation of monotone functions.

Instances of this classes do not add support to a bit vector: rather, they replace the bit vector with a succinct representation of the positions of the ones in the bit vector.

Note that some data may be shared with SparseRank: just use the factory method SparseRank.getSelect() to obtain an instance. In that case, numBits() counts just the new data used to build the class, and not the shared part.

 
 
 public class SparseSelect extends EliasFanoMonotoneLongBigList implements Select {
 	private static final long serialVersionUID = 2L;

The number of bits in the underlying bit array.
 
 	private final long n;
Whether this structure was built from a SparseRank structure, and thus shares part of its internal state.
 
 	protected final boolean fromRank;

Creates a new select structure using a long array.

The resulting structure keeps no reference to the original array.

Parameters:
bits a long array containing the bits.
length the number of valid bits in bits.
 
 	public SparseSelectfinal long[] bitsfinal long length ) {
 		this( LongArrayBitVector.wrapbitslength ) );
 	}

Creates a new select structure using a bit vector.

The resulting structure keeps no reference to the original bit vector.

Parameters:
bitVector the input bit vector.
 
 	public SparseSelectfinal BitVector bitVector ) {
 		thisbitVector.length(), bitVector.count(), bitVector.asLongSet().iterator() );
 	}


Creates a new select structure using an iterator.

This constructor is particularly useful if the positions of the ones are provided by some sequential source.

Parameters:
n the number of bits in the underlying bit vector.
m the number of ones in the underlying bit vector.
iterator an iterator returning the positions of the ones in the underlying bit vector in increasing order.
 
 	public SparseSelectfinal long nlong mfinal LongIterator iterator ) {
 		supermniterator );
 		this. = n;
 		 = false;
 	}	

Creates a new select structure using a list of longs.

Parameters:
list the list of the positions of ones.
 
 	public SparseSelectfinal LongList list ) {
 		superlist );
 		this. = list.isEmpty() ? 0 : list.getLonglist.size() - 1 ) + 1;
 		 = false;
 	}	

Creates a new select structure using a big list of longs.

This constructor is particularly useful if the positions of the ones are provided by some sequential source.

Parameters:
list the list of the positions of ones.
	public SparseSelectfinal LongBigList list ) {
		superlist );
		this. = list.isEmpty() ? 0 : list.getLonglist.size64() - 1 ) + 1;
		 = false;
	}	
	protected SparseSelectfinal long nfinal long mfinal int lfinal long[] lowerBitsfinal SimpleSelect selectUpper ) {
		supermllowerBitsselectUpper );
		this. = n;
		this. = true;
	}

Creates a new SparseRank structure sharing data with this instance.

Returns:
a new SparseRank structure sharing data with this instance.
	public SparseRank getRank() {
		return new SparseRank.bitVector() );
	}
	public long size64() {
		return ;
	}
	public int size() {
		return (int)Math.min. );
	}
	public long getLongfinal long pos ) {
	}
	public long numBits() {
		return .numBits() + (  ? 0 : .bitVector().length() + . * (long). );
	}
	public long selectfinal long rank ) {
		if ( rank >=  ) return -1;
		final int l = this.;
		final long upperBits = .selectrank ) - rank
		if ( l == 0 ) return upperBits;
		final long position = rank * l
		final int startWord = (int)( position / . );
		final int startBit = (int)( position % . );
		final int totalOffset = startBit + l;
		final long result = startWord ] >>> startBit;
		return upperBits << l | ( totalOffset <= . ? result : result | startWord + 1 ] << -startBit ) & ;
	}

Returns the bit vector indexed; since the bits are not stored in this data structure, a copy is built on purpose and returned.

Returns:
a copy of the underlying bit vector.
	public BitVector bitVector() {
		final LongArrayBitVector result = LongArrayBitVector.ofLength );
		forlong i = i-- != 0; ) result.setselecti ) );
		return result;
	}
	public int hashCode() {
		return System.identityHashCodethis );
	}
	public boolean equalsfinal Object o ) {
		return o == this;
	}
	public String toString() {
		return getClass().getName() + '@' + Integer.toHexStringhashCode() );
	}
New to GrepCode? Check out our FAQ X