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) 2010-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 org.slf4j.Logger;
  
  import  com.martiansoftware.jsap.FlaggedOption;
  import  com.martiansoftware.jsap.JSAP;
  import  com.martiansoftware.jsap.JSAPException;
  import  com.martiansoftware.jsap.JSAPResult;
  import  com.martiansoftware.jsap.Parameter;
  import  com.martiansoftware.jsap.SimpleJSAP;
  import  com.martiansoftware.jsap.Switch;
  import  com.martiansoftware.jsap.UnflaggedOption;
  import  com.martiansoftware.jsap.stringparsers.ForNameStringParser;

A z-fast trie, that is, a predecessor/successor data structure using low linear (in the number of keys) additional space and answering to the query string x in time |x|/w + log(max{|x|, |x-|, |x+|}) with high probability, where w is the machine word size, and x-/x+ are the predecessor/successor of x in the currently stored set, respectively.

In rough terms, the z-fast trie uses time |x|/w (which is optimal) to actually look at the string content, and log(max{|x|, |x-|, |x+|}) to perform the search. This is known to be (essentially) optimal. String lengths are up to Integer.MAX_VALUE, and not limited to be a constant multiple of w for the bounds to hold.

The linear overhead of a z-fast trie is very low. For n keys we allocate 2n &minus; 1 nodes containing six references and two longs, plus a dictionary containing n &minus; 1 nodes (thus using around 2n references and 2n longs).

  
  
  public class ZFastTrie<T> extends AbstractObjectSortedSet<T> implements Serializable {
      public static final long serialVersionUID = 2L;
  	private static final Logger LOGGER = LoggerFactory.getLoggerZFastTrie.class );
  	private static final boolean ASSERTS = false;
  	private static final boolean DDDEBUG = false;
  	private static final boolean DDEBUG = false || ;
  	private static final boolean DEBUG = false || ;
If true, signatures are restricted to two bits, generating lots of false positives.
  
  	private static final boolean SHORT_SIGNATURES = false;
The mask used to extract the actual signature (the high bit marks duplicates).
  
 	private static final long SIGNATURE_MASK = 0x7FFFFFFFFFFFFFFFL;
The mask for the high bit (which marks duplicates).
 
 	private static final long DUPLICATE_MASK = 0x8000000000000000L;

The number of elements in the trie.
 
 	private int size;
The root node.
 
 	private transient Node<T> root;
The transformation strategy.
 
 	private final TransformationStrategy<? super T> transform;
A dictionary mapping handles to the corresponding internal nodes.
 
 	public transient Handle2NodeMap<T> handle2Node;
The head of the doubly linked list of leaves.
 
 	private transient Leaf<T> head;
The tail of the doubly linked list of leaves.
 
 	private transient Leaf<T> tail
 
 	private final static long shortSignaturefinal long s ) {
 		return Math.max( 1, s & 3 );
 	}

A linear-probing hash map that compares keys using signatures as a first try.
 
 	protected final static class Handle2NodeMap<U> {
 		private static final int INITIAL_LENGTH = 64;

The transformation strategy.
 
 		protected final TransformationStrategy<? super U> transform;
The node table.
 
 		protected InternalNode<U>[] node;
The signature of the handle of the corresponding entry node.
 
 		protected long[] signature;
        
The number of elements in the table.
 
 		protected int size;
The number of slots in the table (always a power of two).
 
 		protected int length;	
length &minus; 1.
 
 		protected int mask;
 
 		protected void assertTable() {
 			int c = 0;
 			forint i = .i-- != 0; ) {
 				if ( i ] != null ) {
 					assert geti ].handle ), true ) == i ] : i ] + " != " + geti ].handle ), true );
 					c++;
 				}
 			}
 			
 			assert c == size() : c + " != " + size();
 			if (  == 0 ) return;
 			final IntOpenHashSet overallHashes = new IntOpenHashSet();
 			int start = 0;
 			int first = -1;
 			whilestart ] != null ) start = ( start + 1 ) & ;
 			// We are on an empty entry
 			for( ;; ) {
 				whilestart ] == null ) start = ( start + 1 ) & ;
 				// We are on a nonempty entry
 				if ( first == -1 ) first = start;
 				else if ( first == start ) break;
 				int end = start;
 				whileend ] != null ) end = ( end + 1 ) & ;
 				// [start..end) is a maximal nonempty subsequence
 				IntOpenHashSet hashesSeen = new IntOpenHashSet();
 				LongOpenHashSet signaturesSeen = new LongOpenHashSet();
 
 				forint pos = endpos != start; ) {
 					pos = ( pos - 1 ) & ;
 					final boolean newSignature = signaturesSeen.addpos ] &  ); 
 					assert newSignature != ( ( pos ] &  ) != 0 ) : newSignature + " == " + ( ( pos ] &  ) != 0 );
 					hashesSeen.addhashpos ] &  ) );
 				}
 				
 				// Hashes in each maximal nonempty subsequence must be disjoint
 				forIntIterator iterator = hashesSeen.iterator(); iterator.hasNext(); ) assert overallHashes.additerator.nextInt() );
 				
 				start = end;
 			}
 		}

Creates a new handle-to-node map using a given transformation strategy and expected number of elements.

Parameters:
size the expected number of elements.
transform the transformation strategy used for this map.
 
 		@SuppressWarnings("unchecked")
 		public Handle2NodeMapfinal int sizeTransformationStrategy<? super U> transform ) {
 			this. = transform;
 			 = Math.max, 1 << Fast.ceilLog2( 1 + ( 3L * size / 2 ) ) );
 			 =  - 1;
 			 = new long ];
 			 = new InternalNode ];
 		}

Creates a new handle-to-node map using a given transformation strategy.

Parameters:
transform the transformation strategy used for this map.
 
 		@SuppressWarnings("unchecked")
 		public Handle2NodeMapTransformationStrategy<? super U> transform ) {
 			this. = transform;
 			 =  - 1;
 			 = new long ];
 			 = new InternalNode ];
 		}

Generates a hash table position starting from a signature.

Parameters:
s a signature.
 
 		protected int hashfinal long s ) {
 			return (int)( s ^ s >>> 32 ) & ;
 		}

Find the position in the table of a given handle using signatures.

Note that this function just compares signatures (except for duplicates, which are checked explicitly). Thus, it might return false positives when queried with keys that are not handles. Nonetheless, it will always return a correct result on a handle.

Parameters:
v a bit vector.
handleLength the length of the prefix of v that will be used as a handle.
s the signature of the prefix of v of handleLength bits.
Returns:
the position in the table where the specified handle can be found, or a position containing null.
 
 		protected int findPosfinal BitVector vfinal long handleLengthfinal long s ) {
 			int pos = hashs );
 			whilepos ] != 0 ) { // Position is not empty 
 				if ( ( pos ] &  ) == s // Same signature
 						&& ( ( pos ] &  ) == 0 // It's not a duplicate 
 								|| ( handleLength == pos ].handleLength() && // Same handle length (it's a duplicate) 
 									v.equalspos ]..key ), 0, handleLength ) ) ) ) // Same handle
 					return pos;
 				pos = ( pos + 1 ) & ;
 			}
 			return -1;
 		}


Find the position in the table of a given handle using handles.

Note that this function compares handles. Thus, it always returns a correct value.

Parameters:
v a bit vector.
handleLength the length of the prefix of v that will be used as a handle.
s the signature of the prefix of v of handleLength bits.
Returns:
the position in the table where the specified handle can be found, or a position containing null.
 
 		protected int findExactPosfinal BitVector vfinal long handleLengthfinal long s ) {
 			int pos = hashs );
 			whilepos ] != null ) { // Position is not empty
 					if ( ( pos ] &  ) == s && // Same signature
 							handleLength == pos ].handleLength() && // Same handle length
 								v.equalspos ]..key ), 0, handleLength ) ) // Same handle
 						return pos;
 				pos = ( pos + 1 ) & ;
 			}
 			return -1;
 		}
 		
 		@SuppressWarnings("unchecked")
 		public void clear() {
 			 =  - 1;
 			 = 0;
 			 = new long ];
 			 = new InternalNode ];
 		}
 
 
 						private int i = 0;
 						private int pos = -1;
 
 						public boolean hasNext() {
 							return  < ;
 						}
 
 						public LongArrayBitVector next() {
 							if ( ! hasNext() ) throw new NoSuchElementException();
 							while[ ++ ] == null );
 							++;
 							return LongArrayBitVector.copy ].handle ) );
 						}
 					};
 				}
 
 				public boolean containsObject o ) {
 					BitVector v = (BitVector)o;
 					return getvtrue ) != null;
 				}
 
 				public int size() {
 					return ;
 				}
 				
 			};
 		}
 
 		public ObjectSet<Node<U>> values() {
 			return new AbstractObjectSet<Node<U>>() {
 
 				public ObjectIterator<Node<U>> iterator() {
 					return new AbstractObjectIterator<Node<U>>() {
 						private int i = 0;
 						private int pos = -1;
 
 						public boolean hasNext() {
 							return  < ;
 						}
 
 						public Node<U> next() {
 							if ( ! hasNext() ) throw new NoSuchElementException();
 							while[ ++ ] == null );
 							++;
 							return  ];
 						}
 					};
 				}
 
 				public boolean containsObject o ) {
 					@SuppressWarnings("unchecked")
 					final Node<U> node = (Node<U>)o;
 					return getnode.handle ), true ) != null;
 				}
 
 				public int size() {
 					return ;
 				}
 			};
 		}

Replaces an entry with a given node.

Parameters:
oldNode a node appearing in the table.
newNode a node with the same handle as oldNode.
s the signature of the handle of oldNode and newNode.
 
 		public void replaceExistingfinal InternalNode<U> oldNodefinal InternalNode<U> newNodelong s ) {
 			if (  ) ..println"Map.replaceExisting(" + oldNode + ", " + newNode + ", " + s + ")" );
 			if (  ) s = shortSignatures );
 			int pos = hashs );
 			whilepos ] != oldNode ) pos = ( pos + 1 ) & ;
 			if ( pos ] == null ) throw new IllegalStateException();
 			if (  ) assert pos ].handle ).equalsnewNode.handle ) ) : pos ].handle ) + " != " + newNode.handle );
 			pos ] = newNode;
 			if (  ) assertTable();
 		}

Removes an existing entry from the table.

Parameters:
n the node to be removed.
s the signature of the handle of n.
Throws:
IllegalStateException if n is not in the table.
 
 		public void removeExistingfinal InternalNode<U> nlong s ) {
 			if (  ) ..println"Map.removeExisting(" + n + ", " + s + ")" );
 			if (  ) s = shortSignatures );
 
 			int pos = hashs );
 			int lastDup = -1; // Keeps track of the last duplicate entry with the same signature.
 
 			while ( pos ] != n ) {
 				if ( ( pos ] &  ) == s ) lastDup = pos;
 				pos = ( pos + 1 ) & ;
 			}
 
 			if ( pos ] == null ) throw new IllegalStateException();
 			if ( ( pos ] &  ) == 0 && lastDup != -1 ) lastDup ] &= ;  // We are removing the only non-duplicate entry.
 
 			// Move entries, compatibly with their hash code, to fill the hole.
 		    int candidateHoleh;
 		    do {
 				candidateHole = pos;				
 		    	// Find candidate for a move (possibly empty).
 				do {
 					pos = ( pos + 1 ) & ;
 					if ( pos ] == null ) break;
 					h = hashpos ] &  );
 					/* The hash h must lie cyclically between candidateHole and pos: more precisely, h must be after candidateHole
 					 * but before the first free entry in the table (which is equivalent to the previous statement). */
 				} whilecandidateHole <= pos ? candidateHole < h && h <= pos : candidateHole < h || h <= pos );
 				
 				candidateHole ] = pos ];
 				candidateHole ] = pos ];
 		    } whilepos ] != null );
 
 			--;
 			if (  ) assertTable();
 		}

Adds a new entry to the table.

Parameters:
v a node.
See also:
addNew(ZFastTrie.InternalNode, long)
 
 		public void addNewfinal InternalNode<U> v ) {
 			addNewvv.handleHash ) );
 		}

Adds a new entry to the table.

Note that as long as the handle of the given node is not in the table this function will always perform correctly. Otherwise, the table will end up containing two copies of the same key (i.e., handle).

Parameters:
n a node.
s the signature of the handle of n.
 
 		public void addNewfinal InternalNode<U> nlong s ) {
 			if (  ) s = shortSignatures );
 			if (  ) ..println"Map.addNew(" + n + ", " + s + ")" );
 			int pos = hashs );
 			
 			/* Finds a free position, marking the only non-duplicate key (if any) with 
 			 * the same signature along the search path as a duplicate. */
 			whilepos ] != null ) {
 				if ( pos ] == s ) pos ] |= ;
 				pos = ( pos + 1 ) & ;
 			}
 			
 			++;
 			pos ] = s;
 			pos ] = n;
 
 			if ( 3L *  > 2L *  ) {
 				// Rehash. TODO: check that it does not happen too often!
 				 *= 2;
 				 =  - 1;
 				final long newKey[] = new long ];
 				@SuppressWarnings("unchecked")
 				final InternalNode<U>[] newValue = new InternalNode ];
 				final long[] key = this.;
 				final InternalNode<U>[] value = this.;
 				
 				forint i = key.lengthi-- != 0; ) {
 					if ( valuei ] != null ) {
 						s = keyi ] & ;
 						pos = hashs ); 
 						whilenewValuepos ] != null ) {
 							if ( ( newKeypos ] &  ) == s ) newKeypos ] |= ;
 							pos = ( pos + 1 ) & ;
 						}
 						newKeypos ] = s;
 						newValuepos ] = valuei ];
 					}
 				}
 
 				this. = newKey;
 				this. = newValue;
 			}
 			
 			if (  ) assertTable();
 		}
 
 		public int size() {
 			return ;
 		}

Retrieves a node given its handle.

Parameters:
v a bit vector.
handleLength the prefix of v that must be used as a handle.
s the signature of the specified handle.
exact whether the search should be exact; if false, and the given handle does not appear in the table, it is possible that an unpredictable internal node is returned.
Returns:
the node with given handle, or null if there is no such node (if exact is false, a false positive might be returned).
 
 		public InternalNode<U> getfinal BitVector vfinal long handleLengthfinal long sfinal boolean exact ) {
 			final int pos;
 			if (  ) pos =  exact ? findExactPosvhandleLengthshortSignatures ) ) : findPosvhandleLengthshortSignatures ) );
 			else pos = exact ? findExactPosvhandleLengths ) : findPosvhandleLengths );
 			return pos == -1 ? null : pos ];
 		}
 
 		public int getPosfinal BitVector vfinal long handleLengthfinal long sfinal boolean exact ) {
 			if (  ) return exact ? findExactPosvhandleLengthshortSignatures ) ) : findPosvhandleLengthshortSignatures ) );
 			else return exact ? findExactPosvhandleLengths ) : findPosvhandleLengths );
 		}

Retrieves a node given its handle.

Parameters:
handle a handle.
exact whether the search should be exact; if false, and the given handle does not appear in the table, it is possible that an unpredictable internal node is returned.
Returns:
the node with given handle, or null if there is no such node (if exact is false, a false positive might be returned).
See also:
get(BitVector, long, long, boolean)
 
 		public InternalNode<U> getfinal BitVector handlefinal boolean exact ) {
 			return gethandlehandle.length(), Hashes.murmurhandle, 42 ) & exact );
 		}
 		
 		public String toString() {
 			s.append'{' );
 			forLongArrayBitVector vkeySet() ) s.appendv ).append" => " ).appendgetvtrue ) ).append", " );
 			if ( s.length() > 1 ) s.setLengths.length() - 2 );
 			s.append'}' );
 			return s.toString();
 		}
 	}

A node of the trie.
 
 	protected abstract static class Node<U> {
The length of the extent of the parent node, or -1 for the root.
 
 		protected long parentExtentLength;
 
 		public boolean isLeaf() {
 			return this instanceof Leaf;
 		}
 		
 		public boolean isInternal() {
 			return this instanceof InternalNode;
 		}
 
 		public long nameLength() {
 			return  + 1;
 		}
 
 		public long handleLengthTransformationStrategy<? super U> transform ) {
 			return twoFattestextentLengthtransform ) );
 		}
 
 		public abstract BitVector keyTransformationStrategy<? super U> transform );
 		public abstract BitVector handleTransformationStrategy<? super U> transform );
 		public abstract long extentLengthTransformationStrategy<? super U> transform );
 		public abstract BitVector extentTransformationStrategy<? super U> transform );
 		public abstract boolean interceptsfinal long h );
 
 		public long handleHashTransformationStrategy<? super U> transform ) {
 			if (  ) return shortSignature( Hashes.murmurhandletransform ), 42 ) );
 			else return Hashes.murmurhandletransform ), 42 ) & ;
 		}

Returns true if this node is the exit node of a string.

Parameters:
v the string.
transform the transformation strategy used to build the trie this node belongs to.
Returns:
true if the string exits at this node.
 
 		public boolean isExitNodeOffinal LongArrayBitVector vTransformationStrategy<? super U> transform ) {
 			return isExitNodeOfv.length(), v.longestCommonPrefixLengthextenttransform ) ), transform );
 		}

Returns true if this node is the exit node of a string given its length and the length of the longest common prefix with the node extent.

Parameters:
length the length of a string.
lcpLength the length of the longest common prefix between the string and the extent of this node.
Returns:
true if the string exits at this node.
 
 		public boolean isExitNodeOffinal long lengthfinal long lcpLengthTransformationStrategy<? super U> transform  ) {
 			return (  < lcpLength ) && ( lcpLength < extentLengthtransform ) || lcpLength == length );
 		}
 
 		
 		public Leaf<U> leftLeaf() {
 			Node<U> node = this;
 			whilenode.isInternal() ) node = ((InternalNode<U>)node).;
 			return (Leaf<U>)node;
 		}
 		
 		public Leaf<U> rightLeaf() {
 			Node<U> node = this;
 			whilenode.isInternal() ) node = ((InternalNode<U>)node).;
 			return ((Leaf<U>)node);
 		}
 
 		@SuppressWarnings({"rawtypes","unchecked"})
 		public String toString() {
 			Object key = isInternal() ? ((InternalNode<U>)this).. : ((Leaf<U>)this).;
 			final TransformationStrategy transform = key instanceof CharSequence ? TransformationStrategies.prefixFreeIso() : TransformationStrategies.identity();
 			final long extentLength = extentLengthtransform );
 			return ( isLeaf() ? "[" : "(" ) + Integer.toHexStringhashCode() & 0xFFFF ) + 
 				( keytransform ) == null ? "" : 
 					" " + ( extentLength > 16 ? keytransform ).subVector( 0, 8 ) + "..." + key(  transform ).subVectorextentLength - 8, extentLength ): keytransform ).subVector( 0, extentLength ) ) ) +
 					" (" +  + ".." + extentLength + "], " + ( isInternal() ? ((InternalNode<U>)this).handleLength() + "->" + ((InternalNode<U>)this).jumpLength() : "" ) +
 				( isLeaf() ? "]" : ")" );
 		}
 	}

A internal node.
 
 	protected final static class InternalNode<U> extends Node<U> {
The length of the extent (for leaves, this is equal to the length of the transformed key, which is returned by extentLength(TransformationStrategy)).
 
 		protected long extentLength;
The left subtrie.
 
 		protected Node<U> left;
The right subtrie.
 
 		protected Node<U> right;
The left jump pointer.
 
 		protected Node<U> jumpLeft;
The right jump pointer.
 
 		protected Node<U> jumpRight;
The leaf whose key this node refers to.
 
 		protected Leaf<U> reference;
 
 		public long handleLength() {
 		}
 
 		public long jumpLength() {
 			final long handleLength = handleLength();
 			if ( handleLength == 0 ) return .// This only happens on a root node with empty extent.
 			return handleLength + ( handleLength & -handleLength );
 		}
 
 		public boolean isLeaf() {
 			return false;
 		}
 		
 		public boolean isInternal() {
 			return true;
 		}
 		
 		public boolean interceptsfinal long h ) {
 			return h >  && h <= ;
 		}
 
 		public BitVector extentTransformationStrategy<? super U> transform ) {
 			return .keytransform ).subVector( 0,  );
 		}
 
 		public long extentLengthfinal TransformationStrategy<? super U> transform ) {
 			return ;
 		}
 				
 		public BitVector keyTransformationStrategy<? super U> transform ) {
 			return .keytransform );
 		}
 
 		public BitVector handleTransformationStrategy<? super U> transform ) {
 			return .keytransform ).subVector( 0, handleLength() );
 		}
 	}		

An external node, a.k.a. leaf.
 
 	protected final static class Leaf<U> extends Node<U> {
The previous leaf.
 
 		protected Leaf<U> prev;
The next leaf.
 
 		protected Leaf<U> next;
The key associated to this leaf.
 
 		protected U key;
The internal node that refers to the key of this leaf, if any. It will be null for exactly one leaf.
 
 		protected InternalNode<U> reference;
 
 		public BitVector handleTransformationStrategy<? super U> transform ) {
 			return .keytransform ).subVector( 0, handleLengthtransform ) );
 		}
 		
 		public boolean isLeaf() {
 			return true;
 		}
 		
 		public boolean isInternal() {
 			return false;
 		}
 		
 		public boolean interceptsfinal long h ) {
 			return h > ;
 		}
 
 		public BitVector extentfinal TransformationStrategy<? super U> transform ) {
 			return keytransform );
 		}
 				
 		public long extentLengthfinal TransformationStrategy<? super U> transform ) {
 			return transform.length );
 		}
 				
 		public BitVector keyfinal TransformationStrategy<? super U> transform ) {
 			return transform.toBitVector );
 		}
 	}

Creates a new z-fast trie using the given transformation strategy.

Parameters:
transform a transformation strategy that must turn distinct elements into distinct, prefix-free bit vectors.
 
 	public ZFastTriefinal TransformationStrategy<? super T> transform ) {
 		this. = transform;
 		this. = new Handle2NodeMap<T>( transform );
 	}
 	
 	private void initHeadTail() {
 		 = new Leaf<T>();
 		 = new Leaf<T>();
 		. = ;
 		. = ;
 	}

Creates a new z-fast trie using the given elements and transformation strategy.

Parameters:
elements an iterator returning the elements to be inserted in the trie.
transform a transformation strategy that must turn distinct elements into distinct, prefix-free bit vectors.
 
 	public ZFastTriefinal Iterator<? extends T> elementsfinal TransformationStrategy<? super T> transform ) {
 		thistransform );
 		whileelements.hasNext() ) addelements.next() );
 	}

Creates a new z-fast trie using the given elements and transformation strategy.

Parameters:
elements an iterator returning the elements to be inserted in the trie.
transform a transformation strategy that must turn distinct elements into distinct, prefix-free bit vectors.
 
 	public ZFastTriefinal Iterable<? extends T> elementsfinal TransformationStrategy<? super T> transform ) {
 		thiselements.iterator(), transform );
 	}
 
 	public int size() {
 		return  > . ? -1 : (int);
 	}

Returns the 2-fattest number in an interval.

Note that to get the length of the handle of a node you must call this function passing the length of the extent of the parent (one less than the node name) and the length of the extent of the node.

Parameters:
a left extreme (excluded).
b right extreme (included).
Returns:
the 2-fattest number in (a..b].
 
 	public final static long twoFattestfinal long afinal long b ) {
 		return ( -1L << Fast.mostSignificantBita ^ b ) & b );
 	}
 	
 	private static <U> void removeLeaffinal Leaf<U> node ) {
 		node.next.prev = node.prev;
 		node.prev.next = node.next;
 	}
 	
 	private static <U> void addAfterfinal Leaf<U> predfinal Leaf<U> node ) {
 		node.next = pred.next;
 		node.prev = pred;
 		pred.next.prev = node;
 		pred.next = node;
 	}
 	
 	private static <U> void addBeforefinal Leaf<U> succfinal Leaf<U> node ) {
 		node.prev = succ.prev;
 		node.next = succ;
 		succ.prev.next = node;
 		succ.prev = node;
 	}
 	
 	private void assertTrie() {
 		assert  == null || . == -1 : . + " != " + -1; 
 		/* Shortest key */
 		LongArrayBitVector root = null;
 		/* Keeps track of which nodes in map are reachable using the handle-2-node 
 		 * map first, and then left/right pointer from the root. */
 		ObjectOpenHashSet<Node<T>> nodes = new ObjectOpenHashSet<Node<T>>();
 		/* Keeps track of leaves. */
 		ObjectOpenHashSet<Leaf<T>> leaves = new ObjectOpenHashSet<Leaf<T>>();
 		/* Keeps track of reference to leaf keys in internal nodes. */
 		ObjectOpenHashSet<T> references = new ObjectOpenHashSet<T>();
 
 		assert  == 0 && .size() == 0 ||  == .size() + 1;
 		
 		/* Search for the root (shortest handle) and check that nodes and handles do match. */
 		forLongArrayBitVector v : .keySet() ) {
 			final long vHandleLength = .getvtrue ).handleLength();
 			if ( root == null || .getroottrue ).handleLength() > vHandleLength ) root = v;
 			final InternalNode<T> node = .getvtrue );
 			nodes.addnode );
 			assert node.reference.reference == node : node + " -> " + node.reference + " -> " + node.reference.reference;
 		}
 		
 		assert nodes.size() == .size() : nodes.size() + " != " + .size();
 		assert  < 2 || this. == .getroottrue );
 		
 		if (  > 1 ) {
 			/* Verify doubly linked list of leaves. */
 			Leaf<T> toRight = .toLeft = .;
 			if ( .. instanceof CharSequence ) {
 				forint i = 1; i < i++ ) {
 					assert new MutableString( (CharSequence)toRight.key ).compareTo( (CharSequence)toRight.next.key ) < 0 : toRight.key + " >= " + toRight.next.key + " " + toRight + " " + toRight.next;
 					assert new MutableString( (CharSequence)toLeft.key ).compareTo( (CharSequence)toLeft.prev.key ) > 0 : toLeft.key + " >= " + toLeft.prev.key + " " + toLeft + " " + toLeft.prev;
 					toRight = toRight.next;
 					toLeft = toLeft.prev;
 				}
 			}
 
 			final int numNodes = visit.getroottrue ), null, -1, 0, nodesleavesreferences );
 			assert numNodes == 2 *  - 1 : numNodes + " != " + ( 2 *  - 1 );
 			assert leaves.size() == ;
 			int c = 0;
 
 			forLeaf<T> leafleaves ) if ( references.containsleaf.key ) ) c++;
 
 			assert c ==  - 1 : c + " != " + (  - 1 );
 		}
 		else if (  == 1 ) {
 			assert . == this.;
 			assert . == this.;
 		}
 		assert nodes.isEmpty();
 	}
 	
 	private int visitfinal Node<T> nfinal Node<T> parentfinal long parentExtentLengthfinal int depthObjectOpenHashSet<Node<T>> nodesObjectOpenHashSet<Leaf<T>> leavesObjectOpenHashSet<T> references ) {
 		if ( n == null ) return 0;
 		if (  ) {
 			forint i = depthi-- != 0; ) ..print'\t' );
 			..println"Node " + n + " (parent extent length: " + parentExtentLength + ")" + ( n.isInternal() ? " Jump left: " + ((InternalNode<T>)n). + " Jump right: " + ((InternalNode<T>)n). : "" ) );
 		}
 
 		assert parent == null || parent.extent ).equalsn.extent ).subVector( 0, ((InternalNode<T>)parent). ) );
 		assert n ==  || parentExtentLength < n.extentLength );
 		assert n !=  || parentExtentLength <= n.extentLength );
 		assert n.parentExtentLength == parentExtentLength : n.parentExtentLength + " != " + parentExtentLength + " " + n;
 		
 		if ( n.isInternal() ) {
 			assert references.add( ((InternalNode<T>)n).. );
 			assert nodes.removen ) : n;
 			assert .keySet().containsn.handle ) ) : n;
 
 			/* Check that jumps are correct. */
 			final long jumpLength = ((InternalNode<T>)n).jumpLength();
 			Node<T> jumpLeft = ((InternalNode<T>)n).;
 			whilejumpLeft.isInternal() && jumpLength > ((InternalNode<T>)jumpLeft). ) jumpLeft = ((InternalNode<T>)jumpLeft).;
 			assert jumpLeft == ((InternalNode<T>)n). : jumpLeft + " != " + ((InternalNode<T>)n). + " (node: " + n + ")";
 
 			Node<T> jumpRight = ((InternalNode<T>)n).;
 			whilejumpRight.isInternal() && jumpLength > ((InternalNode<T>)jumpRight). ) jumpRight = ((InternalNode<T>)jumpRight).;
 			assert jumpRight == ((InternalNode<T>)n). : jumpRight + " != " + ((InternalNode<T>)n). + " (node: " + n + ")";
 			return 1 + visit( ((InternalNode<T>)n).n, ((InternalNode<T>)n).depth + 1, nodesleavesreferences ) + visit( ((InternalNode<T>)n).nn.extentLength ), depth + 1, nodesleavesreferences );
 		}
 		else {
 			assert leaves.add( (Leaf<T>)n );
 			assert n.extentLength ) == n.key ).length();
 			return 1;
 		}
 	}

Sets the jump pointers of a node by searching exhaustively for handles that are jumps of the node handle length.

Parameters:
node the node whose jump pointers must be set.
 
 	private static <U> void setJumpsfinal InternalNode<U> node ) {
 		if (  ) ..println"setJumps(" + node + ")" );
 		final long jumpLength = node.jumpLength();
 		Node<U> jump;
 
 		forjump = node.leftjump.isInternal() && jumpLength > ((InternalNode<U>)jump).; ) jump = ((InternalNode<U>)jump).;
 		if (  ) assert jump.interceptsjumpLength ) : jumpLength + " not in " + "(" + jump.parentExtentLength + ".." + ((InternalNode<U>)jump). + "] " + jump;
 		node.jumpLeft = jump;
 		forjump = node.rightjump.isInternal() && jumpLength > ((InternalNode<U>)jump).; ) jump = ((InternalNode<U>)jump).;
 		if (  ) assert jump.interceptsjumpLength ) : jumpLength + " not in " + "(" + jump.parentExtentLength + ".." + ((InternalNode<U>)jump). + "] " + jump;
 		node.jumpRight = jump;
 	}

Fixes the right jumps of the ancestors of a node after an insertion.

Parameters:
internal the new internal node.
exitNode the exit node.
rightChild whether the exit node is a right child.
leaf the new leaf.
stack a stack containing the 2-fat ancestors of the parent of the exit node.
 
 	private static <U> void fixRightJumpsAfterInsertionfinal InternalNode<U> internalNode<U> exitNodeboolean rightChildLeaf<U> leaffinal ObjectArrayList<InternalNode<U>> stack ) {
 		if (  ) ..println"fixRightJumpsAfterInsertion(" + internal + ", " + exitNode + ", " + rightChild + ", " + leaf + ", " + stack ); 
 		final long lcp = leaf.parentExtentLength;
 		InternalNode<U> toBeFixed = null;
 		long jumpLength = -1;
 
 		if ( ! rightChild ) {
 			/* Nodes jumping to the left into the exit node but above the lcp must point to internal. */
 			while( ! stack.isEmpty() ) {
 				toBeFixed = stack.pop();
 				jumpLength = toBeFixed.jumpLength();
 				if ( toBeFixed.jumpLeft != exitNode ) break;
 				if ( jumpLength <= lcp ) toBeFixed.jumpLeft = internal;
 			}
 		}
 		else {
 			while( ! stack.isEmpty() ) {
 				toBeFixed = stack.top();
 				jumpLength = toBeFixed.jumpLength();
 				if ( toBeFixed.jumpRight != exitNode || jumpLength > lcp ) break;
 				toBeFixed.jumpRight = internal;
 				stack.pop();
 			}
 
 			while( ! stack.isEmpty() ) {
 				toBeFixed = stack.pop();
 				jumpLength = toBeFixed.jumpLength();
 				whileexitNode.isInternal() && toBeFixed.jumpRight != exitNode ) exitNode = ((InternalNode<U>)exitNode).;
 				if ( toBeFixed.jumpRight != exitNode ) return;
 				toBeFixed.jumpRight = leaf;
 			}
 		}
 	}

Fixes the left jumps of the ancestors of a node after an insertion.

Parameters:
internal the new internal node.
exitNode the exit node.
rightChild whether the exit node is a right child.
leaf the new leaf.
stack a stack containing the 2-fat ancestors of the parent of the exit node.
 
 	private static <U> void fixLeftJumpsAfterInsertionfinal InternalNode<U> internalNode<U> exitNodeboolean rightChildLeaf<U> leaffinal ObjectArrayList<InternalNode<U>> stack ) {
 		if (  ) ..println"fixLeftJumpsAfterInsertion(" + internal + ", " + exitNode + ", " + rightChild + ", " + leaf + ", " + stack ); 
 		final long lcp = leaf.parentExtentLength;
 		InternalNode<U> toBeFixed = null;
 		long jumpLength = -1;
 		
 		if ( rightChild ) {
 			/* Nodes jumping to the right into the exit node but above the lcp must point to internal. */
 			while( ! stack.isEmpty() ) {
 				toBeFixed = stack.pop();
 				jumpLength = toBeFixed.jumpLength();
 				if ( toBeFixed.jumpRight != exitNode ) break;
 				if ( jumpLength <= lcp ) toBeFixed.jumpRight = internal;
 			}
 		}
 		else {
 
 			while( ! stack.isEmpty() ) {
 				toBeFixed = stack.top();
 				jumpLength = toBeFixed.jumpLength();
 				if ( toBeFixed.jumpLeft != exitNode || jumpLength > lcp ) break;
 				toBeFixed.jumpLeft = internal;
 				stack.pop();
 			}
 
 			while( ! stack.isEmpty() ) {
 				toBeFixed = stack.pop();
 				jumpLength = toBeFixed.jumpLength();
 				whileexitNode.isInternal() && toBeFixed.jumpLeft != exitNode ) exitNode = ((InternalNode<U>)exitNode).;
 				if ( toBeFixed.jumpLeft != exitNode ) return;
 				toBeFixed.jumpLeft = leaf;
 			}
 		}
 	}

Fixes the right jumps of the ancestors of a node after a deletion.

Parameters:
parentExitNode the parent of the exit node.
exitNode the exit node.
otherNode the other child of the parent of the exit node.
rightChild whether the parent of the exit node is a right child.
stack a stack containing the 2-fat ancestors of the grandparent of the exit node.
 
 	private static <U> void fixRightJumpsAfterDeletionInternalNode<U> parentExitNodeLeaf<U> exitNodeNode<U> otherNodeboolean rightChildfinal ObjectArrayList<InternalNode<U>> stack ) {
 		if (  ) ..println"fixRightJumpsAfterDeletion(" + parentExitNode + ", " + exitNode + ", " + otherNode + ", " + rightChild + ", " + stack );
 		InternalNode<U> toBeFixed = null;
 		long jumpLength = -1;
 
 		if ( ! rightChild ) {
 			/* Nodes jumping to the left into the exit node but above the lcp must point to internal. */
 			while( ! stack.isEmpty() ) {
 				toBeFixed = stack.pop();
 				jumpLength = toBeFixed.jumpLength();
 				if ( toBeFixed.jumpLeft != parentExitNode ) break;
 				toBeFixed.jumpLeft = otherNode;
 			}
 		}
 		else {
 			while( ! stack.isEmpty() ) {
 				toBeFixed = stack.top();
 				jumpLength = toBeFixed.jumpLength();
 				if ( toBeFixed.jumpRight != parentExitNode ) break;
 				toBeFixed.jumpRight = otherNode;
 				stack.pop();
 			}
 
 			while( ! stack.isEmpty() ) {
 				toBeFixed = stack.pop();
 				if ( toBeFixed.jumpRight != exitNode ) break;
 				jumpLength = toBeFixed.jumpLength();
 				while( ! otherNode.interceptsjumpLength ) ) otherNode = ((InternalNode<U>)otherNode).;
				toBeFixed.jumpRight = otherNode;
	}

Fixes the left jumps of the ancestors of a node after a deletion.

Parameters:
parentExitNode the parent of the exit node.
exitNode the exit node.
otherNode the other child of the parent of the exit node.
rightChild whether the parent of the exit node is a right child.
stack a stack containing the 2-fat ancestors of the grandparent of the exit node.
	private static <U> void fixLeftJumpsAfterDeletionInternalNode<U> parentExitNodeLeaf<U> exitNodeNode<U> otherNodeboolean rightChildfinal ObjectArrayList<InternalNode<U>> stack ) {
		if (  ) ..println"fixLeftJumpsAfterDeletion(" + parentExitNode + ", " + exitNode + ", " + otherNode + ", " + rightChild + ", " + stack );
		InternalNode<U> toBeFixed = null;
		long jumpLength = -1;
		if ( rightChild ) {
			/* Nodes jumping to the left into the exit node but above the lcp must point to internal. */
			while( ! stack.isEmpty() ) {
				toBeFixed = stack.pop();
				jumpLength = toBeFixed.jumpLength();
				if ( toBeFixed.jumpRight != parentExitNode ) break;
				toBeFixed.jumpRight = otherNode;
		else {
			while( ! stack.isEmpty() ) {
				toBeFixed = stack.top();
				jumpLength = toBeFixed.jumpLength();
				if ( toBeFixed.jumpLeft != parentExitNode ) break;
				toBeFixed.jumpLeft = otherNode;
				stack.pop();
			while( ! stack.isEmpty() ) {
				toBeFixed = stack.pop();
				if ( toBeFixed.jumpLeft != exitNode ) break;
				jumpLength = toBeFixed.jumpLength();
				while( ! otherNode.interceptsjumpLength ) ) otherNode = ((InternalNode<U>)otherNode).;
				toBeFixed.jumpLeft = otherNode;
	public boolean addfinal T k ) {
		if (  ) ..println"add(" + k + ")" );
		final LongArrayBitVector v = LongArrayBitVector.copy.toBitVectork ) );
		if (  ) ..println"add(" + v + ")" );
		if (  == 0 ) {
			final Leaf<T> leaf = new Leaf<T>();
			leaf.key = k;
			leaf.parentExtentLength = -1;
			leaf.reference = null;
			addAfterleaf );
			 = leaf;
			if (  ) {
				assert containsk ) : k;
			return true;
		final ObjectArrayList<InternalNode<T>> stack = new ObjectArrayList<InternalNode<T>>( 64 );
		InternalNode<T> parentExitNode;
		boolean rightChild;
		Node<T> exitNode;
		long lcp;
		final long[] state = Hashes.preprocessMurmurv, 42 );
		ParexData<T> parexData = getParentExitNodevstatestack );
		if (  ) assertParentvparexDatastack );
		parentExitNode = parexData.parexNode;
		exitNode = parexData.exitNode;
		lcp = parexData.lcp;
		rightChild = parentExitNode != null && parentExitNode.right == exitNode;
		if (  ) ..println"Parex node: " + parentExitNode + " Exit node: " + exitNode  + " LCP: " + lcp );
		if ( exitNode.isLeaf() && .length( ((Leaf<T>)exitNode). ) == parexData.lcp ) return false// Already there
		final boolean exitDirection = v.getBooleanlcp );
		final long exitNodeHandleLength = exitNode.handleLength );
		final boolean cutLow = lcp >= exitNodeHandleLength;
		Leaf<T> leaf = new Leaf<T>();
		InternalNode<T> internal = new InternalNode<T>();
		final boolean exitNodeIsInternal = exitNode.isInternal();
		leaf.key = k;
		leaf.parentExtentLength = lcp;
		leaf.reference = internal;
		internal.reference = leaf;
		internal.parentExtentLength = exitNode.parentExtentLength;
		internal.extentLength = lcp;
		if ( exitDirection ) {
			internal.jumpRight = internal.right = leaf;
			internal.left = exitNode;
			internal.jumpLeft = cutLow && exitNodeIsInternal ? ((InternalNode<T>)exitNode). : exitNode;
		else {
			internal.jumpLeft = internal.left = leaf;
			internal.right = exitNode;
			internal.jumpRight = cutLow && exitNodeIsInternal ? ((InternalNode<T>)exitNode). : exitNode;
		if ( exitNode ==  )  = internal// Update root
		else {
			if ( rightChild ) parentExitNode.right = internal;
			else parentExitNode.left = internal;
		if (  ) ..println"Cut " + ( cutLow ? "low" : "high") + "; exit to the " + ( exitDirection ? "right" : "left") );
		if ( exitDirection )