Collections Data Structure Java


   * 
   * @param t
   *          mappings to be stored in this map.
   * @throws NullPointerException
   *           if the specified map is null.
   */
  public void putAll(Map t) {
    // Expand enough to hold t's elements without resizing.
    int n = t.size();
    if (n == 0)
      return;
    if (n >= threshold) {
      n = (int) (n / loadFactor + 1);
      if (n > MAXIMUM_CAPACITY)
        n = MAXIMUM_CAPACITY;
      int capacity = table.length;
      while (capacity < n)
        capacity <<= 1;
      resize(capacity);
    }
    for (Iterator i = t.entrySet().iterator(); i.hasNext();) {
      Map.Entry e = (Map.Entry) i.next();
      put(e.getKey(), e.getValue());
    }
  }
  /**
   * 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. A null return can also
   *         indicate that the map previously associated null with
   *         the specified key.
   */
  public Object remove(Object key) {
    Object k = maskNull(key);
    int h = hash(k);
    Entry[] tab = getTable();
    int i = indexFor(h, tab.length);
    Entry prev = tab[i];
    Entry e = prev;
    while (e != null) {
      Entry next = e.next;
      if (h == e.hash && k == e.get()) {
        modCount++;
        size--;
        if (prev == e)
          tab[i] = next;
        else
          prev.next = next;
        return e.value;
      }
      prev = e;
      e = next;
    }
    return null;
  }
  /** Special version of remove needed by Entry set */
  Entry removeMapping(Object o) {
    if (!(o instanceof Map.Entry))
      return null;
    Entry[] tab = getTable();
    Map.Entry entry = (Map.Entry) o;
    Object k = maskNull(entry.getKey());
    int h = hash(k);
    int i = indexFor(h, tab.length);
    Entry prev = tab[i];
    Entry e = prev;
    while (e != null) {
      Entry next = e.next;
      if (h == e.hash && e.equals(entry)) {
        modCount++;
        size--;
        if (prev == e)
          tab[i] = next;
        else
          prev.next = next;
        return e;
      }
      prev = e;
      e = next;
    }
    return null;
  }
  /**
   * Removes all mappings from this map.
   */
  public void clear() {
    // clear out ref queue. We don't need to expunge entries
    // since table is getting cleared.
    while (queue.poll() != null)
      ;
    modCount++;
    Entry tab[] = table;
    for (int i = 0; i < tab.length; ++i)
      tab[i] = null;
    size = 0;
    // Allocation of array may have caused GC, which may have caused
    // additional entries to go stale. Removing these entries from the
    // reference queue will make them eligible for reclamation.
    while (queue.poll() != 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(Object value) {
    if (value == null)
      return containsNullValue();
    Entry tab[] = getTable();
    for (int i = tab.length; i-- > 0;)
      for (Entry e = tab[i]; e != null; e = e.next)
        if (value.equals(e.value))
          return true;
    return false;
  }
  /**
   * Special-case code for containsValue with null argument
   */
  private boolean containsNullValue() {
    Entry tab[] = getTable();
    for (int i = tab.length; i-- > 0;)
      for (Entry e = tab[i]; e != null; e = e.next)
        if (e.value == null)
          return true;
    return false;
  }
  /**
   * The entries in this hash table extend WeakReference, using its main ref
   * field as the key.
   */
  private static class Entry extends WeakReference implements Map.Entry {
    private Object value;
    private final int hash;
    private Entry next;
    /**
     * Create new entry.
     */
    Entry(Object key, Object value, ReferenceQueue queue, int hash, Entry next) {
      super(key, queue);
      this.value = value;
      this.hash = hash;
      this.next = next;
    }
    public Object getKey() {
      return unmaskNull(this.get());
    }
    public Object getValue() {
      return value;
    }
    public Object setValue(Object newValue) {
      Object oldValue = value;
      value = newValue;
      return oldValue;
    }
    public boolean equals(Object o) {
      if (!(o instanceof Map.Entry))
        return false;
      Map.Entry e = (Map.Entry) o;
      Object k1 = getKey();
      Object k2 = e.getKey();
      if (k1 == k2) {
        Object v1 = getValue();
        Object v2 = e.getValue();
        if (v1 == v2 || (v1 != null && v1.equals(v2)))
          return true;
      }
      return false;
    }
    public int hashCode() {
      Object k = getKey();
      Object v = getValue();
      return ((k == null ? 0 : System.identityHashCode(k)) ^ (v == null ? 0 : v.hashCode()));
    }
    public String toString() {
      return getKey() + "=" + getValue();
    }
  }
  private abstract class HashIterator implements Iterator {
    int index;
    Entry entry = null;
    Entry lastReturned = null;
    int expectedModCount = modCount;
    /**
     * Strong reference needed to avoid disappearance of key between hasNext and
     * next
     */
    Object nextKey = null;
    /**
     * Strong reference needed to avoid disappearance of key between nextEntry()
     * and any use of the entry
     */
    Object currentKey = null;
    HashIterator() {
      index = (size() != 0 ? table.length : 0);
    }
    public boolean hasNext() {
      Entry[] t = table;
      while (nextKey == null) {
        Entry e = entry;
        int i = index;
        while (e == null && i > 0)
          e = t[--i];
        entry = e;
        index = i;
        if (e == null) {
          currentKey = null;
          return false;
        }
        nextKey = e.get(); // hold on to key in strong ref
        if (nextKey == null)
          entry = entry.next;
      }
      return true;
    }
    protected Entry nextEntry() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
      if (nextKey == null && !hasNext())
        throw new NoSuchElementException();
      lastReturned = entry;
      entry = entry.next;
      currentKey = nextKey;
      nextKey = null;
      return lastReturned;
    }
    public void remove() {
      if (lastReturned == null)
        throw new IllegalStateException();
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
      WeakIdentityHashMap.this.remove(currentKey);
      expectedModCount = modCount;
      lastReturned = null;
      currentKey = null;
    }
  }
  private class ValueIterator extends HashIterator {
    public Object next() {
      return nextEntry().value;
    }
  }
  private class KeyIterator extends HashIterator {
    public Object next() {
      return nextEntry().getKey();
    }
  }
  private class EntryIterator extends HashIterator {
    public Object next() {
      return nextEntry();
    }
  }
  // Views
  private transient Set entrySet = 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.
   * The set supports element removal, which removes the corresponding mapping
   * from this 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() {
    Set ks = keySet;
    return (ks != null ? ks : (keySet = new KeySet()));
  }
  private class KeySet extends AbstractSet {
    public Iterator iterator() {
      return new KeyIterator();
    }
    public int size() {
      return WeakIdentityHashMap.this.size();
    }
    public boolean contains(Object o) {
      return containsKey(o);
    }
    public boolean remove(Object o) {
      if (containsKey(o)) {
        WeakIdentityHashMap.this.remove(o);
        return true;
      } else
        return false;
    }
    public void clear() {
      WeakIdentityHashMap.this.clear();
    }
    public Object[] toArray() {
      Collection c = new ArrayList(size());
      for (Iterator i = iterator(); i.hasNext();)
        c.add(i.next());
      return c.toArray();
    }
    public Object[] toArray(Object a[]) {
      Collection c = new ArrayList(size());
      for (Iterator i = iterator(); i.hasNext();)
        c.add(i.next());
      return c.toArray(a);
    }
  }
  /**
   * 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. The collection supports element removal, which
   * removes the corresponding mapping from this 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() {
    Collection vs = values;
    return (vs != null ? vs : (values = new Values()));
  }
  private class Values extends AbstractCollection {
    public Iterator iterator() {
      return new ValueIterator();
    }
    public int size() {
      return WeakIdentityHashMap.this.size();
    }
    public boolean contains(Object o) {
      return containsValue(o);
    }
    public void clear() {
      WeakIdentityHashMap.this.clear();
    }
    public Object[] toArray() {
      Collection c = new ArrayList(size());
      for (Iterator i = iterator(); i.hasNext();)
        c.add(i.next());
      return c.toArray();
    }
    public Object[] toArray(Object a[]) {
      Collection c = new ArrayList(size());
      for (Iterator i = iterator(); i.hasNext();)
        c.add(i.next());
      return c.toArray(a);
    }
  }
  /**
   * Returns a collection view of the mappings contained in this map. Each
   * element in the returned collection is a Map.Entry. The
   * collection is backed by the map, so changes to the map are reflected in the
   * collection, and vice-versa. 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 mappings contained in this map.
   * @see java.util.Map.Entry
   */
  public Set entrySet() {
    Set es = entrySet;
    return (es != null ? es : (entrySet = new EntrySet()));
  }
  private class EntrySet extends AbstractSet {
    public Iterator iterator() {
      return new EntryIterator();
    }
    public boolean contains(Object o) {
      if (!(o instanceof Map.Entry))
        return false;
      Map.Entry e = (Map.Entry) o;
      Entry candidate = getEntry(e.getKey());
      return candidate != null && candidate.equals(e);
    }
    public boolean remove(Object o) {
      return removeMapping(o) != null;
    }
    public int size() {
      return WeakIdentityHashMap.this.size();
    }
    public void clear() {
      WeakIdentityHashMap.this.clear();
    }
    public Object[] toArray() {
      Collection c = new ArrayList(size());
      for (Iterator i = iterator(); i.hasNext();)
        c.add(new SimpleEntry((Map.Entry) i.next()));
      return c.toArray();
    }
    public Object[] toArray(Object a[]) {
      Collection c = new ArrayList(size());
      for (Iterator i = iterator(); i.hasNext();)
        c.add(new SimpleEntry((Map.Entry) i.next()));
      return c.toArray(a);
    }
  }
  static class SimpleEntry implements Map.Entry {
    Object key;
    Object value;
    public SimpleEntry(Object key, Object value) {
      this.key = key;
      this.value = value;
    }
    public SimpleEntry(Map.Entry e) {
      this.key = e.getKey();
      this.value = e.getValue();
    }
    public Object getKey() {
      return key;
    }
    public Object getValue() {
      return value;
    }
    public Object setValue(Object value) {
      Object oldValue = this.value;
      this.value = value;
      return oldValue;
    }
    public boolean equals(Object o) {
      if (!(o instanceof Map.Entry))
        return false;
      Map.Entry e = (Map.Entry) o;
      return eq(key, e.getKey()) && eq(value, e.getValue());
    }
    public int hashCode() {
      return ((key == null) ? 0 : key.hashCode()) ^ ((value == null) ? 0 : value.hashCode());
    }
    public String toString() {
      return key + "=" + value;
    }
    private static boolean eq(Object o1, Object o2) {
      return (o1 == null ? o2 == null : o1.equals(o2));
    }
  }
}