treebidimap.java

iBATIS似乎已远离众说纷纭的OR框架之列

     * from the map. It does not support the add or addAll operations.
     *
     * @return a set view of the values contained in this map.
     */
    public Collection values() {
        if (valuesSet == null) {
            valuesSet = new View(this, KEY, VALUE);
        }
        return valuesSet;
    }

    //-----------------------------------------------------------------------
    /**
     * Returns a set view of the entries contained in this map in key order.
     * For simple iteration through the map, the MapIterator is quicker.
     * <p>
     * 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.
     * <p>
     * The set supports element removal, which removes the corresponding mapping
     * from the map. It does not support the add or addAll operations.
     * The returned MapEntry objects do not support setValue.
     *
     * @return a set view of the values contained in this map.
     */
    public Set entrySet() {
        if (entrySet == null) {
            return new EntryView(this, KEY, MAPENTRY);
        }
        return entrySet;
    }

    //-----------------------------------------------------------------------
    /**
     * Gets an iterator over the map entries.
     * <p>
     * For this map, this iterator is the fastest way to iterate over the entries.
     * 
     * @return an iterator
     */
    public MapIterator mapIterator() {
        if (isEmpty()) {
            return EmptyOrderedMapIterator.INSTANCE;
        }
        return new ViewMapIterator(this, KEY);
    }

    /**
     * Gets an ordered iterator over the map entries.
     * <p>
     * This iterator allows both forward and reverse iteration over the entries.
     * 
     * @return an iterator
     */
    public OrderedMapIterator orderedMapIterator() {
        if (isEmpty()) {
            return EmptyOrderedMapIterator.INSTANCE;
        }
        return new ViewMapIterator(this, KEY);
    }

    //-----------------------------------------------------------------------
    /**
     * Gets the inverse map for comparison.
     * 
     * @return the inverse map
     */
    public BidiMap inverseBidiMap() {
        return inverseOrderedBidiMap();
    }

    /**
     * Gets the inverse map for comparison.
     * 
     * @return the inverse map
     */
    public OrderedBidiMap inverseOrderedBidiMap() {
        if (inverse == null) {
            inverse = new Inverse(this);
        }
        return inverse;
    }

    //-----------------------------------------------------------------------
    /**
     * Compares for equals as per the API.
     *
     * @param obj  the object to compare to
     * @return true if equal
     */
    public boolean equals(Object obj) {
        return this.doEquals(obj, KEY);
    }
    
    /**
     * Gets the hash code value for this map as per the API.
     *
     * @return the hash code value for this map
     */
    public int hashCode() {
        return this.doHashCode(KEY);
    }
    
    /**
     * Returns a string version of this Map in standard format.
     * 
     * @return a standard format string version of the map
     */
    public String toString() {
        return this.doToString(KEY);
    }
    
    //-----------------------------------------------------------------------
    /**
     * Common get logic, used to get by key or get by value
     *
     * @param obj  the key or value that we're looking for
     * @param index  the KEY or VALUE int
     * @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(final Comparable obj, final int index) {
        checkNonNullComparable(obj, index);
        Node node = lookup(obj, index);
        return ((node == null) ? null : node.getData(oppositeIndex(index)));
    }

    /**
     * Common put logic, differing only in the return value.
     * 
     * @param key  the key, always the main map key
     * @param value  the value, always the main map value
     * @param index  the KEY or VALUE int, for the return value only
     * @return the previously mapped value
     */
    private Object doPut(final Comparable key, final Comparable value, final int index) {
        checkKeyAndValue(key, value);
        
        // store previous and remove previous mappings
        Object prev = (index == KEY ? doGet(key, KEY) :  doGet(value, VALUE));
        doRemove(key, KEY);
        doRemove(value, VALUE);
        
        Node node = rootNode[KEY];
        if (node == null) {
            // map is empty
            Node root = new Node(key, value);
            rootNode[KEY] = root;
            rootNode[VALUE] = root;
            grow();
            
        } else {
            // add new mapping
            while (true) {
                int cmp = compare(key, node.getData(KEY));
        
                if (cmp == 0) {
                    // shouldn't happen
                    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(key, 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(key, value);
        
                        insertValue(newNode);
                        node.setRight(newNode, KEY);
                        newNode.setParent(node, KEY);
                        doRedBlackInsert(newNode, KEY);
                        grow();
        
                        break;
                    }
                }
            }
        }
        return prev;
    }

    /**
     * Remove by object (remove by key or remove by value)
     *
     * @param o the key, or value, that we're looking for
     * @param index  the KEY or VALUE int
     *
     * @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(final Comparable o, final int index) {
        Node node = lookup(o, index);
        Object rval = null;
        if (node != null) {
            rval = node.getData(oppositeIndex(index));
            doRedBlackDelete(node);
        }
        return rval;
    }

    /**
     * do the actual lookup of a piece of data
     *
     * @param data the key or value to be looked up
     * @param index  the KEY or VALUE int
     * @return the desired Node, or null if there is no mapping of the
     *         specified data
     */
    private Node lookup(final Comparable data, final int index) {
        Node rval = null;
        Node node = rootNode[index];

        while (node != null) {
            int cmp = compare(data, node.getData(index));
            if (cmp == 0) {
                rval = node;
                break;
            } else {
                node = (cmp < 0) ? node.getLeft(index) : node.getRight(index);
            }
        }

        return rval;
    }

    /**
     * get the next larger node from the specified node
     *
     * @param node the node to be searched from
     * @param index  the KEY or VALUE int
     * @return the specified node
     */
    private Node nextGreater(final Node node, final 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 descendants 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;
    }

    /**
     * get the next larger node from the specified node
     *
     * @param node the node to be searched from
     * @param index  the KEY or VALUE int
     * @return the specified node
     */
    private Node nextSmaller(final Node node, final int index) {
        Node rval = null;
        if (node == null) {
            rval = null;
        } else if (node.getLeft(index) != null) {
            // everything to the node's left is smaller. The greatest of
            // the left node's descendants is the next smaller node
            rval = greatestNode(node.getLeft(index), index);
        } else {
            // traverse up our ancestry until we find an ancestor that
            // is null or one whose right 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 right
            // ... and that ancestor is the next greatest node
            Node parent = node.getParent(index);
            Node child = node;

            while ((parent != null) && (child == parent.getLeft(index))) {
                child = parent;
                parent = parent.getParent(index);
            }
            rval = parent;
        }
        return rval;
    }

    //-----------------------------------------------------------------------
    /**
     * Get the opposite index of the specified index
     *
     * @param index  the KEY or VALUE int
     * @return VALUE (if KEY was specified), else KEY
     */
    private static int oppositeIndex(final 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 SUM_OF_INDICES - index;
    }

    /**
     * Compare two objects
     *
     * @param o1  the first object
     * @param o2  the second object
     *
     * @return negative value if o1 &lt; o2; 0 if o1 == o2; positive
     *         value if o1 &gt; o2
     */
    private static int compare(final Comparable o1, final Comparable o2) {
        return o1.compareTo(o2);
    }

    /**
     * Find the least node from a given node.
     *
     * @param node  the node from which we will start searching
     * @param index  the KEY or VALUE int
     * @return the smallest node, from the specified node, in the
     *         specified mapping
     */
    private static Node leastNode(final Node node, final int index) {
        Node rval = node;
        if (rval != null) {
            while (rval.getLeft(index) != null) {
                rval = rval.getLeft(index);
            }
        }
        return rval;
    }

    /**
     * Find the greatest node from a given node.
     *
     * @param node  the node from which we will start searching
     * @param index  the KEY or VALUE int
     * @return the greatest node, from the specified node
     */
    private static Node greatestNode(final Node node, final int index) {
        Node rval = node;
        if (rval != null) {
            while (rval.getRight(index) != null) {
                rval = rval.getRight(index);
            }