doubleorderedmap.java

初级java程序员如果想要更深一步提高自己的实力

/*
 *  Copyright 2002-2004 The Apache Software Foundation
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package org.apache.commons.collections;

import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * Red-Black tree-based implementation of Map. This class guarantees
 * that the map will be in both ascending key order and ascending
 * value order, sorted according to the natural order for the key's
 * and value's classes.
 * <p>
 * This Map is intended for applications that need to be able to look
 * up a key-value pairing by either key or value, and need to do so
 * with equal efficiency.
 * <p>
 * While that goal could be accomplished by taking a pair of TreeMaps
 * and redirecting requests to the appropriate TreeMap (e.g.,
 * containsKey would be directed to the TreeMap that maps values to
 * keys, containsValue would be directed to the TreeMap that maps keys
 * to values), there are problems with that implementation,
 * particularly when trying to keep the two TreeMaps synchronized with
 * each other. And if the data contained in the TreeMaps is large, the
 * cost of redundant storage becomes significant. (See also the new
 * {@link org.apache.commons.collections.bidimap.DualTreeBidiMap DualTreeBidiMap} and
 * {@link org.apache.commons.collections.bidimap.DualHashBidiMap DualHashBidiMap}
 * implementations.)
 * <p>
 * This solution keeps the data properly synchronized and minimizes
 * the data storage. The red-black algorithm is based on TreeMap's,
 * but has been modified to simultaneously map a tree node by key and
 * by value. This doubles the cost of put operations (but so does
 * using two TreeMaps), and nearly doubles the cost of remove
 * operations (there is a savings in that the lookup of the node to be
 * removed only has to be performed once). And since only one node
 * contains the key and value, storage is significantly less than that
 * required by two TreeMaps.
 * <p>
 * There are some limitations placed on data kept in this Map. The
 * biggest one is this:
 * <p>
 * When performing a put operation, neither the key nor the value may
 * already exist in the Map. In the java.util Map implementations
 * (HashMap, TreeMap), you can perform a put with an already mapped
 * key, and neither cares about duplicate values at all ... but this
 * implementation's put method with throw an IllegalArgumentException
 * if either the key or the value is already in the Map.
 * <p>
 * Obviously, that same restriction (and consequence of failing to
 * heed that restriction) applies to the putAll method.
 * <p>
 * The Map.Entry instances returned by the appropriate methods will
 * not allow setValue() and will throw an
 * UnsupportedOperationException on attempts to call that method.
 * <p>
 * New methods are added to take advantage of the fact that values are
 * kept sorted independently of their keys:
 * <p>
 * Object getKeyForValue(Object value) is the opposite of get; it
 * takes a value and returns its key, if any.
 * <p>
 * Object removeValue(Object value) finds and removes the specified
 * value and returns the now un-used key.
 * <p>
 * Set entrySetByValue() returns the Map.Entry's in a Set whose
 * iterator will iterate over the Map.Entry's in ascending order by
 * their corresponding values.
 * <p>
 * Set keySetByValue() returns the keys in a Set whose iterator will
 * iterate over the keys in ascending order by their corresponding
 * values.
 * <p>
 * Collection valuesByValue() returns the values in a Collection whose
 * iterator will iterate over the values in ascending order.
 *
 * @deprecated Replaced by TreeBidiMap in bidimap subpackage. Due to be removed in v4.0.
 * @see BidiMap
 * @see org.apache.commons.collections.bidimap.DualTreeBidiMap
 * @see org.apache.commons.collections.bidimap.DualHashBidiMap
 * @since Commons Collections 2.0
 * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
 * 
 * @author Marc Johnson
 */
public final class DoubleOrderedMap extends AbstractMap {
//  final for performance

    private static final int KEY = 0;
    private static final int VALUE = 1;
    private static final int SUM_OF_INDICES = KEY + VALUE;
    private static final int FIRST_INDEX = 0;
    private static final int NUMBER_OF_INDICES = 2;
    private static final String[] dataName = new String[] { "key", "value" };
    
    private Node[] rootNode = new Node[] { null, null };
    private int nodeCount = 0;
    private int modifications = 0;
    private Set[] setOfKeys = new Set[] { null, null };
    private Set[] setOfEntries = new Set[] { null, null };
    private Collection[] collectionOfValues = new Collection[] { null, null };

    /**
     * Construct a new DoubleOrderedMap
     */
    public DoubleOrderedMap() {
    }

    /**
     * Constructs a new DoubleOrderedMap from an existing Map, with keys and
     * values sorted
     *
     * @param map the map whose mappings are to be placed in this map.
     *
     * @throws 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
     * @throws NullPointerException if any key or value in the map
     *                                 is null
     * @throws IllegalArgumentException if there are duplicate keys
     *                                     or duplicate values in the
     *                                     map
     */
    public DoubleOrderedMap(final Map map)
            throws ClassCastException, NullPointerException,
                   IllegalArgumentException {
        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.
     *
     * @throws ClassCastException if the value is of an
     *                               inappropriate type for this map.
     * @throws NullPointerException if the value is null
     */
    public Object getKeyForValue(final 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(final Object value) {
        return doRemove((Comparable) value, VALUE);
    }

    /**
     * Returns a set view of the mappings contained in this map. Each
     * element in the returned set is a Map.Entry. The set is backed
     * by the map, so changes to the map are reflected in the set, and
     * vice-versa.  If the map is modified while an iteration over the
     * set is in progress, the results of the iteration are
     * undefined. The set supports element removal, which removes the
     * corresponding mapping from the map, via the Iterator.remove,
     * Set.remove, removeAll, retainAll and clear operations.  It does
     * not support the add or addAll operations.<p>
     *
     * The difference between this method and entrySet is that
     * entrySet's iterator() method returns an iterator that iterates
     * over the mappings in ascending order by key. This method's
     * iterator method iterates over the mappings in ascending order
     * by value.
     *
     * @return a set view of the mappings contained in this map.
     */
    public Set entrySetByValue() {

        if (setOfEntries[VALUE] == null) {
            setOfEntries[VALUE] = new AbstractSet() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(VALUE) {

                        protected Object doGetNext() {
                            return lastReturnedNode;
                        }
                    };
                }

                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 DoubleOrderedMap.this.size();
                }

                public void clear() {
                    DoubleOrderedMap.this.clear();
                }
            };
        }

        return setOfEntries[VALUE];
    }

    /**
     * Returns a set view of the keys contained in this map.  The set
     * is backed by the map, so changes to the map are reflected in
     * the set, and vice-versa. If the map is modified while an
     * iteration over the set is in progress, the results of the
     * iteration are undefined. The set supports element removal,
     * which removes the corresponding mapping from the map, via the
     * Iterator.remove, Set.remove, removeAll, retainAll, and clear
     * operations. It does not support the add or addAll
     * operations.<p>
     *
     * The difference between this method and keySet is that keySet's
     * iterator() method returns an iterator that iterates over the
     * keys in ascending order by key. This method's iterator method
     * iterates over the keys in ascending order by value.
     *
     * @return a set view of the keys contained in this map.
     */
    public Set keySetByValue() {

        if (setOfKeys[VALUE] == null) {
            setOfKeys[VALUE] = new AbstractSet() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(VALUE) {

                        protected Object doGetNext() {
                            return lastReturnedNode.getData(KEY);
                        }
                    };
                }

                public int size() {
                    return DoubleOrderedMap.this.size();
                }

                public boolean contains(Object o) {
                    return containsKey(o);
                }

                public boolean remove(Object o) {

                    int oldnodeCount = nodeCount;

                    DoubleOrderedMap.this.remove(o);

                    return nodeCount != oldnodeCount;
                }

                public void clear() {
                    DoubleOrderedMap.this.clear();
                }
            };
        }

        return setOfKeys[VALUE];
    }

    /**
     * Returns a collection view of the values contained in this
     * map. The collection is backed by the map, so changes to the map
     * are reflected in the collection, and vice-versa. If the map is
     * modified while an iteration over the collection is in progress,
     * the results of the iteration are undefined. The collection
     * supports element removal, which removes the corresponding
     * mapping from the map, via the Iterator.remove,
     * Collection.remove, removeAll, retainAll and clear operations.
     * It does not support the add or addAll operations.<p>
     *
     * The difference between this method and values is that values's
     * iterator() method returns an iterator that iterates over the
     * values in ascending order by key. This method's iterator method
     * iterates over the values in ascending order by key.
     *
     * @return a collection view of the values contained in this map.
     */
    public Collection valuesByValue() {

        if (collectionOfValues[VALUE] == null) {
            collectionOfValues[VALUE] = new AbstractCollection() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(VALUE) {

                        protected Object doGetNext() {
                            return lastReturnedNode.getData(VALUE);
                        }
                    };
                }

                public int size() {
                    return DoubleOrderedMap.this.size();
                }

                public boolean contains(Object o) {
                    return containsValue(o);
                }

                public boolean remove(Object o) {

                    int oldnodeCount = nodeCount;

                    removeValue(o);

                    return nodeCount != oldnodeCount;
                }

                public boolean removeAll(Collection c) {

                    boolean  modified = false;
                    Iterator iter     = c.iterator();

                    while (iter.hasNext()) {
                        if (removeValue(iter.next()) != null) {
                            modified = true;
                        }
                    }