This change adds PrefixTree. PrefixTree is used in the upcoming
MultiWordSuggestOracle to provide quick retrieval from a static set
of Strings.
Patch by: bobv, ecc, knorton
Review by: knorton
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@847 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/user/src/com/google/gwt/user/client/ui/PrefixTree.java b/user/src/com/google/gwt/user/client/ui/PrefixTree.java
new file mode 100644
index 0000000..327e4c1
--- /dev/null
+++ b/user/src/com/google/gwt/user/client/ui/PrefixTree.java
@@ -0,0 +1,481 @@
+/*
+ * Copyright 2006 Google Inc.
+ *
+ * Licensed 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 com.google.gwt.user.client.ui;
+
+import com.google.gwt.core.client.JavaScriptObject;
+
+import java.util.AbstractCollection;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+/**
+ * A prefix tree (aka trie).
+ *
+ */
+class PrefixTree extends AbstractCollection {
+
+ /**
+ * Iterates over the structure of a PrefixTree. No concurrency checks are
+ * made. This Iterator will output anything new added to the tree if the new
+ * entry is after the current position of the Iterator.
+ *
+ * This Iterator implementation is iterative and uses an internal stack object
+ * to avoid call-stack limitations and invocation overhead.
+ */
+ private static class PrefixTreeIterator implements Iterator {
+
+ private JavaScriptObject stack;
+
+ /**
+ * Constructor.
+ *
+ * @param tree The base of the PrefixTree to iterate over
+ */
+ public PrefixTreeIterator(PrefixTree tree) {
+ init();
+ addTree(tree, "");
+ }
+
+ public boolean hasNext() {
+ // Have nextImpl peek at the next value that would be returned.
+ return nextImpl(true) != null;
+ }
+
+ /**
+ * {@inheritDoc} Wraps the native implementation with some sanity checking.
+ */
+ public Object next() {
+ final Object toReturn = nextImpl(false);
+
+ // A null response indicates that there was no data to be had.
+ if (toReturn == null) {
+ // Sanity check.
+ if (!hasNext()) {
+ throw new NoSuchElementException("No more elements in the iterator");
+ } else {
+ throw new RuntimeException(
+ "nextImpl() returned null, but hasNext says otherwise");
+ }
+ }
+
+ return toReturn;
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException("PrefixTree does not support "
+ + "removal. Use clear()");
+ }
+
+ /**
+ * Add a frame to the work stack.
+ *
+ * <pre>
+ * frame := {suffixNames, subtrees, prefix, index}
+ * suffixNames := All suffixes in the target PrefixTree
+ * subtrees := All subtrees in the target PrefixTree
+ * prefix := A string that next() will prepend to output from the frame
+ * index := Stores which suffix was last output
+ * </pre>
+ *
+ * @param tree The tree to add
+ * @param prefix The prefix to prepend to values in tree
+ */
+ private native void addTree(PrefixTree tree, String prefix) /*-{
+ var suffixes = [];
+ for (suffix in tree.@com.google.gwt.user.client.ui.PrefixTree::suffixes) {
+ suffixes.push(suffix);
+ }
+
+ var frame = {
+ suffixNames: suffixes,
+ subtrees: tree.@com.google.gwt.user.client.ui.PrefixTree::subtrees,
+ prefix: prefix,
+ index: 0
+ };
+
+ var stack = this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::stack;
+ stack.push(frame);
+ }-*/;
+
+ /**
+ * Initialize JSNI objects.
+ */
+ private native void init() /*-{
+ this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::stack = [];
+ }-*/;
+
+ /**
+ * Access JSNI structures.
+ *
+ * @param peek If this is true, don't advance the iteration, just return the
+ * value that next() would return if it were called
+ * @return The next object, or null if there is an error
+ */
+ private native Object nextImpl(boolean peek) /*-{
+ var stack = this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::stack;
+ var safe = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)
+ var unsafe = @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)
+
+ // Put this in a while loop to handle descent into subtrees without recursion.
+ while (stack.length > 0) {
+ var frame = stack.pop();
+
+ // Check to see if there are any remaining suffixes to output.
+ if (frame.index < frame.suffixNames.length) {
+ var toReturn = frame.prefix + unsafe(frame.suffixNames[frame.index]);
+
+ if (!peek) {
+ frame.index++;
+ }
+
+ // If the current frame has more suffixes, retain it on the stack.
+ if (frame.index < frame.suffixNames.length) {
+ stack.push(frame);
+
+ // Otherwise, put all of the subtrees on the stack.
+ } else {
+ for (key in frame.subtrees) {
+ var target = frame.prefix + unsafe(key);
+ var subtree = frame.subtrees[key];
+ this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::addTree(Lcom/google/gwt/user/client/ui/PrefixTree;Ljava/lang/String;)(subtree, target);
+ }
+ }
+
+ return toReturn;
+
+ // Put all subframes on the stack, and return to top of loop.
+ } else {
+ for (key in frame.subtrees) {
+ var target = frame.prefix + unsafe(key);
+ var subtree = frame.subtrees[key];
+
+ this.@com.google.gwt.user.client.ui.PrefixTree$PrefixTreeIterator::addTree(Lcom/google/gwt/user/client/ui/PrefixTree;Ljava/lang/String;)(subtree, target);
+ }
+ }
+ }
+
+ // This would indicate that next() was called on an empty iterator.
+ // Will throw an exception from next().
+ return null;
+ }-*/;
+ }
+
+ /**
+ * Used by native methods to create an appropriately blessed PrefixTree.
+ *
+ * @param prefixLength Smaller prefix length equals faster, more direct
+ * searches, at a cost of setup time
+ * @return a newly constructed prefix tree
+ */
+ protected static PrefixTree createPrefixTree(int prefixLength) {
+ return new PrefixTree(prefixLength);
+ }
+
+ /**
+ * Ensure that a String can be safely used as a key to an associative-array
+ * JavaScript object by prepending a prefix.
+ *
+ * @param s The String to make safe
+ * @return A safe version of <code>s</code>
+ */
+ private static String safe(String s) {
+ return ':' + s;
+ }
+
+ /**
+ * Undo the operation performed by safe().
+ *
+ * @param s A String returned from safe()
+ * @return The original String passed into safe()
+ */
+ private static String unsafe(String s) {
+ return s.substring(1);
+ }
+
+ /**
+ * Stores the requested prefix length.
+ */
+ protected final int prefixLength;
+
+ /**
+ * Field to store terminal nodes in.
+ */
+ protected JavaScriptObject suffixes;
+
+ /**
+ * Field to store subtrees in.
+ */
+ protected JavaScriptObject subtrees;
+
+ /**
+ * Store the number of elements contained by this PrefixTree and its
+ * sub-trees.
+ */
+ protected int size = 0;
+
+ /**
+ * Constructor.
+ */
+ public PrefixTree() {
+ this(2, null);
+ }
+
+ /**
+ * Constructor.
+ *
+ * @param source Initialize from another collection
+ */
+ public PrefixTree(Collection source) {
+ this(2, source);
+ }
+
+ /**
+ * Constructor.
+ *
+ * @param prefixLength Smaller prefix length equals faster, more direct
+ * searches, at a cost of setup time.
+ */
+ public PrefixTree(final int prefixLength) {
+ this(prefixLength, null);
+ }
+
+ /**
+ * Constructor.
+ *
+ * @param prefixLength Smaller prefix length equals faster, more direct
+ * searches, at a cost of setup time.
+ * @param source Initialize from another collection
+ */
+ public PrefixTree(final int prefixLength, final Collection source) {
+ this.prefixLength = prefixLength;
+ clear();
+
+ if (source != null) {
+ addAll(source);
+ }
+ }
+
+ /**
+ * Adds an object to the PrefixTree.
+ *
+ * @param o The object to add
+ * @throws UnsupportedOperationException if the object is not a String
+ * @return <code>true</code> if the string was added, <code>false</code>
+ * otherwise
+ */
+ public boolean add(Object o) throws UnsupportedOperationException {
+ if (o instanceof String) {
+ return add((String) o);
+ } else {
+ throw new UnsupportedOperationException(
+ "Cannot add non-Strings to PrefixTree");
+ }
+ }
+
+ /**
+ * Add a String to the PrefixTree.
+ *
+ * @param s The data to add
+ * @return <code>true</code> if the string was added, <code>false</code>
+ * otherwise
+ */
+ public native boolean add(String s) /*-{
+ var suffixes =
+ this.@com.google.gwt.user.client.ui.PrefixTree::suffixes;
+ var subtrees =
+ this.@com.google.gwt.user.client.ui.PrefixTree::subtrees;
+ var prefixLength =
+ this.@com.google.gwt.user.client.ui.PrefixTree::prefixLength;
+
+ // This would indicate a mis-use of the code.
+ if ((s == null) || (s.length == 0)) {
+ return false;
+ }
+
+ // Use <= so that strings that are exactly prefixLength long don't
+ // require some kind of null token.
+ if (s.length <= prefixLength) {
+ var safeKey = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)(s);
+ if (suffixes.hasOwnProperty(safeKey)) {
+ return false;
+ } else {
+ // Each tree keeps a count of how large it and its children are.
+ this.@com.google.gwt.user.client.ui.PrefixTree::size++;
+
+ suffixes[safeKey] = true;
+ return true;
+ }
+
+ // Add the string to the appropriate PrefixTree.
+ } else {
+ var prefix = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)(s.slice(0, prefixLength));
+ var theTree;
+
+ if (subtrees.hasOwnProperty(prefix)) {
+ theTree = subtrees[prefix];
+ } else {
+ theTree = @com.google.gwt.user.client.ui.PrefixTree::createPrefixTree(I)(prefixLength * 2);
+ subtrees[prefix] = theTree;
+ }
+
+ var slice = s.slice(prefixLength);
+ if (theTree.@com.google.gwt.user.client.ui.PrefixTree::add(Ljava/lang/String;)(slice)) {
+ // The size of the subtree increased, so we need to update the local count.
+ this.@com.google.gwt.user.client.ui.PrefixTree::size++;
+ return true;
+ } else {
+ return false;
+ }
+ }
+ }-*/;
+
+ /**
+ * Initialize native state.
+ */
+ public native void clear() /*-{
+ this.@com.google.gwt.user.client.ui.PrefixTree::size = 0;
+ this.@com.google.gwt.user.client.ui.PrefixTree::subtrees = {};
+ this.@com.google.gwt.user.client.ui.PrefixTree::suffixes = {};
+ }-*/;
+
+ public boolean contains(Object o) {
+ if (o instanceof String) {
+ return contains((String) o);
+ } else {
+ return false;
+ }
+ }
+
+ public boolean contains(String s) {
+ return (getSuggestions(s, 1)).contains(s);
+ }
+
+ /**
+ * Retrieve suggestions from the PrefixTree. The number of items returned from
+ * getSuggesstions may slightly exceed <code>limit</code> so that all
+ * suffixes and partial stems will be returned. This prevents the search space
+ * from changing size if the PrefixTree is used in an interactive manner.
+ * <br/> The returned List is guaranteed to be safe; changing its contents
+ * will not affect the PrefixTree.
+ *
+ * @param search The prefix to search for
+ * @param limit The desired number of results to retrieve
+ * @return A List of suggestions
+ */
+ public List/* <String> */getSuggestions(String search, int limit) {
+ final List toReturn = new ArrayList();
+ if ((search != null) && (limit > 0)) {
+ suggestImpl(search, "", toReturn, limit);
+ }
+ return toReturn;
+ }
+
+ public Iterator iterator() {
+ return new PrefixTreeIterator(this);
+ }
+
+ /**
+ * Get the number of all elements contained within the PrefixTree.
+ *
+ * @return the size of the prefix tree
+ */
+ public int size() {
+ return size;
+ }
+
+ protected native void suggestImpl(String search, String prefix,
+ Collection output, int limit) /*-{
+ var suffixes =
+ this.@com.google.gwt.user.client.ui.PrefixTree::suffixes;
+ var subtrees =
+ this.@com.google.gwt.user.client.ui.PrefixTree::subtrees;
+ var prefixLength =
+ this.@com.google.gwt.user.client.ui.PrefixTree::prefixLength;
+
+ // Search is too big to be found in current tree, just recurse.
+ if (search.length > prefix.length + prefixLength) {
+ var key = @com.google.gwt.user.client.ui.PrefixTree::safe(Ljava/lang/String;)(search.slice(prefix.length, prefix.length + prefixLength));
+
+ // Just pick the correct subtree, if it exists, and call suggestImpl.
+ if (subtrees.hasOwnProperty(key)) {
+ var subtree = subtrees[key];
+ var target = prefix + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(key);
+ subtree.@com.google.gwt.user.client.ui.PrefixTree::suggestImpl(Ljava/lang/String;Ljava/lang/String;Ljava/util/Collection;I)(search, target, output, limit);
+ }
+
+ // The answer can only exist in this tree's suffixes or subtree keys.
+ } else {
+ // Check local suffixes.
+ for (suffix in suffixes) {
+ var target = prefix + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(suffix);
+ if (target.indexOf(search) == 0) {
+ output.@java.util.Collection::add(Ljava/lang/Object;)(target);
+ }
+
+ if (output.@java.util.Collection::size()() >= limit) {
+ return;
+ }
+ }
+
+ // Check the subtree keys. If the key matches, that implies that all
+ // elements of the subtree would match.
+ for (var key in subtrees) {
+ var target = prefix + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(key);
+ var subtree = subtrees[key];
+
+ // See if the prefix gives us a match.
+ if (target.indexOf(search) == 0) {
+
+ // Provide as many suggestions as will fit into the remaining limit.
+ // If there is only one suggestion, include it.
+ if ((subtree.@com.google.gwt.user.client.ui.PrefixTree::size <= limit - output.@java.util.Collection::size()()) ||
+ (subtree.@com.google.gwt.user.client.ui.PrefixTree::size == 1)) {
+ subtree.@com.google.gwt.user.client.ui.PrefixTree::dump(Ljava/util/Collection;Ljava/lang/String;)(output, target);
+
+ // Otherwise, include as many answers as we can by truncating the suffix
+ } else {
+
+ // Always fully-specify suffixes.
+ for (var suffix in subtree.@com.google.gwt.user.client.ui.PrefixTree::suffixes) {
+ output.@java.util.Collection::add(Ljava/lang/Object;)(target + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(suffix));
+ }
+
+ // Give the keys of the subtree.
+ for (var subkey in subtree.@com.google.gwt.user.client.ui.PrefixTree::subtrees) {
+ output.@java.util.Collection::add(Ljava/lang/Object;)(target + @com.google.gwt.user.client.ui.PrefixTree::unsafe(Ljava/lang/String;)(subkey) + "...");
+ }
+ }
+ }
+ }
+ }
+ }-*/;
+
+ /**
+ * Put all contents of the PrefixTree into a Collection.
+ *
+ * @param output the collection into which the prefixes will be dumped
+ * @param prefix the prefix to filter with
+ */
+ private void dump(Collection output, String prefix) {
+ for (final Iterator i = iterator(); i.hasNext();) {
+ output.add(prefix + (String) i.next());
+ }
+ }
+}
diff --git a/user/test/com/google/gwt/user/client/ui/PrefixTreeTest.java b/user/test/com/google/gwt/user/client/ui/PrefixTreeTest.java
new file mode 100644
index 0000000..0db0926
--- /dev/null
+++ b/user/test/com/google/gwt/user/client/ui/PrefixTreeTest.java
@@ -0,0 +1,217 @@
+/*
+ * Copyright 2007 Google Inc.
+ *
+ * Licensed 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 com.google.gwt.user.client.ui;
+
+import com.google.gwt.junit.client.GWTTestCase;
+
+import java.util.*;
+
+public class PrefixTreeTest extends GWTTestCase {
+ public String getModuleName() {
+ return "com.google.gwt.user.User";
+ }
+
+ /**
+ * Ensure that names of functions declared on the Object prototype are valid
+ * data to insert into the PrefixTree
+ * http://code.google.com/p/google-web-toolkit/issues/detail?id=631
+ */
+ public void testBug631Prefixes() {
+ // Set the prefix length large enough so that we ensure prefixes are
+ // appropriately tested
+ final String[] prototypeNames = {
+ "__proto__", "constructor", "eval", "prototype", "toString",
+ "toSource", "unwatch", "valueOf",};
+
+ for (int i = 0; i < prototypeNames.length; i++) {
+ final String name = prototypeNames[i] + "AAAAAAAAAAAAAAAAAAAA";
+ final PrefixTree tree = new PrefixTree(prototypeNames[i].length());
+
+ assertFalse("Incorrectly found " + name, tree.contains(name));
+
+ assertTrue("First add() didn't return true: " + name, tree.add(name));
+ assertFalse("Second add() of duplicate entry didn't return false: "
+ + name, tree.add(name));
+
+ assertTrue("contains() didn't find added word: " + name,
+ tree.contains(name));
+
+ testSizeByIterator(tree);
+ assertTrue("PrefixTree doesn't contain the desired word",
+ 1 == tree.size());
+ }
+ }
+
+ /**
+ * Ensure that names of functions declared on the Object prototype are valid
+ * data to insert into the PrefixTree
+ * http://code.google.com/p/google-web-toolkit/issues/detail?id=631
+ */
+ public void testBug631Suffixes() {
+ // Set the prefix length large enough so that we ensure suffixes are
+ // appropriately tested
+ final PrefixTree tree = new PrefixTree(100);
+ final String[] prototypeNames = {
+ "__proto__", "constructor", "eval", "prototype", "toString",
+ "toSource", "unwatch", "valueOf",};
+
+ for (int i = 0; i < prototypeNames.length; i++) {
+ final String name = prototypeNames[i];
+
+ assertFalse("Incorrectly found " + name, tree.contains(name));
+
+ assertTrue("First add() didn't return true: " + name, tree.add(name));
+ assertFalse("Second add() of duplicate entry didn't return false: "
+ + name, tree.add(name));
+
+ assertTrue("contains() didn't find added word: " + name,
+ tree.contains(name));
+ }
+
+ testSizeByIterator(tree);
+ assertTrue("PrefixTree doesn't contain all of the desired words",
+ prototypeNames.length == tree.size());
+ }
+
+ /**
+ * Tests adding multiple prefixes and clearing the contents.
+ */
+ public void testMultipleAddsAndClear() {
+ final PrefixTree tree = new PrefixTree();
+
+ assertTrue(tree.add("foo"));
+ assertFalse(tree.add("foo"));
+ assertTrue(tree.add("bar"));
+
+ assertTrue("Expecting iterator to have next", tree.iterator().hasNext());
+ assertTrue("Tree did not have expected size", tree.size() == 2);
+ testSizeByIterator(tree);
+
+ tree.clear();
+ assertFalse("Expecting cleared tree to not hasNext()",
+ tree.iterator().hasNext());
+ assertTrue("Clear did not set size to 0", tree.size() == 0);
+ }
+
+ public void testNewTree() {
+ final PrefixTree tree = new PrefixTree();
+ assertTrue("Newly-created tree had non-zero size", tree.size() == 0);
+ testSizeByIterator(tree);
+
+ assertFalse("Newly-created tree had iterator with a next element",
+ tree.iterator().hasNext());
+ }
+
+ /**
+ * Tests newly constructed prefix tree assumptions.
+ */
+ public void testPlaysWellWithOthers() {
+ final List l = new ArrayList();
+ for (int i = 0; i < 100; i++) {
+ l.add(String.valueOf(i));
+ }
+
+ final PrefixTree tree = new PrefixTree();
+ tree.addAll(l);
+
+ assertTrue("Not all elements copied", tree.size() == l.size());
+ testSizeByIterator(tree);
+
+ assertTrue("Original list does not contain all of the tree",
+ l.containsAll(tree));
+
+ assertTrue("The tree does not contain the original list",
+ tree.containsAll(l));
+ }
+
+ /**
+ * Test whether the prefix tree works appropriately with collections.
+ */
+ public void testSuggestions() {
+ final PrefixTree tree = new PrefixTree();
+
+ assertTrue(tree.add("onetwothree"));
+ assertTrue(tree.add("onetwothree1"));
+ assertTrue(tree.add("onetwothree2"));
+ assertTrue(tree.add("onetwothree3"));
+ assertTrue(tree.add("fourfivesix"));
+ assertTrue(tree.add("fourfivesix1"));
+ assertTrue(tree.add("fourfivesix2"));
+ assertTrue(tree.add("fourfivesix3"));
+ assertTrue(tree.add("seveneightnine"));
+ assertTrue(tree.add("seveneightnine1"));
+ assertTrue(tree.add("seveneightnine2"));
+ assertTrue(tree.add("seveneightnine3"));
+ assertTrue(tree.add("somethingdifferent"));
+
+ assertTrue(tree.size() == 13);
+ testSizeByIterator(tree);
+ assertTrue(tree.iterator().hasNext());
+
+ List l;
+
+ l = tree.getSuggestions("", 13);
+ assertTrue("Expected size of 13, got " + l.size(), l.size() == 13);
+ assertAllStartWith(l, "");
+
+ l = tree.getSuggestions("one", 10);
+ assertTrue("Expected size of 4, got " + l.size(), l.size() == 4);
+ assertAllStartWith(l, "one");
+
+ l = tree.getSuggestions("onetwothree", 10);
+ assertTrue("Expected size of 4, got " + l.size(), l.size() == 4);
+ assertAllStartWith(l, "onetwothree");
+
+ l = tree.getSuggestions("onetwothree1", 10);
+ assertTrue("Expected size of 1, got " + l.size(), l.size() == 1);
+ assertAllStartWith(l, "onetwothree1");
+
+ l = tree.getSuggestions("o", 1);
+ assertTrue("Expected size of 1, got " + l.size(), l.size() == 1);
+ assertTrue(((String) l.get(0)).endsWith("..."));
+ assertAllStartWith(l, "o");
+
+ l = tree.getSuggestions("something", 1);
+ assertTrue("Expected size of 1, got " + l.size(), l.size() == 1);
+ assertEquals("somethingdifferent", l.get(0));
+ assertAllStartWith(l, "somethingdifferent");
+ }
+
+ protected void assertAllStartWith(List l, String prefix) {
+ for (final Iterator i = l.iterator(); i.hasNext();) {
+ final String test = (String) i.next();
+ assertTrue(test + " does not start with " + prefix,
+ test.startsWith(prefix));
+ }
+ }
+
+ /**
+ * Ensure that size() reports the same number of items that the iterator
+ * produces.
+ *
+ * @param tree the tree to test
+ */
+ protected void testSizeByIterator(PrefixTree tree) {
+ int count = 0;
+ for (final Iterator i = tree.iterator(); i.hasNext();) {
+ i.next();
+ count++;
+ }
+
+ assertTrue("Iteration count " + count + " did not match size "
+ + tree.size(), count == tree.size());
+ }
+}
