From 590c07f91763ce548991bde08124960a38c68eaa Mon Sep 17 00:00:00 2001 From: Andreas Beeker Date: Mon, 5 Oct 2015 00:26:45 +0000 Subject: [PATCH] removed obsolete classes git-svn-id: https://svn.apache.org/repos/asf/poi/trunk@1706740 13f79535-47bb-0310-9956-ffa450edef68 --- src/java/org/apache/poi/util/BinaryTree.java | 2107 ------------- src/java/org/apache/poi/util/ShortList.java | 638 ---- .../org/apache/poi/util/AllPOIUtilTests.java | 2 - .../org/apache/poi/util/TestBinaryTree.java | 2645 ----------------- .../org/apache/poi/util/TestShortList.java | 570 ---- 5 files changed, 5962 deletions(-) delete mode 100644 src/java/org/apache/poi/util/BinaryTree.java delete mode 100644 src/java/org/apache/poi/util/ShortList.java delete mode 100644 src/testcases/org/apache/poi/util/TestBinaryTree.java delete mode 100644 src/testcases/org/apache/poi/util/TestShortList.java 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.

- * - * 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.

- * - * 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.

- * - * 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.

- * - * There are some limitations placed on data kept in this Map. The - * biggest one is this:

- * - * 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.

- * - * Obviously, that same restriction (and consequence of failing to - * heed that restriction) applies to the putAll method.

- * - * The Map.Entry instances returned by the appropriate methods will - * not allow setValue() and will throw an - * UnsupportedOperationException on attempts to call that method.

- * - * New methods are added to take advantage of the fact that values are - * kept sorted independently of their keys:

- * - * Object getKeyForValue(Object value) is the opposite of get; it - * takes a value and returns its key, if any.

- * - * Object removeValue(Object value) finds and removes the specified - * value and returns the now un-used key.

- * - * 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.

- * - * Set keySetByValue() returns the keys in a Set whose iterator will - * iterate over the keys in ascending order by their corresponding - * values.

- * - * Collection valuesByValue() returns the values in a Collection whose - * iterator will iterate over the values in ascending order.

- * - * @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.

- * - * 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.

- * - * 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.

- * - * 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: - *

- * - * the mimicry is not perfect, however: - * - * - * @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: - * - * - * hashCode = 1; - * Iterator i = list.iterator(); - * while (i.hasNext()) { - * Object obj = i.next(); - * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); - * } - * - * - * 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)); - } - } -} -- 2.39.5