sequencedhashmap.java

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

     */
    public Object getFirstValue() {
        // sentinel.next points to the "first" element of the sequence -- the head
        // of the list -- and the requisite value is returned from it.  An empty
        // list does not need to be tested.  In cases where the list is empty,
        // sentinel.next will point to the sentinel itself which has a null value,
        // which is exactly what we would want to return if the list is empty (a
        // nice convenient way to avoid test for an empty list)
        return sentinel.next.getValue();
    }

    /**
     *  Return the entry for the "newest" mapping.  That is, return the Map.Entry
     *  for the key-value pair that was first put into the map when compared to
     *  all the other pairings in the map.  The behavior is equivalent to:
     *
     *  <pre>
     *    Object obj = null;
     *    Iterator iter = entrySet().iterator();
     *    while(iter.hasNext()) {
     *      obj = iter.next();
     *    }
     *    return (Map.Entry)obj;
     *  </pre>
     *
     *  However, the implementation of this method ensures an O(1) lookup of the
     *  last key rather than O(n).
     *
     *  @return The last entry in the sequence, or <code>null</code> if the map
     *  is empty.
     */
    public Map.Entry getLast() {
        // sentinel.prev points to the "last" element of the sequence -- the tail
        // of the list, which is exactly the entry we need to return.  We must test
        // for an empty list though because we don't want to return the sentinel!
        return (isEmpty()) ? null : sentinel.prev;
    }

    /**
     *  Return the key for the "newest" mapping.  That is, return the key for the
     *  mapping that was last put into the map when compared to all the other
     *  objects in the map.  This behavior is equivalent to using
     *  <code>getLast().getKey()</code>, but this method provides a slightly
     *  optimized implementation.
     *
     *  @return The last key in the sequence, or <code>null</code> if the map is
     *  empty.
     */
    public Object getLastKey() {
        // sentinel.prev points to the "last" element of the sequence -- the tail
        // of the list -- and the requisite key is returned from it.  An empty list
        // does not need to be tested.  In cases where the list is empty,
        // sentinel.prev will point to the sentinel itself which has a null key,
        // which is exactly what we would want to return if the list is empty (a
        // nice convenient way to avoid test for an empty list)
        return sentinel.prev.getKey();
    }

    /**
     *  Return the value for the "newest" mapping.  That is, return the value for
     *  the mapping that was last put into the map when compared to all the other
     *  objects in the map.  This behavior is equivalent to using
     *  <code>getLast().getValue()</code>, but this method provides a slightly
     *  optimized implementation.
     *
     *  @return The last value in the sequence, or <code>null</code> if the map
     *  is empty.
     */
    public Object getLastValue() {
        // sentinel.prev points to the "last" element of the sequence -- the tail
        // of the list -- and the requisite value is returned from it.  An empty
        // list does not need to be tested.  In cases where the list is empty,
        // sentinel.prev will point to the sentinel itself which has a null value,
        // which is exactly what we would want to return if the list is empty (a
        // nice convenient way to avoid test for an empty list)
        return sentinel.prev.getValue();
    }

    /**
     *  Implements {@link Map#put(Object, Object)}.
     */
    public Object put(Object key, Object value) {
        modCount++;

        Object oldValue = null;

        // lookup the entry for the specified key
        Entry e = (Entry) entries.get(key);

        // check to see if it already exists
        if (e != null) {
            // remove from list so the entry gets "moved" to the end of list
            removeEntry(e);

            // update value in map
            oldValue = e.setValue(value);

            // Note: We do not update the key here because its unnecessary.  We only
            // do comparisons using equals(Object) and we know the specified key and
            // that in the map are equal in that sense.  This may cause a problem if
            // someone does not implement their hashCode() and/or equals(Object)
            // method properly and then use it as a key in this map.  
        } else {
            // add new entry
            e = new Entry(key, value);
            entries.put(key, e);
        }
        // assert(entry in map, but not list)

        // add to list
        insertEntry(e);

        return oldValue;
    }

    /**
     *  Implements {@link Map#remove(Object)}.
     */
    public Object remove(Object key) {
        Entry e = removeImpl(key);
        return (e == null) ? null : e.getValue();
    }

    /**
     *  Fully remove an entry from the map, returning the old entry or null if
     *  there was no such entry with the specified key.
     */
    private Entry removeImpl(Object key) {
        Entry e = (Entry) entries.remove(key);
        if (e == null)
            return null;
        modCount++;
        removeEntry(e);
        return e;
    }

    /**
     *  Adds all the mappings in the specified map to this map, replacing any
     *  mappings that already exist (as per {@link Map#putAll(Map)}).  The order
     *  in which the entries are added is determined by the iterator returned
     *  from {@link Map#entrySet()} for the specified map.
     *
     *  @param t the mappings that should be added to this map.
     *
     *  @throws NullPointerException if <code>t</code> is <code>null</code>
     */
    public void putAll(Map t) {
        Iterator iter = t.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            put(entry.getKey(), entry.getValue());
        }
    }

    /**
     *  Implements {@link Map#clear()}.
     */
    public void clear() {
        modCount++;

        // remove all from the underlying map
        entries.clear();

        // and the list
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    /**
     *  Implements {@link Map#equals(Object)}.
     */
    public boolean equals(Object obj) {
        if (obj == null)
            return false;
        if (obj == this)
            return true;

        if (!(obj instanceof Map))
            return false;

        return entrySet().equals(((Map) obj).entrySet());
    }

    /**
     *  Implements {@link Map#hashCode()}.
     */
    public int hashCode() {
        return entrySet().hashCode();
    }

    /**
     *  Provides a string representation of the entries within the map.  The
     *  format of the returned string may change with different releases, so this
     *  method is suitable for debugging purposes only.  If a specific format is
     *  required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and
     *  iterate over the entries in the map formatting them as appropriate.
     */
    public String toString() {
        StringBuffer buf = new StringBuffer();
        buf.append('[');
        for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
            buf.append(pos.getKey());
            buf.append('=');
            buf.append(pos.getValue());
            if (pos.next != sentinel) {
                buf.append(',');
            }
        }
        buf.append(']');

        return buf.toString();
    }

    /**
     *  Implements {@link Map#keySet()}.
     */
    public Set keySet() {
        return new AbstractSet() {

            // required impls
            public Iterator iterator() {
                return new OrderedIterator(KEY);
            }
            public boolean remove(Object o) {
                Entry e = SequencedHashMap.this.removeImpl(o);
                return (e != null);
            }

            // more efficient impls than abstract set
            public void clear() {
                SequencedHashMap.this.clear();
            }
            public int size() {
                return SequencedHashMap.this.size();
            }
            public boolean isEmpty() {
                return SequencedHashMap.this.isEmpty();
            }
            public boolean contains(Object o) {
                return SequencedHashMap.this.containsKey(o);
            }

        };
    }

    /**
     *  Implements {@link Map#values()}.
     */
    public Collection values() {
        return new AbstractCollection() {
            // required impl
            public Iterator iterator() {
                return new OrderedIterator(VALUE);
            }
            public boolean remove(Object value) {
                // do null comparison outside loop so we only need to do it once.  This
                // provides a tighter, more efficient loop at the expense of slight
                // code duplication.
                if (value == null) {
                    for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
                        if (pos.getValue() == null) {
                            SequencedHashMap.this.removeImpl(pos.getKey());
                            return true;
                        }
                    }
                } else {
                    for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
                        if (value.equals(pos.getValue())) {
                            SequencedHashMap.this.removeImpl(pos.getKey());
                            return true;
                        }
                    }
                }

                return false;
            }

            // more efficient impls than abstract collection
            public void clear() {
                SequencedHashMap.this.clear();
            }
            public int size() {
                return SequencedHashMap.this.size();
            }
            public boolean isEmpty() {
                return SequencedHashMap.this.isEmpty();
            }
            public boolean contains(Object o) {
                return SequencedHashMap.this.containsValue(o);
            }
        };
    }

    /**
     *  Implements {@link Map#entrySet()}.
     */
    public Set entrySet() {
        return new AbstractSet() {
            // helper
            private Entry findEntry(Object o) {
                if (o == null)
                    return null;
                if (!(o instanceof Map.Entry))
                    return null;

                Map.Entry e = (Map.Entry) o;
                Entry entry = (Entry) entries.get(e.getKey());
                if (entry != null && entry.equals(e))
                    return entry;
                else
                    return null;
            }

            // required impl
            public Iterator iterator() {
                return new OrderedIterator(ENTRY);
            }
            public boolean remove(Object o) {
                Entry e = findEntry(o);
                if (e == null)
                    return false;

                return SequencedHashMap.this.removeImpl(e.getKey()) != null;
            }

            // more efficient impls than abstract collection
            public void clear() {
                SequencedHashMap.this.clear();
            }
            public int size() {
                return SequencedHashMap.this.size();
            }
            public boolean isEmpty() {
                return SequencedHashMap.this.isEmpty();
            }
            public boolean contains(Object o) {
                return findEntry(o) != null;
            }
        };
    }