You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2012/07/25 22:42:49 UTC
svn commit: r1365732 [3/5] - in /commons/proper/collections/trunk: ./
src/main/java/org/apache/commons/collections/
src/main/java/org/apache/commons/collections/trie/
src/test/java/org/apache/commons/collections/trie/ src/test/resources/org/
src/test/r...
Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,125 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections.trie;
+
+/**
+ * A {@link KeyAnalyzer} for {@link Short}s.
+ *
+ * @since 4.0
+ * @version $Id$
+ */
+public class ShortKeyAnalyzer implements KeyAnalyzer<Short> {
+
+ private static final long serialVersionUID = -8631376733513512017L;
+
+ /**
+ * A singleton instance of {@link ShortKeyAnalyzer}
+ */
+ public static final ShortKeyAnalyzer INSTANCE = new ShortKeyAnalyzer();
+
+ /**
+ * The length of an {@link Short} in bits
+ */
+ public static final int LENGTH = Short.SIZE;
+
+ /**
+ * A bit mask where the first bit is 1 and the others are zero
+ */
+ private static final int MSB = 0x8000;
+
+ /**
+ * Returns a bit mask where the given bit is set
+ */
+ private static int mask(int bit) {
+ return MSB >>> bit;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int bitsPerElement() {
+ return 1;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int lengthInBits(Short key) {
+ return LENGTH;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean isBitSet(Short key, int bitIndex, int lengthInBits) {
+ return (key & mask(bitIndex)) != 0;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int bitIndex(Short key, int offsetInBits, int lengthInBits,
+ Short other, int otherOffsetInBits, int otherLengthInBits) {
+
+ if (offsetInBits != 0 || otherOffsetInBits != 0) {
+ throw new IllegalArgumentException("offsetInBits=" + offsetInBits
+ + ", otherOffsetInBits=" + otherOffsetInBits);
+ }
+
+ int keyValue = key.shortValue();
+ if (keyValue == 0) {
+ return NULL_BIT_KEY;
+ }
+
+ int otherValue = (other != null ? other.shortValue() : 0);
+
+ if (keyValue != otherValue) {
+ int xorValue = keyValue ^ otherValue;
+ for (int i = 0; i < LENGTH; i++) {
+ if ((xorValue & mask(i)) != 0) {
+ return i;
+ }
+ }
+ }
+
+ return KeyAnalyzer.EQUAL_BIT_KEY;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int compare(Short o1, Short o2) {
+ return o1.compareTo(o2);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean isPrefix(Short prefix, int offsetInBits,
+ int lengthInBits, Short key) {
+
+ int value1 = (prefix.shortValue() << offsetInBits);
+ int value2 = key.shortValue();
+
+ int mask = 0;
+ for (int i = 0; i < lengthInBits; i++) {
+ mask |= (0x1 << i);
+ }
+
+ return (value1 & mask) == (value2 & mask);
+ }
+}
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,153 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections.trie;
+
+/**
+ * An {@link KeyAnalyzer} for {@link String}s.
+ *
+ * @since 4.0
+ * @version $Id$
+ */
+public class StringKeyAnalyzer extends AbstractKeyAnalyzer<String> {
+
+ private static final long serialVersionUID = -7032449491269434877L;
+
+ /**
+ * A singleton instance of {@link StringKeyAnalyzer}
+ */
+ public static final StringKeyAnalyzer INSTANCE = new StringKeyAnalyzer();
+
+ /**
+ * The number of bits per {@link Character}
+ */
+ public static final int LENGTH = Character.SIZE;
+
+ /**
+ * A bit mask where the first bit is 1 and the others are zero
+ */
+ private static final int MSB = 0x8000;
+
+ /**
+ * Returns a bit mask where the given bit is set
+ */
+ private static int mask(int bit) {
+ return MSB >>> bit;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int bitsPerElement() {
+ return LENGTH;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int lengthInBits(String key) {
+ return (key != null ? key.length() * LENGTH : 0);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int bitIndex(String key, int offsetInBits, int lengthInBits,
+ String other, int otherOffsetInBits, int otherLengthInBits) {
+ boolean allNull = true;
+
+ if (offsetInBits % LENGTH != 0 || otherOffsetInBits % LENGTH != 0
+ || lengthInBits % LENGTH != 0 || otherLengthInBits % LENGTH != 0) {
+ throw new IllegalArgumentException(
+ "The offsets and lengths must be at Character boundaries");
+ }
+
+
+ int beginIndex1 = offsetInBits / LENGTH;
+ int beginIndex2 = otherOffsetInBits / LENGTH;
+
+ int endIndex1 = beginIndex1 + lengthInBits / LENGTH;
+ int endIndex2 = beginIndex2 + otherLengthInBits / LENGTH;
+
+ int length = Math.max(endIndex1, endIndex2);
+
+ // Look at each character, and if they're different
+ // then figure out which bit makes the difference
+ // and return it.
+ char k = 0, f = 0;
+ for(int i = 0; i < length; i++) {
+ int index1 = beginIndex1 + i;
+ int index2 = beginIndex2 + i;
+
+ if (index1 >= endIndex1) {
+ k = 0;
+ } else {
+ k = key.charAt(index1);
+ }
+
+ if (other == null || index2 >= endIndex2) {
+ f = 0;
+ } else {
+ f = other.charAt(index2);
+ }
+
+ if (k != f) {
+ int x = k ^ f;
+ return i * LENGTH + (Integer.numberOfLeadingZeros(x) - LENGTH);
+ }
+
+ if (k != 0) {
+ allNull = false;
+ }
+ }
+
+ // All bits are 0
+ if (allNull) {
+ return KeyAnalyzer.NULL_BIT_KEY;
+ }
+
+ // Both keys are equal
+ return KeyAnalyzer.EQUAL_BIT_KEY;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean isBitSet(String key, int bitIndex, int lengthInBits) {
+ if (key == null || bitIndex >= lengthInBits) {
+ return false;
+ }
+
+ int index = (int)(bitIndex / LENGTH);
+ int bit = (int)(bitIndex % LENGTH);
+
+ return (key.charAt(index) & mask(bit)) != 0;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean isPrefix(String prefix, int offsetInBits,
+ int lengthInBits, String key) {
+ if (offsetInBits % LENGTH != 0 || lengthInBits % LENGTH != 0) {
+ throw new IllegalArgumentException(
+ "Cannot determine prefix outside of Character boundaries");
+ }
+
+ String s1 = prefix.substring(offsetInBits / LENGTH, lengthInBits / LENGTH);
+ return key.startsWith(s1);
+ }
+}
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,280 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections.trie;
+
+import java.io.Serializable;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Map;
+import java.util.Set;
+import java.util.SortedMap;
+
+import org.apache.commons.collections.Trie;
+import org.apache.commons.collections.collection.SynchronizedCollection;
+import org.apache.commons.collections.set.SynchronizedSet;
+
+/**
+ * A synchronized {@link Trie}.
+ *
+ * @since 4.0
+ * @version $Id$
+ */
+public class SynchronizedTrie<K, V> implements Trie<K, V>, Serializable {
+
+ private static final long serialVersionUID = 3121878833178676939L;
+
+ private final Trie<K, V> delegate;
+
+ /**
+ * Factory method to create a synchronized trie.
+ *
+ * @param trie the trie to decorate, must not be null
+ * @return a new synchronized trie
+ * @throws IllegalArgumentException if trie is null
+ */
+ public static <K, V> SynchronizedTrie<K, V> synchronizedTrie(Trie<K, V> trie) {
+ return new SynchronizedTrie<K, V>(trie);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Constructor that wraps (not copies).
+ *
+ * @param trie the trie to decorate, must not be null
+ * @throws IllegalArgumentException if set is null
+ */
+ public SynchronizedTrie(Trie<K, V> trie) {
+ if (trie == null) {
+ throw new IllegalArgumentException("Collection must not be null");
+ }
+ this.delegate = trie;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized Entry<K, V> select(K key,
+ Cursor<? super K, ? super V> cursor) {
+ return delegate.select(key, cursor);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized Entry<K, V> select(K key) {
+ return delegate.select(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized K selectKey(K key) {
+ return delegate.selectKey(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized V selectValue(K key) {
+ return delegate.selectValue(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized Entry<K, V> traverse(Cursor<? super K, ? super V> cursor) {
+ return delegate.traverse(cursor);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized Set<Entry<K, V>> entrySet() {
+ return SynchronizedSet.synchronizedSet(delegate.entrySet());
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized Set<K> keySet() {
+ return SynchronizedSet.synchronizedSet(delegate.keySet());
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized Collection<V> values() {
+ return SynchronizedCollection.synchronizedCollection(delegate.values());
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized void clear() {
+ delegate.clear();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized boolean containsKey(Object key) {
+ return delegate.containsKey(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized boolean containsValue(Object value) {
+ return delegate.containsValue(value);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized V get(Object key) {
+ return delegate.get(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized boolean isEmpty() {
+ return delegate.isEmpty();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized V put(K key, V value) {
+ return delegate.put(key, value);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized void putAll(Map<? extends K, ? extends V> m) {
+ delegate.putAll(m);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized V remove(Object key) {
+ return delegate.remove(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized K lastKey() {
+ return delegate.lastKey();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized SortedMap<K, V> subMap(K fromKey, K toKey) {
+ return Collections.synchronizedSortedMap(delegate.subMap(fromKey, toKey));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized SortedMap<K, V> tailMap(K fromKey) {
+ return Collections.synchronizedSortedMap(delegate.tailMap(fromKey));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized Comparator<? super K> comparator() {
+ return delegate.comparator();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized K firstKey() {
+ return delegate.firstKey();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized SortedMap<K, V> headMap(K toKey) {
+ return Collections.synchronizedSortedMap(delegate.headMap(toKey));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized SortedMap<K, V> getPrefixedBy(K key, int offset, int length) {
+ return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key, offset, length));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized SortedMap<K, V> getPrefixedBy(K key, int length) {
+ return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key, length));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized SortedMap<K, V> getPrefixedBy(K key) {
+ return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized SortedMap<K, V> getPrefixedByBits(K key, int lengthInBits) {
+ return Collections.synchronizedSortedMap(delegate.getPrefixedByBits(key, lengthInBits));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized SortedMap<K, V> getPrefixedByBits(K key,
+ int offsetInBits, int lengthInBits) {
+ return Collections.synchronizedSortedMap(delegate.getPrefixedByBits(key, offsetInBits, lengthInBits));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public synchronized int size() {
+ return delegate.size();
+ }
+
+ @Override
+ public synchronized int hashCode() {
+ return delegate.hashCode();
+ }
+
+ @Override
+ public synchronized boolean equals(Object obj) {
+ return delegate.equals(obj);
+ }
+
+ @Override
+ public synchronized String toString() {
+ return delegate.toString();
+ }
+}
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,301 @@
+package org.apache.commons.collections.trie;
+
+import java.io.Serializable;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Map;
+import java.util.Set;
+import java.util.SortedMap;
+
+import org.apache.commons.collections.Trie;
+
+/**
+ * An unmodifiable {@link Trie}.
+ *
+ * @since 4.0
+ * @version $Id$
+ */
+public class UnmodifiableTrie<K, V> implements Trie<K, V>, Serializable {
+
+ private static final long serialVersionUID = -7156426030315945159L;
+
+ private final Trie<K, V> delegate;
+
+ /**
+ * Factory method to create a unmodifiable trie.
+ *
+ * @param trie the trie to decorate, must not be null
+ * @return a new unmodifiable trie
+ * @throws IllegalArgumentException if trie is null
+ */
+ public static <K, V> UnmodifiableTrie<K, V> unmodifiableTrie(Trie<K, V> trie) {
+ return new UnmodifiableTrie<K, V>(trie);
+ }
+
+ //-----------------------------------------------------------------------
+ /**
+ * Constructor that wraps (not copies).
+ *
+ * @param trie the trie to decorate, must not be null
+ * @throws IllegalArgumentException if set is null
+ */
+ public UnmodifiableTrie(Trie<K, V> trie) {
+ if (trie == null) {
+ throw new IllegalArgumentException("Collection must not be null");
+ }
+ this.delegate = trie;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Entry<K, V> select(K key, final Cursor<? super K, ? super V> cursor) {
+ Cursor<K, V> c = new Cursor<K, V>() {
+ public Decision select(Map.Entry<? extends K, ? extends V> entry) {
+ Decision decision = cursor.select(entry);
+ switch (decision) {
+ case REMOVE:
+ case REMOVE_AND_EXIT:
+ throw new UnsupportedOperationException();
+ default:
+ // other decisions are fine
+ break;
+ }
+
+ return decision;
+ }
+ };
+
+ return delegate.select(key, c);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Entry<K, V> select(K key) {
+ return delegate.select(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public K selectKey(K key) {
+ return delegate.selectKey(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public V selectValue(K key) {
+ return delegate.selectValue(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Entry<K, V> traverse(final Cursor<? super K, ? super V> cursor) {
+ Cursor<K, V> c = new Cursor<K, V>() {
+ public Decision select(Map.Entry<? extends K, ? extends V> entry) {
+ Decision decision = cursor.select(entry);
+ switch (decision) {
+ case REMOVE:
+ case REMOVE_AND_EXIT:
+ throw new UnsupportedOperationException();
+ default:
+ // other decisions are fine
+ break;
+ }
+
+ return decision;
+ }
+ };
+
+ return delegate.traverse(c);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Set<Entry<K, V>> entrySet() {
+ return Collections.unmodifiableSet(delegate.entrySet());
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Set<K> keySet() {
+ return Collections.unmodifiableSet(delegate.keySet());
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Collection<V> values() {
+ return Collections.unmodifiableCollection(delegate.values());
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void clear() {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean containsKey(Object key) {
+ return delegate.containsKey(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean containsValue(Object value) {
+ return delegate.containsValue(value);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public V get(Object key) {
+ return delegate.get(key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean isEmpty() {
+ return delegate.isEmpty();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public V put(K key, V value) {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void putAll(Map<? extends K, ? extends V> m) {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public V remove(Object key) {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public K firstKey() {
+ return delegate.firstKey();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public SortedMap<K, V> headMap(K toKey) {
+ return Collections.unmodifiableSortedMap(delegate.headMap(toKey));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public K lastKey() {
+ return delegate.lastKey();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public SortedMap<K, V> subMap(K fromKey, K toKey) {
+ return Collections.unmodifiableSortedMap(
+ delegate.subMap(fromKey, toKey));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public SortedMap<K, V> tailMap(K fromKey) {
+ return Collections.unmodifiableSortedMap(delegate.tailMap(fromKey));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public SortedMap<K, V> getPrefixedBy(K key, int offset, int length) {
+ return Collections.unmodifiableSortedMap(
+ delegate.getPrefixedBy(key, offset, length));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public SortedMap<K, V> getPrefixedBy(K key, int length) {
+ return Collections.unmodifiableSortedMap(
+ delegate.getPrefixedBy(key, length));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public SortedMap<K, V> getPrefixedBy(K key) {
+ return Collections.unmodifiableSortedMap(
+ delegate.getPrefixedBy(key));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public SortedMap<K, V> getPrefixedByBits(K key, int lengthInBits) {
+ return Collections.unmodifiableSortedMap(
+ delegate.getPrefixedByBits(key, lengthInBits));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public SortedMap<K, V> getPrefixedByBits(K key, int offsetInBits,
+ int lengthInBits) {
+ return Collections.unmodifiableSortedMap(
+ delegate.getPrefixedByBits(key, offsetInBits, lengthInBits));
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Comparator<? super K> comparator() {
+ return delegate.comparator();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int size() {
+ return delegate.size();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int hashCode() {
+ return delegate.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ return delegate.equals(obj);
+ }
+
+ @Override
+ public String toString() {
+ return delegate.toString();
+ }
+}
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,38 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/**
+ * This package contains implementations of the
+ * {@link org.apache.commons.collections.Trie Trie} interface.
+ * <p>
+ * The implementations are in the form of direct implementations and decorators.
+ * A decorator wraps another implementation of the interface to add some
+ * specific additional functionality.
+ * <p>
+ * The following implementations are provided in the package:
+ * <ul>
+ * <li>PatriciaTrie - an implementation of a PATRICIA trie
+ * </ul>
+ * <p>
+ * The following decorators are provided:
+ * <ul>
+ * <li>Synchronized - synchronizes method access for multi-threaded environments
+ * <li>Unmodifiable - ensures the collection cannot be altered
+ * </ul>
+ *
+ * @version $Id$
+ */
+package org.apache.commons.collections.trie;
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java (added)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections.trie;
+
+import java.math.BigInteger;
+import java.util.Map;
+import java.util.TreeMap;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class ByteArrayKeyAnalyzerTest {
+
+ private static final int SIZE = 20000;
+
+ @Test
+ public void bitSet() {
+ byte[] key = toByteArray("10100110", 2);
+ ByteArrayKeyAnalyzer ka = new ByteArrayKeyAnalyzer(key.length * 8);
+ int length = ka.lengthInBits(key);
+
+ Assert.assertTrue(ka.isBitSet(key, 0, length));
+ Assert.assertFalse(ka.isBitSet(key, 1, length));
+ Assert.assertTrue(ka.isBitSet(key, 2, length));
+ Assert.assertFalse(ka.isBitSet(key, 3, length));
+ Assert.assertFalse(ka.isBitSet(key, 4, length));
+ Assert.assertTrue(ka.isBitSet(key, 5, length));
+ Assert.assertTrue(ka.isBitSet(key, 6, length));
+ Assert.assertFalse(ka.isBitSet(key, 7, length));
+ }
+
+ @Test
+ public void keys() {
+ PatriciaTrie<byte[], BigInteger> trie
+ = new PatriciaTrie<byte[], BigInteger>(ByteArrayKeyAnalyzer.INSTANCE);
+
+ Map<byte[], BigInteger> map
+ = new TreeMap<byte[], BigInteger>(ByteArrayKeyAnalyzer.INSTANCE);
+
+ for (int i = 0; i < SIZE; i++) {
+ BigInteger value = BigInteger.valueOf(i);
+ byte[] key = toByteArray(value);
+
+ BigInteger existing = trie.put(key, value);
+ Assert.assertNull(existing);
+
+ map.put(key, value);
+ }
+
+ Assert.assertEquals(map.size(), trie.size());
+
+ for (byte[] key : map.keySet()) {
+ BigInteger expected = new BigInteger(1, key);
+ BigInteger value = trie.get(key);
+
+ Assert.assertEquals(expected, value);
+ }
+ }
+
+ @Test
+ public void prefix() {
+ byte[] prefix = toByteArray("00001010", 2);
+ byte[] key1 = toByteArray("11001010", 2);
+ byte[] key2 = toByteArray("10101100", 2);
+
+ ByteArrayKeyAnalyzer keyAnalyzer = new ByteArrayKeyAnalyzer(key1.length * 8);
+
+ int prefixLength = keyAnalyzer.lengthInBits(prefix);
+
+ Assert.assertFalse(keyAnalyzer.isPrefix(prefix, 4, prefixLength, key1));
+ Assert.assertTrue(keyAnalyzer.isPrefix(prefix, 4, prefixLength, key2));
+ }
+
+ private static byte[] toByteArray(String value, int radix) {
+ return toByteArray(Long.parseLong(value, radix));
+ }
+
+ private static byte[] toByteArray(long value) {
+ return toByteArray(BigInteger.valueOf(value));
+ }
+
+ private static byte[] toByteArray(BigInteger value) {
+ byte[] src = value.toByteArray();
+ if (src.length <= 1) {
+ return src;
+ }
+
+ if (src[0] != 0) {
+ return src;
+ }
+
+ byte[] dst = new byte[src.length-1];
+ System.arraycopy(src, 1, dst, 0, dst.length);
+ return dst;
+ }
+}
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java (added)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,1125 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections.trie;
+
+import java.io.BufferedReader;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Random;
+import java.util.SortedMap;
+import java.util.StringTokenizer;
+import java.util.TreeMap;
+import java.util.Map.Entry;
+
+import org.apache.commons.collections.Trie.Cursor;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class PatriciaTrieTest {
+
+ @Test
+ public void testSimple() {
+ PatriciaTrie<Integer, String> intTrie = new PatriciaTrie<Integer, String>(new IntegerKeyAnalyzer());
+ Assert.assertTrue(intTrie.isEmpty());
+ Assert.assertEquals(0, intTrie.size());
+
+ intTrie.put(1, "One");
+ Assert.assertFalse(intTrie.isEmpty());
+ Assert.assertEquals(1, intTrie.size());
+
+ Assert.assertEquals("One", intTrie.remove(1));
+ Assert.assertNull(intTrie.remove(1));
+ Assert.assertTrue(intTrie.isEmpty());
+ Assert.assertEquals(0, intTrie.size());
+
+ intTrie.put(1, "One");
+ Assert.assertEquals("One", intTrie.get(1));
+ Assert.assertEquals("One", intTrie.put(1, "NotOne"));
+ Assert.assertEquals(1, intTrie.size());
+ Assert.assertEquals("NotOne", intTrie.get(1));
+ Assert.assertEquals("NotOne", intTrie.remove(1));
+ Assert.assertNull(intTrie.put(1, "One"));
+ }
+
+ @Test
+ public void testCeilingEntry() {
+ PatriciaTrie<Character, String> charTrie
+ = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+ charTrie.put('c', "c");
+ charTrie.put('p', "p");
+ charTrie.put('l', "l");
+ charTrie.put('t', "t");
+ charTrie.put('k', "k");
+ charTrie.put('a', "a");
+ charTrie.put('y', "y");
+ charTrie.put('r', "r");
+ charTrie.put('u', "u");
+ charTrie.put('o', "o");
+ charTrie.put('w', "w");
+ charTrie.put('i', "i");
+ charTrie.put('e', "e");
+ charTrie.put('x', "x");
+ charTrie.put('q', "q");
+ charTrie.put('b', "b");
+ charTrie.put('j', "j");
+ charTrie.put('s', "s");
+ charTrie.put('n', "n");
+ charTrie.put('v', "v");
+ charTrie.put('g', "g");
+ charTrie.put('h', "h");
+ charTrie.put('m', "m");
+ charTrie.put('z', "z");
+ charTrie.put('f', "f");
+ charTrie.put('d', "d");
+
+ Object[] results = new Object[] {
+ 'a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+ 'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+ 'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+ 'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+ 'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
+ 'z', "z"
+ };
+
+ for(int i = 0; i < results.length; i++) {
+ Map.Entry<Character, String> found = charTrie.ceilingEntry((Character)results[i]);
+ Assert.assertNotNull(found);
+ Assert.assertEquals(results[i], found.getKey());
+ Assert.assertEquals(results[++i], found.getValue());
+ }
+
+ // Remove some & try again...
+ charTrie.remove('a');
+ charTrie.remove('z');
+ charTrie.remove('q');
+ charTrie.remove('l');
+ charTrie.remove('p');
+ charTrie.remove('m');
+ charTrie.remove('u');
+
+ Map.Entry<Character, String> found = charTrie.ceilingEntry('u');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'v', found.getKey());
+
+ found = charTrie.ceilingEntry('a');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'b', found.getKey());
+
+ found = charTrie.ceilingEntry('z');
+ Assert.assertNull(found);
+
+ found = charTrie.ceilingEntry('q');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'r', found.getKey());
+
+ found = charTrie.ceilingEntry('l');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'n', found.getKey());
+
+ found = charTrie.ceilingEntry('p');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'r', found.getKey());
+
+ found = charTrie.ceilingEntry('m');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'n', found.getKey());
+
+ found = charTrie.ceilingEntry('\0');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'b', found.getKey());
+
+ charTrie.put('\0', "");
+ found = charTrie.ceilingEntry('\0');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'\0', found.getKey());
+ }
+
+ @Test
+ public void testLowerEntry() {
+ PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+ charTrie.put('c', "c");
+ charTrie.put('p', "p");
+ charTrie.put('l', "l");
+ charTrie.put('t', "t");
+ charTrie.put('k', "k");
+ charTrie.put('a', "a");
+ charTrie.put('y', "y");
+ charTrie.put('r', "r");
+ charTrie.put('u', "u");
+ charTrie.put('o', "o");
+ charTrie.put('w', "w");
+ charTrie.put('i', "i");
+ charTrie.put('e', "e");
+ charTrie.put('x', "x");
+ charTrie.put('q', "q");
+ charTrie.put('b', "b");
+ charTrie.put('j', "j");
+ charTrie.put('s', "s");
+ charTrie.put('n', "n");
+ charTrie.put('v', "v");
+ charTrie.put('g', "g");
+ charTrie.put('h', "h");
+ charTrie.put('m', "m");
+ charTrie.put('z', "z");
+ charTrie.put('f', "f");
+ charTrie.put('d', "d");
+
+ Object[] results = new Object[] {
+ 'a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+ 'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+ 'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+ 'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+ 'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
+ 'z', "z"
+ };
+
+ for(int i = 0; i < results.length; i+=2) {
+ //System.out.println("Looking for: " + results[i]);
+ Map.Entry<Character, String> found = charTrie.lowerEntry((Character)results[i]);
+ if(i == 0) {
+ Assert.assertNull(found);
+ } else {
+ Assert.assertNotNull(found);
+ Assert.assertEquals(results[i-2], found.getKey());
+ Assert.assertEquals(results[i-1], found.getValue());
+ }
+ }
+
+ Map.Entry<Character, String> found = charTrie.lowerEntry((char)('z' + 1));
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'z', found.getKey());
+
+ // Remove some & try again...
+ charTrie.remove('a');
+ charTrie.remove('z');
+ charTrie.remove('q');
+ charTrie.remove('l');
+ charTrie.remove('p');
+ charTrie.remove('m');
+ charTrie.remove('u');
+
+ found = charTrie.lowerEntry('u');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'t', found.getKey());
+
+ found = charTrie.lowerEntry('v');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'t', found.getKey());
+
+ found = charTrie.lowerEntry('a');
+ Assert.assertNull(found);
+
+ found = charTrie.lowerEntry('z');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'y', found.getKey());
+
+ found = charTrie.lowerEntry((char)('z'+1));
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'y', found.getKey());
+
+ found = charTrie.lowerEntry('q');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'o', found.getKey());
+
+ found = charTrie.lowerEntry('r');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'o', found.getKey());
+
+ found = charTrie.lowerEntry('p');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'o', found.getKey());
+
+ found = charTrie.lowerEntry('l');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'k', found.getKey());
+
+ found = charTrie.lowerEntry('m');
+ Assert.assertNotNull(found);
+ Assert.assertEquals((Character)'k', found.getKey());
+
+ found = charTrie.lowerEntry('\0');
+ Assert.assertNull(found);
+
+ charTrie.put('\0', "");
+ found = charTrie.lowerEntry('\0');
+ Assert.assertNull(found);
+ }
+
+ @Test
+ public void testIteration() {
+ PatriciaTrie<Integer, String> intTrie = new PatriciaTrie<Integer, String>(new IntegerKeyAnalyzer());
+ intTrie.put(1, "One");
+ intTrie.put(5, "Five");
+ intTrie.put(4, "Four");
+ intTrie.put(2, "Two");
+ intTrie.put(3, "Three");
+ intTrie.put(15, "Fifteen");
+ intTrie.put(13, "Thirteen");
+ intTrie.put(14, "Fourteen");
+ intTrie.put(16, "Sixteen");
+
+ TestCursor cursor = new TestCursor(
+ 1, "One", 2, "Two", 3, "Three", 4, "Four", 5, "Five", 13, "Thirteen",
+ 14, "Fourteen", 15, "Fifteen", 16, "Sixteen");
+
+ cursor.starting();
+ intTrie.traverse(cursor);
+ cursor.finished();
+
+ cursor.starting();
+ for (Map.Entry<Integer, String> entry : intTrie.entrySet()) {
+ cursor.select(entry);
+ }
+ cursor.finished();
+
+ cursor.starting();
+ for (Integer integer : intTrie.keySet()) {
+ cursor.checkKey(integer);
+ }
+ cursor.finished();
+
+ cursor.starting();
+ for (String string : intTrie.values()) {
+ cursor.checkValue(string);
+ }
+ cursor.finished();
+
+ PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+ charTrie.put('c', "c");
+ charTrie.put('p', "p");
+ charTrie.put('l', "l");
+ charTrie.put('t', "t");
+ charTrie.put('k', "k");
+ charTrie.put('a', "a");
+ charTrie.put('y', "y");
+ charTrie.put('r', "r");
+ charTrie.put('u', "u");
+ charTrie.put('o', "o");
+ charTrie.put('w', "w");
+ charTrie.put('i', "i");
+ charTrie.put('e', "e");
+ charTrie.put('x', "x");
+ charTrie.put('q', "q");
+ charTrie.put('b', "b");
+ charTrie.put('j', "j");
+ charTrie.put('s', "s");
+ charTrie.put('n', "n");
+ charTrie.put('v', "v");
+ charTrie.put('g', "g");
+ charTrie.put('h', "h");
+ charTrie.put('m', "m");
+ charTrie.put('z', "z");
+ charTrie.put('f', "f");
+ charTrie.put('d', "d");
+ cursor = new TestCursor('a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+ 'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+ 'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+ 'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+ 'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
+ 'z', "z");
+
+ cursor.starting();
+ charTrie.traverse(cursor);
+ cursor.finished();
+
+ cursor.starting();
+ for (Map.Entry<Character, String> entry : charTrie.entrySet()) {
+ cursor.select(entry);
+ }
+ cursor.finished();
+
+ cursor.starting();
+ for (Character character : charTrie.keySet()) {
+ cursor.checkKey(character);
+ }
+ cursor.finished();
+
+ cursor.starting();
+ for (String string : charTrie.values()) {
+ cursor.checkValue(string);
+ }
+ cursor.finished();
+ }
+
+ @Test
+ public void testSelect() {
+ PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+ charTrie.put('c', "c");
+ charTrie.put('p', "p");
+ charTrie.put('l', "l");
+ charTrie.put('t', "t");
+ charTrie.put('k', "k");
+ charTrie.put('a', "a");
+ charTrie.put('y', "y");
+ charTrie.put('r', "r");
+ charTrie.put('u', "u");
+ charTrie.put('o', "o");
+ charTrie.put('w', "w");
+ charTrie.put('i', "i");
+ charTrie.put('e', "e");
+ charTrie.put('x', "x");
+ charTrie.put('q', "q");
+ charTrie.put('b', "b");
+ charTrie.put('j', "j");
+ charTrie.put('s', "s");
+ charTrie.put('n', "n");
+ charTrie.put('v', "v");
+ charTrie.put('g', "g");
+ charTrie.put('h', "h");
+ charTrie.put('m', "m");
+ charTrie.put('z', "z");
+ charTrie.put('f', "f");
+ charTrie.put('d', "d");
+ TestCursor cursor = new TestCursor(
+ 'd', "d", 'e', "e", 'f', "f", 'g', "g",
+ 'a', "a", 'b', "b", 'c', "c",
+ 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+ 'h', "h", 'i', "i", 'j', "j", 'k', "k",
+ 't', "t", 'u', "u", 'v', "v", 'w', "w",
+ 'p', "p", 'q', "q", 'r', "r", 's', "s",
+ 'x', "x", 'y', "y", 'z', "z");
+
+ Assert.assertEquals(26, charTrie.size());
+
+ cursor.starting();
+ charTrie.select('d', cursor);
+ cursor.finished();
+ }
+
+ @Test
+ public void testTraverseCursorRemove() {
+ PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+ charTrie.put('c', "c");
+ charTrie.put('p', "p");
+ charTrie.put('l', "l");
+ charTrie.put('t', "t");
+ charTrie.put('k', "k");
+ charTrie.put('a', "a");
+ charTrie.put('y', "y");
+ charTrie.put('r', "r");
+ charTrie.put('u', "u");
+ charTrie.put('o', "o");
+ charTrie.put('w', "w");
+ charTrie.put('i', "i");
+ charTrie.put('e', "e");
+ charTrie.put('x', "x");
+ charTrie.put('q', "q");
+ charTrie.put('b', "b");
+ charTrie.put('j', "j");
+ charTrie.put('s', "s");
+ charTrie.put('n', "n");
+ charTrie.put('v', "v");
+ charTrie.put('g', "g");
+ charTrie.put('h', "h");
+ charTrie.put('m', "m");
+ charTrie.put('z', "z");
+ charTrie.put('f', "f");
+ charTrie.put('d', "d");
+ TestCursor cursor = new TestCursor('a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+ 'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+ 'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+ 'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+ 'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
+ 'z', "z");
+
+ cursor.starting();
+ charTrie.traverse(cursor);
+ cursor.finished();
+
+ // Test removing both an internal & external node.
+ // 'm' is an example External node in this Trie, and 'p' is an internal.
+
+ Assert.assertEquals(26, charTrie.size());
+
+ Object[] toRemove = new Object[] { 'g', 'd', 'e', 'm', 'p', 'q', 'r', 's' };
+ cursor.addToRemove(toRemove);
+
+ cursor.starting();
+ charTrie.traverse(cursor);
+ cursor.finished();
+
+ Assert.assertEquals(26 - toRemove.length, charTrie.size());
+
+ cursor.starting();
+ charTrie.traverse(cursor);
+ cursor.finished();
+
+ cursor.starting();
+ for (Entry<Character, String> entry : charTrie.entrySet()) {
+ cursor.select(entry);
+ if (Arrays.asList(toRemove).contains(entry.getKey())) {
+ Assert.fail("got an: " + entry);
+ }
+ }
+ cursor.finished();
+ }
+
+ @Test
+ public void testIteratorRemove() {
+ PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+ charTrie.put('c', "c");
+ charTrie.put('p', "p");
+ charTrie.put('l', "l");
+ charTrie.put('t', "t");
+ charTrie.put('k', "k");
+ charTrie.put('a', "a");
+ charTrie.put('y', "y");
+ charTrie.put('r', "r");
+ charTrie.put('u', "u");
+ charTrie.put('o', "o");
+ charTrie.put('w', "w");
+ charTrie.put('i', "i");
+ charTrie.put('e', "e");
+ charTrie.put('x', "x");
+ charTrie.put('q', "q");
+ charTrie.put('b', "b");
+ charTrie.put('j', "j");
+ charTrie.put('s', "s");
+ charTrie.put('n', "n");
+ charTrie.put('v', "v");
+ charTrie.put('g', "g");
+ charTrie.put('h', "h");
+ charTrie.put('m', "m");
+ charTrie.put('z', "z");
+ charTrie.put('f', "f");
+ charTrie.put('d', "d");
+ TestCursor cursor = new TestCursor('a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+ 'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+ 'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+ 'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+ 'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y",
+ 'z', "z");
+
+ // Test removing both an internal & external node.
+ // 'm' is an example External node in this Trie, and 'p' is an internal.
+
+ Assert.assertEquals(26, charTrie.size());
+
+ Object[] toRemove = new Object[] { 'e', 'm', 'p', 'q', 'r', 's' };
+
+ cursor.starting();
+ for(Iterator<Map.Entry<Character, String>> i = charTrie.entrySet().iterator(); i.hasNext(); ) {
+ Map.Entry<Character,String> entry = i.next();
+ cursor.select(entry);
+ if(Arrays.asList(toRemove).contains(entry.getKey())) {
+ i.remove();
+ }
+ }
+ cursor.finished();
+
+ Assert.assertEquals(26 - toRemove.length, charTrie.size());
+
+ cursor.remove(toRemove);
+
+ cursor.starting();
+ for (Entry<Character, String> entry : charTrie.entrySet()) {
+ cursor.select(entry);
+ if (Arrays.asList(toRemove).contains(entry.getKey())) {
+ Assert.fail("got an: " + entry);
+ }
+ }
+ cursor.finished();
+ }
+
+ @Test
+ public void testHamlet() throws Exception {
+ // Make sure that Hamlet is read & stored in the same order as a SortedSet.
+ List<String> original = new ArrayList<String>();
+ List<String> control = new ArrayList<String>();
+ SortedMap<String, String> sortedControl = new TreeMap<String, String>();
+ PatriciaTrie<String, String> trie = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+
+ InputStream in = getClass().getResourceAsStream("hamlet.txt");
+ BufferedReader reader = new BufferedReader(new InputStreamReader(in));
+
+ String read = null;
+ while( (read = reader.readLine()) != null) {
+ StringTokenizer st = new StringTokenizer(read);
+ while(st.hasMoreTokens()) {
+ String token = st.nextToken();
+ original.add(token);
+ sortedControl.put(token, token);
+ trie.put(token, token);
+ }
+ }
+ control.addAll(sortedControl.values());
+
+ Assert.assertEquals(control.size(), sortedControl.size());
+ Assert.assertEquals(sortedControl.size(), trie.size());
+ Iterator<String> iter = trie.values().iterator();
+ for (String aControl : control) {
+ Assert.assertEquals(aControl, iter.next());
+ }
+
+ Random rnd = new Random();
+ int item = 0;
+ iter = trie.values().iterator();
+ int removed = 0;
+ for(; item < control.size(); item++) {
+ Assert.assertEquals(control.get(item), iter.next());
+ if(rnd.nextBoolean()) {
+ iter.remove();
+ removed++;
+ }
+ }
+
+ Assert.assertEquals(control.size(), item);
+ Assert.assertTrue(removed > 0);
+ Assert.assertEquals(control.size(), trie.size() + removed);
+
+ // reset hamlet
+ trie.clear();
+ for (String anOriginal : original) {
+ trie.put(anOriginal, anOriginal);
+ }
+
+ assertEqualArrays(sortedControl.values().toArray(), trie.values().toArray());
+ assertEqualArrays(sortedControl.keySet().toArray(), trie.keySet().toArray());
+ assertEqualArrays(sortedControl.entrySet().toArray(), trie.entrySet().toArray());
+
+ Assert.assertEquals(sortedControl.firstKey(), trie.firstKey());
+ Assert.assertEquals(sortedControl.lastKey(), trie.lastKey());
+
+ SortedMap<String, String> sub = trie.headMap(control.get(523));
+ Assert.assertEquals(523, sub.size());
+ for(int i = 0; i < control.size(); i++) {
+ if(i < 523) {
+ Assert.assertTrue(sub.containsKey(control.get(i)));
+ } else {
+ Assert.assertFalse(sub.containsKey(control.get(i)));
+ }
+ }
+ // Too slow to check values on all, so just do a few.
+ Assert.assertTrue(sub.containsValue(control.get(522)));
+ Assert.assertFalse(sub.containsValue(control.get(523)));
+ Assert.assertFalse(sub.containsValue(control.get(524)));
+
+ try {
+ sub.headMap(control.get(524));
+ Assert.fail("should have thrown IAE");
+ } catch(IllegalArgumentException expected) {}
+
+ Assert.assertEquals(sub.lastKey(), control.get(522));
+ Assert.assertEquals(sub.firstKey(), control.get(0));
+
+ sub = sub.tailMap(control.get(234));
+ Assert.assertEquals(289, sub.size());
+ Assert.assertEquals(control.get(234), sub.firstKey());
+ Assert.assertEquals(control.get(522), sub.lastKey());
+ for(int i = 0; i < control.size(); i++) {
+ if(i < 523 && i > 233) {
+ Assert.assertTrue(sub.containsKey(control.get(i)));
+ } else {
+ Assert.assertFalse(sub.containsKey(control.get(i)));
+ }
+ }
+
+ try {
+ sub.tailMap(control.get(232));
+ Assert.fail("should have thrown IAE");
+ } catch(IllegalArgumentException expected) {}
+
+ sub = sub.subMap(control.get(300), control.get(400));
+ Assert.assertEquals(100, sub.size());
+ Assert.assertEquals(control.get(300), sub.firstKey());
+ Assert.assertEquals(control.get(399), sub.lastKey());
+
+ for(int i = 0; i < control.size(); i++) {
+ if(i < 400 && i > 299) {
+ Assert.assertTrue(sub.containsKey(control.get(i)));
+ } else {
+ Assert.assertFalse(sub.containsKey(control.get(i)));
+ }
+ }
+ }
+
+ @Test
+ public void testPrefixedBy() {
+ PatriciaTrie<String, String> trie
+ = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+
+ final String[] keys = new String[]{
+ "",
+ "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
+ "Alberts", "Allie", "Alliese", "Alabama", "Banane",
+ "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
+ "Amma"
+ };
+
+ for (String key : keys) {
+ trie.put(key, key);
+ }
+
+ SortedMap<String, String> map;
+ Iterator<String> iterator;
+ Iterator<Map.Entry<String, String>> entryIterator;
+ Map.Entry<String, String> entry;
+
+ map = trie.getPrefixedBy("Al");
+ Assert.assertEquals(8, map.size());
+ Assert.assertEquals("Alabama", map.firstKey());
+ Assert.assertEquals("Alliese", map.lastKey());
+ Assert.assertEquals("Albertoo", map.get("Albertoo"));
+ Assert.assertNotNull(trie.get("Xavier"));
+ Assert.assertNull(map.get("Xavier"));
+ Assert.assertNull(trie.get("Alice"));
+ Assert.assertNull(map.get("Alice"));
+ iterator = map.values().iterator();
+ Assert.assertEquals("Alabama", iterator.next());
+ Assert.assertEquals("Albert", iterator.next());
+ Assert.assertEquals("Alberto", iterator.next());
+ Assert.assertEquals("Albertoo", iterator.next());
+ Assert.assertEquals("Alberts", iterator.next());
+ Assert.assertEquals("Alien", iterator.next());
+ Assert.assertEquals("Allie", iterator.next());
+ Assert.assertEquals("Alliese", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+
+ map = trie.getPrefixedBy("Albert");
+ iterator = map.keySet().iterator();
+ Assert.assertEquals("Albert", iterator.next());
+ Assert.assertEquals("Alberto", iterator.next());
+ Assert.assertEquals("Albertoo", iterator.next());
+ Assert.assertEquals("Alberts", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+ Assert.assertEquals(4, map.size());
+ Assert.assertEquals("Albert", map.firstKey());
+ Assert.assertEquals("Alberts", map.lastKey());
+ Assert.assertNull(trie.get("Albertz"));
+ map.put("Albertz", "Albertz");
+ Assert.assertEquals("Albertz", trie.get("Albertz"));
+ Assert.assertEquals(5, map.size());
+ Assert.assertEquals("Albertz", map.lastKey());
+ iterator = map.keySet().iterator();
+ Assert.assertEquals("Albert", iterator.next());
+ Assert.assertEquals("Alberto", iterator.next());
+ Assert.assertEquals("Albertoo", iterator.next());
+ Assert.assertEquals("Alberts", iterator.next());
+ Assert.assertEquals("Albertz", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+ Assert.assertEquals("Albertz", map.remove("Albertz"));
+
+ map = trie.getPrefixedBy("Alberto");
+ Assert.assertEquals(2, map.size());
+ Assert.assertEquals("Alberto", map.firstKey());
+ Assert.assertEquals("Albertoo", map.lastKey());
+ entryIterator = map.entrySet().iterator();
+ entry = entryIterator.next();
+ Assert.assertEquals("Alberto", entry.getKey());
+ Assert.assertEquals("Alberto", entry.getValue());
+ entry = entryIterator.next();
+ Assert.assertEquals("Albertoo", entry.getKey());
+ Assert.assertEquals("Albertoo", entry.getValue());
+ Assert.assertFalse(entryIterator.hasNext());
+ trie.put("Albertoad", "Albertoad");
+ Assert.assertEquals(3, map.size());
+ Assert.assertEquals("Alberto", map.firstKey());
+ Assert.assertEquals("Albertoo", map.lastKey());
+ entryIterator = map.entrySet().iterator();
+ entry = entryIterator.next();
+ Assert.assertEquals("Alberto", entry.getKey());
+ Assert.assertEquals("Alberto", entry.getValue());
+ entry = entryIterator.next();
+ Assert.assertEquals("Albertoad", entry.getKey());
+ Assert.assertEquals("Albertoad", entry.getValue());
+ entry = entryIterator.next();
+ Assert.assertEquals("Albertoo", entry.getKey());
+ Assert.assertEquals("Albertoo", entry.getValue());
+ Assert.assertFalse(entryIterator.hasNext());
+ Assert.assertEquals("Albertoo", trie.remove("Albertoo"));
+ Assert.assertEquals("Alberto", map.firstKey());
+ Assert.assertEquals("Albertoad", map.lastKey());
+ Assert.assertEquals(2, map.size());
+ entryIterator = map.entrySet().iterator();
+ entry = entryIterator.next();
+ Assert.assertEquals("Alberto", entry.getKey());
+ Assert.assertEquals("Alberto", entry.getValue());
+ entry = entryIterator.next();
+ Assert.assertEquals("Albertoad", entry.getKey());
+ Assert.assertEquals("Albertoad", entry.getValue());
+ Assert.assertFalse(entryIterator.hasNext());
+ Assert.assertEquals("Albertoad", trie.remove("Albertoad"));
+ trie.put("Albertoo", "Albertoo");
+
+ map = trie.getPrefixedBy("X");
+ Assert.assertEquals(2, map.size());
+ Assert.assertFalse(map.containsKey("Albert"));
+ Assert.assertTrue(map.containsKey("Xavier"));
+ Assert.assertFalse(map.containsKey("Xalan"));
+ iterator = map.values().iterator();
+ Assert.assertEquals("Xavier", iterator.next());
+ Assert.assertEquals("XyZ", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+
+ map = trie.getPrefixedBy("An");
+ Assert.assertEquals(1, map.size());
+ Assert.assertEquals("Anna", map.firstKey());
+ Assert.assertEquals("Anna", map.lastKey());
+ iterator = map.keySet().iterator();
+ Assert.assertEquals("Anna", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+
+ map = trie.getPrefixedBy("Ban");
+ Assert.assertEquals(1, map.size());
+ Assert.assertEquals("Banane", map.firstKey());
+ Assert.assertEquals("Banane", map.lastKey());
+ iterator = map.keySet().iterator();
+ Assert.assertEquals("Banane", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+
+ map = trie.getPrefixedBy("Am");
+ Assert.assertFalse(map.isEmpty());
+ Assert.assertEquals(3, map.size());
+ Assert.assertEquals("Amber", trie.remove("Amber"));
+ iterator = map.keySet().iterator();
+ Assert.assertEquals("Amma", iterator.next());
+ Assert.assertEquals("Ammun", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+ iterator = map.keySet().iterator();
+ map.put("Amber", "Amber");
+ Assert.assertEquals(3, map.size());
+ try {
+ iterator.next();
+ Assert.fail("CME expected");
+ } catch(ConcurrentModificationException expected) {}
+ Assert.assertEquals("Amber", map.firstKey());
+ Assert.assertEquals("Ammun", map.lastKey());
+
+ map = trie.getPrefixedBy("Ak\0");
+ Assert.assertTrue(map.isEmpty());
+
+ map = trie.getPrefixedBy("Ak");
+ Assert.assertEquals(2, map.size());
+ Assert.assertEquals("Akka", map.firstKey());
+ Assert.assertEquals("Akko", map.lastKey());
+ map.put("Ak", "Ak");
+ Assert.assertEquals("Ak", map.firstKey());
+ Assert.assertEquals("Akko", map.lastKey());
+ Assert.assertEquals(3, map.size());
+ trie.put("Al", "Al");
+ Assert.assertEquals(3, map.size());
+ Assert.assertEquals("Ak", map.remove("Ak"));
+ Assert.assertEquals("Akka", map.firstKey());
+ Assert.assertEquals("Akko", map.lastKey());
+ Assert.assertEquals(2, map.size());
+ iterator = map.keySet().iterator();
+ Assert.assertEquals("Akka", iterator.next());
+ Assert.assertEquals("Akko", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+ Assert.assertEquals("Al", trie.remove("Al"));
+
+ map = trie.getPrefixedBy("Akka");
+ Assert.assertEquals(1, map.size());
+ Assert.assertEquals("Akka", map.firstKey());
+ Assert.assertEquals("Akka", map.lastKey());
+ iterator = map.keySet().iterator();
+ Assert.assertEquals("Akka", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+
+ map = trie.getPrefixedBy("Ab");
+ Assert.assertTrue(map.isEmpty());
+ Assert.assertEquals(0, map.size());
+ try {
+ Object o = map.firstKey();
+ Assert.fail("got a first key: " + o);
+ } catch(NoSuchElementException nsee) {}
+ try {
+ Object o = map.lastKey();
+ Assert.fail("got a last key: " + o);
+ } catch(NoSuchElementException nsee) {}
+ iterator = map.values().iterator();
+ Assert.assertFalse(iterator.hasNext());
+
+ map = trie.getPrefixedBy("Albertooo");
+ Assert.assertTrue(map.isEmpty());
+ Assert.assertEquals(0, map.size());
+ try {
+ Object o = map.firstKey();
+ Assert.fail("got a first key: " + o);
+ } catch(NoSuchElementException nsee) {}
+ try {
+ Object o = map.lastKey();
+ Assert.fail("got a last key: " + o);
+ } catch(NoSuchElementException nsee) {}
+ iterator = map.values().iterator();
+ Assert.assertFalse(iterator.hasNext());
+
+ map = trie.getPrefixedBy("");
+ Assert.assertSame(trie, map); // stricter than necessary, but a good check
+
+ map = trie.getPrefixedBy("\0");
+ Assert.assertTrue(map.isEmpty());
+ Assert.assertEquals(0, map.size());
+ try {
+ Object o = map.firstKey();
+ Assert.fail("got a first key: " + o);
+ } catch(NoSuchElementException nsee) {}
+ try {
+ Object o = map.lastKey();
+ Assert.fail("got a last key: " + o);
+ } catch(NoSuchElementException nsee) {}
+ iterator = map.values().iterator();
+ Assert.assertFalse(iterator.hasNext());
+ }
+
+ @Test
+ public void testPrefixByOffsetAndLength() {
+ PatriciaTrie<String, String> trie
+ = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+
+ final String[] keys = new String[]{
+ "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
+ "Alberts", "Allie", "Alliese", "Alabama", "Banane",
+ "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
+ "Amma"
+ };
+
+ for (String key : keys) {
+ trie.put(key, key);
+ }
+
+ SortedMap<String, String> map;
+ Iterator<String> iterator;
+
+ map = trie.getPrefixedBy("Alice", 2);
+ Assert.assertEquals(8, map.size());
+ Assert.assertEquals("Alabama", map.firstKey());
+ Assert.assertEquals("Alliese", map.lastKey());
+ Assert.assertEquals("Albertoo", map.get("Albertoo"));
+ Assert.assertNotNull(trie.get("Xavier"));
+ Assert.assertNull(map.get("Xavier"));
+ Assert.assertNull(trie.get("Alice"));
+ Assert.assertNull(map.get("Alice"));
+ iterator = map.values().iterator();
+ Assert.assertEquals("Alabama", iterator.next());
+ Assert.assertEquals("Albert", iterator.next());
+ Assert.assertEquals("Alberto", iterator.next());
+ Assert.assertEquals("Albertoo", iterator.next());
+ Assert.assertEquals("Alberts", iterator.next());
+ Assert.assertEquals("Alien", iterator.next());
+ Assert.assertEquals("Allie", iterator.next());
+ Assert.assertEquals("Alliese", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+
+ map = trie.getPrefixedBy("BAlice", 1, 2);
+ Assert.assertEquals(8, map.size());
+ Assert.assertEquals("Alabama", map.firstKey());
+ Assert.assertEquals("Alliese", map.lastKey());
+ Assert.assertEquals("Albertoo", map.get("Albertoo"));
+ Assert.assertNotNull(trie.get("Xavier"));
+ Assert.assertNull(map.get("Xavier"));
+ Assert.assertNull(trie.get("Alice"));
+ Assert.assertNull(map.get("Alice"));
+ iterator = map.values().iterator();
+ Assert.assertEquals("Alabama", iterator.next());
+ Assert.assertEquals("Albert", iterator.next());
+ Assert.assertEquals("Alberto", iterator.next());
+ Assert.assertEquals("Albertoo", iterator.next());
+ Assert.assertEquals("Alberts", iterator.next());
+ Assert.assertEquals("Alien", iterator.next());
+ Assert.assertEquals("Allie", iterator.next());
+ Assert.assertEquals("Alliese", iterator.next());
+ Assert.assertFalse(iterator.hasNext());
+ }
+
+ @Test
+ public void testPrefixedByRemoval() {
+ PatriciaTrie<String, String> trie
+ = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+
+ final String[] keys = new String[]{
+ "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
+ "Alberts", "Allie", "Alliese", "Alabama", "Banane",
+ "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
+ "Amma"
+ };
+
+ for (String key : keys) {
+ trie.put(key, key);
+ }
+
+ SortedMap<String, String> map = trie.getPrefixedBy("Al");
+ Assert.assertEquals(8, map.size());
+ Iterator<String> iter = map.keySet().iterator();
+ Assert.assertEquals("Alabama", iter.next());
+ Assert.assertEquals("Albert", iter.next());
+ Assert.assertEquals("Alberto", iter.next());
+ Assert.assertEquals("Albertoo", iter.next());
+ Assert.assertEquals("Alberts", iter.next());
+ Assert.assertEquals("Alien", iter.next());
+ iter.remove();
+ Assert.assertEquals(7, map.size());
+ Assert.assertEquals("Allie", iter.next());
+ Assert.assertEquals("Alliese", iter.next());
+ Assert.assertFalse(iter.hasNext());
+
+ map = trie.getPrefixedBy("Ak");
+ Assert.assertEquals(2, map.size());
+ iter = map.keySet().iterator();
+ Assert.assertEquals("Akka", iter.next());
+ iter.remove();
+ Assert.assertEquals(1, map.size());
+ Assert.assertEquals("Akko", iter.next());
+ if(iter.hasNext()) {
+ Assert.fail("shouldn't have next (but was: " + iter.next() + ")");
+ }
+ Assert.assertFalse(iter.hasNext());
+ }
+
+ @Test
+ public void testTraverseWithAllNullBitKey() {
+ PatriciaTrie<String, String> trie
+ = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+
+ //
+ // One entry in the Trie
+ // Entry is stored at the root
+ //
+
+ // trie.put("", "All Bits Are Zero");
+ trie.put("\0", "All Bits Are Zero");
+
+ //
+ // / ("") <-- root
+ // \_/ \
+ // null
+ //
+
+ final List<String> strings = new ArrayList<String>();
+ trie.traverse(new Cursor<String, String>() {
+ public Decision select(Entry<? extends String, ? extends String> entry) {
+ strings.add(entry.getValue());
+ return Decision.CONTINUE;
+ }
+ });
+
+ Assert.assertEquals(1, strings.size());
+
+ strings.clear();
+ for (String s : trie.values()) {
+ strings.add(s);
+ }
+ Assert.assertEquals(1, strings.size());
+ }
+
+ @Test
+ public void testSelectWithAllNullBitKey() {
+ PatriciaTrie<String, String> trie
+ = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+
+ // trie.put("", "All Bits Are Zero");
+ trie.put("\0", "All Bits Are Zero");
+
+ final List<String> strings = new ArrayList<String>();
+ trie.select("Hello", new Cursor<String, String>() {
+ public Decision select(Entry<? extends String, ? extends String> entry) {
+ strings.add(entry.getValue());
+ return Decision.CONTINUE;
+ }
+ });
+ Assert.assertEquals(1, strings.size());
+ }
+
+ private static class TestCursor implements Cursor<Object, Object> {
+ private List<Object> keys;
+ private List<Object> values;
+ private Object selectFor;
+ private List<Object> toRemove;
+ private int index = 0;
+
+ TestCursor(Object... objects) {
+ if(objects.length % 2 != 0) {
+ throw new IllegalArgumentException("must be * 2");
+ }
+
+ keys = new ArrayList<Object>(objects.length / 2);
+ values = new ArrayList<Object>(keys.size());
+ toRemove = Collections.emptyList();
+ for(int i = 0; i < objects.length; i++) {
+ keys.add(objects[i]);
+ values.add(objects[++i]);
+ }
+ }
+
+ void selectFor(Object object) {
+ selectFor = object;
+ }
+
+ void addToRemove(Object... objects) {
+ toRemove = new ArrayList<Object>(Arrays.asList(objects));
+ }
+
+ void remove(Object... objects) {
+ for (Object object : objects) {
+ int idx = keys.indexOf(object);
+ keys.remove(idx);
+ values.remove(idx);
+ }
+ }
+
+ void starting() {
+ index = 0;
+ }
+
+ public void checkKey(Object k) {
+ Assert.assertEquals(keys.get(index++), k);
+ }
+
+ public void checkValue(Object o) {
+ Assert.assertEquals(values.get(index++), o);
+ }
+
+ public Decision select(Entry<?, ?> entry) {
+ // System.out.println("Scanning: " + entry.getKey());
+ Assert.assertEquals(keys.get(index), entry.getKey());
+ Assert.assertEquals(values.get(index), entry.getValue());
+ index++;
+
+ if(toRemove.contains(entry.getKey())) {
+ // System.out.println("Removing: " + entry.getKey());
+ index--;
+ keys.remove(index);
+ values.remove(index);
+ toRemove.remove(entry.getKey());
+ return Decision.REMOVE;
+ }
+
+ if(selectFor != null && selectFor.equals(entry.getKey())) {
+ return Decision.EXIT;
+ } else {
+ return Decision.CONTINUE;
+ }
+ }
+
+ void finished() {
+ Assert.assertEquals(keys.size(), index);
+ }
+ }
+
+ private static void assertEqualArrays(Object[] a, Object[] b) {
+ Assert.assertTrue(Arrays.equals(a, b));
+ }
+}
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
------------------------------------------------------------------------------
svn:executable = *
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
------------------------------------------------------------------------------
svn:mime-type = text/plain