You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by db...@apache.org on 2016/08/30 04:47:40 UTC
[3/4] cassandra git commit: simple formatting fixes (braces)
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java
index b359416..8067ccc 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java
@@ -44,10 +44,10 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
private static final long serialVersionUID = -2303909182832019043L;
/**
- * The root node of the {@link Trie}.
+ * The root node of the {@link Trie}.
*/
final TrieEntry<K, V> root = new TrieEntry<>(null, null, -1);
-
+
/**
* Each of these fields are initialized to contain an instance of the
* appropriate view the first time this view is requested. The views are
@@ -56,52 +56,52 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
private transient volatile Set<K> keySet;
private transient volatile Collection<V> values;
private transient volatile Set<Map.Entry<K,V>> entrySet;
-
+
/**
* The current size of the {@link Trie}
*/
private int size = 0;
-
+
/**
* The number of times this {@link Trie} has been modified.
* It's used to detect concurrent modifications and fail-fast
* the {@link Iterator}s.
*/
transient int modCount = 0;
-
+
public AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)
{
super(keyAnalyzer);
}
-
+
public AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> m)
{
super(keyAnalyzer);
putAll(m);
}
-
+
@Override
public void clear()
{
root.key = null;
root.bitIndex = -1;
root.value = null;
-
+
root.parent = null;
root.left = root;
root.right = null;
root.predecessor = root;
-
+
size = 0;
incrementModCount();
}
-
+
@Override
public int size()
{
return size;
}
-
+
/**
* A helper method to increment the {@link Trie} size
* and the modification counter.
@@ -111,7 +111,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
size++;
incrementModCount();
}
-
+
/**
* A helper method to decrement the {@link Trie} size
* and increment the modification counter.
@@ -121,7 +121,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
size--;
incrementModCount();
}
-
+
/**
* A helper method to increment the modification counter.
*/
@@ -129,15 +129,15 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
++modCount;
}
-
+
@Override
public V put(K key, V value)
{
if (key == null)
throw new NullPointerException("Key cannot be null");
-
+
int lengthInBits = lengthInBits(key);
-
+
// The only place to store a key with a length
// of zero bits is the root node
if (lengthInBits == 0)
@@ -149,7 +149,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
return root.setKeyValue(key, value);
}
-
+
TrieEntry<K, V> found = getNearestEntryForKey(key);
if (compareKeys(key, found.key))
{
@@ -160,7 +160,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
return found.setKeyValue(key, value);
}
-
+
int bitIndex = bitIndex(key, found.key);
if (!Tries.isOutOfBoundsIndex(bitIndex))
{
@@ -176,7 +176,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
// A bits of the Key are zero. The only place to
// store such a Key is the root Node!
-
+
/* NULL BIT KEY */
if (root.isEmpty())
incrementSize();
@@ -184,24 +184,25 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
incrementModCount();
return root.setKeyValue(key, value);
-
+
}
else if (Tries.isEqualBitKey(bitIndex))
{
// This is a very special and rare case.
-
+
/* REPLACE OLD KEY+VALUE */
- if (found != root) {
+ if (found != root)
+ {
incrementModCount();
return found.setKeyValue(key, value);
}
}
}
-
- throw new IndexOutOfBoundsException("Failed to put: "
+
+ throw new IndexOutOfBoundsException("Failed to put: "
+ key + " -> " + value + ", " + bitIndex);
}
-
+
/**
* Adds the given {@link TrieEntry} to the {@link Trie}
*/
@@ -215,7 +216,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
if (current.bitIndex >= entry.bitIndex || current.bitIndex <= path.bitIndex)
{
entry.predecessor = entry;
-
+
if (!isBitSet(entry.key, entry.bitIndex))
{
entry.left = entry;
@@ -226,30 +227,30 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
entry.left = current;
entry.right = entry;
}
-
+
entry.parent = path;
if (current.bitIndex >= entry.bitIndex)
current.parent = entry;
-
+
// if we inserted an uplink, set the predecessor on it
if (current.bitIndex <= path.bitIndex)
current.predecessor = entry;
-
+
if (path == root || !isBitSet(entry.key, path.bitIndex))
path.left = entry;
else
path.right = entry;
-
+
return entry;
}
-
+
path = current;
-
+
current = !isBitSet(entry.key, current.bitIndex)
? current.left : current.right;
}
}
-
+
@Override
public V get(Object k)
{
@@ -261,7 +262,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
* Returns the entry associated with the specified key in the
* AbstractPatriciaTrie. Returns null if the map contains no mapping
* for this key.
- *
+ *
* This may throw ClassCastException if the object is not of type K.
*/
TrieEntry<K,V> getEntry(Object k)
@@ -269,18 +270,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
K key = Tries.cast(k);
if (key == null)
return null;
-
+
TrieEntry<K,V> entry = getNearestEntryForKey(key);
return !entry.isEmpty() && compareKeys(key, entry.key) ? entry : null;
}
-
+
@Override
public Map.Entry<K, V> select(K key)
{
Reference<Map.Entry<K, V>> reference = new Reference<>();
return !selectR(root.left, -1, key, reference) ? reference.get() : null;
}
-
+
@Override
public Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor)
{
@@ -327,11 +328,11 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
return false;
}
-
+
/**
- *
+ *
*/
- private boolean selectR(TrieEntry<K,V> h, int bitIndex,
+ private boolean selectR(TrieEntry<K,V> h, int bitIndex,
final K key, final Cursor<? super K, ? super V> cursor,
final Reference<Map.Entry<K, V>> reference)
{
@@ -377,10 +378,10 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
return selectR(h.left, h.bitIndex, key, cursor, reference);
}
}
-
+
return false;
}
-
+
@Override
public Map.Entry<K, V> traverse(Cursor<? super K, ? super V> cursor)
{
@@ -388,10 +389,10 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
while (entry != null)
{
TrieEntry<K, V> current = entry;
-
+
Decision decision = cursor.select(current);
entry = nextEntry(current);
-
+
switch(decision)
{
case EXIT:
@@ -409,21 +410,21 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
case CONTINUE: // do nothing.
}
}
-
+
return null;
}
-
+
@Override
public boolean containsKey(Object k)
{
if (k == null)
return false;
-
+
K key = Tries.cast(k);
TrieEntry<K, V> entry = getNearestEntryForKey(key);
return !entry.isEmpty() && compareKeys(key, entry.key);
}
-
+
@Override
public Set<Map.Entry<K,V>> entrySet()
{
@@ -432,7 +433,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
return entrySet;
}
-
+
@Override
public Set<K> keySet()
{
@@ -440,7 +441,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
keySet = new KeySet();
return keySet;
}
-
+
@Override
public Collection<V> values()
{
@@ -448,18 +449,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
values = new Values();
return values;
}
-
+
/**
* {@inheritDoc}
- *
- * @throws ClassCastException if provided key is of an incompatible type
+ *
+ * @throws ClassCastException if provided key is of an incompatible type
*/
@Override
public V remove(Object k)
{
if (k == null)
return null;
-
+
K key = Tries.cast(k);
TrieEntry<K, V> current = root.left;
TrieEntry<K, V> path = root;
@@ -476,17 +477,17 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
return null;
}
}
-
+
path = current;
current = !isBitSet(key, current.bitIndex) ? current.left : current.right;
}
}
-
+
/**
* Returns the nearest entry for a given key. This is useful
* for finding knowing if a given key exists (and finding the value
* for it), or for inserting the key.
- *
+ *
* The actual get implementation. This is very similar to
* selectR but with the exception that it might return the
* root Entry even if it's empty.
@@ -500,17 +501,17 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
if (current.bitIndex <= path.bitIndex)
return current;
-
+
path = current;
current = !isBitSet(key, current.bitIndex) ? current.left : current.right;
}
}
-
+
/**
* Removes a single entry from the {@link Trie}.
- *
+ *
* If we found a Key (Entry h) then figure out if it's
- * an internal (hard to remove) or external Entry (easy
+ * an internal (hard to remove) or external Entry (easy
* to remove)
*/
V removeEntry(TrieEntry<K, V> h)
@@ -526,14 +527,14 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
removeExternalEntry(h);
}
}
-
+
decrementSize();
return h.setKeyValue(null, null);
}
-
+
/**
* Removes an external entry from the {@link Trie}.
- *
+ *
* If it's an external Entry then just remove it.
* This is very easy and straight forward.
*/
@@ -546,11 +547,11 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
else if (!h.isExternalNode())
{
throw new IllegalArgumentException(h + " is not an external Entry!");
- }
-
+ }
+
TrieEntry<K, V> parent = h.parent;
TrieEntry<K, V> child = (h.left == h) ? h.right : h.left;
-
+
if (parent.left == h)
{
parent.left = child;
@@ -559,7 +560,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
parent.right = child;
}
-
+
// either the parent is changing, or the predecessor is changing.
if (child.bitIndex > parent.bitIndex)
{
@@ -569,12 +570,12 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
child.predecessor = parent;
}
-
+
}
-
+
/**
* Removes an internal entry from the {@link Trie}.
- *
+ *
* If it's an internal Entry then "good luck" with understanding
* this code. The Idea is essentially that Entry p takes Entry h's
* place in the trie which requires some re-wiring.
@@ -588,18 +589,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
else if (!h.isInternalNode())
{
throw new IllegalArgumentException(h + " is not an internal Entry!");
- }
-
+ }
+
TrieEntry<K, V> p = h.predecessor;
-
+
// Set P's bitIndex
p.bitIndex = h.bitIndex;
-
+
// Fix P's parent, predecessor and child Nodes
{
TrieEntry<K, V> parent = p.parent;
TrieEntry<K, V> child = (p.left == h) ? p.right : p.left;
-
+
// if it was looping to itself previously,
// it will now be pointed from it's parent
// (if we aren't removing it's parent --
@@ -608,7 +609,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
// predecessor.
if (p.predecessor == p && p.parent != h)
p.predecessor = p.parent;
-
+
if (parent.left == p)
{
parent.left = child;
@@ -617,23 +618,23 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
parent.right = child;
}
-
+
if (child.bitIndex > parent.bitIndex)
{
child.parent = parent;
}
}
-
+
// Fix H's parent and child Nodes
- {
- // If H is a parent of its left and right child
+ {
+ // If H is a parent of its left and right child
// then change them to P
if (h.left.parent == h)
h.left.parent = p;
if (h.right.parent == h)
h.right.parent = p;
-
+
// Change H's parent
if (h.parent.left == h)
{
@@ -644,22 +645,22 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
h.parent.right = p;
}
}
-
+
// Copy the remaining fields from H to P
//p.bitIndex = h.bitIndex;
p.parent = h.parent;
p.left = h.left;
p.right = h.right;
-
+
// Make sure that if h was pointing to any uplinks,
// p now points to them.
if (isValidUplink(p.left, p))
p.left.predecessor = p;
-
+
if (isValidUplink(p.right, p))
p.right.predecessor = p;
}
-
+
/**
* Returns the entry lexicographically after the given entry.
* If the given entry is null, returns the first node.
@@ -668,38 +669,38 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
return (node == null) ? firstEntry() : nextEntryImpl(node.predecessor, node, null);
}
-
+
/**
* Scans for the next node, starting at the specified point, and using 'previous'
* as a hint that the last node we returned was 'previous' (so we know not to return
* it again). If 'tree' is non-null, this will limit the search to the given tree.
- *
+ *
* The basic premise is that each iteration can follow the following steps:
- *
+ *
* 1) Scan all the way to the left.
* a) If we already started from this node last time, proceed to Step 2.
* b) If a valid uplink is found, use it.
* c) If the result is an empty node (root not set), break the scan.
* d) If we already returned the left node, break the scan.
- *
+ *
* 2) Check the right.
* a) If we already returned the right node, proceed to Step 3.
* b) If it is a valid uplink, use it.
* c) Do Step 1 from the right node.
- *
+ *
* 3) Back up through the parents until we encounter find a parent
* that we're not the right child of.
- *
+ *
* 4) If there's no right child of that parent, the iteration is finished.
* Otherwise continue to Step 5.
- *
+ *
* 5) Check to see if the right child is a valid uplink.
* a) If we already returned that child, proceed to Step 6.
* Otherwise, use it.
- *
+ *
* 6) If the right child of the parent is the parent itself, we've
* already found & returned the end of the Trie, so exit.
- *
+ *
* 7) Do Step 1 on the parent's right child.
*/
TrieEntry<K, V> nextEntryImpl(TrieEntry<K, V> start, TrieEntry<K, V> previous, TrieEntry<K, V> tree)
@@ -717,18 +718,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
// returned the left of this node.
if (previous == current.left)
break;
-
+
if (isValidUplink(current.left, current))
return current.left;
-
+
current = current.left;
}
}
-
+
// If there's no data at all, exit.
if (current.isEmpty())
return null;
-
+
// If we've already returned the left,
// and the immediate right is null,
// there's only one entry in the Trie
@@ -740,18 +741,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
//
if (current.right == null)
return null;
-
+
// If nothing valid on the left, try the right.
if (previous != current.right)
{
// See if it immediately is valid.
if (isValidUplink(current.right, current))
return current.right;
-
+
// Must search on the right's side if it wasn't initially valid.
return nextEntryImpl(current.right, previous, tree);
}
-
+
// Neither left nor right are valid, find the first parent
// whose child did not come from the right & traverse it.
while (current == current.parent.right)
@@ -759,33 +760,33 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
// If we're going to traverse to above the subtree, stop.
if (current == tree)
return null;
-
+
current = current.parent;
}
// If we're on the top of the subtree, we can't go any higher.
if (current == tree)
return null;
-
+
// If there's no right, the parent must be root, so we're done.
if (current.parent.right == null)
return null;
-
+
// If the parent's right points to itself, we've found one.
if (previous != current.parent.right && isValidUplink(current.parent.right, current.parent))
return current.parent.right;
-
+
// If the parent's right is itself, there can't be any more nodes.
if (current.parent.right == current.parent)
return null;
-
+
// We need to traverse down the parent's right's path.
return nextEntryImpl(current.parent.right, previous, tree);
}
-
+
/**
* Returns the first entry the {@link Trie} is storing.
- *
+ *
* This is implemented by going always to the left until
* we encounter a valid uplink. That uplink is the first key.
*/
@@ -794,9 +795,9 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
// if Trie is empty, no first node.
return isEmpty() ? null : followLeft(root);
}
-
- /**
- * Goes left through the tree until it finds a valid node.
+
+ /**
+ * Goes left through the tree until it finds a valid node.
*/
TrieEntry<K, V> followLeft(TrieEntry<K, V> node)
{
@@ -806,80 +807,80 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
// if we hit root and it didn't have a node, go right instead.
if (child.isEmpty())
child = node.right;
-
+
if (child.bitIndex <= node.bitIndex)
return child;
-
+
node = child;
}
}
-
- /**
- * Returns true if 'next' is a valid uplink coming from 'from'.
+
+ /**
+ * Returns true if 'next' is a valid uplink coming from 'from'.
*/
static boolean isValidUplink(TrieEntry<?, ?> next, TrieEntry<?, ?> from)
{
return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty();
}
-
+
/**
- * A {@link Reference} allows us to return something through a Method's
- * argument list. An alternative would be to an Array with a length of
+ * A {@link Reference} allows us to return something through a Method's
+ * argument list. An alternative would be to an Array with a length of
* one (1) but that leads to compiler warnings. Computationally and memory
- * wise there's no difference (except for the need to load the
+ * wise there's no difference (except for the need to load the
* {@link Reference} Class but that happens only once).
*/
private static class Reference<E>
{
-
+
private E item;
-
+
public void set(E item)
{
this.item = item;
}
-
+
public E get()
{
return item;
}
}
-
+
/**
* A {@link Trie} is a set of {@link TrieEntry} nodes
*/
static class TrieEntry<K,V> extends BasicEntry<K, V>
{
-
+
private static final long serialVersionUID = 4596023148184140013L;
-
+
/** The index this entry is comparing. */
protected int bitIndex;
-
+
/** The parent of this entry. */
protected TrieEntry<K,V> parent;
-
+
/** The left child of this entry. */
protected TrieEntry<K,V> left;
-
+
/** The right child of this entry. */
protected TrieEntry<K,V> right;
-
- /** The entry who uplinks to this entry. */
+
+ /** The entry who uplinks to this entry. */
protected TrieEntry<K,V> predecessor;
-
+
public TrieEntry(K key, V value, int bitIndex)
{
super(key, value);
-
+
this.bitIndex = bitIndex;
-
+
this.parent = null;
this.left = this;
this.right = null;
this.predecessor = this;
}
-
+
/**
* Whether or not the entry is storing a key.
* Only the root can potentially be empty, all other
@@ -889,27 +890,27 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
return key == null;
}
-
- /**
- * Neither the left nor right child is a loopback
+
+ /**
+ * Neither the left nor right child is a loopback
*/
public boolean isInternalNode()
{
return left != this && right != this;
}
-
- /**
- * Either the left or right child is a loopback
+
+ /**
+ * Either the left or right child is a loopback
*/
public boolean isExternalNode()
{
return !isInternalNode();
}
}
-
+
/**
- * This is a entry set view of the {@link Trie} as returned
+ * This is a entry set view of the {@link Trie} as returned
* by {@link Map#entrySet()}
*/
private class EntrySet extends AbstractSet<Map.Entry<K,V>>
@@ -919,17 +920,17 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
return new EntryIterator();
}
-
+
@Override
public boolean contains(Object o)
{
if (!(o instanceof Map.Entry))
return false;
-
+
TrieEntry<K,V> candidate = getEntry(((Map.Entry<?, ?>)o).getKey());
return candidate != null && candidate.equals(o);
}
-
+
@Override
public boolean remove(Object o)
{
@@ -937,19 +938,19 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
AbstractPatriciaTrie.this.remove(o);
return size != size();
}
-
+
@Override
public int size()
{
return AbstractPatriciaTrie.this.size();
}
-
+
@Override
public void clear()
{
AbstractPatriciaTrie.this.clear();
}
-
+
/**
* An {@link Iterator} that returns {@link Entry} Objects
*/
@@ -962,9 +963,9 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
}
}
}
-
+
/**
- * This is a key set view of the {@link Trie} as returned
+ * This is a key set view of the {@link Trie} as returned
* by {@link Map#keySet()}
*/
private class KeySet extends AbstractSet<K>
@@ -974,19 +975,19 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
return new KeyIterator();
}
-
+
@Override
public int size()
{
return AbstractPatriciaTrie.this.size();
}
-
+
@Override
public boolean contains(Object o)
{
return containsKey(o);
}
-
+
@Override
public boolean remove(Object o)
{
@@ -994,13 +995,13 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
AbstractPatriciaTrie.this.remove(o);
return size != size();
}
-
+
@Override
public void clear()
{
AbstractPatriciaTrie.this.clear();
}
-
+
/**
* An {@link Iterator} that returns Key Objects
*/
@@ -1013,9 +1014,9 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
}
}
}
-
+
/**
- * This is a value view of the {@link Trie} as returned
+ * This is a value view of the {@link Trie} as returned
* by {@link Map#values()}
*/
private class Values extends AbstractCollection<V>
@@ -1025,25 +1026,25 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
return new ValueIterator();
}
-
+
@Override
public int size()
{
return AbstractPatriciaTrie.this.size();
}
-
+
@Override
public boolean contains(Object o)
{
return containsValue(o);
}
-
+
@Override
public void clear()
{
AbstractPatriciaTrie.this.clear();
}
-
+
@Override
public boolean remove(Object o)
{
@@ -1058,7 +1059,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
}
return false;
}
-
+
/**
* An {@link Iterator} that returns Value Objects
*/
@@ -1071,9 +1072,9 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
}
}
}
-
- /**
- * An iterator for the entries.
+
+ /**
+ * An iterator for the entries.
*/
abstract class TrieIterator<E> implements Iterator<E>
{
@@ -1081,10 +1082,10 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
* For fast-fail
*/
protected int expectedModCount = AbstractPatriciaTrie.this.modCount;
-
+
protected TrieEntry<K, V> next; // the next node to return
protected TrieEntry<K, V> current; // the current entry we're on
-
+
/**
* Starts iteration from the root
*/
@@ -1092,7 +1093,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
next = AbstractPatriciaTrie.this.nextEntry(null);
}
-
+
/**
* Starts iteration at the given entry
*/
@@ -1100,7 +1101,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
next = firstEntry;
}
-
+
/**
* Returns the next {@link TrieEntry}
*/
@@ -1108,16 +1109,16 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
if (expectedModCount != AbstractPatriciaTrie.this.modCount)
throw new ConcurrentModificationException();
-
+
TrieEntry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
-
+
next = findNext(e);
current = e;
return e;
}
-
+
/**
* @see PatriciaTrie#nextEntry(TrieEntry)
*/
@@ -1125,26 +1126,26 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
{
return AbstractPatriciaTrie.this.nextEntry(prior);
}
-
+
@Override
public boolean hasNext()
{
return next != null;
}
-
+
@Override
public void remove()
{
if (current == null)
throw new IllegalStateException();
-
+
if (expectedModCount != AbstractPatriciaTrie.this.modCount)
throw new ConcurrentModificationException();
-
+
TrieEntry<K, V> node = current;
current = null;
AbstractPatriciaTrie.this.removeEntry(node);
-
+
expectedModCount = AbstractPatriciaTrie.this.modCount;
}
}
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java
index 0bf9c20..f24ec14 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java
@@ -29,74 +29,75 @@ import java.util.Map;
*/
/**
- * This class provides some basic {@link Trie} functionality and
+ * This class provides some basic {@link Trie} functionality and
* utility methods for actual {@link Trie} implementations.
*/
abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializable, Trie<K, V>
{
private static final long serialVersionUID = -6358111100045408883L;
-
+
/**
- * The {@link KeyAnalyzer} that's being used to build the
+ * The {@link KeyAnalyzer} that's being used to build the
* PATRICIA {@link Trie}
*/
protected final KeyAnalyzer<? super K> keyAnalyzer;
-
- /**
- * Constructs a new {@link Trie} using the given {@link KeyAnalyzer}
+
+ /**
+ * Constructs a new {@link Trie} using the given {@link KeyAnalyzer}
*/
public AbstractTrie(KeyAnalyzer<? super K> keyAnalyzer)
{
this.keyAnalyzer = Tries.notNull(keyAnalyzer, "keyAnalyzer");
}
-
+
@Override
public K selectKey(K key)
{
Map.Entry<K, V> entry = select(key);
return entry != null ? entry.getKey() : null;
}
-
+
@Override
public V selectValue(K key)
{
Map.Entry<K, V> entry = select(key);
return entry != null ? entry.getValue() : null;
}
-
+
@Override
public String toString()
{
StringBuilder buffer = new StringBuilder();
buffer.append("Trie[").append(size()).append("]={\n");
- for (Map.Entry<K, V> entry : entrySet()) {
+ for (Map.Entry<K, V> entry : entrySet())
+ {
buffer.append(" ").append(entry).append("\n");
}
buffer.append("}\n");
return buffer.toString();
}
-
+
/**
* Returns the length of the given key in bits
- *
+ *
* @see KeyAnalyzer#lengthInBits(Object)
*/
final int lengthInBits(K key)
{
return key == null ? 0 : keyAnalyzer.lengthInBits(key);
}
-
+
/**
- * Returns whether or not the given bit on the
+ * Returns whether or not the given bit on the
* key is set or false if the key is null.
- *
+ *
* @see KeyAnalyzer#isBitSet(Object, int)
*/
final boolean isBitSet(K key, int bitIndex)
{
return key != null && keyAnalyzer.isBitSet(key, bitIndex);
}
-
+
/**
* Utility method for calling {@link KeyAnalyzer#bitIndex(Object, Object)}
*/
@@ -104,7 +105,7 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa
{
if (key != null && otherKey != null)
{
- return keyAnalyzer.bitIndex(key, otherKey);
+ return keyAnalyzer.bitIndex(key, otherKey);
}
else if (key != null)
{
@@ -114,10 +115,10 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa
{
return bitIndex(otherKey);
}
-
+
return KeyAnalyzer.NULL_BIT_KEY;
}
-
+
private int bitIndex(K key)
{
int lengthInBits = lengthInBits(key);
@@ -126,10 +127,10 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa
if (isBitSet(key, i))
return i;
}
-
+
return KeyAnalyzer.NULL_BIT_KEY;
}
-
+
/**
* An utility method for calling {@link KeyAnalyzer#compare(Object, Object)}
*/
@@ -143,10 +144,10 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa
{
return false;
}
-
+
return keyAnalyzer.compare(key, other) == 0;
}
-
+
/**
* A basic implementation of {@link Entry}
*/
@@ -155,17 +156,17 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa
private static final long serialVersionUID = -944364551314110330L;
protected K key;
-
+
protected V value;
-
+
private transient int hashCode = 0;
-
+
public BasicEntry(K key, V value)
{
this.key = key;
this.value = value;
}
-
+
/**
* Replaces the current key and value with the provided
* key & value
@@ -176,19 +177,19 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa
this.hashCode = 0;
return setValue(value);
}
-
+
@Override
public K getKey()
{
return key;
}
-
+
@Override
public V getValue()
{
return value;
}
-
+
@Override
public V setValue(V value)
{
@@ -196,7 +197,7 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa
this.value = value;
return previous;
}
-
+
@Override
public int hashCode()
{
@@ -204,7 +205,7 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa
hashCode = (key != null ? key.hashCode() : 0);
return hashCode;
}
-
+
@Override
public boolean equals(Object o)
{
@@ -216,11 +217,11 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa
{
return false;
}
-
+
Map.Entry<?, ?> other = (Map.Entry<?, ?>)o;
return Tries.areEqual(key, other.getKey()) && Tries.areEqual(value, other.getValue());
}
-
+
@Override
public String toString()
{
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java
index 513fae0..dde3c8a 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java
@@ -28,39 +28,39 @@ import java.util.Map.Entry;
*/
/**
- * A {@link Cursor} can be used to traverse a {@link Trie}, visit each node
- * step by step and make {@link Decision}s on each step how to continue with
+ * A {@link Cursor} can be used to traverse a {@link Trie}, visit each node
+ * step by step and make {@link Decision}s on each step how to continue with
* traversing the {@link Trie}.
*/
public interface Cursor<K, V>
{
-
+
/**
- * The {@link Decision} tells the {@link Cursor} what to do on each step
+ * The {@link Decision} tells the {@link Cursor} what to do on each step
* while traversing the {@link Trie}.
- *
- * NOTE: Not all operations that work with a {@link Cursor} support all
+ *
+ * NOTE: Not all operations that work with a {@link Cursor} support all
* {@link Decision} types
*/
enum Decision
{
-
+
/**
* Exit the traverse operation
*/
- EXIT,
-
+ EXIT,
+
/**
* Continue with the traverse operation
*/
- CONTINUE,
-
+ CONTINUE,
+
/**
* Remove the previously returned element
* from the {@link Trie} and continue
*/
- REMOVE,
-
+ REMOVE,
+
/**
* Remove the previously returned element
* from the {@link Trie} and exit from the
@@ -68,15 +68,15 @@ public interface Cursor<K, V>
*/
REMOVE_AND_EXIT
}
-
+
/**
- * Called for each {@link Entry} in the {@link Trie}. Return
+ * Called for each {@link Entry} in the {@link Trie}. Return
* {@link Decision#EXIT} to finish the {@link Trie} operation,
* {@link Decision#CONTINUE} to go to the next {@link Entry},
* {@link Decision#REMOVE} to remove the {@link Entry} and
* continue iterating or {@link Decision#REMOVE_AND_EXIT} to
* remove the {@link Entry} and stop iterating.
- *
+ *
* Note: Not all operations support {@link Decision#REMOVE}.
*/
Decision select(Map.Entry<? extends K, ? extends V> entry);
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java
index 9cab4ae..c6ef665 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java
@@ -37,36 +37,36 @@ public interface KeyAnalyzer<K> extends Comparator<K>
* bits were all zero (0).
*/
int NULL_BIT_KEY = -1;
-
- /**
+
+ /**
* Returned by {@link #bitIndex(Object, Object)} if a the
* bits of two keys were all equal.
*/
int EQUAL_BIT_KEY = -2;
-
+
/**
- * Returned by {@link #bitIndex(Object, Object)} if a keys
+ * Returned by {@link #bitIndex(Object, Object)} if a keys
* indices are out of bounds.
*/
int OUT_OF_BOUNDS_BIT_KEY = -3;
-
+
/**
* Returns the key's length in bits.
*/
int lengthInBits(K key);
-
+
/**
* Returns {@code true} if a key's bit it set at the given index.
*/
boolean isBitSet(K key, int bitIndex);
-
+
/**
* Returns the index of the first bit that is different in the two keys.
*/
int bitIndex(K key, K otherKey);
-
+
/**
- * Returns {@code true} if the second argument is a
+ * Returns {@code true} if the second argument is a
* prefix of the first argument.
*/
boolean isPrefix(K key, K prefix);
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java
index 3c672ec..9187894 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java
@@ -29,98 +29,98 @@ import java.util.*;
/**
* <h3>PATRICIA {@link Trie}</h3>
- *
+ *
* <i>Practical Algorithm to Retrieve Information Coded in Alphanumeric</i>
- *
- * <p>A PATRICIA {@link Trie} is a compressed {@link Trie}. Instead of storing
- * all data at the edges of the {@link Trie} (and having empty internal nodes),
- * PATRICIA stores data in every node. This allows for very efficient traversal,
- * insert, delete, predecessor, successor, prefix, range, and {@link #select(Object)}
- * operations. All operations are performed at worst in O(K) time, where K
- * is the number of bits in the largest item in the tree. In practice,
- * operations actually take O(A(K)) time, where A(K) is the average number of
+ *
+ * <p>A PATRICIA {@link Trie} is a compressed {@link Trie}. Instead of storing
+ * all data at the edges of the {@link Trie} (and having empty internal nodes),
+ * PATRICIA stores data in every node. This allows for very efficient traversal,
+ * insert, delete, predecessor, successor, prefix, range, and {@link #select(Object)}
+ * operations. All operations are performed at worst in O(K) time, where K
+ * is the number of bits in the largest item in the tree. In practice,
+ * operations actually take O(A(K)) time, where A(K) is the average number of
* bits of all items in the tree.
- *
+ *
* <p>Most importantly, PATRICIA requires very few comparisons to keys while
- * doing any operation. While performing a lookup, each comparison (at most
- * K of them, described above) will perform a single bit comparison against
+ * doing any operation. While performing a lookup, each comparison (at most
+ * K of them, described above) will perform a single bit comparison against
* the given key, instead of comparing the entire key to another key.
- *
- * <p>The {@link Trie} can return operations in lexicographical order using the
- * {@link #traverse(Cursor)}, 'prefix', 'submap', or 'iterator' methods. The
- * {@link Trie} can also scan for items that are 'bitwise' (using an XOR
- * metric) by the 'select' method. Bitwise closeness is determined by the
- * {@link KeyAnalyzer} returning true or false for a bit being set or not in
+ *
+ * <p>The {@link Trie} can return operations in lexicographical order using the
+ * {@link #traverse(Cursor)}, 'prefix', 'submap', or 'iterator' methods. The
+ * {@link Trie} can also scan for items that are 'bitwise' (using an XOR
+ * metric) by the 'select' method. Bitwise closeness is determined by the
+ * {@link KeyAnalyzer} returning true or false for a bit being set or not in
* a given key.
- *
- * <p>Any methods here that take an {@link Object} argument may throw a
- * {@link ClassCastException} if the method is expecting an instance of K
+ *
+ * <p>Any methods here that take an {@link Object} argument may throw a
+ * {@link ClassCastException} if the method is expecting an instance of K
* and it isn't K.
- *
+ *
* @see <a href="http://en.wikipedia.org/wiki/Radix_tree">Radix Tree</a>
* @see <a href="http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA">PATRICIA</a>
* @see <a href="http://www.imperialviolet.org/binary/critbit.pdf">Crit-Bit Tree</a>
- *
+ *
* @author Roger Kapsi
* @author Sam Berlin
*/
public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Serializable
{
private static final long serialVersionUID = -2246014692353432660L;
-
+
public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)
{
super(keyAnalyzer);
}
-
+
public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> m)
{
super(keyAnalyzer, m);
}
-
+
@Override
public Comparator<? super K> comparator()
{
return keyAnalyzer;
}
-
+
@Override
public SortedMap<K, V> prefixMap(K prefix)
{
return lengthInBits(prefix) == 0 ? this : new PrefixRangeMap(prefix);
}
-
+
@Override
public K firstKey()
{
return firstEntry().getKey();
}
-
+
@Override
public K lastKey()
{
TrieEntry<K, V> entry = lastEntry();
return entry != null ? entry.getKey() : null;
}
-
+
@Override
public SortedMap<K, V> headMap(K toKey)
{
return new RangeEntryMap(null, toKey);
}
-
+
@Override
public SortedMap<K, V> subMap(K fromKey, K toKey)
{
return new RangeEntryMap(fromKey, toKey);
}
-
+
@Override
public SortedMap<K, V> tailMap(K fromKey)
{
return new RangeEntryMap(fromKey, null);
- }
-
+ }
+
/**
* Returns an entry strictly higher than the given key,
* or null if no such entry exists.
@@ -128,10 +128,10 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
private TrieEntry<K,V> higherEntry(K key)
{
// TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
+ // tree. (We do it here because there are other well-defined
// functions to perform the search.)
int lengthInBits = lengthInBits(key);
-
+
if (lengthInBits == 0)
{
if (!root.isEmpty())
@@ -145,11 +145,11 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return firstEntry();
}
}
-
+
TrieEntry<K, V> found = getNearestEntryForKey(key);
if (compareKeys(key, found.key))
return nextEntry(found);
-
+
int bitIndex = bitIndex(key, found.key);
if (Tries.isValidBitIndex(bitIndex))
{
@@ -178,7 +178,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + key);
}
-
+
/**
* Returns a key-value mapping associated with the least key greater
* than or equal to the given key, or null if there is no such key.
@@ -199,12 +199,12 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
// These steps ensure that the returned value is either the
// entry for the key itself, or the first entry directly after
// the key.
-
+
// TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
+ // tree. (We do it here because there are other well-defined
// functions to perform the search.)
int lengthInBits = lengthInBits(key);
-
+
if (lengthInBits == 0)
{
if (!root.isEmpty())
@@ -216,11 +216,11 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return firstEntry();
}
}
-
+
TrieEntry<K, V> found = getNearestEntryForKey(key);
if (compareKeys(key, found.key))
return found;
-
+
int bitIndex = bitIndex(key, found.key);
if (Tries.isValidBitIndex(bitIndex))
{
@@ -267,7 +267,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
modCount -= 2; // we didn't really modify it.
return prior;
}
-
+
/**
* Returns a key-value mapping associated with the greatest key
* strictly less than the given key, or null if there is no such key.
@@ -287,19 +287,19 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
//
// These steps ensure that the returned value is always just before
// the key or null (if there was nothing before it).
-
+
// TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
+ // tree. (We do it here because there are other well-defined
// functions to perform the search.)
int lengthInBits = lengthInBits(key);
-
+
if (lengthInBits == 0)
return null; // there can never be anything before root.
-
+
TrieEntry<K, V> found = getNearestEntryForKey(key);
if (compareKeys(key, found.key))
return previousEntry(found);
-
+
int bitIndex = bitIndex(key, found.key);
if (Tries.isValidBitIndex(bitIndex))
{
@@ -317,26 +317,26 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + key);
}
-
+
/**
* Returns a key-value mapping associated with the greatest key
* less than or equal to the given key, or null if there is no such key.
*/
- TrieEntry<K,V> floorEntry(K key) {
+ TrieEntry<K,V> floorEntry(K key) {
// TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
+ // tree. (We do it here because there are other well-defined
// functions to perform the search.)
int lengthInBits = lengthInBits(key);
-
+
if (lengthInBits == 0)
{
return !root.isEmpty() ? root : null;
}
-
+
TrieEntry<K, V> found = getNearestEntryForKey(key);
if (compareKeys(key, found.key))
return found;
-
+
int bitIndex = bitIndex(key, found.key);
if (Tries.isValidBitIndex(bitIndex))
{
@@ -361,56 +361,56 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + key);
}
-
+
/**
* Finds the subtree that contains the prefix.
- *
+ *
* This is very similar to getR but with the difference that
* we stop the lookup if h.bitIndex > lengthInBits.
*/
private TrieEntry<K, V> subtree(K prefix)
{
int lengthInBits = lengthInBits(prefix);
-
+
TrieEntry<K, V> current = root.left;
TrieEntry<K, V> path = root;
while(true)
{
if (current.bitIndex <= path.bitIndex || lengthInBits < current.bitIndex)
break;
-
+
path = current;
current = !isBitSet(prefix, current.bitIndex)
? current.left : current.right;
- }
+ }
// Make sure the entry is valid for a subtree.
TrieEntry<K, V> entry = current.isEmpty() ? path : current;
-
+
// If entry is root, it can't be empty.
if (entry.isEmpty())
return null;
-
+
// if root && length of root is less than length of lookup,
// there's nothing.
// (this prevents returning the whole subtree if root has an empty
// string and we want to lookup things with "\0")
if (entry == root && lengthInBits(entry.getKey()) < lengthInBits)
return null;
-
+
// Found key's length-th bit differs from our key
// which means it cannot be the prefix...
if (isBitSet(prefix, lengthInBits) != isBitSet(entry.key, lengthInBits))
return null;
-
+
// ... or there are less than 'length' equal bits
int bitIndex = bitIndex(prefix, entry.key);
return (bitIndex >= 0 && bitIndex < lengthInBits) ? null : entry;
}
-
+
/**
* Returns the last entry the {@link Trie} is storing.
- *
+ *
* <p>This is implemented by going always to the right until
* we encounter a valid uplink. That uplink is the last key.
*/
@@ -418,7 +418,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
{
return followRight(root.left);
}
-
+
/**
* Traverses down the right path until it finds an uplink.
*/
@@ -427,40 +427,40 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
// if Trie is empty, no last entry.
if (node.right == null)
return null;
-
+
// Go as far right as possible, until we encounter an uplink.
while (node.right.bitIndex > node.bitIndex)
{
node = node.right;
}
-
+
return node.right;
}
-
+
/**
* Returns the node lexicographically before the given node (or null if none).
- *
+ *
* This follows four simple branches:
* - If the uplink that returned us was a right uplink:
* - If predecessor's left is a valid uplink from predecessor, return it.
* - Else, follow the right path from the predecessor's left.
* - If the uplink that returned us was a left uplink:
- * - Loop back through parents until we encounter a node where
+ * - Loop back through parents until we encounter a node where
* node != node.parent.left.
* - If node.parent.left is uplink from node.parent:
* - If node.parent.left is not root, return it.
* - If it is root & root isEmpty, return null.
* - If it is root & root !isEmpty, return root.
* - If node.parent.left is not uplink from node.parent:
- * - Follow right path for first right child from node.parent.left
- *
+ * - Follow right path for first right child from node.parent.left
+ *
* @param start the start entry
*/
private TrieEntry<K, V> previousEntry(TrieEntry<K, V> start)
{
if (start.predecessor == null)
throw new IllegalArgumentException("must have come from somewhere!");
-
+
if (start.predecessor.right == start)
{
return isValidUplink(start.predecessor.left, start.predecessor)
@@ -493,11 +493,11 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return followRight(node.parent.left);
}
}
-
+
/**
* Returns the entry lexicographically after the given entry.
* If the given entry is null, returns the first node.
- *
+ *
* This will traverse only within the subtree. If the given node
* is not within the subtree, this will have undefined results.
*/
@@ -505,12 +505,12 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
{
return (node == null) ? firstEntry() : nextEntryImpl(node.predecessor, node, parentOfSubtree);
}
-
+
private boolean isPrefix(K key, K prefix)
{
return keyAnalyzer.isPrefix(key, prefix);
}
-
+
/**
* A range view of the {@link Trie}
*/
@@ -522,7 +522,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
private transient volatile Set<Map.Entry<K, V>> entrySet;
/**
- * Creates and returns an {@link #entrySet()}
+ * Creates and returns an {@link #entrySet()}
* view of the {@link RangeMap}
*/
protected abstract Set<Map.Entry<K, V>> createEntrySet();
@@ -531,47 +531,47 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
* Returns the FROM Key
*/
protected abstract K getFromKey();
-
+
/**
* Whether or not the {@link #getFromKey()} is in the range
*/
protected abstract boolean isFromInclusive();
-
+
/**
* Returns the TO Key
*/
protected abstract K getToKey();
-
+
/**
* Whether or not the {@link #getToKey()} is in the range
*/
protected abstract boolean isToInclusive();
-
-
+
+
@Override
public Comparator<? super K> comparator()
{
return PatriciaTrie.this.comparator();
}
-
+
@Override
public boolean containsKey(Object key)
{
return inRange(Tries.<K>cast(key)) && PatriciaTrie.this.containsKey(key);
}
-
+
@Override
public V remove(Object key)
{
return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.remove(key);
}
-
+
@Override
public V get(Object key)
{
return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.get(key);
}
-
+
@Override
public V put(K key, V value)
{
@@ -580,7 +580,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return PatriciaTrie.this.put(key, value);
}
-
+
@Override
public Set<Map.Entry<K, V>> entrySet()
{
@@ -588,7 +588,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
entrySet = createEntrySet();
return entrySet;
}
-
+
@Override
public SortedMap<K, V> subMap(K fromKey, K toKey)
{
@@ -600,7 +600,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return createRangeMap(fromKey, isFromInclusive(), toKey, isToInclusive());
}
-
+
@Override
public SortedMap<K, V> headMap(K toKey)
{
@@ -609,7 +609,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return createRangeMap(getFromKey(), isFromInclusive(), toKey, isToInclusive());
}
-
+
@Override
public SortedMap<K, V> tailMap(K fromKey)
{
@@ -645,7 +645,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
}
/**
- * Returns true if the provided key is in the FROM range
+ * Returns true if the provided key is in the FROM range
* of the {@link RangeMap}
*/
protected boolean inFromRange(K key, boolean forceInclusive)
@@ -658,7 +658,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
}
/**
- * Returns true if the provided key is in the TO range
+ * Returns true if the provided key is in the TO range
* of the {@link RangeMap}
*/
protected boolean inToRange(K key, boolean forceInclusive)
@@ -675,32 +675,32 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
*/
protected abstract SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);
}
-
+
/**
* A {@link RangeMap} that deals with {@link Entry}s
*/
private class RangeEntryMap extends RangeMap
{
- /**
- * The key to start from, null if the beginning.
+ /**
+ * The key to start from, null if the beginning.
*/
protected final K fromKey;
-
- /**
- * The key to end at, null if till the end.
+
+ /**
+ * The key to end at, null if till the end.
*/
protected final K toKey;
-
- /**
- * Whether or not the 'from' is inclusive.
+
+ /**
+ * Whether or not the 'from' is inclusive.
*/
protected final boolean fromInclusive;
-
- /**
- * Whether or not the 'to' is inclusive.
+
+ /**
+ * Whether or not the 'to' is inclusive.
*/
protected final boolean toInclusive;
-
+
/**
* Creates a {@link RangeEntryMap} with the fromKey included and
* the toKey excluded from the range
@@ -709,7 +709,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
{
this(fromKey, true, toKey, false);
}
-
+
/**
* Creates a {@link RangeEntryMap}
*/
@@ -717,24 +717,24 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
{
if (fromKey == null && toKey == null)
throw new IllegalArgumentException("must have a from or to!");
-
+
if (fromKey != null && toKey != null && keyAnalyzer.compare(fromKey, toKey) > 0)
throw new IllegalArgumentException("fromKey > toKey");
-
+
this.fromKey = fromKey;
this.fromInclusive = fromInclusive;
this.toKey = toKey;
this.toInclusive = toInclusive;
}
-
-
+
+
@Override
public K firstKey()
{
Map.Entry<K,V> e = fromKey == null
? firstEntry()
: fromInclusive ? ceilingEntry(fromKey) : higherEntry(fromKey);
-
+
K first = e != null ? e.getKey() : null;
if (e == null || toKey != null && !inToRange(first, false))
throw new NoSuchElementException();
@@ -742,58 +742,58 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return first;
}
-
+
@Override
public K lastKey()
{
Map.Entry<K,V> e = toKey == null
? lastEntry()
: toInclusive ? floorEntry(toKey) : lowerEntry(toKey);
-
+
K last = e != null ? e.getKey() : null;
if (e == null || fromKey != null && !inFromRange(last, false))
throw new NoSuchElementException();
return last;
}
-
+
@Override
protected Set<Entry<K, V>> createEntrySet()
{
return new RangeEntrySet(this);
}
-
+
@Override
public K getFromKey()
{
return fromKey;
}
-
+
@Override
public K getToKey()
{
return toKey;
}
-
+
@Override
public boolean isFromInclusive()
{
return fromInclusive;
}
-
+
@Override
public boolean isToInclusive()
{
return toInclusive;
}
-
+
@Override
protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
{
return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
}
}
-
+
/**
* A {@link Set} view of a {@link RangeMap}
*/
@@ -816,7 +816,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
this.delegate = delegate;
}
-
+
@Override
public Iterator<Map.Entry<K, V>> iterator()
{
@@ -830,7 +830,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return new EntryIterator(first, last);
}
-
+
@Override
public int size()
{
@@ -848,13 +848,13 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return size;
}
-
+
@Override
public boolean isEmpty()
{
return !iterator().hasNext();
}
-
+
@Override
public boolean contains(Object o)
{
@@ -870,7 +870,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
TrieEntry<K, V> node = getEntry(key);
return node != null && Tries.areEqual(node.getValue(), entry.getValue());
}
-
+
@Override
public boolean remove(Object o)
{
@@ -892,9 +892,9 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return false;
}
-
- /**
- * An {@link Iterator} for {@link RangeEntrySet}s.
+
+ /**
+ * An {@link Iterator} for {@link RangeEntrySet}s.
*/
private final class EntryIterator extends TrieIterator<Map.Entry<K,V>>
{
@@ -908,40 +908,40 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
super(first);
this.excludedKey = (last != null ? last.getKey() : null);
}
-
+
@Override
public boolean hasNext()
{
return next != null && !Tries.areEqual(next.key, excludedKey);
}
-
+
@Override
public Map.Entry<K,V> next()
{
if (next == null || Tries.areEqual(next.key, excludedKey))
throw new NoSuchElementException();
-
+
return nextEntry();
}
}
- }
-
- /**
- * A submap used for prefix views over the {@link Trie}.
+ }
+
+ /**
+ * A submap used for prefix views over the {@link Trie}.
*/
private class PrefixRangeMap extends RangeMap
{
-
+
private final K prefix;
-
+
private K fromKey = null;
-
+
private K toKey = null;
-
+
private int expectedModCount = -1;
-
+
private int size = -1;
-
+
/**
* Creates a {@link PrefixRangeMap}
*/
@@ -949,11 +949,11 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
{
this.prefix = prefix;
}
-
+
/**
* This method does two things. It determinates the FROM
* and TO range of the {@link PrefixRangeMap} and the number
- * of elements in the range. This method must be called every
+ * of elements in the range. This method must be called every
* time the {@link Trie} has changed.
*/
private int fixup()
@@ -964,69 +964,69 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
{
Iterator<Map.Entry<K, V>> it = entrySet().iterator();
size = 0;
-
+
Map.Entry<K, V> entry = null;
if (it.hasNext())
{
entry = it.next();
size = 1;
}
-
+
fromKey = entry == null ? null : entry.getKey();
if (fromKey != null)
{
TrieEntry<K, V> prior = previousEntry((TrieEntry<K, V>)entry);
fromKey = prior == null ? null : prior.getKey();
}
-
+
toKey = fromKey;
-
+
while (it.hasNext())
{
++size;
entry = it.next();
}
-
+
toKey = entry == null ? null : entry.getKey();
-
+
if (toKey != null)
{
entry = nextEntry((TrieEntry<K, V>)entry);
toKey = entry == null ? null : entry.getKey();
}
-
+
expectedModCount = PatriciaTrie.this.modCount;
}
-
+
return size;
}
-
+
@Override
public K firstKey()
{
fixup();
-
+
Map.Entry<K,V> e = fromKey == null ? firstEntry() : higherEntry(fromKey);
K first = e != null ? e.getKey() : null;
if (e == null || !isPrefix(first, prefix))
throw new NoSuchElementException();
-
+
return first;
}
-
+
@Override
public K lastKey()
{
fixup();
-
+
Map.Entry<K,V> e = toKey == null ? lastEntry() : lowerEntry(toKey);
K last = e != null ? e.getKey() : null;
if (e == null || !isPrefix(last, prefix))
throw new NoSuchElementException();
-
+
return last;
}
-
+
/**
* Returns true if this {@link PrefixRangeMap}'s key is a prefix
* of the provided key.
@@ -1045,7 +1045,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
{
return inRange(key);
}
-
+
/**
* Returns true if the provided Key is in the FROM range
* of the {@link PrefixRangeMap}
@@ -1055,7 +1055,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
{
return isPrefix(key, prefix);
}
-
+
/**
* Returns true if the provided Key is in the TO range
* of the {@link PrefixRangeMap}
@@ -1065,37 +1065,37 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
{
return isPrefix(key, prefix);
}
-
+
@Override
protected Set<Map.Entry<K, V>> createEntrySet()
{
return new PrefixRangeEntrySet(this);
}
-
+
@Override
public K getFromKey()
{
return fromKey;
}
-
+
@Override
public K getToKey()
{
return toKey;
}
-
+
@Override
public boolean isFromInclusive()
{
return false;
}
-
+
@Override
public boolean isToInclusive()
{
return false;
}
-
+
@Override
protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive)
@@ -1103,18 +1103,18 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
}
}
-
+
/**
* A prefix {@link RangeEntrySet} view of the {@link Trie}
*/
private final class PrefixRangeEntrySet extends RangeEntrySet
{
private final PrefixRangeMap delegate;
-
+
private TrieEntry<K, V> prefixStart;
-
+
private int expectedModCount = -1;
-
+
/**
* Creates a {@link PrefixRangeEntrySet}
*/
@@ -1123,13 +1123,13 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
super(delegate);
this.delegate = delegate;
}
-
+
@Override
public int size()
{
return delegate.fixup();
}
-
+
@Override
public Iterator<Map.Entry<K,V>> iterator()
{
@@ -1138,7 +1138,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
prefixStart = subtree(delegate.prefix);
expectedModCount = PatriciaTrie.this.modCount;
}
-
+
if (prefixStart == null)
{
Set<Map.Entry<K,V>> empty = Collections.emptySet();
@@ -1153,62 +1153,62 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
return new EntryIterator(prefixStart, delegate.prefix);
}
}
-
- /**
- * An {@link Iterator} that holds a single {@link TrieEntry}.
+
+ /**
+ * An {@link Iterator} that holds a single {@link TrieEntry}.
*/
private final class SingletonIterator implements Iterator<Map.Entry<K, V>>
{
private final TrieEntry<K, V> entry;
-
+
private int hit = 0;
-
+
public SingletonIterator(TrieEntry<K, V> entry)
{
this.entry = entry;
}
-
+
@Override
public boolean hasNext()
{
return hit == 0;
}
-
+
@Override
public Map.Entry<K, V> next()
{
if (hit != 0)
throw new NoSuchElementException();
-
+
++hit;
return entry;
}
-
+
@Override
public void remove()
{
if (hit != 1)
throw new IllegalStateException();
-
+
++hit;
PatriciaTrie.this.removeEntry(entry);
}
}
-
- /**
- * An {@link Iterator} for iterating over a prefix search.
+
+ /**
+ * An {@link Iterator} for iterating over a prefix search.
*/
private final class EntryIterator extends TrieIterator<Map.Entry<K, V>>
{
// values to reset the subtree if we remove it.
protected final K prefix;
protected boolean lastOne;
-
+
protected TrieEntry<K, V> subtree; // the subtree to search within
-
+
/**
- * Starts iteration at the given entry & search only
+ * Starts iteration at the given entry & search only
* within the given subtree.
*/
EntryIterator(TrieEntry<K, V> startScan, K prefix)
@@ -1217,7 +1217,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
next = PatriciaTrie.this.followLeft(startScan);
this.prefix = prefix;
}
-
+
@Override
public Map.Entry<K,V> next()
{
@@ -1226,13 +1226,13 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
next = null;
return entry;
}
-
+
@Override
protected TrieEntry<K, V> findNext(TrieEntry<K, V> prior)
{
return PatriciaTrie.this.nextEntryInSubtree(prior, subtree);
}
-
+
@Override
public void remove()
{
@@ -1242,9 +1242,9 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se
int bitIdx = subtree.bitIndex;
if (current == subtree)
needsFixing = true;
-
+
super.remove();
-
+
// If the subtree changed its bitIndex or we
// removed the old subtree, get a new one.
if (bitIdx != subtree.bitIndex || needsFixing)
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java
index 44809f3..1866fec 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java
@@ -30,16 +30,16 @@ import org.apache.cassandra.index.sasi.utils.trie.Cursor.Decision;
*/
/**
- * Defines the interface for a prefix tree, an ordered tree data structure. For
+ * Defines the interface for a prefix tree, an ordered tree data structure. For
* more information, see <a href="http://en.wikipedia.org/wiki/Trie">Tries</a>.
- *
+ *
* @author Roger Kapsi
* @author Sam Berlin
*/
public interface Trie<K, V> extends SortedMap<K, V>
{
/**
- * Returns the {@link Map.Entry} whose key is closest in a bitwise XOR
+ * Returns the {@link Map.Entry} whose key is closest in a bitwise XOR
* metric to the given key. This is NOT lexicographic closeness.
* For example, given the keys:
*
@@ -48,103 +48,103 @@ public interface Trie<K, V> extends SortedMap<K, V>
* <li>H = 1001000
* <li>L = 1001100
* </ol>
- *
- * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
- * return 'L', because the XOR distance between D & L is smaller
- * than the XOR distance between D & H.
- *
+ *
+ * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
+ * return 'L', because the XOR distance between D & L is smaller
+ * than the XOR distance between D & H.
+ *
* @return The {@link Map.Entry} whose key is closest in a bitwise XOR metric
* to the provided key.
*/
Map.Entry<K, V> select(K key);
-
+
/**
- * Returns the key that is closest in a bitwise XOR metric to the
+ * Returns the key that is closest in a bitwise XOR metric to the
* provided key. This is NOT lexicographic closeness!
- *
+ *
* For example, given the keys:
- *
+ *
* <ol>
* <li>D = 1000100
* <li>H = 1001000
* <li>L = 1001100
* </ol>
- *
- * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
- * return 'L', because the XOR distance between D & L is smaller
- * than the XOR distance between D & H.
- *
+ *
+ * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
+ * return 'L', because the XOR distance between D & L is smaller
+ * than the XOR distance between D & H.
+ *
* @return The key that is closest in a bitwise XOR metric to the provided key.
*/
@SuppressWarnings("unused")
K selectKey(K key);
-
+
/**
- * Returns the value whose key is closest in a bitwise XOR metric to
+ * Returns the value whose key is closest in a bitwise XOR metric to
* the provided key. This is NOT lexicographic closeness!
- *
+ *
* For example, given the keys:
- *
+ *
* <ol>
* <li>D = 1000100
* <li>H = 1001000
* <li>L = 1001100
* </ol>
- *
- * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
- * return 'L', because the XOR distance between D & L is smaller
- * than the XOR distance between D & H.
- *
+ *
+ * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
+ * return 'L', because the XOR distance between D & L is smaller
+ * than the XOR distance between D & H.
+ *
* @return The value whose key is closest in a bitwise XOR metric
* to the provided key.
*/
@SuppressWarnings("unused")
V selectValue(K key);
-
+
/**
* Iterates through the {@link Trie}, starting with the entry whose bitwise
* value is closest in an XOR metric to the given key. After the closest
* entry is found, the {@link Trie} will call select on that entry and continue
* calling select for each entry (traversing in order of XOR closeness,
* NOT lexicographically) until the cursor returns {@link Decision#EXIT}.
- *
+ *
* <p>The cursor can return {@link Decision#CONTINUE} to continue traversing.
- *
+ *
* <p>{@link Decision#REMOVE_AND_EXIT} is used to remove the current element
* and stop traversing.
- *
+ *
* <p>Note: The {@link Decision#REMOVE} operation is not supported.
- *
- * @return The entry the cursor returned {@link Decision#EXIT} on, or null
+ *
+ * @return The entry the cursor returned {@link Decision#EXIT} on, or null
* if it continued till the end.
*/
Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor);
-
+
/**
- * Traverses the {@link Trie} in lexicographical order.
+ * Traverses the {@link Trie} in lexicographical order.
* {@link Cursor#select(java.util.Map.Entry)} will be called on each entry.
- *
- * <p>The traversal will stop when the cursor returns {@link Decision#EXIT},
- * {@link Decision#CONTINUE} is used to continue traversing and
- * {@link Decision#REMOVE} is used to remove the element that was selected
+ *
+ * <p>The traversal will stop when the cursor returns {@link Decision#EXIT},
+ * {@link Decision#CONTINUE} is used to continue traversing and
+ * {@link Decision#REMOVE} is used to remove the element that was selected
* and continue traversing.
- *
+ *
* <p>{@link Decision#REMOVE_AND_EXIT} is used to remove the current element
* and stop traversing.
- *
- * @return The entry the cursor returned {@link Decision#EXIT} on, or null
+ *
+ * @return The entry the cursor returned {@link Decision#EXIT} on, or null
* if it continued till the end.
*/
Map.Entry<K,V> traverse(Cursor<? super K, ? super V> cursor);
-
+
/**
- * Returns a view of this {@link Trie} of all elements that are prefixed
+ * Returns a view of this {@link Trie} of all elements that are prefixed
* by the given key.
- *
- * <p>In a {@link Trie} with fixed size keys, this is essentially a
+ *
+ * <p>In a {@link Trie} with fixed size keys, this is essentially a
* {@link #get(Object)} operation.
- *
- * <p>For example, if the {@link Trie} contains 'Anna', 'Anael',
+ *
+ * <p>For example, if the {@link Trie} contains 'Anna', 'Anael',
* 'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then
* a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'.
*/
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java
index c258dd2..84080c2 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java
@@ -29,7 +29,7 @@ package org.apache.cassandra.index.sasi.utils.trie;
*/
public class Tries
{
- /**
+ /**
* Returns true if bitIndex is a {@link KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY}
*/
static boolean isOutOfBoundsIndex(int bitIndex)
@@ -37,7 +37,7 @@ public class Tries
return bitIndex == KeyAnalyzer.OUT_OF_BOUNDS_BIT_KEY;
}
- /**
+ /**
* Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY}
*/
static boolean isEqualBitKey(int bitIndex)
@@ -45,17 +45,17 @@ public class Tries
return bitIndex == KeyAnalyzer.EQUAL_BIT_KEY;
}
- /**
- * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY}
+ /**
+ * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY}
*/
static boolean isNullBitKey(int bitIndex)
{
return bitIndex == KeyAnalyzer.NULL_BIT_KEY;
}
- /**
- * Returns true if the given bitIndex is valid. Indices
- * are considered valid if they're between 0 and
+ /**
+ * Returns true if the given bitIndex is valid. Indices
+ * are considered valid if they're between 0 and
* {@link Integer#MAX_VALUE}
*/
static boolean isValidBitIndex(int bitIndex)
@@ -72,7 +72,7 @@ public class Tries
}
/**
- * Throws a {@link NullPointerException} with the given message if
+ * Throws a {@link NullPointerException} with the given message if
* the argument is null.
*/
static <T> T notNull(T o, String message)
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java b/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java
index b02e29f..e668b75 100644
--- a/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java
+++ b/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java
@@ -290,7 +290,8 @@ public class CQLSSTableWriter implements Closeable
{
int size = Math.min(values.size(), boundNames.size());
List<ByteBuffer> rawValues = new ArrayList<>(size);
- for (int i = 0; i < size; i++) {
+ for (int i = 0; i < size; i++)
+ {
ColumnSpecification spec = boundNames.get(i);
rawValues.add(values.get(spec.name.toString()));
}
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java b/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java
index d2c83bf..87d2a6e 100644
--- a/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java
+++ b/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java
@@ -1500,7 +1500,8 @@ public abstract class SSTableReader extends SSTable implements SelfRefCounted<SS
protected RowIndexEntry getCachedPosition(KeyCacheKey unifiedKey, boolean updateStats)
{
- if (keyCache != null && keyCache.getCapacity() > 0 && metadata.params.caching.cacheKeys()) {
+ if (keyCache != null && keyCache.getCapacity() > 0 && metadata.params.caching.cacheKeys())
+ {
if (updateStats)
{
RowIndexEntry cachedEntry = keyCache.get(unifiedKey);