sequencedhashmap.java

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

    // constants to define what the iterator should return on "next"
    private static final int KEY = 0;
    private static final int VALUE = 1;
    private static final int ENTRY = 2;
    private static final int REMOVED_MASK = 0x80000000;

    private class OrderedIterator implements Iterator {
        /** 
         *  Holds the type that should be returned from the iterator.  The value
         *  should be either {@link #KEY}, {@link #VALUE}, or {@link #ENTRY}.  To
         *  save a tiny bit of memory, this field is also used as a marker for when
         *  remove has been called on the current object to prevent a second remove
         *  on the same element.  Essentially, if this value is negative (i.e. the
         *  bit specified by {@link #REMOVED_MASK} is set), the current position
         *  has been removed.  If positive, remove can still be called.
         */
        private int returnType;

        /**
         *  Holds the "current" position in the iterator.  When pos.next is the
         *  sentinel, we've reached the end of the list.
         */
        private Entry pos = sentinel;

        /**
         *  Holds the expected modification count.  If the actual modification
         *  count of the map differs from this value, then a concurrent
         *  modification has occurred.
         */
        private transient long expectedModCount = modCount;

        /**
         *  Construct an iterator over the sequenced elements in the order in which
         *  they were added.  The {@link #next()} method returns the type specified
         *  by <code>returnType</code> which must be either {@link #KEY}, {@link
         *  #VALUE}, or {@link #ENTRY}.
         */
        public OrderedIterator(int returnType) {
            //// Since this is a private inner class, nothing else should have
            //// access to the constructor.  Since we know the rest of the outer
            //// class uses the iterator correctly, we can leave of the following
            //// check:
            //if(returnType >= 0 && returnType <= 2) {
            //  throw new IllegalArgumentException("Invalid iterator type");
            //}

            // Set the "removed" bit so that the iterator starts in a state where
            // "next" must be called before "remove" will succeed.
            this.returnType = returnType | REMOVED_MASK;
        }

        /**
         *  Returns whether there is any additional elements in the iterator to be
         *  returned.
         *
         *  @return <code>true</code> if there are more elements left to be
         *  returned from the iterator; <code>false</code> otherwise.
         */
        public boolean hasNext() {
            return pos.next != sentinel;
        }

        /**
         *  Returns the next element from the iterator.
         *
         *  @return the next element from the iterator.
         *
         *  @throws NoSuchElementException if there are no more elements in the
         *  iterator.
         *
         *  @throws ConcurrentModificationException if a modification occurs in
         *  the underlying map.
         */
        public Object next() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (pos.next == sentinel) {
                throw new NoSuchElementException();
            }

            // clear the "removed" flag
            returnType = returnType & ~REMOVED_MASK;

            pos = pos.next;
            switch (returnType) {
                case KEY :
                    return pos.getKey();
                case VALUE :
                    return pos.getValue();
                case ENTRY :
                    return pos;
                default :
                    // should never happen
                    throw new Error("bad iterator type: " + returnType);
            }

        }

        /**
         *  Removes the last element returned from the {@link #next()} method from
         *  the sequenced map.
         *
         *  @throws IllegalStateException if there isn't a "last element" to be
         *  removed.  That is, if {@link #next()} has never been called, or if
         *  {@link #remove()} was already called on the element.
         *
         *  @throws ConcurrentModificationException if a modification occurs in
         *  the underlying map.
         */
        public void remove() {
            if ((returnType & REMOVED_MASK) != 0) {
                throw new IllegalStateException("remove() must follow next()");
            }
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }

            SequencedHashMap.this.removeImpl(pos.getKey());

            // update the expected mod count for the remove operation
            expectedModCount++;

            // set the removed flag
            returnType = returnType | REMOVED_MASK;
        }
    }

    // APIs maintained from previous version of SequencedHashMap for backwards
    // compatibility

    /**
     * Creates a shallow copy of this object, preserving the internal structure
     * by copying only references.  The keys and values themselves are not
     * <code>clone()</code>'d.  The cloned object maintains the same sequence.
     *
     * @return A clone of this instance.  
     *
     * @throws CloneNotSupportedException if clone is not supported by a
     * subclass.
     */
    public Object clone() throws CloneNotSupportedException {
        // yes, calling super.clone() silly since we're just blowing away all
        // the stuff that super might be doing anyway, but for motivations on
        // this, see:
        // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
        SequencedHashMap map = (SequencedHashMap) super.clone();

        // create new, empty sentinel
        map.sentinel = createSentinel();

        // create a new, empty entry map
        // note: this does not preserve the initial capacity and load factor.
        map.entries = new HashMap();

        // add all the mappings
        map.putAll(this);

        // Note: We cannot just clone the hashmap and sentinel because we must
        // duplicate our internal structures.  Cloning those two will not clone all
        // the other entries they reference, and so the cloned hash map will not be
        // able to maintain internal consistency because there are two objects with
        // the same entries.  See discussion in the Entry implementation on why we
        // cannot implement a clone of the Entry (and thus why we need to recreate
        // everything).

        return map;
    }

    /**
     *  Returns the Map.Entry at the specified index
     *
     *  @throws ArrayIndexOutOfBoundsException if the specified index is
     *  <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
     */
    private Map.Entry getEntry(int index) {
        Entry pos = sentinel;

        if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index + " < 0");
        }

        // loop to one before the position
        int i = -1;
        while (i < (index - 1) && pos.next != sentinel) {
            i++;
            pos = pos.next;
        }
        // pos.next is the requested position

        // if sentinel is next, past end of list
        if (pos.next == sentinel) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + (i + 1));
        }

        return pos.next;
    }

    /**
     * Gets the key at the specified index.
     *
     * @param index  the index to retrieve
     * @return the key at the specified index, or null
     * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
     *  <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
     */
    public Object get(int index) {
        return getEntry(index).getKey();
    }

    /**
     * Gets the value at the specified index.
     *
     * @param index  the index to retrieve
     * @return the value at the specified index, or null
     * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
     *  <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
     */
    public Object getValue(int index) {
        return getEntry(index).getValue();
    }

    /**
     * Gets the index of the specified key.
     * 
     * @param key  the key to find the index of
     * @return the index, or -1 if not found
     */
    public int indexOf(Object key) {
        Entry e = (Entry) entries.get(key);
        if (e == null) {
            return -1;
        }
        int pos = 0;
        while (e.prev != sentinel) {
            pos++;
            e = e.prev;
        }
        return pos;
    }

    /**
     * Gets an iterator over the keys.
     * 
     * @return an iterator over the keys
     */
    public Iterator iterator() {
        return keySet().iterator();
    }

    /**
     * Gets the last index of the specified key.
     * 
     * @param key  the key to find the index of
     * @return the index, or -1 if not found
     */
    public int lastIndexOf(Object key) {
        // keys in a map are guaranteed to be unique
        return indexOf(key);
    }

    /**
     * Returns a List view of the keys rather than a set view.  The returned
     * list is unmodifiable.  This is required because changes to the values of
     * the list (using {@link java.util.ListIterator#set(Object)}) will
     * effectively remove the value from the list and reinsert that value at
     * the end of the list, which is an unexpected side effect of changing the
     * value of a list.  This occurs because changing the key, changes when the
     * mapping is added to the map and thus where it appears in the list.
     *
     * <p>An alternative to this method is to use {@link #keySet()}
     *
     * @see #keySet()
     * @return The ordered list of keys.  
     */
    public List sequence() {
        List l = new ArrayList(size());
        Iterator iter = keySet().iterator();
        while (iter.hasNext()) {
            l.add(iter.next());
        }

        return UnmodifiableList.decorate(l);
    }

    /**
     * Removes the element at the specified index.
     *
     * @param index The index of the object to remove.
     * @return      The previous value corresponding the <code>key</code>, or
     *              <code>null</code> if none existed.
     *
     * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
     * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
     */
    public Object remove(int index) {
        return remove(get(index));
    }

    // per Externalizable.readExternal(ObjectInput)

    /**
     * Deserializes this map from the given stream.
     *
     * @param in the stream to deserialize from
     * @throws IOException if the stream raises it
     * @throws ClassNotFoundException if the stream raises it
     */
    public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
        int size = in.readInt();
        for (int i = 0; i < size; i++) {
            Object key = in.readObject();
            Object value = in.readObject();
            put(key, value);
        }
    }

    /**
     * Serializes this map to the given stream.
     *
     * @param out  the stream to serialize to
     * @throws IOException  if the stream raises it
     */
    public void writeExternal(ObjectOutput out) throws IOException {
        out.writeInt(size());
        for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
            out.writeObject(pos.getKey());
            out.writeObject(pos.getValue());
        }
    }

    // add a serial version uid, so that if we change things in the future
    // without changing the format, we can still deserialize properly.
    private static final long serialVersionUID = 3380552487888102930L;

}