removed obsolete classes

git-svn-id: https://svn.apache.org/repos/asf/poi/trunk@1706740 13f79535-47bb-0310-9956-ffa450edef68

5 files changed, 0 insertions, 5962 deletions

diff --git a/src/java/org/apache/poi/util/BinaryTree.java b/src/java/org/apache/poi/util/BinaryTree.java
deleted file mode 100644
index e2ae5e58c0..0000000000
--- a/src/java/org/apache/poi/util/BinaryTree.java
+++ /dev/null
@@ -1,2107 +0,0 @@
-/* ====================================================================
-   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.poi.util;
-
-import java.util.*;
-
-/**
- * Red-Black tree-based implementation of Map. This class guarantees
- * that the map will be in both ascending key order and ascending
- * value order, sorted according to the natural order for the key's
- * and value's classes.<p>
- *
- * This Map is intended for applications that need to be able to look
- * up a key-value pairing by either key or value, and need to do so
- * with equal efficiency.<p>
- *
- * While that goal could be accomplished by taking a pair of TreeMaps
- * and redirecting requests to the appropriate TreeMap (e.g.,
- * containsKey would be directed to the TreeMap that maps values to
- * keys, containsValue would be directed to the TreeMap that maps keys
- * to values), there are problems with that implementation,
- * particularly when trying to keep the two TreeMaps synchronized with
- * each other. And if the data contained in the TreeMaps is large, the
- * cost of redundant storage becomes significant.<p>
- *
- * This solution keeps the data properly synchronized and minimizes
- * the data storage. The red-black algorithm is based on TreeMap's,
- * but has been modified to simultaneously map a tree node by key and
- * by value. This doubles the cost of put operations (but so does
- * using two TreeMaps), and nearly doubles the cost of remove
- * operations (there is a savings in that the lookup of the node to be
- * removed only has to be performed once). And since only one node
- * contains the key and value, storage is significantly less than that
- * required by two TreeMaps.<p>
- *
- * There are some limitations placed on data kept in this Map. The
- * biggest one is this:<p>
- *
- * When performing a put operation, neither the key nor the value may
- * already exist in the Map. In the java.util Map implementations
- * (HashMap, TreeMap), you can perform a put with an already mapped
- * key, and neither cares about duplicate values at all ... but this
- * implementation's put method with throw an IllegalArgumentException
- * if either the key or the value is already in the Map.<p>
- *
- * Obviously, that same restriction (and consequence of failing to
- * heed that restriction) applies to the putAll method.<p>
- *
- * The Map.Entry instances returned by the appropriate methods will
- * not allow setValue() and will throw an
- * UnsupportedOperationException on attempts to call that method.<p>
- *
- * New methods are added to take advantage of the fact that values are
- * kept sorted independently of their keys:<p>
- *
- * Object getKeyForValue(Object value) is the opposite of get; it
- * takes a value and returns its key, if any.<p>
- *
- * Object removeValue(Object value) finds and removes the specified
- * value and returns the now un-used key.<p>
- *
- * Set entrySetByValue() returns the Map.Entry's in a Set whose
- * iterator will iterate over the Map.Entry's in ascending order by
- * their corresponding values.<p>
- *
- * Set keySetByValue() returns the keys in a Set whose iterator will
- * iterate over the keys in ascending order by their corresponding
- * values.<p>
- *
- * Collection valuesByValue() returns the values in a Collection whose
- * iterator will iterate over the values in ascending order.<p>
- *
- * @author Marc Johnson (mjohnson at apache dot org)
- */
-//for performance
-@SuppressWarnings("rawtypes")
-public class BinaryTree extends AbstractMap {
-    final Node[] _root;
-    int _size = 0;
-    int _modifications = 0;
-    private final Set[] _key_set = new Set[] { null, null };
-    private final Set[] _entry_set = new Set[] { null, null };
-    private final Collection[] _value_collection = new Collection[] { null, null };
-    static int      _KEY              = 0;
-    static int      _VALUE            = 1;
-    private static int      _INDEX_SUM        = _KEY + _VALUE;
-    private static int      _MINIMUM_INDEX    = 0;
-    private static int      _INDEX_COUNT      = 2;
-    private static String[] _data_name        = new String[]
-    {
-        "key", "value"
-    };
-
-    /**
-     * Construct a new BinaryTree
-     */
-    public BinaryTree() {
-        _root = new Node[]{ null, null, };
-    }
-
-    /**
-     * Constructs a new BinaryTree from an existing Map, with keys and
-     * values sorted
-     *
-     * @param map the map whose mappings are to be placed in this map.
-     *
-     * @exception ClassCastException if the keys in the map are not
-     *                               Comparable, or are not mutually
-     *                               comparable; also if the values in
-     *                               the map are not Comparable, or
-     *                               are not mutually Comparable
-     * @exception NullPointerException if any key or value in the map
-     *                                 is null
-     * @exception IllegalArgumentException if there are duplicate keys
-     *                                     or duplicate values in the
-     *                                     map
-     */
-    public BinaryTree(Map map)
-        throws ClassCastException, NullPointerException,
-                IllegalArgumentException
-    {
-    	this();
-        putAll(map);
-    }
-
-    /**
-     * Returns the key to which this map maps the specified value.
-     * Returns null if the map contains no mapping for this value.
-     *
-     * @param value value whose associated key is to be returned.
-     *
-     * @return the key to which this map maps the specified value, or
-     *         null if the map contains no mapping for this value.
-     *
-     * @exception ClassCastException if the value is of an
-     *                               inappropriate type for this map.
-     * @exception NullPointerException if the value is null
-     */
-    public Object getKeyForValue(Object value)
-        throws ClassCastException, NullPointerException
-    {
-        return doGet(( Comparable ) value, _VALUE);
-    }
-
-    /**
-     * Removes the mapping for this value from this map if present
-     *
-     * @param value value whose mapping is to be removed from the map.
-     *
-     * @return previous key associated with specified value, or null
-     *         if there was no mapping for value.
-     */
-    public Object removeValue(Object value)
-    {
-        return doRemove(( Comparable ) value, _VALUE);
-    }
-
-    /**
-     * Returns a set view of the mappings contained in this map. Each
-     * element in the returned set is a Map.Entry. The set is backed
-     * by the map, so changes to the map are reflected in the set, and
-     * vice-versa.  If the map is modified while an iteration over the
-     * set is in progress, the results of the iteration are
-     * undefined. The set supports element removal, which removes the
-     * corresponding mapping from the map, via the Iterator.remove,
-     * Set.remove, removeAll, retainAll and clear operations.  It does
-     * not support the add or addAll operations.<p>
-     *
-     * The difference between this method and entrySet is that
-     * entrySet's iterator() method returns an iterator that iterates
-     * over the mappings in ascending order by key. This method's
-     * iterator method iterates over the mappings in ascending order
-     * by value.
-     *
-     * @return a set view of the mappings contained in this map.
-     */
-    public Set entrySetByValue()
-    {
-        if (_entry_set[ _VALUE ] == null)
-        {
-            _entry_set[ _VALUE ] = new AbstractSet()
-            {
-                public Iterator iterator()
-                {
-                    return new BinaryTreeIterator(_VALUE)
-                    {
-                        protected Object doGetNext()
-                        {
-                            return _last_returned_node;
-                        }
-                    };
-                }
-
-                public boolean contains(Object o)
-                {
-                    if (!(o instanceof Map.Entry))
-                    {
-                        return false;
-                    }
-                    Map.Entry entry = ( Map.Entry ) o;
-                    Object    key   = entry.getKey();
-                    Node      node  = lookup(( Comparable ) entry.getValue(),
-                                             _VALUE);
-
-                    return (node != null) && node.getData(_KEY).equals(key);
-                }
-
-                public boolean remove(Object o)
-                {
-                    if (!(o instanceof Map.Entry))
-                    {
-                        return false;
-                    }
-                    Map.Entry entry = ( Map.Entry ) o;
-                    Object    key   = entry.getKey();
-                    Node      node  = lookup(( Comparable ) entry.getValue(),
-                                             _VALUE);
-
-                    if ((node != null) && node.getData(_KEY).equals(key))
-                    {
-                        doRedBlackDelete(node);
-                        return true;
-                    }
-                    return false;
-                }
-
-                public int size()
-                {
-                    return BinaryTree.this.size();
-                }
-
-                public void clear()
-                {
-                    BinaryTree.this.clear();
-                }
-            };
-        }
-        return _entry_set[ _VALUE ];
-    }
-
-    /**
-     * Returns a set view of the keys contained in this map.  The set
-     * is backed by the map, so changes to the map are reflected in
-     * the set, and vice-versa. If the map is modified while an
-     * iteration over the set is in progress, the results of the
-     * iteration are undefined. The set supports element removal,
-     * which removes the corresponding mapping from the map, via the
-     * Iterator.remove, Set.remove, removeAll, retainAll, and clear
-     * operations. It does not support the add or addAll
-     * operations.<p>
-     *
-     * The difference between this method and keySet is that keySet's
-     * iterator() method returns an iterator that iterates over the
-     * keys in ascending order by key. This method's iterator method
-     * iterates over the keys in ascending order by value.
-     *
-     * @return a set view of the keys contained in this map.
-     */
-
-    public Set keySetByValue()
-    {
-        if (_key_set[ _VALUE ] == null)
-        {
-            _key_set[ _VALUE ] = new AbstractSet()
-            {
-                public Iterator iterator()
-                {
-                    return new BinaryTreeIterator(_VALUE)
-                    {
-                        protected Object doGetNext()
-                        {
-                            return _last_returned_node.getData(_KEY);
-                        }
-                    };
-                }
-
-                public int size()
-                {
-                    return BinaryTree.this.size();
-                }
-
-                public boolean contains(Object o)
-                {
-                    return containsKey(o);
-                }
-
-                public boolean remove(Object o)
-                {
-                    int old_size = _size;
-
-                    BinaryTree.this.remove(o);
-                    return _size != old_size;
-                }
-
-                public void clear()
-                {
-                    BinaryTree.this.clear();
-                }
-            };
-        }
-        return _key_set[ _VALUE ];
-    }
-
-    /**
-     * Returns a collection view of the values contained in this
-     * map. The collection is backed by the map, so changes to the map
-     * are reflected in the collection, and vice-versa. If the map is
-     * modified while an iteration over the collection is in progress,
-     * the results of the iteration are undefined. The collection
-     * supports element removal, which removes the corresponding
-     * mapping from the map, via the Iterator.remove,
-     * Collection.remove, removeAll, retainAll and clear operations.
-     * It does not support the add or addAll operations.<p>
-     *
-     * The difference between this method and values is that values's
-     * iterator() method returns an iterator that iterates over the
-     * values in ascending order by key. This method's iterator method
-     * iterates over the values in ascending order by key.
-     *
-     * @return a collection view of the values contained in this map.
-     */
-
-    public Collection valuesByValue()
-    {
-        if (_value_collection[ _VALUE ] == null)
-        {
-            _value_collection[ _VALUE ] = new AbstractCollection()
-            {
-                public Iterator iterator()
-                {
-                    return new BinaryTreeIterator(_VALUE)
-                    {
-                        protected Object doGetNext()
-                        {
-                            return _last_returned_node.getData(_VALUE);
-                        }
-                    };
-                }
-
-                public int size()
-                {
-                    return BinaryTree.this.size();
-                }
-
-                public boolean contains(Object o)
-                {
-                    return containsValue(o);
-                }
-
-                public boolean remove(Object o)
-                {
-                    int old_size = _size;
-
-                    removeValue(o);
-                    return _size != old_size;
-                }
-
-                public boolean removeAll(Collection c)
-                {
-                    boolean  modified = false;
-                    Iterator iter     = c.iterator();
-
-                    while (iter.hasNext())
-                    {
-                        if (removeValue(iter.next()) != null)
-                        {
-                            modified = true;
-                        }
-                    }
-                    return modified;
-                }
-
-                public void clear()
-                {
-                    BinaryTree.this.clear();
-                }
-            };
-        }
-        return _value_collection[ _VALUE ];
-    }
-
-    /**
-     * common remove logic (remove by key or remove by value)
-     *
-     * @param o the key, or value, that we're looking for
-     * @param index _KEY or _VALUE
-     *
-     * @return the key, if remove by value, or the value, if remove by
-     *         key. null if the specified key or value could not be
-     *         found
-     */
-    private Object doRemove(Comparable o, int index)
-    {
-        Node   node = lookup(o, index);
-        Object rval = null;
-
-        if (node != null)
-        {
-            rval = node.getData(oppositeIndex(index));
-            doRedBlackDelete(node);
-        }
-        return rval;
-    }
-
-    /**
-     * common get logic, used to get by key or get by value
-     *
-     * @param o the key or value that we're looking for
-     * @param index _KEY or _VALUE
-     *
-     * @return the key (if the value was mapped) or the value (if the
-     *         key was mapped); null if we couldn't find the specified
-     *         object
-     */
-    private Object doGet(Comparable o, int index)
-    {
-        checkNonNullComparable(o, index);
-        Node node = lookup(o, index);
-
-        return ((node == null) ? null
-                               : node.getData(oppositeIndex(index)));
-    }
-
-    /**
-     * Get the opposite index of the specified index
-     *
-     * @param index _KEY or _VALUE
-     *
-     * @return _VALUE (if _KEY was specified), else _KEY
-     */
-    private int oppositeIndex(int index)
-    {
-
-        // old trick ... to find the opposite of a value, m or n,
-        // subtract the value from the sum of the two possible
-        // values. (m + n) - m = n; (m + n) - n = m
-        return _INDEX_SUM - index;
-    }
-
-    /**
-     * do the actual lookup of a piece of data
-     *
-     * @param data the key or value to be looked up
-     * @param index _KEY or _VALUE
-     *
-     * @return the desired Node, or null if there is no mapping of the
-     *         specified data
-     */
-    public Node lookup(Comparable data, int index)
-    {
-        Node rval = null;
-        Node node = _root[ index ];
-
-        while (node != null)
-        {
-            int cmp = compare(data, node.getData(index));
-
-            if (cmp == 0)
-            {
-                rval = node;
-                break;
-            }
-            node = (cmp < 0) ? node.getLeft(index)
-                             : node.getRight(index);
-        }
-        return rval;
-    }
-
-    /**
-     * Compare two objects
-     *
-     * @param o1 the first object
-     * @param o2 the second object
-     *
-     * @return negative value if o1 < o2; 0 if o1 == o2; positive
-     *         value if o1 > o2
-     */
-    private static int compare(Comparable o1, Comparable o2)
-    {
-        return o1.compareTo(o2);
-    }
-
-    /**
-     * find the least node from a given node. very useful for starting
-     * a sorting iterator ...
-     *
-     * @param node the node from which we will start searching
-     * @param index _KEY or _VALUE
-     *
-     * @return the smallest node, from the specified node, in the
-     *         specified mapping
-     */
-    static Node leastNode(Node node, int index)
-    {
-        Node rval = node;
-
-        if (rval != null)
-        {
-            while (rval.getLeft(index) != null)
-            {
-                rval = rval.getLeft(index);
-            }
-        }
-        return rval;
-    }
-
-    /**
-     * get the next larger node from the specified node
-     *
-     * @param node the node to be searched from
-     * @param index _KEY or _VALUE
-     *
-     * @return the specified node
-     */
-    static Node nextGreater(Node node, int index)
-    {
-        Node rval = null;
-
-        if (node == null)
-        {
-            rval = null;
-        }
-        else if (node.getRight(index) != null)
-        {
-
-            // everything to the node's right is larger. The least of
-            // the right node's descendents is the next larger node
-            rval = leastNode(node.getRight(index), index);
-        }
-        else
-        {
-
-            // traverse up our ancestry until we find an ancestor that
-            // is null or one whose left child is our ancestor. If we
-            // find a null, then this node IS the largest node in the
-            // tree, and there is no greater node. Otherwise, we are
-            // the largest node in the subtree on that ancestor's left
-            // ... and that ancestor is the next greatest node
-            Node parent = node.getParent(index);
-            Node child  = node;
-
-            while ((parent != null) && (child == parent.getRight(index)))
-            {
-                child  = parent;
-                parent = parent.getParent(index);
-            }
-            rval = parent;
-        }
-        return rval;
-    }
-
-    /**
-     * copy the color from one node to another, dealing with the fact
-     * that one or both nodes may, in fact, be null
-     *
-     * @param from the node whose color we're copying; may be null
-     * @param to the node whose color we're changing; may be null
-     * @param index _KEY or _VALUE
-     */
-    private static void copyColor(Node from, Node to, int index)
-    {
-        if (to != null)
-        {
-            if (from == null)
-            {
-
-                // by default, make it black
-                to.setBlack(index);
-            }
-            else
-            {
-                to.copyColor(from, index);
-            }
-        }
-    }
-
-    /**
-     * is the specified node red? if the node does not exist, no, it's
-     * black, thank you
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static boolean isRed(Node node, int index)
-    {
-        return node == null ? false : node.isRed(index);
-    }
-
-    /**
-     * is the specified black red? if the node does not exist, sure,
-     * it's black, thank you
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static boolean isBlack(Node node, int index)
-    {
-        return node == null ? true : node.isBlack(index);
-    }
-
-    /**
-     * force a node (if it exists) red
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static void makeRed(Node node, int index)
-    {
-        if (node != null)
-        {
-            node.setRed(index);
-        }
-    }
-
-    /**
-     * force a node (if it exists) black
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static void makeBlack(Node node, int index)
-    {
-        if (node != null)
-        {
-            node.setBlack(index);
-        }
-    }
-
-    /**
-     * get a node's grandparent. mind you, the node, its parent, or
-     * its grandparent may not exist. no problem
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static Node getGrandParent(Node node, int index)
-    {
-        return getParent(getParent(node, index), index);
-    }
-
-    /**
-     * get a node's parent. mind you, the node, or its parent, may not
-     * exist. no problem
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static Node getParent(Node node, int index)
-    {
-        return ((node == null) ? null
-                               : node.getParent(index));
-    }
-
-    /**
-     * get a node's right child. mind you, the node may not exist. no
-     * problem
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static Node getRightChild(Node node, int index)
-    {
-        return (node == null) ? null
-                              : node.getRight(index);
-    }
-
-    /**
-     * get a node's left child. mind you, the node may not exist. no
-     * problem
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static Node getLeftChild(Node node, int index)
-    {
-        return (node == null) ? null
-                              : node.getLeft(index);
-    }
-
-    /**
-     * is this node its parent's left child? mind you, the node, or
-     * its parent, may not exist. no problem. if the node doesn't
-     * exist ... it's its non-existent parent's left child. If the
-     * node does exist but has no parent ... no, we're not the
-     * non-existent parent's left child. Otherwise (both the specified
-     * node AND its parent exist), check.
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static boolean isLeftChild(Node node, int index) {
-        if (node == null) {
-            return true;
-        }
-        if (node.getParent(index) == null) {
-            return false;
-        }
-        return node == node.getParent(index).getLeft(index);
-    }
-
-    /**
-     * is this node its parent's right child? mind you, the node, or
-     * its parent, may not exist. no problem. if the node doesn't
-     * exist ... it's its non-existent parent's right child. If the
-     * node does exist but has no parent ... no, we're not the
-     * non-existent parent's right child. Otherwise (both the
-     * specified node AND its parent exist), check.
-     *
-     * @param node the node (may be null) in question
-     * @param index _KEY or _VALUE
-     */
-    private static boolean isRightChild(Node node, int index)
-    {
-        if (node == null) {
-            return true;
-        }
-        if (node.getParent(index) == null) {
-            return false;
-        }
-        return node == node.getParent(index).getRight(index);
-    }
-
-    /**
-     * do a rotate left. standard fare in the world of balanced trees
-     *
-     * @param node the node to be rotated
-     * @param index _KEY or _VALUE
-     */
-    private void rotateLeft(Node node, int index)
-    {
-        Node right_child = node.getRight(index);
-
-        node.setRight(right_child.getLeft(index), index);
-        if (right_child.getLeft(index) != null)
-        {
-            right_child.getLeft(index).setParent(node, index);
-        }
-        right_child.setParent(node.getParent(index), index);
-        if (node.getParent(index) == null)
-        {
-
-            // node was the root ... now its right child is the root
-            _root[ index ] = right_child;
-        }
-        else if (node.getParent(index).getLeft(index) == node)
-        {
-            node.getParent(index).setLeft(right_child, index);
-        }
-        else
-        {
-            node.getParent(index).setRight(right_child, index);
-        }
-        right_child.setLeft(node, index);
-        node.setParent(right_child, index);
-    }
-
-    /**
-     * do a rotate right. standard fare in the world of balanced trees
-     *
-     * @param node the node to be rotated
-     * @param index _KEY or _VALUE
-     */
-    private void rotateRight(Node node, int index)
-    {
-        Node left_child = node.getLeft(index);
-
-        node.setLeft(left_child.getRight(index), index);
-        if (left_child.getRight(index) != null)
-        {
-            left_child.getRight(index).setParent(node, index);
-        }
-        left_child.setParent(node.getParent(index), index);
-        if (node.getParent(index) == null)
-        {
-
-            // node was the root ... now its left child is the root
-            _root[ index ] = left_child;
-        }
-        else if (node.getParent(index).getRight(index) == node)
-        {
-            node.getParent(index).setRight(left_child, index);
-        }
-        else
-        {
-            node.getParent(index).setLeft(left_child, index);
-        }
-        left_child.setRight(node, index);
-        node.setParent(left_child, index);
-    }
-
-    /**
-     * complicated red-black insert stuff. Based on Sun's TreeMap
-     * implementation, though it's barely recognizeable any more
-     *
-     * @param inserted_node the node to be inserted
-     * @param index _KEY or _VALUE
-     */
-    private void doRedBlackInsert(Node inserted_node, int index)
-    {
-        Node current_node = inserted_node;
-
-        makeRed(current_node, index);
-        while ((current_node != null) && (current_node != _root[ index ])
-                && (isRed(current_node.getParent(index), index)))
-        {
-            if (isLeftChild(getParent(current_node, index), index))
-            {
-                Node y = getRightChild(getGrandParent(current_node, index),
-                                       index);
-
-                if (isRed(y, index))
-                {
-                    makeBlack(getParent(current_node, index), index);
-                    makeBlack(y, index);
-                    makeRed(getGrandParent(current_node, index), index);
-                    current_node = getGrandParent(current_node, index);
-                }
-                else
-                {
-                    if (isRightChild(current_node, index))
-                    {
-                        current_node = getParent(current_node, index);
-                        rotateLeft(current_node, index);
-                    }
-                    makeBlack(getParent(current_node, index), index);
-                    makeRed(getGrandParent(current_node, index), index);
-                    if (getGrandParent(current_node, index) != null)
-                    {
-                        rotateRight(getGrandParent(current_node, index),
-                                    index);
-                    }
-                }
-            }
-            else
-            {
-
-                // just like clause above, except swap left for right
-                Node y = getLeftChild(getGrandParent(current_node, index),
-                                      index);
-
-                if (isRed(y, index))
-                {
-                    makeBlack(getParent(current_node, index), index);
-                    makeBlack(y, index);
-                    makeRed(getGrandParent(current_node, index), index);
-                    current_node = getGrandParent(current_node, index);
-                }
-                else
-                {
-                    if (isLeftChild(current_node, index))
-                    {
-                        current_node = getParent(current_node, index);
-                        rotateRight(current_node, index);
-                    }
-                    makeBlack(getParent(current_node, index), index);
-                    makeRed(getGrandParent(current_node, index), index);
-                    if (getGrandParent(current_node, index) != null)
-                    {
-                        rotateLeft(getGrandParent(current_node, index),
-                                   index);
-                    }
-                }
-            }
-        }
-        makeBlack(_root[ index ], index);
-    }
-
-    /**
-     * complicated red-black delete stuff. Based on Sun's TreeMap
-     * implementation, though it's barely recognizeable any more
-     *
-     * @param deleted_node the node to be deleted
-     */
-    void doRedBlackDelete(Node deleted_node)
-    {
-        for (int index = _MINIMUM_INDEX; index < _INDEX_COUNT; index++)
-        {
-
-            // if deleted node has both left and children, swap with
-            // the next greater node
-            if ((deleted_node.getLeft(index) != null)
-                    && (deleted_node.getRight(index) != null))
-            {
-                swapPosition(nextGreater(deleted_node, index), deleted_node,
-                             index);
-            }
-            Node replacement = ((deleted_node.getLeft(index) != null)
-                                ? deleted_node.getLeft(index)
-                                : deleted_node.getRight(index));
-
-            if (replacement != null)
-            {
-                replacement.setParent(deleted_node.getParent(index), index);
-                if (deleted_node.getParent(index) == null)
-                {
-                    _root[ index ] = replacement;
-                }
-                else if (deleted_node
-                         == deleted_node.getParent(index).getLeft(index))
-                {
-                    deleted_node.getParent(index).setLeft(replacement, index);
-                }
-                else
-                {
-                    deleted_node.getParent(index).setRight(replacement,
-                                           index);
-                }
-                deleted_node.setLeft(null, index);
-                deleted_node.setRight(null, index);
-                deleted_node.setParent(null, index);
-                if (isBlack(deleted_node, index))
-                {
-                    doRedBlackDeleteFixup(replacement, index);
-                }
-            }
-            else
-            {
-
-                // replacement is null
-                if (deleted_node.getParent(index) == null)
-                {
-
-                    // empty tree
-                    _root[ index ] = null;
-                }
-                else
-                {
-
-                    // deleted node had no children
-                    if (isBlack(deleted_node, index))
-                    {
-                        doRedBlackDeleteFixup(deleted_node, index);
-                    }
-                    if (deleted_node.getParent(index) != null)
-                    {
-                        if (deleted_node
-                                == deleted_node.getParent(index)
-                                    .getLeft(index))
-                        {
-                            deleted_node.getParent(index).setLeft(null,
-                                                   index);
-                        }
-                        else
-                        {
-                            deleted_node.getParent(index).setRight(null,
-                                                   index);
-                        }
-                        deleted_node.setParent(null, index);
-                    }
-                }
-            }
-        }
-        shrink();
-    }
-
-    /**
-     * complicated red-black delete stuff. Based on Sun's TreeMap
-     * implementation, though it's barely recognizeable any more. This
-     * rebalances the tree (somewhat, as red-black trees are not
-     * perfectly balanced -- perfect balancing takes longer)
-     *
-     * @param replacement_node  the node being replaced
-     * @param index _KEY or _VALUE
-     */
-    private void doRedBlackDeleteFixup(Node replacement_node,
-                                       int index)
-    {
-        Node current_node = replacement_node;
-
-        while ((current_node != _root[ index ])
-                && (isBlack(current_node, index)))
-        {
-            if (isLeftChild(current_node, index))
-            {
-                Node sibling_node =
-                    getRightChild(getParent(current_node, index), index);
-
-                if (isRed(sibling_node, index))
-                {
-                    makeBlack(sibling_node, index);
-                    makeRed(getParent(current_node, index), index);
-                    rotateLeft(getParent(current_node, index), index);
-                    sibling_node =
-                        getRightChild(getParent(current_node, index), index);
-                }
-                if (isBlack(getLeftChild(sibling_node, index), index)
-                        && isBlack(getRightChild(sibling_node, index), index))
-                {
-                    makeRed(sibling_node, index);
-                    current_node = getParent(current_node, index);
-                }
-                else
-                {
-                    if (isBlack(getRightChild(sibling_node, index), index))
-                    {
-                        makeBlack(getLeftChild(sibling_node, index), index);
-                        makeRed(sibling_node, index);
-                        rotateRight(sibling_node, index);
-                        sibling_node =
-                            getRightChild(getParent(current_node, index),
-                                          index);
-                    }
-                    copyColor(getParent(current_node, index), sibling_node,
-                              index);
-                    makeBlack(getParent(current_node, index), index);
-                    makeBlack(getRightChild(sibling_node, index), index);
-                    rotateLeft(getParent(current_node, index), index);
-                    current_node = _root[ index ];
-                }
-            }
-            else
-            {
-                Node sibling_node =
-                    getLeftChild(getParent(current_node, index), index);
-
-                if (isRed(sibling_node, index))
-                {
-                    makeBlack(sibling_node, index);
-                    makeRed(getParent(current_node, index), index);
-                    rotateRight(getParent(current_node, index), index);
-                    sibling_node =
-                        getLeftChild(getParent(current_node, index), index);
-                }
-                if (isBlack(getRightChild(sibling_node, index), index)
-                        && isBlack(getLeftChild(sibling_node, index), index))
-                {
-                    makeRed(sibling_node, index);
-                    current_node = getParent(current_node, index);
-                }
-                else
-                {
-                    if (isBlack(getLeftChild(sibling_node, index), index))
-                    {
-                        makeBlack(getRightChild(sibling_node, index), index);
-                        makeRed(sibling_node, index);
-                        rotateLeft(sibling_node, index);
-                        sibling_node =
-                            getLeftChild(getParent(current_node, index),
-                                         index);
-                    }
-                    copyColor(getParent(current_node, index), sibling_node,
-                              index);
-                    makeBlack(getParent(current_node, index), index);
-                    makeBlack(getLeftChild(sibling_node, index), index);
-                    rotateRight(getParent(current_node, index), index);
-                    current_node = _root[ index ];
-                }
-            }
-        }
-        makeBlack(current_node, index);
-    }
-
-    /**
-     * swap two nodes (except for their content), taking care of
-     * special cases where one is the other's parent ... hey, it
-     * happens.
-     *
-     * @param x one node
-     * @param y another node
-     * @param index _KEY or _VALUE
-     */
-    private void swapPosition(Node x, Node y, int index)
-    {
-
-        // Save initial values.
-        Node    x_old_parent      = x.getParent(index);
-        Node    x_old_left_child  = x.getLeft(index);
-        Node    x_old_right_child = x.getRight(index);
-        Node    y_old_parent      = y.getParent(index);
-        Node    y_old_left_child  = y.getLeft(index);
-        Node    y_old_right_child = y.getRight(index);
-        boolean x_was_left_child  =
-            (x.getParent(index) != null)
-            && (x == x.getParent(index).getLeft(index));
-        boolean y_was_left_child  =
-            (y.getParent(index) != null)
-            && (y == y.getParent(index).getLeft(index));
-
-        // Swap, handling special cases of one being the other's parent.
-        if (x == y_old_parent)
-        {   // x was y's parent
-            x.setParent(y, index);
-            if (y_was_left_child)
-            {
-                y.setLeft(x, index);
-                y.setRight(x_old_right_child, index);
-            }
-            else
-            {
-                y.setRight(x, index);
-                y.setLeft(x_old_left_child, index);
-            }
-        }
-        else
-        {
-            x.setParent(y_old_parent, index);
-            if (y_old_parent != null)
-            {
-                if (y_was_left_child)
-                {
-                    y_old_parent.setLeft(x, index);
-                }
-                else
-                {
-                    y_old_parent.setRight(x, index);
-                }
-            }
-            y.setLeft(x_old_left_child, index);
-            y.setRight(x_old_right_child, index);
-        }
-        if (y == x_old_parent)
-        {   // y was x's parent
-            y.setParent(x, index);
-            if (x_was_left_child)
-            {
-                x.setLeft(y, index);
-                x.setRight(y_old_right_child, index);
-            }
-            else
-            {
-                x.setRight(y, index);
-                x.setLeft(y_old_left_child, index);
-            }
-        }
-        else
-        {
-            y.setParent(x_old_parent, index);
-            if (x_old_parent != null)
-            {
-                if (x_was_left_child)
-                {
-                    x_old_parent.setLeft(y, index);
-                }
-                else
-                {
-                    x_old_parent.setRight(y, index);
-                }
-            }
-            x.setLeft(y_old_left_child, index);
-            x.setRight(y_old_right_child, index);
-        }
-
-        // Fix children's parent pointers
-        if (x.getLeft(index) != null)
-        {
-            x.getLeft(index).setParent(x, index);
-        }
-        if (x.getRight(index) != null)
-        {
-            x.getRight(index).setParent(x, index);
-        }
-        if (y.getLeft(index) != null)
-        {
-            y.getLeft(index).setParent(y, index);
-        }
-        if (y.getRight(index) != null)
-        {
-            y.getRight(index).setParent(y, index);
-        }
-        x.swapColors(y, index);
-
-        // Check if _root changed
-        if (_root[ index ] == x)
-        {
-            _root[ index ] = y;
-        }
-        else if (_root[ index ] == y)
-        {
-            _root[ index ] = x;
-        }
-    }
-
-    /**
-     * check if an object is fit to be proper input ... has to be
-     * Comparable and non-null
-     *
-     * @param o the object being checked
-     * @param index _KEY or _VALUE (used to put the right word in the
-     *              exception message)
-     *
-     * @exception NullPointerException if o is null
-     * @exception ClassCastException if o is not Comparable
-     */
-    private static void checkNonNullComparable(Object o,
-                                               int index)
-    {
-        if (o == null)
-        {
-            throw new NullPointerException(_data_name[ index ]
-                                           + " cannot be null");
-        }
-        if (!(o instanceof Comparable))
-        {
-            throw new ClassCastException(_data_name[ index ]
-                                         + " must be Comparable");
-        }
-    }
-
-    /**
-     * check a key for validity (non-null and implements Comparable)
-     *
-     * @param key the key to be checked
-     *
-     * @exception NullPointerException if key is null
-     * @exception ClassCastException if key is not Comparable
-     */
-    private static void checkKey(Object key)
-    {
-        checkNonNullComparable(key, _KEY);
-    }
-
-    /**
-     * check a value for validity (non-null and implements Comparable)
-     *
-     * @param value the value to be checked
-     *
-     * @exception NullPointerException if value is null
-     * @exception ClassCastException if value is not Comparable
-     */
-    private static void checkValue(Object value)
-    {
-        checkNonNullComparable(value, _VALUE);
-    }
-
-    /**
-     * check a key and a value for validity (non-null and implements
-     * Comparable)
-     *
-     * @param key the key to be checked
-     * @param value the value to be checked
-     *
-     * @exception NullPointerException if key or value is null
-     * @exception ClassCastException if key or value is not Comparable
-     */
-    private static void checkKeyAndValue(Object key, Object value)
-    {
-        checkKey(key);
-        checkValue(value);
-    }
-
-    /**
-     * increment the modification count -- used to check for
-     * concurrent modification of the map through the map and through
-     * an Iterator from one of its Set or Collection views
-     */
-    private void modify()
-    {
-        _modifications++;
-    }
-
-    /**
-     * bump up the size and note that the map has changed
-     */
-    private void grow()
-    {
-        modify();
-        _size++;
-    }
-
-    /**
-     * decrement the size and note that the map has changed
-     */
-    private void shrink()
-    {
-        modify();
-        _size--;
-    }
-
-    /**
-     * insert a node by its value
-     *
-     * @param newNode the node to be inserted
-     *
-     * @exception IllegalArgumentException if the node already exists
-     *                                     in the value mapping
-     */
-    private void insertValue(Node newNode)
-        throws IllegalArgumentException
-    {
-        Node node = _root[ _VALUE ];
-
-        while (true)
-        {
-            int cmp = compare(newNode.getData(_VALUE), node.getData(_VALUE));
-
-            if (cmp == 0)
-            {
-                throw new IllegalArgumentException(
-                    "Cannot store a duplicate value (\""
-                    + newNode.getData(_VALUE) + "\") in this Map");
-            }
-            else if (cmp < 0)
-            {
-                if (node.getLeft(_VALUE) != null)
-                {
-                    node = node.getLeft(_VALUE);
-                }
-                else
-                {
-                    node.setLeft(newNode, _VALUE);
-                    newNode.setParent(node, _VALUE);
-                    doRedBlackInsert(newNode, _VALUE);
-                    break;
-                }
-            }
-            else
-            {   // cmp > 0
-                if (node.getRight(_VALUE) != null)
-                {
-                    node = node.getRight(_VALUE);
-                }
-                else
-                {
-                    node.setRight(newNode, _VALUE);
-                    newNode.setParent(node, _VALUE);
-                    doRedBlackInsert(newNode, _VALUE);
-                    break;
-                }
-            }
-        }
-    }
-
-    /* ********** START implementation of Map ********** */
-
-    /**
-     * Returns the number of key-value mappings in this map. If the
-     * map contains more than Integer.MAX_VALUE elements, returns
-     * Integer.MAX_VALUE.
-     *
-     * @return the number of key-value mappings in this map.
-     */
-    public int size()
-    {
-        return _size;
-    }
-
-    /**
-     * Returns true if this map contains a mapping for the specified
-     * key.
-     *
-     * @param key key whose presence in this map is to be tested.
-     *
-     * @return true if this map contains a mapping for the specified
-     *         key.
-     *
-     * @exception ClassCastException if the key is of an inappropriate
-     *                               type for this map.
-     * @exception NullPointerException if the key is null
-     */
-    public boolean containsKey(Object key)
-        throws ClassCastException, NullPointerException
-    {
-        checkKey(key);
-        return lookup(( Comparable ) key, _KEY) != null;
-    }
-
-    /**
-     * Returns true if this map maps one or more keys to the
-     * specified value.
-     *
-     * @param value value whose presence in this map is to be tested.
-     *
-     * @return true if this map maps one or more keys to the specified
-     *         value.
-     */
-    public boolean containsValue(Object value)
-    {
-        checkValue(value);
-        return lookup(( Comparable ) value, _VALUE) != null;
-    }
-
-    /**
-     * Returns the value to which this map maps the specified
-     * key. Returns null if the map contains no mapping for this key.
-     *
-     * @param key key whose associated value is to be returned.
-     *
-     * @return the value to which this map maps the specified key, or
-     *         null if the map contains no mapping for this key.
-     *
-     * @exception ClassCastException if the key is of an inappropriate
-     *                               type for this map.
-     * @exception NullPointerException if the key is null
-     */
-    public Object get(Object key)
-        throws ClassCastException, NullPointerException
-    {
-        return doGet(( Comparable ) key, _KEY);
-    }
-
-    /**
-     * Associates the specified value with the specified key in this
-     * map.
-     *
-     * @param key key with which the specified value is to be
-     *            associated.
-     * @param value value to be associated with the specified key.
-     *
-     * @return null
-     *
-     * @exception ClassCastException if the class of the specified key
-     *                               or value prevents it from being
-     *                               stored in this map.
-     * @exception NullPointerException if the specified key or value
-     *                                 is null
-     * @exception IllegalArgumentException if the key duplicates an
-     *                                     existing key, or if the
-     *                                     value duplicates an
-     *                                     existing value
-     */
-    public Object put(Object key, Object value)
-        throws ClassCastException, NullPointerException,
-                IllegalArgumentException
-    {
-        checkKeyAndValue(key, value);
-        Node node = _root[ _KEY ];
-
-        if (node == null)
-        {
-            Node root = new Node(( Comparable ) key, ( Comparable ) value);
-
-            _root[ _KEY ]   = root;
-            _root[ _VALUE ] = root;
-            grow();
-        }
-        else
-        {
-            while (true)
-            {
-                int cmp = compare(( Comparable ) key, node.getData(_KEY));
-
-                if (cmp == 0)
-                {
-                    throw new IllegalArgumentException(
-                        "Cannot store a duplicate key (\"" + key
-                        + "\") in this Map");
-                }
-                else if (cmp < 0)
-                {
-                    if (node.getLeft(_KEY) != null)
-                    {
-                        node = node.getLeft(_KEY);
-                    }
-                    else
-                    {
-                        Node newNode = new Node(( Comparable ) key,
-                                                ( Comparable ) value);
-
-                        insertValue(newNode);
-                        node.setLeft(newNode, _KEY);
-                        newNode.setParent(node, _KEY);
-                        doRedBlackInsert(newNode, _KEY);
-                        grow();
-                        break;
-                    }
-                }
-                else
-                {   // cmp > 0
-                    if (node.getRight(_KEY) != null)
-                    {
-                        node = node.getRight(_KEY);
-                    }
-                    else
-                    {
-                        Node newNode = new Node(( Comparable ) key,
-                                                ( Comparable ) value);
-
-                        insertValue(newNode);
-                        node.setRight(newNode, _KEY);
-                        newNode.setParent(node, _KEY);
-                        doRedBlackInsert(newNode, _KEY);
-                        grow();
-                        break;
-                    }
-                }
-            }
-        }
-        return null;
-    }
-
-    /**
-     * Removes the mapping for this key from this map if present
-     *
-     * @param key key whose mapping is to be removed from the map.
-     *
-     * @return previous value associated with specified key, or null
-     *         if there was no mapping for key.
-     */
-    public Object remove(Object key)
-    {
-        return doRemove(( Comparable ) key, _KEY);
-    }
-
-    /**
-     * Removes all mappings from this map
-     */
-    public void clear()
-    {
-        modify();
-        _size           = 0;
-        _root[ _KEY ]   = null;
-        _root[ _VALUE ] = null;
-    }
-
-    /**
-     * Returns a set view of the keys contained in this map.  The set
-     * is backed by the map, so changes to the map are reflected in
-     * the set, and vice-versa. If the map is modified while an
-     * iteration over the set is in progress, the results of the
-     * iteration are undefined. The set supports element removal,
-     * which removes the corresponding mapping from the map, via the
-     * Iterator.remove, Set.remove, removeAll, retainAll, and clear
-     * operations.  It does not support the add or addAll operations.
-     *
-     * @return a set view of the keys contained in this map.
-     */
-    public Set keySet()
-    {
-        if (_key_set[ _KEY ] == null)
-        {
-            _key_set[ _KEY ] = new AbstractSet()
-            {
-                public Iterator iterator()
-                {
-                    return new BinaryTreeIterator(_KEY)
-                    {
-                        protected Object doGetNext()
-                        {
-                            return _last_returned_node.getData(_KEY);
-                        }
-                    };
-                }
-
-                public int size()
-                {
-                    return BinaryTree.this.size();
-                }
-
-                public boolean contains(Object o)
-                {
-                    return containsKey(o);
-                }
-
-                public boolean remove(Object o)
-                {
-                    int old_size = _size;
-
-                    BinaryTree.this.remove(o);
-                    return _size != old_size;
-                }
-
-                public void clear()
-                {
-                    BinaryTree.this.clear();
-                }
-            };
-        }
-        return _key_set[ _KEY ];
-    }
-
-    /**
-     * Returns a collection view of the values contained in this
-     * map. The collection is backed by the map, so changes to the map
-     * are reflected in the collection, and vice-versa. If the map is
-     * modified while an iteration over the collection is in progress,
-     * the results of the iteration are undefined. The collection
-     * supports element removal, which removes the corresponding
-     * mapping from the map, via the Iterator.remove,
-     * Collection.remove, removeAll, retainAll and clear operations.
-     * It does not support the add or addAll operations.
-     *
-     * @return a collection view of the values contained in this map.
-     */
-    public Collection values()
-    {
-        if (_value_collection[ _KEY ] == null)
-        {
-            _value_collection[ _KEY ] = new AbstractCollection()
-            {
-                public Iterator iterator()
-                {
-                    return new BinaryTreeIterator(_KEY)
-                    {
-                        protected Object doGetNext()
-                        {
-                            return _last_returned_node.getData(_VALUE);
-                        }
-                    };
-                }
-
-                public int size()
-                {
-                    return BinaryTree.this.size();
-                }
-
-                public boolean contains(Object o)
-                {
-                    return containsValue(o);
-                }
-
-                public boolean remove(Object o)
-                {
-                    int old_size = _size;
-
-                    removeValue(o);
-                    return _size != old_size;
-                }
-
-                public boolean removeAll(Collection c)
-                {
-                    boolean  modified = false;
-                    Iterator iter     = c.iterator();
-
-                    while (iter.hasNext())
-                    {
-                        if (removeValue(iter.next()) != null)
-                        {
-                            modified = true;
-                        }
-                    }
-                    return modified;
-                }
-
-                public void clear()
-                {
-                    BinaryTree.this.clear();
-                }
-            };
-        }
-        return _value_collection[ _KEY ];
-    }
-
-    /**
-     * Returns a set view of the mappings contained in this map. Each
-     * element in the returned set is a Map.Entry. The set is backed
-     * by the map, so changes to the map are reflected in the set, and
-     * vice-versa.  If the map is modified while an iteration over the
-     * set is in progress, the results of the iteration are
-     * undefined. The set supports element removal, which removes the
-     * corresponding mapping from the map, via the Iterator.remove,
-     * Set.remove, removeAll, retainAll and clear operations.  It does
-     * not support the add or addAll operations.
-     *
-     * @return a set view of the mappings contained in this map.
-     */
-    public Set entrySet()
-    {
-        if (_entry_set[ _KEY ] == null)
-        {
-            _entry_set[ _KEY ] = new AbstractSet()
-            {
-                public Iterator iterator()
-                {
-                    return new BinaryTreeIterator(_KEY)
-                    {
-                        protected Object doGetNext()
-                        {
-                            return _last_returned_node;
-                        }
-                    };
-                }
-
-                public boolean contains(Object o)
-                {
-                    if (!(o instanceof Map.Entry))
-                    {
-                        return false;
-                    }
-                    Map.Entry entry = ( Map.Entry ) o;
-                    Object    value = entry.getValue();
-                    Node      node  = lookup(( Comparable ) entry.getKey(),
-                                             _KEY);
-
-                    return (node != null)
-                           && node.getData(_VALUE).equals(value);
-                }
-
-                public boolean remove(Object o)
-                {
-                    if (!(o instanceof Map.Entry))
-                    {
-                        return false;
-                    }
-                    Map.Entry entry = ( Map.Entry ) o;
-                    Object    value = entry.getValue();
-                    Node      node  = lookup(( Comparable ) entry.getKey(),
-                                             _KEY);
-
-                    if ((node != null) && node.getData(_VALUE).equals(value))
-                    {
-                        doRedBlackDelete(node);
-                        return true;
-                    }
-                    return false;
-                }
-
-                public int size()
-                {
-                    return BinaryTree.this.size();
-                }
-
-                public void clear()
-                {
-                    BinaryTree.this.clear();
-                }
-            };
-        }
-        return _entry_set[ _KEY ];
-    }
-
-    /* **********  END  implementation of Map ********** */
-    private abstract class BinaryTreeIterator
-        implements Iterator
-    {
-        private int    _expected_modifications;
-        protected Node _last_returned_node;
-        private Node   _next_node;
-        private int    _type;
-
-        /**
-         * Constructor
-         *
-         * @param type
-         */
-        BinaryTreeIterator(int type)
-        {
-            _type                   = type;
-            _expected_modifications = BinaryTree.this._modifications;
-            _last_returned_node     = null;
-            _next_node              = leastNode(_root[ _type ], _type);
-        }
-
-        /**
-         * @return 'next', whatever that means for a given kind of
-         *         BinaryTreeIterator
-         */
-
-        protected abstract Object doGetNext();
-
-        /* ********** START implementation of Iterator ********** */
-
-        /**
-         * @return true if the iterator has more elements.
-         */
-
-        public boolean hasNext()
-        {
-            return _next_node != null;
-        }
-
-        /**
-         * @return the next element in the iteration.
-         *
-         * @exception NoSuchElementException if iteration has no more
-         *                                   elements.
-         * @exception ConcurrentModificationException if the
-         *                                            BinaryTree is
-         *                                            modified behind
-         *                                            the iterator's
-         *                                            back
-         */
-
-        public Object next()
-            throws NoSuchElementException, ConcurrentModificationException
-        {
-            if (_next_node == null)
-            {
-                throw new NoSuchElementException();
-            }
-            if (_modifications != _expected_modifications)
-            {
-                throw new ConcurrentModificationException();
-            }
-            _last_returned_node = _next_node;
-            _next_node          = nextGreater(_next_node, _type);
-            return doGetNext();
-        }
-
-        /**
-         * Removes from the underlying collection the last element
-         * returned by the iterator. This method can be called only
-         * once per call to next. The behavior of an iterator is
-         * unspecified if the underlying collection is modified while
-         * the iteration is in progress in any way other than by
-         * calling this method.
-         *
-         * @exception IllegalStateException if the next method has not
-         *                                  yet been called, or the
-         *                                  remove method has already
-         *                                  been called after the last
-         *                                  call to the next method.
-         * @exception ConcurrentModificationException if the
-         *                                            BinaryTree is
-         *                                            modified behind
-         *                                            the iterator's
-         *                                            back
-         */
-
-        public void remove()
-            throws IllegalStateException, ConcurrentModificationException
-        {
-            if (_last_returned_node == null)
-            {
-                throw new IllegalStateException();
-            }
-            if (_modifications != _expected_modifications)
-            {
-                throw new ConcurrentModificationException();
-            }
-            doRedBlackDelete(_last_returned_node);
-            _expected_modifications++;
-            _last_returned_node = null;
-        }
-
-        /* **********  END  implementation of Iterator ********** */
-    }   // end private abstract class BinaryTreeIterator
-
-    // for performance
-    private static final class Node
-        implements Map.Entry
-    {
-        private Comparable[] _data;
-        private Node[]       _left;
-        private Node[]       _right;
-        private Node[]       _parent;
-        private boolean[]    _black;
-        private int          _hashcode;
-        private boolean      _calculated_hashcode;
-
-        /**
-         * Make a new cell with given key and value, and with null
-         * links, and black (true) colors.
-         *
-         * @param key
-         * @param value
-         */
-
-        Node(Comparable key, Comparable value)
-        {
-            _data                = new Comparable[]
-            {
-                key, value
-            };
-            _left                = new Node[]
-            {
-                null, null
-            };
-            _right               = new Node[]
-            {
-                null, null
-            };
-            _parent              = new Node[]
-            {
-                null, null
-            };
-            _black               = new boolean[]
-            {
-                true, true
-            };
-            _calculated_hashcode = false;
-        }
-
-        /**
-         * get the specified data
-         *
-         * @param index _KEY or _VALUE
-         *
-         * @return the key or value
-         */
-        public Comparable getData(int index)
-        {
-            return _data[ index ];
-        }
-
-        /**
-         * Set this node's left node
-         *
-         * @param node the new left node
-         * @param index _KEY or _VALUE
-         */
-        public void setLeft(Node node, int index)
-        {
-            _left[ index ] = node;
-        }
-
-        /**
-         * get the left node
-         *
-         * @param index _KEY or _VALUE
-         *
-         * @return the left node -- may be null
-         */
-
-        public Node getLeft(int index)
-        {
-            return _left[ index ];
-        }
-
-        /**
-         * Set this node's right node
-         *
-         * @param node the new right node
-         * @param index _KEY or _VALUE
-         */
-        public void setRight(Node node, int index)
-        {
-            _right[ index ] = node;
-        }
-
-        /**
-         * get the right node
-         *
-         * @param index _KEY or _VALUE
-         *
-         * @return the right node -- may be null
-         */
-
-        public Node getRight(int index)
-        {
-            return _right[ index ];
-        }
-
-        /**
-         * Set this node's parent node
-         *
-         * @param node the new parent node
-         * @param index _KEY or _VALUE
-         */
-        public void setParent(Node node, int index)
-        {
-            _parent[ index ] = node;
-        }
-
-        /**
-         * get the parent node
-         *
-         * @param index _KEY or _VALUE
-         *
-         * @return the parent node -- may be null
-         */
-        public Node getParent(int index)
-        {
-            return _parent[ index ];
-        }
-
-        /**
-         * exchange colors with another node
-         *
-         * @param node the node to swap with
-         * @param index _KEY or _VALUE
-         */
-        public void swapColors(Node node, int index)
-        {
-
-            // Swap colors -- old hacker's trick
-            _black[ index ]      ^= node._black[ index ];
-            node._black[ index ] ^= _black[ index ];
-            _black[ index ]      ^= node._black[ index ];
-        }
-
-        /**
-         * is this node black?
-         *
-         * @param index _KEY or _VALUE
-         *
-         * @return true if black (which is represented as a true boolean)
-         */
-        public boolean isBlack(int index)
-        {
-            return _black[ index ];
-        }
-
-        /**
-         * is this node red?
-         *
-         * @param index _KEY or _VALUE
-         *
-         * @return true if non-black
-         */
-        public boolean isRed(int index)
-        {
-            return !_black[ index ];
-        }
-
-        /**
-         * make this node black
-         *
-         * @param index _KEY or _VALUE
-         */
-        public void setBlack(int index)
-        {
-            _black[ index ] = true;
-        }
-
-        /**
-         * make this node red
-         *
-         * @param index _KEY or _VALUE
-         */
-        public void setRed(int index)
-        {
-            _black[ index ] = false;
-        }
-
-        /**
-         * make this node the same color as another
-         *
-         * @param node the node whose color we're adopting
-         * @param index _KEY or _VALUE
-         */
-        public void copyColor(Node node, int index)
-        {
-            _black[ index ] = node._black[ index ];
-        }
-
-        /* ********** START implementation of Map.Entry ********** */
-
-        /**
-         * @return the key corresponding to this entry.
-         */
-        public Object getKey()
-        {
-            return _data[ _KEY ];
-        }
-
-        /**
-         * @return the value corresponding to this entry.
-         */
-        public Object getValue()
-        {
-            return _data[ _VALUE ];
-        }
-
-        /**
-         * Optional operation that is not permitted in this
-         * implementation
-         *
-         * @param ignored
-         *
-         * @return does not return
-         */
-        public Object setValue(Object ignored)
-            throws UnsupportedOperationException
-        {
-            throw new UnsupportedOperationException(
-                "Map.Entry.setValue is not supported");
-        }
-
-        /**
-         * Compares the specified object with this entry for equality.
-         * Returns true if the given object is also a map entry and
-         * the two entries represent the same mapping.
-         *
-         * @param o object to be compared for equality with this map
-         *          entry.
-         * @return true if the specified object is equal to this map
-         *         entry.
-         */
-        public boolean equals(Object o)
-        {
-            if (this == o)
-            {
-                return true;
-            }
-            if (!(o instanceof Map.Entry))
-            {
-                return false;
-            }
-            Map.Entry e = ( Map.Entry ) o;
-
-            return _data[ _KEY ].equals(e.getKey())
-                   && _data[ _VALUE ].equals(e.getValue());
-        }
-
-        /**
-         * @return the hash code value for this map entry.
-         */
-
-        public int hashCode()
-        {
-            if (!_calculated_hashcode)
-            {
-                _hashcode            = _data[ _KEY ].hashCode()
-                                       ^ _data[ _VALUE ].hashCode();
-                _calculated_hashcode = true;
-            }
-            return _hashcode;
-        }
-
-        /* **********  END  implementation of Map.Entry ********** */
-    }
-}
diff --git a/src/java/org/apache/poi/util/ShortList.java b/src/java/org/apache/poi/util/ShortList.java
deleted file mode 100644
index 3a6cfb8d96..0000000000
--- a/src/java/org/apache/poi/util/ShortList.java
+++ /dev/null
@@ -1,638 +0,0 @@
-/* ====================================================================
-   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.poi.util;
-
-/**
- * A List of short's; as full an implementation of the java.util.List
- * interface as possible, with an eye toward minimal creation of
- * objects
- *
- * the mimicry of List is as follows:
- * <ul>
- * <li> if possible, operations designated 'optional' in the List
- *      interface are attempted
- * <li> wherever the List interface refers to an Object, substitute
- *      short
- * <li> wherever the List interface refers to a Collection or List,
- *      substitute ShortList
- * </ul>
- *
- * the mimicry is not perfect, however:
- * <ul>
- * <li> operations involving Iterators or ListIterators are not
- *      supported
- * <li> remove(Object) becomes removeValue to distinguish it from
- *      remove(short index)
- * <li> subList is not supported
- * </ul>
- *
- * @author Marc Johnson
- */
-
-public class ShortList
-{
-    private short[]          _array;
-    private int              _limit;
-    private static final int _default_size = 128;
-
-    /**
-     * create an ShortList of default size
-     */
-
-    public ShortList()
-    {
-        this(_default_size);
-    }
-
-    /**
-     * create a copy of an existing ShortList
-     *
-     * @param list the existing ShortList
-     */
-
-    public ShortList(final ShortList list)
-    {
-        this(list._array.length);
-        System.arraycopy(list._array, 0, _array, 0, _array.length);
-        _limit = list._limit;
-    }
-
-    /**
-     * create an ShortList with a predefined initial size
-     *
-     * @param initialCapacity the size for the internal array
-     */
-
-    public ShortList(final int initialCapacity)
-    {
-        _array = new short[ initialCapacity ];
-        _limit = 0;
-    }
-
-    /**
-     * add the specfied value at the specified index
-     *
-     * @param index the index where the new value is to be added
-     * @param value the new value
-     *
-     * @exception IndexOutOfBoundsException if the index is out of
-     *            range (index < 0 || index > size()).
-     */
-
-    public void add(final int index, final short value)
-    {
-        if (index > _limit)
-        {
-            throw new IndexOutOfBoundsException();
-        }
-        else if (index == _limit)
-        {
-            add(value);
-        }
-        else
-        {
-
-            // index < limit -- insert into the middle
-            if (_limit == _array.length)
-            {
-                growArray(_limit * 2);
-            }
-            System.arraycopy(_array, index, _array, index + 1,
-                             _limit - index);
-            _array[ index ] = value;
-            _limit++;
-        }
-    }
-
-    /**
-     * Appends the specified element to the end of this list
-     *
-     * @param value element to be appended to this list.
-     *
-     * @return true (as per the general contract of the Collection.add
-     *         method).
-     */
-
-    public boolean add(final short value)
-    {
-        if (_limit == _array.length)
-        {
-            growArray(_limit * 2);
-        }
-        _array[ _limit++ ] = value;
-        return true;
-    }
-
-    /**
-     * Appends all of the elements in the specified collection to the
-     * end of this list, in the order that they are returned by the
-     * specified collection's iterator.  The behavior of this
-     * operation is unspecified if the specified collection is
-     * modified while the operation is in progress.  (Note that this
-     * will occur if the specified collection is this list, and it's
-     * nonempty.)
-     *
-     * @param c collection whose elements are to be added to this
-     *          list.
-     *
-     * @return true if this list changed as a result of the call.
-     */
-
-    public boolean addAll(final ShortList c)
-    {
-        if (c._limit != 0)
-        {
-            if ((_limit + c._limit) > _array.length)
-            {
-                growArray(_limit + c._limit);
-            }
-            System.arraycopy(c._array, 0, _array, _limit, c._limit);
-            _limit += c._limit;
-        }
-        return true;
-    }
-
-    /**
-     * Inserts all of the elements in the specified collection into
-     * this list at the specified position.  Shifts the element
-     * currently at that position (if any) and any subsequent elements
-     * to the right (increases their indices).  The new elements will
-     * appear in this list in the order that they are returned by the
-     * specified collection's iterator.  The behavior of this
-     * operation is unspecified if the specified collection is
-     * modified while the operation is in progress.  (Note that this
-     * will occur if the specified collection is this list, and it's
-     * nonempty.)
-     *
-     * @param index index at which to insert first element from the
-     *              specified collection.
-     * @param c elements to be inserted into this list.
-     *
-     * @return true if this list changed as a result of the call.
-     *
-     * @exception IndexOutOfBoundsException if the index is out of
-     *            range (index < 0 || index > size())
-     */
-
-    public boolean addAll(final int index, final ShortList c)
-    {
-        if (index > _limit)
-        {
-            throw new IndexOutOfBoundsException();
-        }
-        if (c._limit != 0)
-        {
-            if ((_limit + c._limit) > _array.length)
-            {
-                growArray(_limit + c._limit);
-            }
-
-            // make a hole
-            System.arraycopy(_array, index, _array, index + c._limit,
-                             _limit - index);
-
-            // fill it in
-            System.arraycopy(c._array, 0, _array, index, c._limit);
-            _limit += c._limit;
-        }
-        return true;
-    }
-
-    /**
-     * Removes all of the elements from this list.  This list will be
-     * empty after this call returns (unless it throws an exception).
-     */
-
-    public void clear()
-    {
-        _limit = 0;
-    }
-
-    /**
-     * Returns true if this list contains the specified element.  More
-     * formally, returns true if and only if this list contains at
-     * least one element e such that o == e
-     *
-     * @param o element whose presence in this list is to be tested.
-     *
-     * @return true if this list contains the specified element.
-     */
-
-    public boolean contains(final short o)
-    {
-        boolean rval = false;
-
-        for (int j = 0; !rval && (j < _limit); j++)
-        {
-            if (_array[ j ] == o)
-            {
-                rval = true;
-            }
-        }
-        return rval;
-    }
-
-    /**
-     * Returns true if this list contains all of the elements of the
-     * specified collection.
-     *
-     * @param c collection to be checked for containment in this list.
-     *
-     * @return true if this list contains all of the elements of the
-     *         specified collection.
-     */
-
-    public boolean containsAll(final ShortList c)
-    {
-        boolean rval = true;
-
-        if (this != c)
-        {
-            for (int j = 0; rval && (j < c._limit); j++)
-            {
-                if (!contains(c._array[ j ]))
-                {
-                    rval = false;
-                }
-            }
-        }
-        return rval;
-    }
-
-    /**
-     * Compares the specified object with this list for equality.
-     * Returns true if and only if the specified object is also a
-     * list, both lists have the same size, and all corresponding
-     * pairs of elements in the two lists are equal.  (Two elements e1
-     * and e2 are equal if e1 == e2.)  In other words, two lists are
-     * defined to be equal if they contain the same elements in the
-     * same order.  This definition ensures that the equals method
-     * works properly across different implementations of the List
-     * interface.
-     *
-     * @param o the object to be compared for equality with this list.
-     *
-     * @return true if the specified object is equal to this list.
-     */
-
-    public boolean equals(final Object o)
-    {
-        boolean rval = this == o;
-
-        if (!rval && (o != null) && (o.getClass() == this.getClass()))
-        {
-            ShortList other = ( ShortList ) o;
-
-            if (other._limit == _limit)
-            {
-
-                // assume match
-                rval = true;
-                for (int j = 0; rval && (j < _limit); j++)
-                {
-                    rval = _array[ j ] == other._array[ j ];
-                }
-            }
-        }
-        return rval;
-    }
-
-    /**
-     * Returns the element at the specified position in this list.
-     *
-     * @param index index of element to return.
-     *
-     * @return the element at the specified position in this list.
-     *
-     * @exception IndexOutOfBoundsException if the index is out of
-     *            range (index < 0 || index >= size()).
-     */
-
-    public short get(final int index)
-    {
-        if (index >= _limit)
-        {
-            throw new IndexOutOfBoundsException();
-        }
-        return _array[ index ];
-    }
-
-    /**
-     * Returns the hash code value for this list.  The hash code of a
-     * list is defined to be the result of the following calculation:
-     *
-     * <code>
-     * hashCode = 1;
-     * Iterator i = list.iterator();
-     * while (i.hasNext()) {
-     *      Object obj = i.next();
-     *      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
-     * }
-     * </code>
-     *
-     * This ensures that list1.equals(list2) implies that
-     * list1.hashCode()==list2.hashCode() for any two lists, list1 and
-     * list2, as required by the general contract of Object.hashCode.
-     *
-     * @return the hash code value for this list.
-     */
-
-    public int hashCode()
-    {
-        int hash = 0;
-
-        for (int j = 0; j < _limit; j++)
-        {
-            hash = (31 * hash) + _array[ j ];
-        }
-        return hash;
-    }
-
-    /**
-     * Returns the index in this list of the first occurrence of the
-     * specified element, or -1 if this list does not contain this
-     * element.  More formally, returns the lowest index i such that
-     * (o == get(i)), or -1 if there is no such index.
-     *
-     * @param o element to search for.
-     *
-     * @return the index in this list of the first occurrence of the
-     *         specified element, or -1 if this list does not contain
-     *         this element.
-     */
-
-    public int indexOf(final short o)
-    {
-        int rval = 0;
-
-        for (; rval < _limit; rval++)
-        {
-            if (o == _array[ rval ])
-            {
-                break;
-            }
-        }
-        if (rval == _limit)
-        {
-            rval = -1;   // didn't find it
-        }
-        return rval;
-    }
-
-    /**
-     * Returns true if this list contains no elements.
-     *
-     * @return true if this list contains no elements.
-     */
-
-    public boolean isEmpty()
-    {
-        return _limit == 0;
-    }
-
-    /**
-     * Returns the index in this list of the last occurrence of the
-     * specified element, or -1 if this list does not contain this
-     * element.  More formally, returns the highest index i such that
-     * (o == get(i)), or -1 if there is no such index.
-     *
-     * @param o element to search for.
-     *
-     * @return the index in this list of the last occurrence of the
-     *         specified element, or -1 if this list does not contain
-     *         this element.
-     */
-
-    public int lastIndexOf(final short o)
-    {
-        int rval = _limit - 1;
-
-        for (; rval >= 0; rval--)
-        {
-            if (o == _array[ rval ])
-            {
-                break;
-            }
-        }
-        return rval;
-    }
-
-    /**
-     * Removes the element at the specified position in this list.
-     * Shifts any subsequent elements to the left (subtracts one from
-     * their indices).  Returns the element that was removed from the
-     * list.
-     *
-     * @param index the index of the element to removed.
-     *
-     * @return the element previously at the specified position.
-     *
-     * @exception IndexOutOfBoundsException if the index is out of
-     *            range (index < 0 || index >= size()).
-     */
-
-    public short remove(final int index)
-    {
-        if (index >= _limit)
-        {
-            throw new IndexOutOfBoundsException();
-        }
-        short rval = _array[ index ];
-
-        System.arraycopy(_array, index + 1, _array, index, _limit - index);
-        _limit--;
-        return rval;
-    }
-
-    /**
-     * Removes the first occurrence in this list of the specified
-     * element (optional operation).  If this list does not contain
-     * the element, it is unchanged.  More formally, removes the
-     * element with the lowest index i such that (o.equals(get(i)))
-     * (if such an element exists).
-     *
-     * @param o element to be removed from this list, if present.
-     *
-     * @return true if this list contained the specified element.
-     */
-
-    public boolean removeValue(final short o)
-    {
-        boolean rval = false;
-
-        for (int j = 0; !rval && (j < _limit); j++)
-        {
-            if (o == _array[ j ])
-            {
-                System.arraycopy(_array, j + 1, _array, j, _limit - j);
-                _limit--;
-                rval = true;
-            }
-        }
-        return rval;
-    }
-
-    /**
-     * Removes from this list all the elements that are contained in
-     * the specified collection
-     *
-     * @param c collection that defines which elements will be removed
-     *          from this list.
-     *
-     * @return true if this list changed as a result of the call.
-     */
-
-    public boolean removeAll(final ShortList c)
-    {
-        boolean rval = false;
-
-        for (int j = 0; j < c._limit; j++)
-        {
-            if (removeValue(c._array[ j ]))
-            {
-                rval = true;
-            }
-        }
-        return rval;
-    }
-
-    /**
-     * Retains only the elements in this list that are contained in
-     * the specified collection.  In other words, removes from this
-     * list all the elements that are not contained in the specified
-     * collection.
-     *
-     * @param c collection that defines which elements this set will
-     *          retain.
-     *
-     * @return true if this list changed as a result of the call.
-     */
-
-    public boolean retainAll(final ShortList c)
-    {
-        boolean rval = false;
-
-        for (int j = 0; j < _limit; )
-        {
-            if (!c.contains(_array[ j ]))
-            {
-                remove(j);
-                rval = true;
-            }
-            else
-            {
-                j++;
-            }
-        }
-        return rval;
-    }
-
-    /**
-     * Replaces the element at the specified position in this list
-     * with the specified element
-     *
-     * @param index index of element to replace.
-     * @param element element to be stored at the specified position.
-     *
-     * @return the element previously at the specified position.
-     *
-     * @exception IndexOutOfBoundsException if the index is out of
-     *            range (index < 0 || index >= size()).
-     */
-
-    public short set(final int index, final short element)
-    {
-        if (index >= _limit)
-        {
-            throw new IndexOutOfBoundsException();
-        }
-        short rval = _array[ index ];
-
-        _array[ index ] = element;
-        return rval;
-    }
-
-    /**
-     * Returns the number of elements in this list. If this list
-     * contains more than Integer.MAX_VALUE elements, returns
-     * Integer.MAX_VALUE.
-     *
-     * @return the number of elements in this ShortList
-     */
-
-    public int size()
-    {
-        return _limit;
-    }
-
-    /**
-     * Returns an array containing all of the elements in this list in
-     * proper sequence.  Obeys the general contract of the
-     * Collection.toArray method.
-     *
-     * @return an array containing all of the elements in this list in
-     *         proper sequence.
-     */
-
-    public short [] toArray()
-    {
-        short[] rval = new short[ _limit ];
-
-        System.arraycopy(_array, 0, rval, 0, _limit);
-        return rval;
-    }
-
-    /**
-     * Returns an array containing all of the elements in this list in
-     * proper sequence.  Obeys the general contract of the
-     * Collection.toArray(Object[]) method.
-     *
-     * @param a the array into which the elements of this list are to
-     *          be stored, if it is big enough; otherwise, a new array
-     *          is allocated for this purpose.
-     *
-     * @return an array containing the elements of this list.
-     */
-
-    public short [] toArray(final short [] a)
-    {
-        short[] rval;
-
-        if (a.length == _limit)
-        {
-            System.arraycopy(_array, 0, a, 0, _limit);
-            rval = a;
-        }
-        else
-        {
-            rval = toArray();
-        }
-        return rval;
-    }
-
-    private void growArray(final int new_size)
-    {
-        int     size      = (new_size == _array.length) ? new_size + 1
-                                                        : new_size;
-        short[] new_array = new short[ size ];
-
-        System.arraycopy(_array, 0, new_array, 0, _limit);
-        _array = new_array;
-    }
-}   // end public class ShortList
-
diff --git a/src/testcases/org/apache/poi/util/AllPOIUtilTests.java b/src/testcases/org/apache/poi/util/AllPOIUtilTests.java
index 34ad0f4bd3..f018b02298 100644
--- a/src/testcases/org/apache/poi/util/AllPOIUtilTests.java
+++ b/src/testcases/org/apache/poi/util/AllPOIUtilTests.java
@@ -26,7 +26,6 @@ import org.junit.runners.Suite;
 @RunWith(Suite.class)
 @Suite.SuiteClasses({
       TestArrayUtil.class
-    , TestBinaryTree.class
     , TestBitField.class
     , TestByteField.class
     , TestHexDump.class
@@ -37,7 +36,6 @@ import org.junit.runners.Suite;
     , TestPOILogFactory.class
     , TestPOILogger.class
     , TestShortField.class
-    , TestShortList.class
     , TestStringUtil.class
     , TestTempFile.class
 })
diff --git a/src/testcases/org/apache/poi/util/TestBinaryTree.java b/src/testcases/org/apache/poi/util/TestBinaryTree.java
deleted file mode 100644
index 542635980f..0000000000
--- a/src/testcases/org/apache/poi/util/TestBinaryTree.java
+++ /dev/null
@@ -1,2645 +0,0 @@
-
-/* ====================================================================
-   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.poi.util;
-
-import junit.framework.*;
-
-import java.util.*;
-
-/**
- * Class TestBinaryTree
- *
- * @author Marc Johnson (mjohnson at apache dot org)
- */
-public final class TestBinaryTree extends TestCase {
-
-    public void testSize() {
-        Map m = new BinaryTree();
-
-        assertEquals(0, m.size());
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ].getValue());
-            assertEquals(k + 1, m.size());
-        }
-        int count = m.size();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.remove(nodes[ k ].getKey());
-            --count;
-            assertEquals(count, m.size());
-
-            // failed remove should not affect size
-            m.remove(nodes[ k ].getKey());
-            assertEquals(count, m.size());
-        }
-    }
-
-    public void testIsEmpty() {
-        Map m = new BinaryTree();
-
-        assertTrue(m.isEmpty());
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ].getValue());
-            assertTrue(!m.isEmpty());
-        }
-        int count = m.size();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.remove(nodes[ k ].getKey());
-            --count;
-            if (count == 0)
-            {
-                assertTrue(m.isEmpty());
-            }
-            else
-            {
-                assertTrue(!m.isEmpty());
-            }
-
-            // failed remove should not affect emptiness
-            m.remove(nodes[ k ].getKey());
-            if (count == 0)
-            {
-                assertTrue(m.isEmpty());
-            }
-            else
-            {
-                assertTrue(!m.isEmpty());
-            }
-        }
-    }
-
-    public void testContainsKey() {
-        Map m = new BinaryTree();
-
-        try
-        {
-            m.containsKey(new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        try
-        {
-            m.containsKey(null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        assertTrue(!m.containsKey("foo"));
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            assertTrue(m.containsKey(nodes[ k ].getKey()));
-        }
-        assertTrue(!m.containsKey(Integer.valueOf(-1)));
-        try
-        {
-            m.containsKey("foo");
-            fail("Should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.remove(nodes[ k ].getKey());
-            assertTrue(!m.containsKey(nodes[ k ].getKey()));
-        }
-    }
-
-    public void testContainsValue() {
-        Map           m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            assertTrue(m.containsValue(nodes[ k ]));
-        }
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.remove(nodes[ k ].getKey());
-            assertTrue(!m.containsValue(nodes[ k ]));
-        }
-    }
-
-    public void testGet() {
-        Map m = new BinaryTree();
-
-        try
-        {
-            m.get(new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        try
-        {
-            m.get(null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        assertNull(m.get("foo"));
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            assertSame(m.get(nodes[ k ].getKey()), nodes[ k ]);
-        }
-        assertNull(m.get(Integer.valueOf(-1)));
-        try
-        {
-            m.get("foo");
-            fail("Should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        for (int k = 0; k < nodes.length; k++)
-        {
-            assertNotNull(m.get(nodes[ k ].getKey()));
-            m.remove(nodes[ k ].getKey());
-            assertNull(m.get(nodes[ k ].getKey()));
-        }
-    }
-
-    public void testPut() {
-        Map m = new BinaryTree();
-
-        try
-        {
-            m.put(new Object(), "foo");
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        try
-        {
-            m.put(null, "foo");
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        try
-        {
-            m.put("foo", null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        try
-        {
-            m.put("foo", new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        LocalTestNode[] nodes = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            assertNull(m.put(nodes[ k ].getKey(), nodes[ k ].getValue()));
-            try
-            {
-                m.put(nodes[ k ].getKey(), "foo");
-            }
-            catch (IllegalArgumentException ignored)
-            {
-            }
-        }
-    }
-
-    public void testRemove() {
-        BinaryTree    m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        try
-        {
-            m.remove(null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        try
-        {
-            m.remove(new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        assertNull(m.remove(Integer.valueOf(-1)));
-        try
-        {
-            m.remove("foo");
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        for (int k = 0; k < nodes.length; k += 2)
-        {
-            Comparable key = nodes[ k ].getKey();
-
-            assertNotNull(m.get(key));
-            assertSame(nodes[ k ], m.remove(key));
-            assertNull(m.remove(key));
-            assertNull(m.get(key));
-        }
-        for (int k = 1; k < nodes.length; k += 2)
-        {
-            Comparable key = nodes[ k ].getKey();
-
-            assertNotNull(m.get(key));
-            assertSame(nodes[ k ], m.remove(key));
-            assertNull(m.remove(key));
-            assertNull(m.get(key));
-        }
-        assertTrue(m.isEmpty());
-    }
-
-    public void testPutAll() {
-        Map           m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        Map m1 = new HashMap();
-
-        m1.put(null, "foo");
-        try
-        {
-            m.putAll(m1);
-            fail("Should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        m1 = new HashMap();
-        m1.put(new Object(), "bar");
-        try
-        {
-            m.putAll(m1);
-            fail("Should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        m1 = new HashMap();
-        m1.put("fubar", null);
-        try
-        {
-            m.putAll(m1);
-            fail("Should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        m1 = new HashMap();
-        m1.put("fubar", new Object());
-        try
-        {
-            m.putAll(m1);
-            fail("Should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        assertEquals(nodes.length, m.size());
-        m  = new BinaryTree();
-        m1 = new HashMap();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m1.put(nodes[ k ].getKey(), nodes[ k ].getValue());
-        }
-        m.putAll(m1);
-        assertEquals(nodes.length, m.size());
-        for (int k = 0; k < nodes.length; k++)
-        {
-            assertSame(nodes[ k ].getValue(), m.get(nodes[ k ].getKey()));
-        }
-    }
-
-    public void testClear() {
-        Map           m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ].getValue());
-            assertTrue(!m.isEmpty());
-        }
-        assertTrue(!m.isEmpty());
-        for (int k = 0; k < nodes.length; k++)
-        {
-            assertTrue(m.containsKey(nodes[ k ].getKey()));
-            assertTrue(m.containsValue(nodes[ k ].getValue()));
-        }
-        m.clear();
-        assertTrue(m.isEmpty());
-        for (int k = 0; k < nodes.length; k++)
-        {
-            assertTrue(!m.containsKey(nodes[ k ].getKey()));
-            assertTrue(!m.containsValue(nodes[ k ].getValue()));
-        }
-    }
-
-    public void testKeySet() {
-        testKeySet(new BinaryTree());
-        Map           m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        testKeySet(m);
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        int count = m.size();
-
-        for (Iterator iter = m.keySet().iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            iter.remove();
-            --count;
-            assertEquals(count, m.size());
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        Set s = m.keySet();
-
-        try
-        {
-            s.remove(null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        try
-        {
-            s.remove(new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        for (int k = 0; k < nodes.length; k++)
-        {
-            Comparable key = nodes[ k ].getKey();
-
-            assertTrue(s.remove(key));
-            assertTrue(!s.contains(key));
-            assertTrue(!m.containsKey(key));
-            assertTrue(!m.containsValue(nodes[ k ]));
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        Collection c1 = new LinkedList();
-        Collection c2 = new LinkedList();
-
-        c2.add(Integer.valueOf(-99));
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ].getKey());
-            c2.add(nodes[ k ].getKey());
-        }
-        assertTrue(m.keySet().containsAll(c1));
-        assertTrue(!m.keySet().containsAll(c2));
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        c1.add(Integer.valueOf(-55));
-        try
-        {
-            m.keySet().addAll(c1);
-            fail("should have caught exception of addAll()");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ].getKey());
-        }
-        assertTrue(!m.keySet().retainAll(c1));
-        assertEquals(nodes.length, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            if (k % 2 == 1)
-            {
-                c1.add(nodes[ k ].getKey());
-            }
-        }
-        assertTrue(m.keySet().retainAll(c1));
-        assertEquals(nodes.length / 2, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(m.keySet().retainAll(c1));
-        assertEquals(0, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(!m.keySet().removeAll(c1));
-        assertEquals(nodes.length, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            if (k % 2 == 0)
-            {
-                c1.add(nodes[ k ].getKey());
-            }
-        }
-        assertTrue(m.keySet().removeAll(c1));
-        assertEquals(nodes.length / 2, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ].getKey());
-        }
-        assertTrue(m.keySet().removeAll(c1));
-        assertTrue(m.size() == 0);
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        m.keySet().clear();
-        assertTrue(m.size() == 0);
-    }
-
-    public void testValues() {
-        testValues(new BinaryTree());
-        Map           m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        testValues(m);
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        int count = m.size();
-
-        for (Iterator iter = m.values().iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            iter.remove();
-            --count;
-            assertEquals(count, m.size());
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        count = m.size();
-        Collection s = m.values();
-
-        for (int k = 0; k < count; k++)
-        {
-            assertTrue(s.remove(nodes[ k ]));
-            assertTrue(!s.contains(nodes[ k ]));
-            assertTrue(!m.containsKey(nodes[ k ].getKey()));
-            assertTrue(!m.containsValue(nodes[ k ]));
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        Collection c1 = new LinkedList();
-        Collection c2 = new LinkedList();
-
-        c2.add(new LocalTestNode(-123));
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ]);
-            c2.add(nodes[ k ]);
-        }
-        assertTrue(m.values().containsAll(c1));
-        assertTrue(!m.values().containsAll(c2));
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ]);
-        }
-        try
-        {
-            m.values().addAll(c1);
-            fail("should have caught exception of addAll()");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ]);
-        }
-        assertTrue(!m.values().retainAll(c1));
-        assertEquals(nodes.length, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            if (k % 2 == 1)
-            {
-                c1.add(nodes[ k ]);
-            }
-        }
-        assertTrue(m.values().retainAll(c1));
-        assertEquals(nodes.length / 2, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(m.values().retainAll(c1));
-        assertEquals(0, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(!m.values().removeAll(c1));
-        assertEquals(nodes.length, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            if (k % 2 == 0)
-            {
-                c1.add(nodes[ k ]);
-            }
-        }
-        assertTrue(m.values().removeAll(c1));
-        assertEquals(nodes.length / 2, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ]);
-        }
-        assertTrue(m.values().removeAll(c1));
-        assertEquals(0, m.size());
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        m.values().clear();
-        assertEquals(0, m.size());
-    }
-
-    public void testEntrySet() {
-        testEntrySet(new BinaryTree());
-        Map           m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        testEntrySet(m);
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        try
-        {
-            (( Map.Entry ) m.entrySet().iterator().next())
-                .setValue(new LocalTestNode(-1));
-            fail("Should have caught UnsupportedOperationException");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        int count = m.size();
-
-        for (Iterator iter = m.entrySet().iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            iter.remove();
-            --count;
-            assertEquals(count, m.size());
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        Collection c1 = new LinkedList();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ].getKey());
-        }
-        try
-        {
-            m.entrySet().addAll(c1);
-            fail("should have caught exception of addAll()");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        m.entrySet().clear();
-        assertEquals(0, m.size());
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        int x = 0;
-
-        for (Iterator iter = m.entrySet().iterator(); iter.hasNext(); )
-        {
-            Map.Entry entry = ( Map.Entry ) iter.next();
-
-            assertSame(entry.getKey(), nodes[ x ].getKey());
-            assertSame(entry.getValue(), nodes[ x ]);
-            x++;
-        }
-    }
-
-    public void testEquals() {
-        Map           m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(!m.equals(null));
-        assertEquals(m, m);
-        Map m1 = new HashMap();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m1.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertEquals(m, m1);
-        m1 = new BinaryTree();
-        for (int k = 0; k < (nodes.length - 1); k++)
-        {
-            m1.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(!m.equals(m1));
-        m1 = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m1.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        LocalTestNode node1 = new LocalTestNode(-1000);
-
-        m1.put(node1.getKey(), node1);
-        assertTrue(!m.equals(m1));
-        m1 = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m1.put(nodes[ k ].getKey(), nodes[ nodes.length - (k + 1) ]);
-        }
-        assertTrue(!m.equals(m1));
-        m1 = new BinaryTree();
-        for (int k = nodes.length - 1; k >= 0; k--)
-        {
-            m1.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertEquals(m, m1);
-    }
-
-    public void testHashCode() {
-        Map           m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        Map m1 = new BinaryTree();
-
-        for (int k = nodes.length - 1; k >= 0; k--)
-        {
-            m1.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(m.hashCode() == m1.hashCode());
-    }
-
-    public void testConstructors() {
-        BinaryTree m = new BinaryTree();
-
-        assertTrue(m.isEmpty());
-        BinaryTree m1 = new BinaryTree(m);
-
-        assertTrue(m1.isEmpty());
-        m1 = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m1.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        m = new BinaryTree(m1);
-        assertEquals(m, m1);
-        Map m2 = new HashMap();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m2.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        m = new BinaryTree(m2);
-        assertEquals(m, m2);
-
-        // reject duplicated values
-        m2 = new HashMap();
-        m2.put("1", "foo");
-        m2.put("2", "foo");
-        try
-        {
-            m = new BinaryTree(m2);
-            fail("Should have caught IllegalArgumentException");
-        }
-        catch (IllegalArgumentException ignored)
-        {
-        }
-
-        // reject null values
-        m2.put("2", null);
-        try
-        {
-            m = new BinaryTree(m2);
-            fail("Should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-
-        // reject non-Comparable values
-        m2.put("2", new Object());
-        try
-        {
-            m = new BinaryTree(m2);
-            fail("Should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-
-        // reject incompatible values
-        m2.put("2", Integer.valueOf(2));
-        try
-        {
-            m = new BinaryTree(m2);
-            fail("Should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-
-        // reject incompatible keys
-        m2.remove("2");
-        m2.put(Integer.valueOf(2), "bad key");
-        try
-        {
-            m = new BinaryTree(m2);
-            fail("Should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-
-        // reject non-Comparable keys
-        m2.clear();
-        m2.put("1", "foo");
-        m2.put(new Object(), "bad key");
-        try
-        {
-            m = new BinaryTree(m2);
-            fail("Should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-    }
-
-    public void testGetKeyForValue() {
-        BinaryTree m = new BinaryTree();
-
-        try
-        {
-            m.getKeyForValue(new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        try
-        {
-            m.getKeyForValue(null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        assertNull(m.getKeyForValue("foo"));
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            assertSame(m.getKeyForValue(nodes[ k ]), nodes[ k ].getKey());
-        }
-        assertNull(m.getKeyForValue(new LocalTestNode(-1)));
-        try
-        {
-            m.getKeyForValue("foo");
-            fail("Should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        for (int k = 0; k < nodes.length; k++)
-        {
-            assertNotNull(m.getKeyForValue(nodes[ k ]));
-            m.remove(nodes[ k ].getKey());
-            assertNull(m.getKeyForValue(nodes[ k ]));
-        }
-    }
-
-    public void testRemoveValue() {
-        BinaryTree    m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        try
-        {
-            m.removeValue(null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        try
-        {
-            m.removeValue(new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        assertNull(m.remove(Integer.valueOf(-1)));
-        try
-        {
-            m.removeValue("foo");
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        for (int k = 0; k < nodes.length; k += 2)
-        {
-            assertNotNull(m.getKeyForValue(nodes[ k ]));
-            assertSame(nodes[ k ].getKey(), m.removeValue(nodes[ k ]));
-            assertNull(m.removeValue(nodes[ k ]));
-            assertNull(m.getKeyForValue(nodes[ k ]));
-        }
-        for (int k = 1; k < nodes.length; k += 2)
-        {
-            assertNotNull(m.getKeyForValue(nodes[ k ]));
-            assertSame(nodes[ k ].getKey(), m.removeValue(nodes[ k ]));
-            assertNull(m.removeValue(nodes[ k ]));
-            assertNull(m.getKeyForValue(nodes[ k ]));
-        }
-        assertTrue(m.isEmpty());
-    }
-
-    public void testEntrySetByValue() {
-        testEntrySetByValue(new BinaryTree());
-        BinaryTree    m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        testEntrySetByValue(m);
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        try
-        {
-            (( Map.Entry ) m.entrySetByValue().iterator().next())
-                .setValue(new LocalTestNode(-1));
-            fail("Should have caught UnsupportedOperationException");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        int count = m.size();
-
-        for (Iterator iter = m.entrySetByValue().iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            iter.remove();
-            --count;
-            assertEquals(count, m.size());
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        Collection c1 = new LinkedList();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ].getKey());
-        }
-        try
-        {
-            m.entrySetByValue().addAll(c1);
-            fail("should have caught exception of addAll()");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        m.entrySetByValue().clear();
-        assertEquals(0, m.size());
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        int x = 0;
-
-        for (Iterator iter = m.entrySetByValue().iterator(); iter.hasNext(); )
-        {
-            Map.Entry entry = ( Map.Entry ) iter.next();
-
-            assertSame(entry.getKey(), nodes[ x ].getKey());
-            assertSame(entry.getValue(), nodes[ x ]);
-            x++;
-        }
-    }
-
-    public void testKeySetByValue() {
-        testKeySetByValue(new BinaryTree());
-        BinaryTree    m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        testKeySetByValue(m);
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        int count = m.size();
-
-        for (Iterator iter = m.keySetByValue().iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            iter.remove();
-            --count;
-            assertEquals(count, m.size());
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        Set s = m.keySetByValue();
-
-        try
-        {
-            s.remove(null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        try
-        {
-            s.remove(new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        for (int k = 0; k < nodes.length; k++)
-        {
-            Comparable key = nodes[ k ].getKey();
-
-            assertTrue(s.remove(key));
-            assertTrue(!s.contains(key));
-            assertTrue(!m.containsKey(key));
-            assertTrue(!m.containsValue(nodes[ k ]));
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        Collection c1 = new LinkedList();
-        Collection c2 = new LinkedList();
-
-        c2.add(Integer.valueOf(-99));
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ].getKey());
-            c2.add(nodes[ k ].getKey());
-        }
-        assertTrue(m.keySetByValue().containsAll(c1));
-        assertTrue(!m.keySetByValue().containsAll(c2));
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        c1.add(Integer.valueOf(-55));
-        try
-        {
-            m.keySetByValue().addAll(c1);
-            fail("should have caught exception of addAll()");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ].getKey());
-        }
-        assertTrue(!m.keySetByValue().retainAll(c1));
-        assertEquals(nodes.length, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            if (k % 2 == 1)
-            {
-                c1.add(nodes[ k ].getKey());
-            }
-        }
-        assertTrue(m.keySetByValue().retainAll(c1));
-        assertEquals(nodes.length / 2, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(m.keySetByValue().retainAll(c1));
-        assertEquals(0, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(!m.keySetByValue().removeAll(c1));
-        assertEquals(nodes.length, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            if (k % 2 == 0)
-            {
-                c1.add(nodes[ k ].getKey());
-            }
-        }
-        assertTrue(m.keySetByValue().removeAll(c1));
-        assertEquals(nodes.length / 2, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ].getKey());
-        }
-        assertTrue(m.keySetByValue().removeAll(c1));
-        assertTrue(m.size() == 0);
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        m.keySetByValue().clear();
-        assertTrue(m.size() == 0);
-    }
-
-    public void testValuesByValue() {
-        testValuesByValue(new BinaryTree());
-        BinaryTree    m       = new BinaryTree();
-        LocalTestNode nodes[] = makeLocalNodes();
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        testValuesByValue(m);
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        int count = m.size();
-
-        for (Iterator iter = m.valuesByValue().iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            iter.remove();
-            --count;
-            assertEquals(count, m.size());
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        count = m.size();
-        Collection s = m.valuesByValue();
-
-        for (int k = 0; k < count; k++)
-        {
-            assertTrue(s.remove(nodes[ k ]));
-            assertTrue(!s.contains(nodes[ k ]));
-            assertTrue(!m.containsKey(nodes[ k ].getKey()));
-            assertTrue(!m.containsValue(nodes[ k ]));
-        }
-        assertTrue(m.isEmpty());
-        m = new BinaryTree();
-        Collection c1 = new LinkedList();
-        Collection c2 = new LinkedList();
-
-        c2.add(new LocalTestNode(-123));
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ]);
-            c2.add(nodes[ k ]);
-        }
-        assertTrue(m.valuesByValue().containsAll(c1));
-        assertTrue(!m.valuesByValue().containsAll(c2));
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ]);
-        }
-        try
-        {
-            m.valuesByValue().addAll(c1);
-            fail("should have caught exception of addAll()");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ]);
-        }
-        assertTrue(!m.valuesByValue().retainAll(c1));
-        assertEquals(nodes.length, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            if (k % 2 == 1)
-            {
-                c1.add(nodes[ k ]);
-            }
-        }
-        assertTrue(m.valuesByValue().retainAll(c1));
-        assertEquals(nodes.length / 2, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(m.valuesByValue().retainAll(c1));
-        assertEquals(0, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        assertTrue(!m.valuesByValue().removeAll(c1));
-        assertEquals(nodes.length, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            if (k % 2 == 0)
-            {
-                c1.add(nodes[ k ]);
-            }
-        }
-        assertTrue(m.valuesByValue().removeAll(c1));
-        assertEquals(nodes.length / 2, m.size());
-        m  = new BinaryTree();
-        c1 = new LinkedList();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-            c1.add(nodes[ k ]);
-        }
-        assertTrue(m.valuesByValue().removeAll(c1));
-        assertEquals(0, m.size());
-        m = new BinaryTree();
-        for (int k = 0; k < nodes.length; k++)
-        {
-            m.put(nodes[ k ].getKey(), nodes[ k ]);
-        }
-        m.valuesByValue().clear();
-        assertEquals(0, m.size());
-    }
-
-    /* ********** START helper methods ********** */
-    private static void testKeySet(final Map m) {
-        Set s = m.keySet();
-
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        LocalTestNode node = new LocalTestNode(-1);
-
-        m.put(node.getKey(), node);
-        assertTrue(s.contains(node.getKey()));
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        m.remove(node.getKey());
-        assertTrue(!s.contains(node.getKey()));
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        try
-        {
-            s.contains(null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        try
-        {
-            s.contains(new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        for (int k = 0; k < m.size(); k++)
-        {
-            assertTrue(s.contains(Integer.valueOf(k)));
-        }
-        int count = 0;
-
-        for (Iterator iter = s.iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            ++count;
-        }
-        assertEquals(count, s.size());
-
-        // force the map to have some content
-        m.put(node.getKey(), node);
-        Iterator      iter  = m.keySet().iterator();
-        LocalTestNode node2 = new LocalTestNode(-2);
-
-        m.put(node2.getKey(), node2);
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a put");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.remove(node2.getKey());
-        iter = s.iterator();
-        m.remove(node.getKey());
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Map remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter = s.iterator();
-        s.remove(node.getKey());
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Set remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        iter  = s.iterator();
-        count = 0;
-        boolean terminated = false;
-
-        try
-        {
-            while (true)
-            {
-                iter.next();
-                ++count;
-            }
-        }
-        catch (NoSuchElementException ignored)
-        {
-            terminated = true;
-        }
-        assertTrue(terminated);
-        assertEquals(m.size(), count);
-        iter = s.iterator();
-        try
-        {
-            iter.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter = s.iterator();
-        iter.next();
-        m.put(node2.getKey(), node2);
-        try
-        {
-            iter.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        Iterator iter2 = s.iterator();
-
-        iter2.next();
-        LocalTestNode node3 = new LocalTestNode(-3);
-
-        m.put(node3.getKey(), node3);
-        try
-        {
-            iter2.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        int r_count = 0;
-
-        for (iter = s.iterator(); iter.hasNext(); )
-        {
-            if (iter.next().equals(node.getKey()))
-            {
-                try
-                {
-                    iter.remove();
-                    ++r_count;
-                    iter.remove();
-                    fail("2nd remove should have failed");
-                }
-                catch (IllegalStateException ignored)
-                {
-                    assertEquals(1, r_count);
-                }
-            }
-        }
-        assertEquals(1, r_count);
-        assertTrue(!s.contains(node.getKey()));
-        r_count = 0;
-        m.put(node.getKey(), node);
-        Object[] a1 = s.toArray();
-
-        assertEquals(s.size(), a1.length);
-        if (a1.length > 1)
-        {
-            Comparable first = ( Comparable ) a1[ 0 ];
-
-            for (int k = 1; k < a1.length; k++)
-            {
-                Comparable second = ( Comparable ) a1[ k ];
-
-                assertTrue(first.compareTo(second) < 0);
-                first = second;
-            }
-            iter  = s.iterator();
-            first = ( Comparable ) iter.next();
-            for (; iter.hasNext(); )
-            {
-                Comparable second = ( Comparable ) iter.next();
-
-                assertTrue(first.compareTo(second) < 0);
-                first = second;
-            }
-        }
-        try
-        {
-            String array2[] = ( String [] ) s.toArray(new String[ 0 ]);
-
-            if (s.size() != 0)
-            {
-                fail("should have caught exception creating an invalid array");
-            }
-        }
-        catch (ArrayStoreException ignored)
-        {
-        }
-        Comparable array2[] =
-            ( Comparable [] ) s.toArray(new Comparable[ 0 ]);
-        Integer    array3[] =
-            ( Integer [] ) s.toArray(new Integer[ s.size() ]);
-
-        if (array3.length > 1)
-        {
-            Integer first = array3[ 0 ];
-
-            for (int k = 1; k < array3.length; k++)
-            {
-                Integer second = array3[ k ];
-
-                assertTrue(first.compareTo(second) < 0);
-                first = second;
-            }
-        }
-        try
-        {
-            s.add("foo");
-            fail("should have thrown an exception");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        assertTrue(!s.equals(null));
-        assertEquals(s, s);
-        Set hs = new HashSet(s);
-
-        assertEquals(s, hs);
-        assertEquals(hs, s);
-        assertTrue(s.hashCode() == hs.hashCode());
-    }
-
-    private static void testKeySetByValue(final BinaryTree m) {
-        Set s = m.keySetByValue();
-
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        LocalTestNode node = new LocalTestNode(-1);
-
-        m.put(node.getKey(), node);
-        assertTrue(s.contains(node.getKey()));
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        m.remove(node.getKey());
-        assertTrue(!s.contains(node.getKey()));
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        try
-        {
-            s.contains(null);
-            fail("should have caught NullPointerException");
-        }
-        catch (NullPointerException ignored)
-        {
-        }
-        try
-        {
-            s.contains(new Object());
-            fail("should have caught ClassCastException");
-        }
-        catch (ClassCastException ignored)
-        {
-        }
-        for (int k = 0; k < m.size(); k++)
-        {
-            assertTrue(s.contains(Integer.valueOf(k)));
-        }
-        int count = 0;
-
-        for (Iterator iter = s.iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            ++count;
-        }
-        assertEquals(count, s.size());
-
-        // force the map to have some content
-        m.put(node.getKey(), node);
-        Iterator      iter  = m.keySetByValue().iterator();
-        LocalTestNode node2 = new LocalTestNode(-2);
-
-        m.put(node2.getKey(), node2);
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a put");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.remove(node2.getKey());
-        iter = s.iterator();
-        m.remove(node.getKey());
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Map remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter = s.iterator();
-        s.remove(node.getKey());
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Set remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        iter  = s.iterator();
-        count = 0;
-        boolean terminated = false;
-
-        try
-        {
-            while (true)
-            {
-                iter.next();
-                ++count;
-            }
-        }
-        catch (NoSuchElementException ignored)
-        {
-            terminated = true;
-        }
-        assertTrue(terminated);
-        assertEquals(m.size(), count);
-        iter = s.iterator();
-        try
-        {
-            iter.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter = s.iterator();
-        iter.next();
-        m.put(node2.getKey(), node2);
-        try
-        {
-            iter.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        Iterator iter2 = s.iterator();
-
-        iter2.next();
-        LocalTestNode node3 = new LocalTestNode(-3);
-
-        m.put(node3.getKey(), node3);
-        try
-        {
-            iter2.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        int r_count = 0;
-
-        for (iter = s.iterator(); iter.hasNext(); )
-        {
-            if (iter.next().equals(node.getKey()))
-            {
-                try
-                {
-                    iter.remove();
-                    ++r_count;
-                    iter.remove();
-                    fail("2nd remove should have failed");
-                }
-                catch (IllegalStateException ignored)
-                {
-                    assertEquals(1, r_count);
-                }
-            }
-        }
-        assertEquals(1, r_count);
-        assertTrue(!s.contains(node.getKey()));
-        r_count = 0;
-        m.put(node.getKey(), node);
-        Object[] a1 = s.toArray();
-
-        assertEquals(s.size(), a1.length);
-
-//          if (a1.length > 1)
-//          {
-//              Comparable first = ( Comparable ) a1[ 0 ];
-//              for (int k = 1; k < a1.length; k++)
-//              {
-//                  Comparable second = ( Comparable ) a1[ k ];
-//                  assertTrue(first.compareTo(second) < 0);
-//                  first = second;
-//              }
-//              iter  = s.iterator();
-//              first = ( Comparable ) iter.next();
-//              for (; iter.hasNext(); )
-//              {
-//                  Comparable second = ( Comparable ) iter.next();
-//                  assertTrue(first.compareTo(second) < 0);
-//                  first = second;
-//              }
-//          }
-        try
-        {
-            String array2[] = ( String [] ) s.toArray(new String[ 0 ]);
-
-            if (s.size() != 0)
-            {
-                fail("should have caught exception creating an invalid array");
-            }
-        }
-        catch (ArrayStoreException ignored)
-        {
-        }
-        Comparable array2[] =
-            ( Comparable [] ) s.toArray(new Comparable[ 0 ]);
-        Integer    array3[] =
-            ( Integer [] ) s.toArray(new Integer[ s.size() ]);
-
-//          if (array3.length > 1)
-//          {
-//              Integer first = array3[ 0 ];
-//              for (int k = 1; k < array3.length; k++)
-//              {
-//                  Integer second = array3[ k ];
-//                  assertTrue(first.compareTo(second) < 0);
-//                  first = second;
-//              }
-//          }
-        try
-        {
-            s.add("foo");
-            fail("should have thrown an exception");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        assertTrue(!s.equals(null));
-        assertEquals(s, s);
-        Set hs = new HashSet(s);
-
-        assertEquals(s, hs);
-        assertEquals(hs, s);
-        assertTrue(s.hashCode() == hs.hashCode());
-    }
-
-    private static void testValues(Map m) {
-        Collection s = m.values();
-
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        LocalTestNode node = new LocalTestNode(-1);
-
-        m.put(node.getKey(), node);
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        m.remove(node.getKey());
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        assertTrue(!s.contains(node));
-        for (int k = 0; k < m.size(); k++)
-        {
-            assertTrue(s.contains(new LocalTestNode(k)));
-        }
-        m.put(node.getKey(), node);
-        assertTrue(s.contains(node));
-        m.remove(node.getKey());
-        assertTrue(!s.contains(node));
-        int count = 0;
-
-        for (Iterator iter = s.iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            ++count;
-        }
-        assertEquals(s.size(), count);
-        LocalTestNode node4 = new LocalTestNode(-4);
-
-        m.put(node4.getKey(), node4);
-        Iterator iter = s.iterator();
-
-        m.put(node.getKey(), node);
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a put");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        iter = s.iterator();
-        m.remove(node.getKey());
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Map remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter = s.iterator();
-        s.remove(node);
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Set remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        iter  = s.iterator();
-        count = 0;
-        boolean terminated = false;
-
-        try
-        {
-            while (true)
-            {
-                iter.next();
-                ++count;
-            }
-        }
-        catch (NoSuchElementException ignored)
-        {
-            terminated = true;
-        }
-        assertTrue(terminated);
-        assertEquals(m.size(), count);
-        iter = s.iterator();
-        try
-        {
-            iter.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        Iterator iter2 = s.iterator();
-
-        try
-        {
-            iter2.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter = s.iterator();
-        iter.next();
-        LocalTestNode node2 = new LocalTestNode(-2);
-
-        m.put(node2.getKey(), node2);
-        try
-        {
-            iter.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        LocalTestNode node3 = new LocalTestNode(-3);
-
-        m.put(node3.getKey(), node3);
-        iter2 = s.iterator();
-        while (iter2.hasNext())
-        {
-            iter2.next();
-        }
-        int r_count = 0;
-
-        for (iter = s.iterator(); iter.hasNext(); )
-        {
-            if (iter.next().equals(node3))
-            {
-                try
-                {
-                    iter.remove();
-                    ++r_count;
-                    iter.remove();
-                    fail("2nd remove should have failed");
-                }
-                catch (IllegalStateException ignored)
-                {
-                    assertEquals(1, r_count);
-                }
-            }
-        }
-        assertEquals(1, r_count);
-        assertTrue(!s.contains(node3));
-        Object[] a1 = s.toArray();
-
-        assertTrue(a1.length == s.size());
-        if (a1.length > 1)
-        {
-            Comparable first = ( Comparable ) a1[ 0 ];
-
-            for (int k = 1; k < a1.length; k++)
-            {
-                Comparable second = ( Comparable ) a1[ k ];
-
-                assertTrue(first.compareTo(second) < 0);
-                first = second;
-            }
-            iter  = s.iterator();
-            first = ( Comparable ) iter.next();
-            for (; iter.hasNext(); )
-            {
-                Comparable second = ( Comparable ) iter.next();
-
-                assertTrue(first.compareTo(second) < 0);
-                first = second;
-            }
-        }
-        try
-        {
-            String array2[] = ( String [] ) s.toArray(new String[ 0 ]);
-
-            if (s.size() != 0)
-            {
-                fail("should have caught exception creating an invalid array");
-            }
-        }
-        catch (ArrayStoreException ignored)
-        {
-        }
-        m.remove(node.getKey());
-        m.remove(node2.getKey());
-        m.remove(node3.getKey());
-        LocalTestNode array2[] =
-            ( LocalTestNode [] ) s.toArray(new LocalTestNode[ 0 ]);
-        LocalTestNode array3[] =
-            ( LocalTestNode [] ) s.toArray(new LocalTestNode[ s.size() ]);
-
-        if (array3.length > 1)
-        {
-            LocalTestNode first = array3[ 0 ];
-
-            for (int k = 1; k < array3.length; k++)
-            {
-                LocalTestNode second = array3[ k ];
-
-                assertTrue(first.compareTo(second) < 0);
-                first = second;
-            }
-        }
-        try
-        {
-            s.add(node.getKey());
-            fail("should have thrown an exception");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        assertTrue(!s.equals(null));
-        assertEquals(s, s);
-        Set hs = new HashSet(s);
-
-        assertTrue(!s.equals(hs));
-        assertTrue(!hs.equals(s));
-    }
-
-    private static void testValuesByValue(BinaryTree m) {
-        Collection s = m.valuesByValue();
-
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        LocalTestNode node = new LocalTestNode(-1);
-
-        m.put(node.getKey(), node);
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        m.remove(node.getKey());
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        assertTrue(!s.contains(node));
-        for (int k = 0; k < m.size(); k++)
-        {
-            assertTrue(s.contains(new LocalTestNode(k)));
-        }
-        m.put(node.getKey(), node);
-        assertTrue(s.contains(node));
-        m.remove(node.getKey());
-        assertTrue(!s.contains(node));
-        int count = 0;
-
-        for (Iterator iter = s.iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            ++count;
-        }
-        assertEquals(s.size(), count);
-        LocalTestNode node4 = new LocalTestNode(-4);
-
-        m.put(node4.getKey(), node4);
-        Iterator iter = s.iterator();
-
-        m.put(node.getKey(), node);
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a put");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        iter = s.iterator();
-        m.remove(node.getKey());
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Map remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter = s.iterator();
-        s.remove(node);
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Set remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        iter  = s.iterator();
-        count = 0;
-        boolean terminated = false;
-
-        try
-        {
-            while (true)
-            {
-                iter.next();
-                ++count;
-            }
-        }
-        catch (NoSuchElementException ignored)
-        {
-            terminated = true;
-        }
-        assertTrue(terminated);
-        assertEquals(m.size(), count);
-        iter = s.iterator();
-        try
-        {
-            iter.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        Iterator iter2 = s.iterator();
-
-        try
-        {
-            iter2.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter = s.iterator();
-        iter.next();
-        LocalTestNode node2 = new LocalTestNode(-2);
-
-        m.put(node2.getKey(), node2);
-        try
-        {
-            iter.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        LocalTestNode node3 = new LocalTestNode(-3);
-
-        m.put(node3.getKey(), node3);
-        iter2 = s.iterator();
-        while (iter2.hasNext())
-        {
-            iter2.next();
-        }
-        int r_count = 0;
-
-        for (iter = s.iterator(); iter.hasNext(); )
-        {
-            if (iter.next().equals(node3))
-            {
-                try
-                {
-                    iter.remove();
-                    ++r_count;
-                    iter.remove();
-                    fail("2nd remove should have failed");
-                }
-                catch (IllegalStateException ignored)
-                {
-                    assertEquals(1, r_count);
-                }
-            }
-        }
-        assertEquals(1, r_count);
-        assertTrue(!s.contains(node3));
-        Object[] a1 = s.toArray();
-
-        assertTrue(a1.length == s.size());
-        try
-        {
-            String array2[] = ( String [] ) s.toArray(new String[ 0 ]);
-
-            if (s.size() != 0)
-            {
-                fail("should have caught exception creating an invalid array");
-            }
-        }
-        catch (ArrayStoreException ignored)
-        {
-        }
-        m.remove(node.getKey());
-        m.remove(node2.getKey());
-        m.remove(node3.getKey());
-        LocalTestNode array2[] =
-            ( LocalTestNode [] ) s.toArray(new LocalTestNode[ 0 ]);
-        LocalTestNode array3[] =
-            ( LocalTestNode [] ) s.toArray(new LocalTestNode[ s.size() ]);
-
-        try
-        {
-            s.add(node.getKey());
-            fail("should have thrown an exception");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        assertTrue(!s.equals(null));
-        assertEquals(s, s);
-        Set hs = new HashSet(s);
-
-        assertTrue(!s.equals(hs));
-        assertTrue(!hs.equals(s));
-    }
-
-    private static void testEntrySet(Map m) {
-        Set s = m.entrySet();
-
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        LocalTestNode node = new LocalTestNode(-1);
-
-        m.put(node.getKey(), node);
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        m.remove(node.getKey());
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        int count = 0;
-
-        for (Iterator iter = s.iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            ++count;
-        }
-        assertEquals(s.size(), count);
-        LocalTestNode node2 = new LocalTestNode(-2);
-
-        if (m.size() == 0)
-        {
-            m.put(node2.getKey(), node2);
-        }
-        Iterator iter = s.iterator();
-
-        m.put(node.getKey(), node);
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a put");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.remove(node2.getKey());
-        iter = s.iterator();
-        m.remove(node.getKey());
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Map remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter  = s.iterator();
-        count = 0;
-        boolean terminated = false;
-
-        try
-        {
-            while (true)
-            {
-                iter.next();
-                ++count;
-            }
-        }
-        catch (NoSuchElementException ignored)
-        {
-            terminated = true;
-        }
-        assertTrue(terminated);
-        assertEquals(m.size(), count);
-        iter = s.iterator();
-        try
-        {
-            iter.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        iter = s.iterator();
-        iter.next();
-        LocalTestNode node3 = new LocalTestNode(-3);
-
-        m.put(node3.getKey(), node3);
-        try
-        {
-            iter.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        int r_count = 0;
-        int when    = m.size() / 2;
-        int timer   = 0;
-
-        for (iter = s.iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            if (timer == when)
-            {
-                try
-                {
-                    iter.remove();
-                    ++r_count;
-                    iter.remove();
-                    fail("2nd remove should have failed");
-                }
-                catch (IllegalStateException ignored)
-                {
-                    assertEquals(1, r_count);
-                }
-            }
-            timer++;
-        }
-        assertEquals(1, r_count);
-        Iterator iter2 = s.iterator();
-
-        try
-        {
-            iter2.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        iter2 = s.iterator();
-        while (iter2.hasNext())
-        {
-            iter2.next();
-        }
-        LocalTestNode node4 = new LocalTestNode(-4);
-
-        m.put(node4.getKey(), node4);
-        try
-        {
-            iter2.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        Object[] a1 = s.toArray();
-
-        assertTrue(a1.length == s.size());
-        if (a1.length > 1)
-        {
-            Map.Entry first = ( Map.Entry ) a1[ 0 ];
-
-            for (int k = 1; k < a1.length; k++)
-            {
-                Map.Entry second = ( Map.Entry ) a1[ k ];
-
-                assertTrue((( Comparable ) first.getKey())
-                    .compareTo(( Comparable ) second.getKey()) < 0);
-                first = second;
-            }
-            iter  = s.iterator();
-            first = ( Map.Entry ) iter.next();
-            for (; iter.hasNext(); )
-            {
-                Map.Entry second = ( Map.Entry ) iter.next();
-
-                assertTrue((( Comparable ) first.getKey())
-                    .compareTo(( Comparable ) second.getKey()) < 0);
-                first = second;
-            }
-        }
-        try
-        {
-            Integer array2[] = ( Integer [] ) s.toArray(new Integer[ 0 ]);
-
-            if (s.size() != 0)
-            {
-                fail("should have caught exception creating an invalid array");
-            }
-        }
-        catch (ArrayStoreException ignored)
-        {
-        }
-        Map.Entry array2[] = ( Map.Entry [] ) s.toArray(new Map.Entry[ 0 ]);
-        Map.Entry array3[] =
-            ( Map.Entry [] ) s.toArray(new Map.Entry[ s.size() ]);
-
-        if (array3.length > 1)
-        {
-            Comparable first =
-                ( Comparable ) (( Map.Entry ) array3[ 0 ]).getKey();
-
-            for (int k = 1; k < array3.length; k++)
-            {
-                Comparable second =
-                    ( Comparable ) (( Map.Entry ) array3[ k ]).getKey();
-
-                assertTrue(first.compareTo(second) < 0);
-                first = second;
-            }
-        }
-        try
-        {
-            s.add(node.getKey());
-            fail("should have thrown an exception");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        assertTrue(!s.equals(null));
-        assertEquals("SetEquality 1", s, s);
-        Set hs = new HashSet(s);
-
-        assertEquals("SetEquality 2", s, hs);
-        assertEquals("SetEquality 3", hs, s);
-        assertTrue(s.hashCode() == hs.hashCode());
-    }
-
-    private static void testEntrySetByValue(BinaryTree m) {
-        Set s = m.entrySetByValue();
-
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        LocalTestNode node = new LocalTestNode(-1);
-
-        m.put(node.getKey(), node);
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        m.remove(node.getKey());
-        assertEquals(m.size(), s.size());
-        assertEquals(m.isEmpty(), s.isEmpty());
-        int count = 0;
-
-        for (Iterator iter = s.iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            ++count;
-        }
-        assertEquals(s.size(), count);
-        LocalTestNode node2 = new LocalTestNode(-2);
-
-        if (m.size() == 0)
-        {
-            m.put(node2.getKey(), node2);
-        }
-        Iterator iter = s.iterator();
-
-        m.put(node.getKey(), node);
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a put");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.remove(node2.getKey());
-        iter = s.iterator();
-        m.remove(node.getKey());
-        try
-        {
-            iter.next();
-            fail("next() should have thrown an exception after a Map remove");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        m.put(node.getKey(), node);
-        iter  = s.iterator();
-        count = 0;
-        boolean terminated = false;
-
-        try
-        {
-            while (true)
-            {
-                iter.next();
-                ++count;
-            }
-        }
-        catch (NoSuchElementException ignored)
-        {
-            terminated = true;
-        }
-        assertTrue(terminated);
-        assertEquals(m.size(), count);
-        iter = s.iterator();
-        try
-        {
-            iter.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        iter = s.iterator();
-        iter.next();
-        LocalTestNode node3 = new LocalTestNode(-3);
-
-        m.put(node3.getKey(), node3);
-        try
-        {
-            iter.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        int r_count = 0;
-        int when    = m.size() / 2;
-        int timer   = 0;
-
-        for (iter = s.iterator(); iter.hasNext(); )
-        {
-            iter.next();
-            if (timer == when)
-            {
-                try
-                {
-                    iter.remove();
-                    ++r_count;
-                    iter.remove();
-                    fail("2nd remove should have failed");
-                }
-                catch (IllegalStateException ignored)
-                {
-                    assertEquals(1, r_count);
-                }
-            }
-            timer++;
-        }
-        assertEquals(1, r_count);
-        Iterator iter2 = s.iterator();
-
-        try
-        {
-            iter2.remove();
-            fail("Should have thrown exception");
-        }
-        catch (IllegalStateException ignored)
-        {
-        }
-        iter2 = s.iterator();
-        while (iter2.hasNext())
-        {
-            iter2.next();
-        }
-        LocalTestNode node4 = new LocalTestNode(-4);
-
-        m.put(node4.getKey(), node4);
-        try
-        {
-            iter2.remove();
-            fail("should have thrown exception");
-        }
-        catch (ConcurrentModificationException ignored)
-        {
-        }
-        Object[] a1 = s.toArray();
-
-        assertTrue(a1.length == s.size());
-        if (a1.length > 1)
-        {
-            Map.Entry first = ( Map.Entry ) a1[ 0 ];
-
-            for (int k = 1; k < a1.length; k++)
-            {
-                Map.Entry second = ( Map.Entry ) a1[ k ];
-
-                assertTrue((( Comparable ) first.getKey())
-                    .compareTo(( Comparable ) second.getKey()) < 0);
-                first = second;
-            }
-            iter  = s.iterator();
-            first = ( Map.Entry ) iter.next();
-            for (; iter.hasNext(); )
-            {
-                Map.Entry second = ( Map.Entry ) iter.next();
-
-                assertTrue((( Comparable ) first.getKey())
-                    .compareTo(( Comparable ) second.getKey()) < 0);
-                first = second;
-            }
-        }
-        try
-        {
-            Integer array2[] = ( Integer [] ) s.toArray(new Integer[ 0 ]);
-
-            if (s.size() != 0)
-            {
-                fail("should have caught exception creating an invalid array");
-            }
-        }
-        catch (ArrayStoreException ignored)
-        {
-        }
-        Map.Entry array2[] = ( Map.Entry [] ) s.toArray(new Map.Entry[ 0 ]);
-        Map.Entry array3[] =
-            ( Map.Entry [] ) s.toArray(new Map.Entry[ s.size() ]);
-
-        if (array3.length > 1)
-        {
-            Comparable first =
-                ( Comparable ) (( Map.Entry ) array3[ 0 ]).getValue();
-
-            for (int k = 1; k < array3.length; k++)
-            {
-                Comparable second =
-                    ( Comparable ) (( Map.Entry ) array3[ k ]).getValue();
-
-                assertTrue(first.compareTo(second) < 0);
-                first = second;
-            }
-        }
-        try
-        {
-            s.add(node.getKey());
-            fail("should have thrown an exception");
-        }
-        catch (UnsupportedOperationException ignored)
-        {
-        }
-        assertTrue(!s.equals(null));
-        assertEquals("SetEquality 1", s, s);
-        Set hs = new HashSet(s);
-
-        assertEquals("SetEquality 2", s, hs);
-        assertEquals("SetEquality 3", hs, s);
-        assertTrue(s.hashCode() == hs.hashCode());
-    }
-
-    private LocalTestNode [] makeLocalNodes()
-    {
-        LocalTestNode nodes[] = new LocalTestNode[ 1023 ];
-
-        for (int k = 0; k < nodes.length; k++)
-        {
-            nodes[ k ] = new LocalTestNode(k);
-        }
-        return nodes;
-    }
-}
diff --git a/src/testcases/org/apache/poi/util/TestShortList.java b/src/testcases/org/apache/poi/util/TestShortList.java
deleted file mode 100644
index 1605b51ff3..0000000000
--- a/src/testcases/org/apache/poi/util/TestShortList.java
+++ /dev/null
@@ -1,570 +0,0 @@
-/* ====================================================================
-   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.poi.util;
-
-import junit.framework.TestCase;
-
-/**
- * Class to test ShortList
- *
- * @author Marc Johnson
- */
-public final class TestShortList extends TestCase {
-
-    public void testConstructors() {
-        ShortList list = new ShortList();
-
-        assertTrue(list.isEmpty());
-        list.add(( short ) 0);
-        list.add(( short ) 1);
-        ShortList list2 = new ShortList(list);
-
-        assertEquals(list, list2);
-        ShortList list3 = new ShortList(2);
-
-        assertTrue(list3.isEmpty());
-    }
-
-    public void testAdd() {
-        ShortList list      = new ShortList();
-        short[]   testArray =
-        {
-            0, 1, 2, 3, 5
-        };
-
-        for (int j = 0; j < testArray.length; j++)
-        {
-            list.add(testArray[ j ]);
-        }
-        for (int j = 0; j < testArray.length; j++)
-        {
-            assertEquals(testArray[ j ], list.get(j));
-        }
-        assertEquals(testArray.length, list.size());
-
-        // add at the beginning
-        list.add(0, ( short ) -1);
-        assertEquals(( short ) -1, list.get(0));
-        assertEquals(testArray.length + 1, list.size());
-        for (int j = 0; j < testArray.length; j++)
-        {
-            assertEquals(testArray[ j ], list.get(j + 1));
-        }
-
-        // add in the middle
-        list.add(5, ( short ) 4);
-        assertEquals(( short ) 4, list.get(5));
-        assertEquals(testArray.length + 2, list.size());
-        for (int j = 0; j < list.size(); j++)
-        {
-            assertEquals(( short ) (j - 1), list.get(j));
-        }
-
-        // add at the end
-        list.add(list.size(), ( short ) 6);
-        assertEquals(testArray.length + 3, list.size());
-        for (int j = 0; j < list.size(); j++)
-        {
-            assertEquals(( short ) (j - 1), list.get(j));
-        }
-
-        // add past end
-        try
-        {
-            list.add(list.size() + 1, ( short ) 8);
-            fail("should have thrown exception");
-        }
-        catch (IndexOutOfBoundsException e)
-        {
-
-            // as expected
-        }
-
-        // test growth
-        list = new ShortList(0);
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(j);
-        }
-        assertEquals(1000, list.size());
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(j, list.get(j));
-        }
-        list = new ShortList(0);
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(0, j);
-        }
-        assertEquals(1000, list.size());
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(j, list.get(999 - j));
-        }
-    }
-
-    public void testAddAll() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 5; j++)
-        {
-            list.add(j);
-        }
-        ShortList list2 = new ShortList(0);
-
-        list2.addAll(list);
-        list2.addAll(list);
-        assertEquals(2 * list.size(), list2.size());
-        for (short j = 0; j < 5; j++)
-        {
-            assertEquals(list2.get(j), j);
-            assertEquals(list2.get(j + list.size()), j);
-        }
-        ShortList empty = new ShortList();
-        int       limit = list.size();
-
-        for (int j = 0; j < limit; j++)
-        {
-            assertTrue(list.addAll(j, empty));
-            assertEquals(limit, list.size());
-        }
-        try
-        {
-            list.addAll(limit + 1, empty);
-            fail("should have thrown an exception");
-        }
-        catch (IndexOutOfBoundsException e)
-        {
-
-            // as expected
-        }
-
-        // try add at beginning
-        empty.addAll(0, list);
-        assertEquals(empty, list);
-
-        // try in the middle
-        empty.addAll(1, list);
-        assertEquals(2 * list.size(), empty.size());
-        assertEquals(list.get(0), empty.get(0));
-        assertEquals(list.get(0), empty.get(1));
-        assertEquals(list.get(1), empty.get(2));
-        assertEquals(list.get(1), empty.get(6));
-        assertEquals(list.get(2), empty.get(3));
-        assertEquals(list.get(2), empty.get(7));
-        assertEquals(list.get(3), empty.get(4));
-        assertEquals(list.get(3), empty.get(8));
-        assertEquals(list.get(4), empty.get(5));
-        assertEquals(list.get(4), empty.get(9));
-
-        // try at the end
-        empty.addAll(empty.size(), list);
-        assertEquals(3 * list.size(), empty.size());
-        assertEquals(list.get(0), empty.get(0));
-        assertEquals(list.get(0), empty.get(1));
-        assertEquals(list.get(0), empty.get(10));
-        assertEquals(list.get(1), empty.get(2));
-        assertEquals(list.get(1), empty.get(6));
-        assertEquals(list.get(1), empty.get(11));
-        assertEquals(list.get(2), empty.get(3));
-        assertEquals(list.get(2), empty.get(7));
-        assertEquals(list.get(2), empty.get(12));
-        assertEquals(list.get(3), empty.get(4));
-        assertEquals(list.get(3), empty.get(8));
-        assertEquals(list.get(3), empty.get(13));
-        assertEquals(list.get(4), empty.get(5));
-        assertEquals(list.get(4), empty.get(9));
-        assertEquals(list.get(4), empty.get(14));
-    }
-
-    public void testClear() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 500; j++)
-        {
-            list.add(j);
-        }
-        assertEquals(500, list.size());
-        list.clear();
-        assertEquals(0, list.size());
-        for (short j = 0; j < 500; j++)
-        {
-            list.add(( short ) (j + 1));
-        }
-        assertEquals(500, list.size());
-        for (short j = 0; j < 500; j++)
-        {
-            assertEquals(j + 1, list.get(j));
-        }
-    }
-
-    public void testContains() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j += 2)
-        {
-            list.add(j);
-        }
-        for (short j = 0; j < 1000; j++)
-        {
-            if (j % 2 == 0)
-            {
-                assertTrue(list.contains(j));
-            }
-            else
-            {
-                assertTrue(!list.contains(j));
-            }
-        }
-    }
-
-    public void testContainsAll() {
-        ShortList list = new ShortList();
-
-        assertTrue(list.containsAll(list));
-        for (short j = 0; j < 10; j++)
-        {
-            list.add(j);
-        }
-        ShortList list2 = new ShortList(list);
-
-        assertTrue(list2.containsAll(list));
-        assertTrue(list.containsAll(list2));
-        list2.add(( short ) 10);
-        assertTrue(list2.containsAll(list));
-        assertTrue(!list.containsAll(list2));
-        list.add(( short ) 11);
-        assertTrue(!list2.containsAll(list));
-        assertTrue(!list.containsAll(list2));
-    }
-
-    public void testEquals() {
-        ShortList list = new ShortList();
-
-        assertEquals(list, list);
-        assertTrue(!list.equals(null));
-        ShortList list2 = new ShortList(200);
-
-        assertEquals(list, list2);
-        assertEquals(list2, list);
-        assertEquals(list.hashCode(), list2.hashCode());
-        list.add(( short ) 0);
-        list.add(( short ) 1);
-        list2.add(( short ) 1);
-        list2.add(( short ) 0);
-        assertTrue(!list.equals(list2));
-        list2.removeValue(( short ) 1);
-        list2.add(( short ) 1);
-        assertEquals(list, list2);
-        assertEquals(list2, list);
-        list2.add(( short ) 2);
-        assertTrue(!list.equals(list2));
-        assertTrue(!list2.equals(list));
-    }
-
-    public void testGet() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(j);
-        }
-        for (short j = 0; j < 1001; j++)
-        {
-            try
-            {
-                assertEquals(j, list.get(j));
-                if (j == 1000)
-                {
-                    fail("should have gotten exception");
-                }
-            }
-            catch (IndexOutOfBoundsException e)
-            {
-                if (j != 1000)
-                {
-                    fail("unexpected IndexOutOfBoundsException");
-                }
-            }
-        }
-    }
-
-    public void testIndexOf() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(( short ) (j / 2));
-        }
-        for (short j = 0; j < 1000; j++)
-        {
-            if (j < 500)
-            {
-                assertEquals(j * 2, list.indexOf(j));
-            }
-            else
-            {
-                assertEquals(-1, list.indexOf(j));
-            }
-        }
-    }
-
-    public void testIsEmpty() {
-        ShortList list1 = new ShortList();
-        ShortList list2 = new ShortList(1000);
-        ShortList list3 = new ShortList(list1);
-
-        assertTrue(list1.isEmpty());
-        assertTrue(list2.isEmpty());
-        assertTrue(list3.isEmpty());
-        list1.add(( short ) 1);
-        list2.add(( short ) 2);
-        list3 = new ShortList(list2);
-        assertTrue(!list1.isEmpty());
-        assertTrue(!list2.isEmpty());
-        assertTrue(!list3.isEmpty());
-        list1.clear();
-        list2.remove(0);
-        list3.removeValue(( short ) 2);
-        assertTrue(list1.isEmpty());
-        assertTrue(list2.isEmpty());
-        assertTrue(list3.isEmpty());
-    }
-
-    public void testLastIndexOf() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(( short ) (j / 2));
-        }
-        for (short j = 0; j < 1000; j++)
-        {
-            if (j < 500)
-            {
-                assertEquals(1 + j * 2, list.lastIndexOf(j));
-            }
-            else
-            {
-                assertEquals(-1, list.indexOf(j));
-            }
-        }
-    }
-
-    public void testRemove() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(j);
-        }
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(j, list.remove(0));
-            assertEquals(( short ) (999 - j), list.size());
-        }
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(j);
-        }
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(( short ) (999 - j),
-                         list.remove(( short ) (999 - j)));
-            assertEquals(999 - j, list.size());
-        }
-        try
-        {
-            list.remove(0);
-            fail("should have caught IndexOutOfBoundsException");
-        }
-        catch (IndexOutOfBoundsException e)
-        {
-
-            // as expected
-        }
-    }
-
-    public void testRemoveValue() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(( short ) (j / 2));
-        }
-        for (short j = 0; j < 1000; j++)
-        {
-            if (j < 500)
-            {
-                assertTrue(list.removeValue(j));
-                assertTrue(list.removeValue(j));
-            }
-            assertTrue(!list.removeValue(j));
-        }
-    }
-
-    public void testRemoveAll() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(j);
-        }
-        ShortList listCopy = new ShortList(list);
-        ShortList listOdd  = new ShortList();
-        ShortList listEven = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            if (j % 2 == 0)
-            {
-                listEven.add(j);
-            }
-            else
-            {
-                listOdd.add(j);
-            }
-        }
-        list.removeAll(listEven);
-        assertEquals(list, listOdd);
-        list.removeAll(listOdd);
-        assertTrue(list.isEmpty());
-        listCopy.removeAll(listOdd);
-        assertEquals(listCopy, listEven);
-        listCopy.removeAll(listEven);
-        assertTrue(listCopy.isEmpty());
-    }
-
-    public void testRetainAll() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(j);
-        }
-        ShortList listCopy = new ShortList(list);
-        ShortList listOdd  = new ShortList();
-        ShortList listEven = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            if (j % 2 == 0)
-            {
-                listEven.add(j);
-            }
-            else
-            {
-                listOdd.add(j);
-            }
-        }
-        list.retainAll(listOdd);
-        assertEquals(list, listOdd);
-        list.retainAll(listEven);
-        assertTrue(list.isEmpty());
-        listCopy.retainAll(listEven);
-        assertEquals(listCopy, listEven);
-        listCopy.retainAll(listOdd);
-        assertTrue(listCopy.isEmpty());
-    }
-
-    public void testSet() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(j);
-        }
-        for (short j = 0; j < 1001; j++)
-        {
-            try
-            {
-                list.set(j, ( short ) (j + 1));
-                if (j == 1000)
-                {
-                    fail("Should have gotten exception");
-                }
-                assertEquals(j + 1, list.get(j));
-            }
-            catch (IndexOutOfBoundsException e)
-            {
-                if (j != 1000)
-                {
-                    fail("premature exception");
-                }
-            }
-        }
-    }
-
-    public void testSize() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(j, list.size());
-            list.add(j);
-            assertEquals(j + 1, list.size());
-        }
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(1000 - j, list.size());
-            list.removeValue(j);
-            assertEquals(999 - j, list.size());
-        }
-    }
-
-    public void testToArray() {
-        ShortList list = new ShortList();
-
-        for (short j = 0; j < 1000; j++)
-        {
-            list.add(j);
-        }
-        short[] a1 = list.toArray();
-
-        assertEquals(a1.length, list.size());
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(a1[ j ], list.get(j));
-        }
-        short[] a2 = new short[ list.size() ];
-        short[] a3 = list.toArray(a2);
-
-        assertSame(a2, a3);
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(a2[ j ], list.get(j));
-        }
-        short[] aShort = new short[ list.size() - 1 ];
-        short[] aLong  = new short[ list.size() + 1 ];
-        short[] a4     = list.toArray(aShort);
-        short[] a5     = list.toArray(aLong);
-
-        assertTrue(a4 != aShort);
-        assertTrue(a5 != aLong);
-        assertEquals(a4.length, list.size());
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(a3[ j ], list.get(j));
-        }
-        assertEquals(a5.length, list.size());
-        for (short j = 0; j < 1000; j++)
-        {
-            assertEquals(a5[ j ], list.get(j));
-        }
-    }
-}