Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package it.unimi.dsi.sux4j.util;
  
  /*		 
   * 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/>.
  *
  */
 
 
 import java.io.File;
A compressed big list of longs; each element occupies a number of bits bounded by one plus its bit length plus the logarithm of the average bit length of an element.

Instances of this class store in a highly compacted form a list of longs. Values are provided either through an iterable object, or through an iterator, but in the latter case the user must also provide a (not necessarily strict) lower bound (0 by default) on the returned values. The compression is particularly high if the distribution of the values of the list is skewed towards the smallest values.

An additional bulk method makes it possible to extract several consecutive entries at high speed.

Implementation details

Instances of this class store values by offsetting them so that they are strictly positive. Then, the bits of each element, excluding the most significant one, are concatenated in a bit array, and the positions of the initial bit of each element are stored using the Elias–Fano representation. If the distribution of the elements is skewed towards small values, this method achieves very a good compression (and, in any case, w.r.t. exact binary length it will not lose more than one bit per element, plus lower-order terms).

During the construction, the list of borders (i.e., bit positions where each stored element starts) must be temporarily stored. For very large lists, it might be useful to use a constructor that provides offline storage for borders.

 
 public class EliasFanoLongBigList extends AbstractLongBigList implements Serializable {
 	private static final long serialVersionUID = 2L;
The number of elements in this list.
 
 	private final long length;
The storage for small elements.
 
 	private final LongArrayBitVector bits;
The offset (derived from the lower bound computed or provided at construction time) that must be added before returning a value.
 
 	private final long offset;
The position of the initial bit of each element, plus a final marker for the end of the bit array.
 
 	
 	private static long findMinfinal LongIterator iterator ) {
 		long lowerBound = .;
 		whileiterator.hasNext() ) lowerBound = Math.minlowerBounditerator.nextLong() );
 		return lowerBound;
 	}

Creates a new Elias–Fano long big list.

Parameters:
elements an iterable object.
 
 	public EliasFanoLongBigListfinal LongIterable elements ) {
 		thiselements.iterator(), findMinelements.iterator() ) ); 
 	}

Creates a new Elias–Fano long big list.

Parameters:
elements an iterable object.
 
 	public EliasFanoLongBigListfinal IntIterable elements ) {
 		thisnew LongIterable() {
 			public LongIterator iterator() {
 				return LongIterators.wrapelements.iterator() );
			}
		});
	}

Creates a new Elias–Fano long big list.

Parameters:
elements an iterable object.
	public EliasFanoLongBigListfinal ShortIterable elements ) {
		thisnew LongIterable() {
			public LongIterator iterator() {
				return LongIterators.wrapelements.iterator() );
			}
		});
	}

Creates a new Elias–Fano long big list.

Parameters:
elements an iterable object.
	public EliasFanoLongBigListfinal ByteIterable elements ) {
		thisnew LongIterable() {
			public LongIterator iterator() {
				return LongIterators.wrapelements.iterator() );
			}
		});
	}

Creates a new Elias–Fano long big list.

Parameters:
iterator an iterator returning natural numbers.
	public EliasFanoLongBigListfinal LongIterator iterator ) {
		thisiterator, 0 );
	}

Creates a new Elias–Fano long big list.

Parameters:
iterator an iterator returning natural numbers.
	public EliasFanoLongBigListfinal IntIterator iterator ) {
		this( LongIterators.wrapiterator ) );
	}

Creates a new Elias–Fano long big list.

Parameters:
iterator an iterator returning natural numbers.
	public EliasFanoLongBigListfinal ShortIterator iterator ) {
		this( LongIterators.wrapiterator ) );
	}

Creates a new Elias–Fano long big list.

Parameters:
iterator an iterator returning natural numbers.
	public EliasFanoLongBigListfinal ByteIterator iterator ) {
		this( LongIterators.wrapiterator ) );
	}

Creates a new Elias–Fano long big list.

Parameters:
iterator an iterator returning natural numbers.
lowerBound a (not necessarily strict) lower bound on the values returned by iterator.
	public EliasFanoLongBigListfinal IntIterator iteratorfinal int lowerBound ) {
		this( LongIterators.wrapiterator ), lowerBound );
	}

Creates a new Elias–Fano long big list.

Parameters:
iterator an iterator returning natural numbers.
lowerBound a (not necessarily strict) lower bound on the values returned by iterator.
	public EliasFanoLongBigListfinal ShortIterator iteratorfinal short lowerBound ) {
		this( LongIterators.wrapiterator ), lowerBound );
	}

Creates a new Elias–Fano long big list.

Parameters:
iterator an iterator returning natural numbers.
lowerBound a (not necessarily strict) lower bound on the values returned by iterator.
	public EliasFanoLongBigListfinal ByteIterator iteratorfinal byte lowerBound ) {
		this( LongIterators.wrapiterator ), lowerBound );
	}

Creates a new Elias–Fano long big list.

This constructor does not use offline space.

Parameters:
iterator an iterator returning natural numbers.
lowerBound a (not necessarily strict) lower bound on the values returned by iterator.
	public EliasFanoLongBigListfinal LongIterator iteratorlong lowerBound ) {
		thisiteratorlowerBoundfalse );
	}

Creates a new Elias–Fano long big list with low memory requirements.

This constructor will use a temporary file to store the border array if offline is true.

Parameters:
iterator an iterator returning natural numbers.
lowerBound a (not necessarily strict) lower bound on the values returned by iterator.
offline if true, the construction uses offline memory.
	public EliasFanoLongBigListfinal LongIterator iteratorlong lowerBoundboolean offline ) {
		this. = -lowerBound + 1;
		 = LongArrayBitVector.getInstance();
		LongArrayList borders = null;
		File tempFile = null;
		DataOutputStream dos = null;
		try {
			if ( offline ) {
				tempFile = File.createTempFileEliasFanoLongBigList.class.getSimpleName(), "borders" );
				tempFile.deleteOnExit();
				dos = new DataOutputStreamnew FastBufferedOutputStreamnew FileOutputStreamtempFile ) ) );
			}
			else borders = new LongArrayList();
			if ( offline ) dos.writeLong( 0 );
			else borders.add( 0 );
			long lastBorder = 0, maxBorder = 0;
			long v;
			long c = 0;
			int msb;
			whileiterator.hasNext() ) {
				v = iterator.nextLong();
				if ( v < lowerBound ) throw new IllegalArgumentExceptionv + " < " + lowerBound );
				v -= lowerBound;
				v++;
				msb = Fast.mostSignificantBitv );
				lastBorder += msb;
				if ( offline ) dos.writeLonglastBorder ); 
				else borders.addlastBorder );
				if ( maxBorder < lastBorder ) maxBorder = lastBorder;
				.appendv & ( 1L << msb ) - 1, msb );
				c++;
			}
			this. = c;
			if ( offline ) dos.close();
			this. = new EliasFanoMonotoneLongBigListc + 1, maxBorder + 1, offline ? BinIO.asLongIteratortempFile ) : borders.iterator() );
			if ( offline ) tempFile.delete();
			this..trim();
		}
		catchIOException e ) {
			throw new RuntimeExceptione );
		}
	}
	public long getLongfinal long index ) {
		final long from = .getLongindex ), to = .getLongindex + 1 );
		return ( ( 1L << ( to - from ) ) | .getLongfromto ) ) - ;
	}

Extracts a number of consecutive entries into a given array fragment.

Parameters:
index the index of the first entry returned.
dest the destination array; it will be filled with length consecutive entries starting at position offset.
offset the first position written in dest.
length the number of elements written in dest starting at offset.
Returns:
dest
See also:
get(long,long[])
	public long[] getlong indexfinal long dest[], final int offsetfinal int length ) {
		long from = .getLongindex++ ), to;
		// We use the destination array to cache borders.
		.getindexdestoffsetlength );
		forint i = 0; i < lengthi++ ) { 
			to = destoffset + i ];
			destoffset + i ] = ( ( 1L << ( to - from ) ) | .getLongfromto ) ) - this.;
			from = to;
		}
		return dest;
	}

Extracts a number of consecutive entries into a given array.

Parameters:
index the index of the first entry returned.
dest the destination array; it will be filled with consecutive entries.
Returns:
dest
See also:
get(long,long[],int,int)
	public long[] getfinal long indexfinal long dest[] ) {
		return getindexdest, 0, dest.length );
	}
	public long size64() {
		return ;
	}
	public long numBits() {
		return .numBits() + .length();
	}
New to GrepCode? Check out our FAQ X