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/>.
  *
  */
 
 
 import java.io.File;
 
A distributor based on a hollow trie.

Implementation details

This class implements a distributor on top of a hollow trie. First, a compacted trie is built from the delimiter set. Then, for each key we compute the node of the trie in which the bucket of the key is established. This gives us, for each node of the trie, a set of paths to which we must associate an action (exit on the left, go through, exit on the right). Overall, the number of such paths is equal to the number of keys plus the number of delimiters, so the mapping from each pair node/path to the respective action takes linear space. Now, from the compacted trie we just retain a hollow trie, as the path-length information is sufficient to rebuild the keys of the above mapping. By sizing the bucket size around the logarithm of the average length, we obtain a distributor that occupies linear space.

 
 
 public class HollowTrieDistributor<T> extends AbstractObject2LongFunction<T> implements Size64 {
 	private final static Logger LOGGER = LoggerFactory.getLoggerHollowTrieDistributor.class );
 	private static final long serialVersionUID = 3L;
 	private static final boolean DEBUG = false;
 	private static final boolean ASSERTS = false;

An integer representing the exit-on-the-left behaviour.
 
 	private final static int LEFT = 0;
An integer representing the exit-on-the-right behaviour.
 
 	private final static int RIGHT = 1;
An integer representing the follow-the-try behaviour.
 
 	private final static int FOLLOW = 2;

The transformation used to map object to bit vectors.
 
 	private final TransformationStrategy<? super T> transformationStrategy;
The bitstream representing the hollow trie.
 
 	private final LongArrayBitVector trie;
The list of skips, indexed by the internal nodes (we do not need skips on the leaves).
 
 	private final EliasFanoLongBigList skips;
For each external node and each possible path, the related behaviour.
 
The number of (internal and external) nodes of the trie.
 
 	private final long size;
The balanced parentheses structure used to represent the trie.
 
 	private final BalancedParentheses balParen;
Records the keys which are false follows.
 
The average skip length in bits (actually, the average length in bits of a skip length increased by one).
 
 	protected double meanSkipLength;

A debug function used to store explicitly the internal behaviour.
 
A debug function used to store explicitly the false follow detector.
 
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.
log2BucketSize the logarithm of 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.
	public HollowTrieDistributorfinal Iterable<? extends T> elementsfinal int log2BucketSizefinal TransformationStrategy<? super T> transformationStrategy ) throws IOException {
		thiselementslog2BucketSizetransformationStrategynull );
	}

Creates a hollow trie distributor.

Parameters:
elements the elements among which the trie must be able to rank.
log2BucketSize the logarithm of 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.
tempDir the directory where temporary files will be created, or for the default directory.
	public HollowTrieDistributorfinal Iterable<? extends T> elementsfinal int log2BucketSizefinal TransformationStrategy<? super T> transformationStrategyfinal File tempDir ) throws IOException {
		this. = transformationStrategy;
		final int bucketSize = 1 << log2BucketSize;

The file containing the external keys (pairs node/path).
		final File externalKeysFile;
The values associated to the keys in externalKeysFile.
		LongBigList externalValues;
The file containing the keys (pairs node/path) that are (either true or false) follows.
		final File falseFollowsKeyFile;
The values (true/false) associated to the keys in falseFollows.
		LongBigList falseFollowsValues;
		if (  ) ..println"Bucket size: " + bucketSize );
		final long[] count = new long[ 1 ];
			final Iterator<? extends T> iterator = elements.iterator();
			boolean toAdvance = true;
			private T curr;
			public boolean hasNext() {
				if (  ) {
					 = false;
					int i;
					fori = 0; i < bucketSize && .hasNext(); i++ ) {
						count[ 0 ]++;
					}
					if ( i != bucketSize )  = null;
				}
				return  != null;
			}
			public T next() {
				if ( ! hasNext() ) throw new NoSuchElementException();
				 = true;
				return ;
			}
		}, transformationStrategy );
		 = count[ 0 ];
		if (  ) {
		}
		externalKeysFile = File.createTempFileHollowTrieDistributor.class.getName(), "ext"tempDir );
		externalKeysFile.deleteOnExit();
		falseFollowsKeyFile = File.createTempFileHollowTrieDistributor.class.getName(), "false"tempDir );
		falseFollowsKeyFile.deleteOnExit();
		externalValues = LongArrayBitVector.getInstance().asLongBigList( 1 );
		falseFollowsValues = LongArrayBitVector.getInstance().asLongBigList( 1 );
		long sumOfSkipLengths = 0;
		if ( intermediateTrie.size64() > 0 ) {
			@SuppressWarnings("resource")
			final OutputBitStream externalKeys = new OutputBitStreamexternalKeysFile );
			@SuppressWarnings("resource")
			final OutputBitStream falseFollowsKeys = new OutputBitStreamfalseFollowsKeyFile );
			Iterator<? extends T> iterator = elements.iterator();
			LongArrayBitVector bucketKey[] = new LongArrayBitVectorbucketSize ];
			LongArrayBitVector leftDelimiterrightDelimiter = null;
			long delimiterLcp = -1;
			 = intermediateTrie.trie;
			 = intermediateTrie.skips;
			 = intermediateTrie.balParen;
			LongArrayBitVector emitted = LongArrayBitVector.ofLengthintermediateTrie.size64() );
			pl.displayLocalSpeed = true;
			pl.displayFreeMemory = true;
			pl.expectedUpdates = ;
			pl.start"Computing function keys..." );
			whileiterator.hasNext() ) {
				int realBucketSize;
				forrealBucketSize = 0; realBucketSize < bucketSize && iterator.hasNext(); realBucketSize++ ) {
					bucketKeyrealBucketSize ] = LongArrayBitVector.copytransformationStrategy.toBitVectoriterator.next() ) );
				}
				// The next delimiter
				leftDelimiter = rightDelimiter;
				rightDelimiter = realBucketSize == bucketSize ? bucketKeybucketSize - 1 ] : null;
				delimiterLcp = ( rightDelimiter != null && leftDelimiter != null ) ? rightDelimiter.longestCommonPrefixLengthleftDelimiter ) : -1;
				long stackP[] = new long[ 1024 ];
				long stackR[] = new long[ 1024 ];
				int stackS[] = new int[ 1024 ];
				long stackIndex[] = new long[ 1024 ];
				stackP[ 0 ] = 1;
				int depth = 0;
				int pathLength;
				long lastNode = -1;
				BitVector lastPath = null;
				LongArrayBitVector curr = nullprev;
				forint j = 0; j < realBucketSizej++ ) {
					prev = curr;
					curr = bucketKeyj ];
					if (  ) ..printlncurr );
					long p = 1, length = curr.length(), index = 0, r = 0;
					int s = 0, skip = 0;
					boolean isInternal;
					int startPath = -1, endPath = -1;
					boolean exitLeft = false;
					if (  ) ..println"Distributing " + curr + "\ntrie:" +  );
					long maxDescentLength
					if ( prev != null )  {
						final int 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" );
						// Adjust stack using lcp between present string and previous one
						whiledepth > 0 && stackSdepth ] > prefix ) depth--;
					}
					p = stackPdepth ];
					r = stackRdepth ];
					s = stackSdepth ];
					index = stackIndexdepth ];
					if ( leftDelimiter == null ) {
						maxDescentLength = rightDelimiter.longestCommonPrefixLengthcurr ) + 1;
						exitLeft = true;
					}
					else if ( rightDelimiter == null ) {
						maxDescentLength = leftDelimiter.longestCommonPrefixLengthcurr ) + 1;
						exitLeft = false;
					}
					else maxDescentLength = ( exitLeft = curr.getBooleandelimiterLcp ) ) ? rightDelimiter.longestCommonPrefixLengthcurr  ) + 1 : leftDelimiter.longestCommonPrefixLengthcurr ) + 1;
					for(;;) {
						isInternal = .getBooleanp );
						if ( isInternal ) skip = (int).getLongr );	
						if (  ) {
							final int usedLength = (int)( isInternal ? Math.minlengths + skip ) : length - s );
							final BitVector usedPath = curr.subVectorss + usedLength );
							..println"Interrogating" + ( isInternal ? "" : " leaf" ) + " <" + ( p - 1 ) + ", [" + usedLength + ", " + Integer.toHexStringusedPath.hashCode() ) + "] " + usedPath + "> " + ( isInternal ? "" : "(skip: " + skip + ")" ) ); 
						}
						if ( isInternal && s + skip < maxDescentLength && ! emitted.getBooleanr ) ) {
							sumOfSkipLengths += Fast.lengthskip + 1 );
							emitted.setrtrue );
							falseFollowsValues.add( 0 );
							falseFollowsKeys.writeLongp - 1, . );
							falseFollowsKeys.writeDeltaskip );
							forint i = 0; i < skipi += . ) 
								falseFollowsKeys.writeLongcurr.getLongs + i, Math.mins + i + .s + skip ) ), Math.min.skip - i ) );
							if (  ) ..println"Adding true follow at " + ( p - 1 ) + " [" + skip + ", " + Integer.toHexStringcurr.subVectorss + skip ).hashCode() ) + "] " + curr.subVectorss + skip ) );
							if (  ) {
								long key[] = new long[ ( skip + . - 1 ) / . + 1 ];
								key[ 0 ] = p - 1;
								forint i = 0; i < skipi += . ) keyi / . + 1 ] = curr.getLongs + i, Math.mins + i + .s + skip ) );
								long result = .put( LongArrayBitVector.wrapkeyskip + . ), 0 );
								assert result == -1 : result + " != " + -1;
							}
						}
						if ( ! isInternal || ( s += skip ) >= maxDescentLength ) break;
						if (  ) ..println"Turning " + ( curr.getBooleans ) ? "right" : "left" ) + " at bit " + s + "... " );
						if ( curr.getBooleans ) ) {
							final long q = .findClosep ) + 1;
							index += ( q - p ) / 2;
							r += ( q - p ) / 2;
							//System.err.println( "Increasing index by " + ( q - p + 1 ) / 2 + " to " + index + "..." );
							p = q;
						}
						else {
							p++;
							r++;
						}
						if (  ) assert p < .length();
						s++;
						if ( ++depth >= stackP.length ) {
							stackP = LongArrays.growstackPdepth + 1 );
							stackR = LongArrays.growstackRdepth + 1 );
							stackS = IntArrays.growstackSdepth + 1 );
							stackIndex = LongArrays.grow(  stackIndexdepth + 1 );
						}
						stackPdepth ] = p;
						stackRdepth ] = r;
						stackSdepth ] = s;
						stackIndexdepth ] = index;
					}
					if ( isInternal ) {
						startPath = s - skip;
						endPath = (int)Math.minlengths );
					}
					else {
						startPath = s;
						endPath = (int)length;
					}
					// If we exit on a leaf, we invalidate last node/path data
					if ( ! isInternal ) lastNode = -1;
					if ( lastNode != p - 1 || ! curr.subVectorstartPathendPath ).equalslastPath ) ) {
						externalValues.addexitLeft ?  :  );
						pathLength = endPath - startPath;
						externalKeys.writeLongp - 1, . );
						externalKeys.writeDeltapathLength );
						forint i = 0; i < pathLengthi += . ) 
							externalKeys.writeLongcurr.getLongstartPath + i, Math.minstartPath + i + .endPath ) ), Math.min.endPath - i - startPath ) );
						if (  ) ..println"Computed " + ( isInternal ? "" : "leaf " ) + "mapping <" + ( p - 1 ) + ", [" + pathLength + ", " + Integer.toHexStringcurr.subVectorstartPathendPath ).hashCode() ) + "] " + curr.subVectorstartPathendPath ) + "> -> " + ( exitLeft ? "left" : "right" ) );
						if (  ) {
							long key[] = new long[ ( pathLength + . - 1 ) / . + 1 ];
							key[ 0 ] = p - 1;
							forint i = 0; i < pathLengthi += . ) keyi / . + 1 ] = curr.getLongstartPath + i, Math.minstartPath + i + .endPath ) );
							assert .put( LongArrayBitVector.wrapkeypathLength + . ), exitLeft ?  :  ) == -1;
						}
						if ( isInternal ) {
							if (  ) ..println"Adding false follow [" + pathLength + ", " + Integer.toHexStringcurr.subVectorstartPathendPath ).hashCode() ) + "] " + curr.subVectorstartPathendPath ) );
							lastPath = curr.subVectorstartPathendPath );
							lastNode = p - 1;
							falseFollowsValues.add( 1 );
							falseFollowsKeys.writeLongp - 1, . );
							falseFollowsKeys.writeDeltapathLength );
							forint i = 0; i < pathLengthi += . ) 
								falseFollowsKeys.writeLongcurr.getLongstartPath + i, Math.minstartPath + i + .endPath ) ), Math.min.endPath - i - startPath ) );
							if (  ) {
								long key[] = new long[ ( pathLength + . - 1 ) / . + 1 ];
								key[ 0 ] = p - 1;
								forint i = 0; i < pathLengthi += . ) keyi / . + 1 ] = curr.getLongstartPath + i, Math.minstartPath + i + .endPath ) );
								assert .put( LongArrayBitVector.wrapkeypathLength + . ), 1 ) == -1;
							}
						}
					}
				}
			}
			 = (double)sumOfSkipLengths / ;
			pl.done();
			externalKeys.close();
			falseFollowsKeys.close();
		}
		else {
			 = null
			 = null;
			 = null;
			return;
		}

A class iterating over the temporary files produced by the intermediate trie.
		class IterableStream implements Iterable<BitVector> {
			private long n;
			public IterableStreamfinal InputBitStream ibsfinal Object2LongFunction<BitVectortestFunctionfinal LongBigList testValues ) {
				this. = ibs;
				this. = testValues.size64();
				this. = testFunction;
				this. = testValues;
			}
				try {
					.position( 0 );
						private long pos = 0;
						public boolean hasNext() {
							return  < ;
						}
						public BitVector next() {
							if ( ! hasNext() ) throw new NoSuchElementException();
							try {
								final long index = .readLong( 64 );
								assert index >= 0;
								final int pathLength = .readDelta();
								final long key[] = new long[ ( ( pathLength + . - 1 ) / . + 1 ) ];
								key[ 0 ] = index;
								forint i = 0; i < ( pathLength + . - 1 ) / .i++ ) keyi + 1 ] = .readLong( Math.min.pathLength - i * . ) );
								if (  ) {
									..println"Adding mapping <" + index + ", " +  LongArrayBitVector.wrapkeypathLength + . ).subVector. ) + "> -> " + .getLong ));
									..println(  LongArrayBitVector.wrapkeypathLength + . ) );
								}
								if (  ) if (  != null ) assert .getLong( LongArrayBitVector.wrapkeypathLength + . ) ) == .getLong ) : .getLong( LongArrayBitVector.wrapkeypathLength + . ) ) + " != " + .getLong ) ;
								++;
								return LongArrayBitVector.wrapkeypathLength + . );
							}
							catch ( IOException e ) {
								throw new RuntimeExceptione );
							}
						}
					};
				}
				catch ( IOException e ) {
					throw new RuntimeExceptione );
				}
			}
		};
		 = new MWHCFunction.Builder<BitVector>().keysnew IterableStreamnew InputBitStreamexternalKeysFile ), externalValues ) ).transform( TransformationStrategies.identity() ).valuesexternalValues, 1 ).build();
		 = new MWHCFunction.Builder<BitVector>().keysnew IterableStreamnew InputBitStreamfalseFollowsKeyFile ), falseFollowsValues ) ).transform( TransformationStrategies.identity() ).valuesfalseFollowsValues, 1 ).build();
		if (  ) {
		}
		.debug"False positives: " + ( .size64() - intermediateTrie.size64() ) );
		externalKeysFile.delete();
		falseFollowsKeyFile.delete();
	}
	@SuppressWarnings("unchecked")
	public long getLongfinal Object o ) {
		if (  == 0 ) return 0;
		final BitVector bitVector = .toBitVector( (T)o ).fast();
		LongArrayBitVector key = LongArrayBitVector.getInstance();
		BitVector fragment = null;
		long p = 1, length = bitVector.length(), index = 0, r = 0;
		int s = 0, skip = 0, behaviour;
		long lastLeftTurn = 0;
		long lastLeftTurnIndex = 0;
		boolean isInternal;
		if (  ) ..println"Distributing " + bitVector + "\ntrie:" +  );
		for(;;) {
			isInternal = .getBooleanp );
			if ( isInternal ) skip = (int).getLongr );
			if (  ) {
				final int usedLength = (int)( isInternal ? Math.minlengths + skip ) : length - s );
				final BitVector usedPath = bitVector.subVectorss + usedLength );
				..println"Interrogating" + ( isInternal ? "" : " leaf" ) + " <" + ( p - 1 ) + 
					", [" + Math.minlengths + skip ) + ", " 
					+ Integer.toHexStringusedPath.hashCode() ) + "] " + 
					usedPath + "> " + ( isInternal ? "" : "(skip: " + skip + ")" ) );
			}
			if ( isInternal && .getLongkey.length( 0 ).appendp - 1, . ).appendfragment = bitVector.subVectors, Math.minlengths + skip ) ) ) ) == 0 ) behaviour = ;
			else behaviour = (int).getLongkey.length( 0 ).appendp - 1, . ).appendisInternal ? fragment : bitVector.subVectorslength ) ) );
			if (  ) {
				assert ! isInternal || .getLongkey.length( 0 ).appendp - 1, . ).appendfragment ) ) != -1;
				if ( behaviour !=  ) {
					assert ! isInternal || .getLongkey.length( 0 ).appendp - 1, . ).appendfragment ) ) == 1;				
					final long result
					result = .getLongkey.length( 0 ).appendp - 1, . ).appendisInternal ? fragment : bitVector.subVectorslength ) ) ); 
					assert result != -1 : isInternal ? "Missing internal node" : "Missing leaf"// Only if you don't test with non-keys
					if ( result != -1 ) assert result == behaviour : result + " != " + behaviour;
				}
				else {
					assert s + skip <= length;
					assert .getLongkey.length( 0 ).appendp - 1, . ).appendfragment ) ) == 0;
				}
			}
			if (  ) ..println"Exit behaviour: " + behaviour );
			if ( behaviour !=  || ! isInternal || ( s += skip ) >= length ) break;
			if (  ) ..println"Turning " + ( bitVector.getBooleans ) ? "right" : "left" ) + " at bit " + s + "... " );
			if ( bitVector.getBooleans ) ) {
				final long q = .findClosep ) + 1;
				index += ( q - p ) / 2;
				r += ( q - p ) / 2;
				//System.err.println( "Increasing index by " + ( q - p + 1 ) / 2 + " to " + index + "..." );
				p = q;
			}
			else {
				lastLeftTurn = p;
				lastLeftTurnIndex = index;
				p++;
				r++;
			}
			if (  ) assert p < .length();
			s++;
		}
		if ( behaviour ==  ) {
			if (  ) ..println"Returning (on the left) " + index );
			return index;	
		}
		else {
			if ( isInternal ) {
				final long q = .findCloselastLeftTurn );
				//System.err.println( p + ", " + q + " ," + lastLeftTurn + ", " +lastLeftTurnIndex);;
				index = ( q - lastLeftTurn + 1 ) / 2 + lastLeftTurnIndex;			
				if (  ) ..println"Returning (on the right, internal) " + index );
			}
			else {
				index++;
				if (  ) ..println"Returning (on the right, external) " + index );
			}
			return index;	
		}
	}
	public long numBits() {
	}
	public boolean containsKeyObject o ) {
		return true;
	}
	public long size64() {
		return ;
	}
	public int size() {
		return (int)Math.min(  . );
	}
	public double bitsPerSkip() {
		return (double).numBits() / .size64();
	}
New to GrepCode? Check out our FAQ X