doubleorderedmap.java

JAVA 文章管理系统源码

     */
    private static void checkNonNullComparable(final Object o,
                                               final int index) {

        if (o == null) {
            throw new NullPointerException(dataName[index]
                                           + " cannot be null");
        }

        if (!(o instanceof Comparable)) {
            throw new ClassCastException(dataName[index]
                                         + " must be Comparable");
        }
    }

    /**
     * check a key for validity (non-null and implements Comparable)
     *
     * @param key the key to be checked
     *
     * @throws NullPointerException if key is null
     * @throws ClassCastException if key is not Comparable
     */
    private static void checkKey(final Object key) {
        checkNonNullComparable(key, KEY);
    }

    /**
     * check a value for validity (non-null and implements Comparable)
     *
     * @param value the value to be checked
     *
     * @throws NullPointerException if value is null
     * @throws ClassCastException if value is not Comparable
     */
    private static void checkValue(final 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
     *
     * @throws NullPointerException if key or value is null
     * @throws ClassCastException if key or value is not Comparable
     */
    private static void checkKeyAndValue(final Object key,
                                         final 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();

        nodeCount++;
    }

    /**
     * decrement the size and note that the map has changed
     */
    private void shrink() {

        modify();

        nodeCount--;
    }

    /**
     * insert a node by its value
     *
     * @param newNode the node to be inserted
     *
     * @throws IllegalArgumentException if the node already exists
     *                                     in the value mapping
     */
    private void insertValue(final Node newNode)
            throws IllegalArgumentException {

        Node node = rootNode[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.MAXVALUE elements, returns
     * Integer.MAXVALUE.
     *
     * @return the number of key-value mappings in this map.
     */
    public int size() {
        return nodeCount;
    }

    /**
     * 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.
     *
     * @throws ClassCastException if the key is of an inappropriate
     *                               type for this map.
     * @throws NullPointerException if the key is null
     */
    public boolean containsKey(final 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(final 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.
     *
     * @throws ClassCastException if the key is of an inappropriate
     *                               type for this map.
     * @throws NullPointerException if the key is null
     */
    public Object get(final 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
     *
     * @throws ClassCastException if the class of the specified key
     *                               or value prevents it from being
     *                               stored in this map.
     * @throws NullPointerException if the specified key or value
     *                                 is null
     * @throws IllegalArgumentException if the key duplicates an
     *                                     existing key, or if the
     *                                     value duplicates an
     *                                     existing value
     */
    public Object put(final Object key, final Object value)
            throws ClassCastException, NullPointerException,
                   IllegalArgumentException {

        checkKeyAndValue(key, value);

        Node node = rootNode[KEY];

        if (node == null) {
            Node root = new Node((Comparable) key, (Comparable) value);

            rootNode[KEY]   = root;
            rootNode[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(final Object key) {
        return doRemove((Comparable) key, KEY);
    }

    /**
     * Removes all mappings from this map
     */
    public void clear() {

        modify();

        nodeCount   = 0;
        rootNode[KEY]   = null;
        rootNode[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 (setOfKeys[KEY] == null) {
            setOfKeys[KEY] = new AbstractSet() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(KEY) {

                        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[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 (collectionOfValues[KEY] == null) {
            collectionOfValues[KEY] = new AbstractCollection() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(KEY) {

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

                public int size() {