Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package it.unimi.dsi.sux4j.mph;
  
  /*		 
   * 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 version of a PaCoTrieDistributor whose space usage depends on the average string length, rather than on the maximum string length; mainly of theoretical interest.

Author(s):
Sebastiano Vigna
 
 
 public class VLPaCoTrieDistributor<T> extends AbstractObject2LongFunction<T> implements Size64 {
 	private final static Logger LOGGER = LoggerFactory.getLoggerVLPaCoTrieDistributor.class );
 	private static final long serialVersionUID = 1L;
 	private static final boolean DEBUG = false;
 	private static final boolean DDEBUG = false;
Infinity-like value for initialising node prefixes. It's one less than java.lang.Integer.MAX_VALUE because we need to be able to add one without overflowing.
 
 	private static final int MAX_PREFIX = . - 1;
The bitstream representing the PaCo trie.
 
 	private final byte[] trie;
The number of leaves in the trie.
 
 	private final long numberOfLeaves;
The transformation used to map object to bit vectors.
 
 	private final TransformationStrategy<? super T> transformationStrategy;
A class representing explicitly a partial trie. The toStream(it.unimi.dsi.io.OutputBitStream,it.unimi.dsi.logging.ProgressLogger) method writes an instance of this class to a bit stream.
 
 	private final static class PartialTrie<T> {
 		private final static boolean ASSERTS = true;

A node in the trie.
 
 		protected static class Node {
Left child.
 
 			public Node left;
Right child.
 
 			public Node right;
The path compacted in this node (null if there is no compaction at this node).
 
 			public final LongArrayBitVector path;
The length of the minimum disambiguating prefix on the left.
 
 			public int prefixLeft;
The length of the minimum disambiguating prefix on the right.
 
 			public int prefixRight;

Creates a node.

Parameters:
left the left child.
right the right child.
path the path compacted at this node.
 
 			public Nodefinal Node leftfinal Node rightfinal LongArrayBitVector path ) {
 				this. = left;
 				this. = right;
 				this. = path;
 			}

Returns true if this node is a leaf.

Returns:
true if this node is a leaf.
 
			public boolean isLeaf() {
				return  == null &&  == null;
			}
			public String toString() {
				return "[" +  + "]";
			}
		}

The root of the trie.
		protected final Node root;

Leaves in the trie.
		protected final long size;

The offset of each delimiter.
		protected final LongBigArrayBigList offset;

Creates a partial compacted trie using given elements, bucket size and transformation strategy.

Parameters:
elements the elements among which the trie must be able to rank.
bucketSize the size of a bucket.
transformationStrategy a transformation strategy that must turn the elements in elements into a list of distinct, lexicographically increasing (in iteration order) bit vectors.
pl
		public PartialTriefinal Iterable<? extends T> elementsfinal long sizefinal int bucketSizefinal TransformationStrategy<? super T> transformationStrategyProgressLogger pl ) {
			Iterator<? extends T> iterator = elements.iterator(); 
			Node node;
			LongArrayBitVector curr = LongArrayBitVector.getInstance();
			int posprefix;
			if ( iterator.hasNext() ) {
				pl.start"Building trie..." );
				LongArrayBitVector prev = LongArrayBitVector.copytransformationStrategy.toBitVectoriterator.next() ) );
				LongArrayBitVector shortest = prev.copy();
				long shortestIndex = 0;
				// The last delimiter seen, if root is not null.
				LongArrayBitVector prevDelimiter = LongArrayBitVector.getInstance();
				long count = 1;
				Node root = null;
				long maxLength = prev.length();
				// Last element will be unused
				 = new LongBigArrayBigListsize / bucketSize + 1 );
				whileiterator.hasNext() ) {
					// Check order
					curr.replacetransformationStrategy.toBitVectoriterator.next() ) );
					prefix = (int)curr.longestCommonPrefixLengthprev );
					if ( prefix == prev.length() && prefix == curr.length()  ) throw new IllegalArgumentException"The input bit vectors are not distinct" );
					if ( prefix == prev.length() || prefix == curr.length() ) throw new IllegalArgumentException"The input bit vectors are not prefix-free" );
					if ( prev.getBooleanprefix ) ) throw new IllegalArgumentException"The input bit vectors are not lexicographically sorted" );
					if ( count % bucketSize == 0 ) {
						// Found delimiter. Insert into trie.
						if ( root == null ) {
							root = new Nodenullnullshortest.copy() );
							prevDelimiter.replaceshortest );
						}
						else {
							prefix = (int)shortest.longestCommonPrefixLengthprevDelimiter );
							pos = 0;
							node = root;
							Node n = null;
							whilenode != null ) {
								final long pathLength = node.path.length();
								if ( prefix < pathLength ) {
									n = new Nodenode.leftnode.rightnode.path.copyprefix + 1, pathLength ) );
									node.path.lengthprefix );
									node.path.trim();
									node.left = n;
									node.right = new Nodenullnullshortest.copypos + prefix + 1, shortest.length() ) ); 
									break;
								}
								prefix -= pathLength + 1;
								pos += pathLength + 1;
								node = node.right;
								if (  ) assert node == null || prefix >= 0 : prefix + " <= " + 0;
							}
							if (  ) assert node != null;
							prevDelimiter.replaceshortest );
						}
						.addshortestIndex );
						shortest.replacecurr );
						shortestIndex = count;
					}
					if ( curr.length() < shortest.length() ) {
						shortest.replacecurr );
						shortestIndex = count;
					}
					prev.replacecurr );
					maxLength = Math.maxmaxLengthprev.length() );
					count++;
				}
				pl.done();
				this. = count;
				if (  ) ..println"Offsets: " +  );			
				// There's no reason to set up an actual distributor if we can just use the offsets.
				if ( this. <= bucketSize * 2 ) root = null;
				this. = root;
				if ( root != null ) {
					pl.start"Reducing paths..." );
					iterator = elements.iterator();
					// The stack of nodes visited the last time
					final Node stack[] = new Node[ (int)maxLength ];
					// The length of the path compacted in the trie up to the corresponding node, excluded
					final int[] len = new int[ (int)maxLength ];
					stack[ 0 ] = root;
					int depth = 0;
					boolean first = true;
					whileiterator.hasNext() ) {
						curr.replacetransformationStrategy.toBitVectoriterator.next() ) );
						if ( ! first )  {
							// Adjust stack using lcp between present string and previous one
							prefix = (int)prev.longestCommonPrefixLengthcurr );
							whiledepth > 0 && lendepth ] > prefix ) depth--;
						}
						else first = false;
						node = stackdepth ];
						pos = lendepth ];
						for(;;) {
							final LongArrayBitVector path = node.path;
							prefix = (int)curr.subVectorpos ).longestCommonPrefixLengthpath );
							if ( prefix < path.length() ) {
								/* If we are at the left of the current node, we simply update prefixLeft. Otherwise,
								 * can update prefixRight only *once*. */
								if ( path.getBooleanprefix ) ) node.prefixLeft = prefix;
								else if ( node.prefixRight ==  ) node.prefixRight = prefix
								break;
							}
							pos += path.length() + 1;
							if ( pos > curr.length() ) break;
							node = curr.getBooleanpos - 1 ) ? node.right : node.left;
							// Update stack
							len[ ++depth ] = pos;
							stackdepth ] = node;
						}
						prev.replacecurr );
					}
					pl.done();
				}
			}
			else {
				this. = null;
				this. = 0;
				 = null;
			}
		}

Accumulates the gain in bits w.r.t. a standard trie (just for statistical purposes).
		protected long gain;
		private final OutputBitStream bitCount = new OutputBitStream( NullOutputStream.getInstance(), 0 );

Writes this trie in bit stream format to the given stream.

Parameters:
obs an output bit stream.
Returns:
the number of leaves in the trie.
		public long toStreamfinal OutputBitStream obsfinal ProgressLogger pl ) throws IOException {
			final long result = toStreamobspl );
			.debug"Gain: " +  );
			return result;
		}
		private long toStreamfinal Node nfinal OutputBitStream obsProgressLogger pl ) throws IOException {
			if ( n == null ) return 0;
			if (  ) assert ( n.left != null ) == ( n.right != null );
			// We recursively create the stream of the left and right trees
			final OutputBitStream left = new OutputBitStreamleftStream, 0 );
			long leavesLeft = toStreamn.leftleftpl );
			long leftBits = left.writtenBits();
			left.flush();
			final OutputBitStream right = new OutputBitStreamrightStream, 0 );
			long leavesRight = toStreamn.rightrightpl );
			long rightBits = right.writtenBits();
			right.flush();
			obs.writeLongDeltan.isLeaf() ? 0 : leftBits ); // Skip pointer (nonzero if non leaf)
			final int pathLength = (int)Math.minn.path.length(), Math.maxn.prefixLeftn.prefixRight ) + 1 );
			final int missing =  (int)( n.path.length() - pathLength );
			// We gain one bit for each missing bit
			 += missing;
			/* For efficiency, the path is written in 64-bit blocks exactly as 
			 * it is represented in a LongArrayBitVector. */
			 += .writeLongDeltan.path.length() ) - obs.writeDeltapathLength ); // We gain if the path length is written in less bits than it should be.
			if ( pathLength > 0 ) forint i = 0; i < pathLengthi += . ) obs.writeLongn.path.getLongi, Math.mini + .pathLength ) ), Math.min.pathLength - i ) );
			// Nothing after the path in leaves.
			if ( n.isLeaf() ) return 1;
			n.left = n.right = null;
			// We count the missing bit as a gain, but of course in an internal node we must subtract the space needed to represent their cardinality.
			 -= obs.writeDeltamissing );
			obs.writeLongDeltaleavesLeft ); // The number of leaves in the left subtree
			// Write left and right trees
			obs.writeleftStream.arrayleftBits );
			obs.writerightStream.arrayrightBits );
			return leavesLeft + leavesRight;
		}
		private void recToStringfinal Node nfinal MutableString printPrefixfinal MutableString resultfinal MutableString pathfinal int level ) {
			if ( n == null ) return;
			result.appendprintPrefix ).append'(' ).appendlevel ).append')' );
			if ( n.path != null ) {
				path.appendn.path );
				result.append" path:" ).appendn.path );
			}
			result.append'\n' );
			path.append'0' );
			recToStringn.leftprintPrefix.append'\t' ).append"0 => " ), resultpathlevel + 1 );
			path.charAtpath.length() - 1, '1' ); 
			recToStringn.rightprintPrefix.replaceprintPrefix.length() - 5, printPrefix.length(), "1 => "), resultpathlevel + 1 );
			path.deletepath.length() - 1, path.length() ); 
			printPrefix.deleteprintPrefix.length() - 6, printPrefix.length() );
			//System.err.println( "Path now: " + path + " Going to delete from " + ( path.length() - n.pathLength));
			path.delete( (int)( path.length() - n.path.length() ), path.length() );
		}
		public String toString() {
			recToStringnew MutableString(), snew MutableString(), 0 );
			return s.toString();
		}
	}

Creates a partial compacted trie using given elements, bucket size and transformation strategy.

Parameters:
elements the elements among which the trie must be able to rank.
bucketSize the size of a bucket.
transformationStrategy a transformation strategy that must turn the elements in elements into a list of distinct, lexicographically increasing (in iteration order) bit vectors.
	@SuppressWarnings("resource")
	public VLPaCoTrieDistributorfinal Iterable<? extends T> elementsfinal long sizefinal int bucketSizefinal TransformationStrategy<? super T> transformationStrategy ) throws IOException {
		this. = transformationStrategy;
		pl.displayLocalSpeed = true;
		pl.displayFreeMemory = true;
		pl.itemsName = "keys";
		PartialTrie<T> immutableBinaryTrie = new PartialTrie<T>( elementssizebucketSizetransformationStrategypl );
		OutputBitStream trie = new OutputBitStreamfbStream, 0 );
		pl.expectedUpdates = immutableBinaryTrie.size;
		pl.start"Converting to bitstream..." );
		 = immutableBinaryTrie.toStreamtriepl );
		pl.done();
		 = immutableBinaryTrie.offset;
		.debug(  "Trie bit size: " + trie.writtenBits() );
		trie.flush();
		fbStream.trim();
		this. = fbStream.array;
		if (  ) {
			recToStringnew InputBitStreamthis. ), new MutableString(), snew MutableString(), 0 );
		}
	}
	@SuppressWarnings("unchecked")
	public long getLongObject o ) {
		if (  == 0 ) return 0;
		try {
			if (  ) ..println"Getting " + o + "...");
			final long length = v.length();
			@SuppressWarnings("resource")
			final InputBitStream trie = new InputBitStreamthis. );
			long pos = 0, readBitsskipxort;
			long leavesOnTheLeft = 0, leftSubtrieLeaves;
			int pathLengthsizemissing;
			long leaves = ;
			for( ;; ) {
				skip = trie.readLongDelta();
				pathLength = trie.readDelta();
				if (  ) ..println"Path length: " + pathLength );
				xor = t = 0;
				readBits = trie.readBits();
				forint i = 0; i < ( pathLength + . - 1 ) / .i++ ) {
					size = Math.min.pathLength - i * . );
					xor = v.getLongpos, Math.minlengthpos += size ) ) ^ ( t = trie.readLongsize ) );
					if ( xor != 0 || pos >= length ) break;
				}
				if ( xor != 0 || pos > length ) {
					if (  ) ..println"Path mismatch: " +  ( ( ( ( xor & -xor ) & t ) != 0 ) ? "smaller" : "greater" ) + " than trie path at (leaf = " + leavesOnTheLeft + ")" );
					// If we are lexicographically smaller than the trie, we just return the leaves to our left.
					if ( ( ( xor & -xor ) & t ) != 0 ) return leavesOnTheLeft;
					else {
						if ( skip == 0 ) {
							if (  ) ..println"Leaf node" );
							return leavesOnTheLeft + 1;
						}
						if (  ) ..println"Non-leaf node" );
						// Skip remaining path, if any and missing bits count
						trie.skippathLength - ( trie.readBits() - readBits ) );
						trie.readDelta();
						return leavesOnTheLeft + leaves;
					}
				}
				if ( skip == 0 ) {
					if (  ) ..println"Exact match (leaf = " + leavesOnTheLeft + ")" + pos + " " + length );
					return leavesOnTheLeft;
				}
				missing = trie.readDelta();
				if (  ) ..println"Missing bits: " + missing );
				// Increment pos by missing bits
				pos += missing;
				if ( pos >= v.length() ) return leavesOnTheLeft;
				leftSubtrieLeaves = trie.readLongDelta();
				if ( v.getBooleanpos++ ) ) {
					// Right
					trie.skipskip );
					leavesOnTheLeft += leftSubtrieLeaves;
					leaves -= leftSubtrieLeaves;
					if (  ) ..println"Turining right (" + leavesOnTheLeft + " leaves on the left)..." );
				}
				else {
					// Left
					leaves = leftSubtrieLeaves;
					if (  ) ..println"Turining left (" + leavesOnTheLeft + " leaves on the left)..." );
				}
catchIOException cantHappen ) {
			throw new RuntimeExceptioncantHappen );
		}
	}
	private void recToStringfinal InputBitStream triefinal MutableString printPrefixfinal MutableString resultfinal MutableString pathfinal int level ) throws IOException {
		long skip = trie.readLongDelta();
		//System.err.println( "Called with prefix " + printPrefix );
		result.appendprintPrefix ).append'(' ).appendlevel ).append')' );
		int pathLength = trie.readDelta();
		LongArrayBitVector p = LongArrayBitVector.getInstancepathLength );
		forint i = 0; i < ( pathLength + . - 1 ) / .i++ ) {
			int size = Math.min.pathLength - i * . );
			p.appendtrie.readLongsize ), size );
		}
		if ( skip == 0 ) return// Leaf
		int missing = trie.readDelta();
		path.appendp );
		result.append" path:" ).appendp );
		whilemissing-- != 0 ) result.append'*' );
		result.append'\n' );
		trie.readDelta(); // Skip number of leaves in the left subtree
		path.append'0' );
		recToStringtrieprintPrefix.append'\t' ).append"0 => " ), resultpathlevel + 1 );
		path.charAtpath.length() - 1, '1' ); 
		recToStringtrieprintPrefix.replaceprintPrefix.length() - 5, printPrefix.length(), "1 => "), resultpathlevel + 1 );
		path.deletepath.length() - 1, path.length() ); 
		printPrefix.deleteprintPrefix.length() - 6, printPrefix.length() );
		//System.err.println( "Path now: " + path + " Going to delete from " + ( path.length() - n.pathLength));
		path.deletepath.length() - pathLengthpath.length() );
	}
	public long numBits() {
	}
	public boolean containsKeyObject o ) {
		return true;
	}
	public long size64() {
	}
	public int size() {
		return (int)Math.min. );
	}
New to GrepCode? Check out our FAQ X