Collections Data Structure Java

/*
 * Copyright 2004-2010 the Seasar Foundation and the Others.
 *
 * 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.slim3.util;
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.lang.reflect.Array;
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;
/**
 * A set acts like array.
 * 
 * @author higa
 * @param 
 *            the element type
 * @since 1.0.0
 */
public class ArraySet extends AbstractSet implements Set, Cloneable,
    java.io.Serializable {
  static final long serialVersionUID = -5024744406713321676L;
  private transient ArrayMap map;
  // Dummy value to associate with an Object in the backing Map
  private static final Object PRESENT = new Object();
  /**
   * Constructor.
   */
  public ArraySet() {
    map = new ArrayMap();
  }
  /**
   * Constructor.
   * 
   * @param c
   *            the collection whose elements are to be placed into this set.
   * @throws NullPointerException
   *             if the specified collection is null.
   */
  public ArraySet(Collection c) throws NullPointerException {
    if (c == null) {
      throw new NullPointerException("The c parameter must not be null.");
    }
    map = new ArrayMap(Math.max((int) (c.size() / .75f) + 1, 16));
    addAll(c);
  }
  /**
   * Constructor.
   * 
   * @param initialCapacity
   *            the initial capacity of the hash table.
   * @throws IllegalArgumentException
   *             if the initial capacity is less than zero.
   */
  public ArraySet(int initialCapacity) {
    map = new ArrayMap(initialCapacity);
  }
  /**
   * Returns an element specified by the index.
   * 
   * @param index
   *            the index
   * @return an element
   */
  public E get(int index) {
    return map.getKey(index);
  }
  /**
   * Returns an iterator over the elements in this set. The elements are
   * returned in no particular order.
   * 
   * @return an Iterator over the elements in this set.
   * @see ConcurrentModificationException
   */
  @Override
  public Iterator iterator() {
    return map.keySet().iterator();
  }
  /**
   * Returns the number of elements in this set (its cardinality).
   * 
   * @return the number of elements in this set (its cardinality).
   */
  @Override
  public int size() {
    return map.size();
  }
  /**
   * Returns true if this set contains no elements.
   * 
   * @return true if this set contains no elements.
   */
  @Override
  public boolean isEmpty() {
    return map.isEmpty();
  }
  /**
   * Returns true if this set contains the specified element.
   * 
   * @param o
   *            element whose presence in this set is to be tested.
   * @return true if this set contains the specified element.
   */
  @Override
  public boolean contains(Object o) {
    return map.containsKey(o);
  }
  /**
   * Adds the specified element to this set if it is not already present.
   * 
   * @param o
   *            element to be added to this set.
   * @return true if the set did not already contain the specified
   *         element.
   */
  @Override
  public boolean add(E o) {
    return map.put(o, PRESENT) == null;
  }
  /**
   * Removes the specified element from this set if it is present.
   * 
   * @param o
   *            object to be removed from this set, if present.
   * @return true if the set contained the specified element.
   */
  @Override
  public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
  }
  /**
   * Removes all of the elements from this set.
   */
  @Override
  public void clear() {
    map.clear();
  }
  /**
   * Returns a shallow copy of this HashSet instance: the elements
   * themselves are not cloned.
   * 
   * @return a shallow copy of this set.
   */
  @SuppressWarnings("unchecked")
  @Override
  public Object clone() {
    try {
      ArraySet newSet = (ArraySet) super.clone();
      newSet.map = (ArrayMap) map.clone();
      return newSet;
    } catch (CloneNotSupportedException e) {
      throw new InternalError();
    }
  }
  /**
   * Save the state of this HashSet instance to a stream (that is,
   * serialize this set).
   * 
   * @serialData The capacity of the backing HashMap instance (int),
   *             and its load factor (float) are emitted, followed by the size
   *             of the set (the number of elements it contains) (int),
   *             followed by all of its elements (each an Object) in no
   *             particular order.
   */
  private void writeObject(java.io.ObjectOutputStream s)
      throws java.io.IOException {
    s.defaultWriteObject();
    s.writeInt(map.size());
    for (Iterator i = map.keySet().iterator(); i.hasNext();) {
      s.writeObject(i.next());
    }
  }
  /**
   * Reconstitute the HashSet instance from a stream (that is,
   * deserialize it).
   */
  @SuppressWarnings("unchecked")
  private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();
    int size = s.readInt();
    map = new ArrayMap(size);
    for (int i = 0; i < size; i++) {
      E e = (E) s.readObject();
      map.put(e, PRESENT);
    }
  }
}
class ArrayMap extends AbstractMap implements Map, Cloneable,
    Externalizable {
  private static final long serialVersionUID = 1L;
  /**
   * The default initial capacity.
   */
  protected static final int INITIAL_CAPACITY = 17;
  /**
   * The default load factor.
   */
  protected static final float LOAD_FACTOR = 0.75f;
  /**
   * The threshold to extend the capacity.
   */
  protected transient int threshold;
  /**
   * The map table.
   */
  protected transient Entry[] mapTable;
  /**
   * The list table.
   */
  protected transient Entry[] listTable;
  /**
   * The number of entries.
   */
  protected transient int size = 0;
  /**
   * The set of entries.
   */
  protected transient Set> entrySet = null;
  /**
   * Constructor.
   */
  public ArrayMap() {
    this(INITIAL_CAPACITY);
  }
  /**
   * Constructor.
   * 
   * @param initialCapacity
   *            the initial capacity
   */
  public ArrayMap(int initialCapacity) {
    if (initialCapacity <= 0) {
      initialCapacity = INITIAL_CAPACITY;
    }
    mapTable = createArray(initialCapacity);
    listTable = createArray(initialCapacity);
    threshold = (int) (initialCapacity * LOAD_FACTOR);
  }
  /**
   * Constructor.
   * 
   * @param map
   *            other map
   */
  public ArrayMap(Map map) {
    this((int) (map.size() / LOAD_FACTOR) + 1);
    putAll(map);
  }
  @Override
  public final int size() {
    return size;
  }
  @Override
  public final boolean isEmpty() {
    return size == 0;
  }
  @Override
  public final boolean containsValue(Object value) {
    return indexOf(value) >= 0;
  }
  /**
   * Returns the index in the list table.
   * 
   * @param value
   *            the value
   * @return the index
   */
  public final int indexOf(Object value) {
    if (value != null) {
      for (int i = 0; i < size; i++) {
        if (value.equals(listTable[i].value)) {
          return i;
        }
      }
    } else {
      for (int i = 0; i < size; i++) {
        if (listTable[i].value == null) {
          return i;
        }
      }
    }
    return -1;
  }
  @Override
  public boolean containsKey(Object key) {
    Entry[] tbl = mapTable;
    if (key != null) {
      int hashCode = key.hashCode();
      int index = (hashCode & 0x7FFFFFFF) % tbl.length;
      for (Entry e = tbl[index]; e != null; e = e.next) {
        if (e.hashCode == hashCode && key.equals(e.key)) {
          return true;
        }
      }
    } else {
      for (Entry e = tbl[0]; e != null; e = e.next) {
        if (e.key == null) {
          return true;
        }
      }
    }
    return false;
  }
  @Override
  public V get(Object key) {
    Entry[] tbl = mapTable;
    if (key != null) {
      int hashCode = key.hashCode();
      int index = (hashCode & 0x7FFFFFFF) % tbl.length;
      for (Entry e = tbl[index]; e != null; e = e.next) {
        if (e.hashCode == hashCode && key.equals(e.key)) {
          return e.value;
        }
      }
    } else {
      for (Entry e = tbl[0]; e != null; e = e.next) {
        if (e.key == null) {
          return e.value;
        }
      }
    }
    return null;
  }
  /**
   * Returns the value for the index.
   * 
   * @param index
   *            the index
   * @return the value
   */
  public final V get(int index) {
    return getEntry(index).value;
  }
  /**
   * Returns the key for the index.
   * 
   * @param index
   *            the index
   * @return the key
   */
  public final K getKey(int index) {
    return getEntry(index).key;
  }
  /**
   * Returns the entry for the index.
   * 
   * @param index
   *            the index
   * @return the entry
   */
  public final Entry getEntry(int index) {
    if (index >= size) {
      throw new IndexOutOfBoundsException("Index:" + index + ", Size:"
          + size);
    }
    return listTable[index];
  }
  @Override
  public V put(K key, V value) {
    int hashCode = 0;
    int index = 0;
    if (key != null) {
      hashCode = key.hashCode();
      index = (hashCode & 0x7FFFFFFF) % mapTable.length;
      for (Entry e = mapTable[index]; e != null; e = e.next) {
        if ((e.hashCode == hashCode) && key.equals(e.key)) {
          return swapValue(e, value);
        }
      }
    } else {
      for (Entry e = mapTable[0]; e != null; e = e.next) {
        if (e.key == null) {
          return swapValue(e, value);
        }
      }
    }
    ensureCapacity();
    index = (hashCode & 0x7FFFFFFF) % mapTable.length;
    Entry e = new Entry(hashCode, key, value, mapTable[index]);
    mapTable[index] = e;
    listTable[size++] = e;
    return null;
  }
  /**
   * Sets the value for the index.
   * 
   * @param index
   *            the index
   * @param value
   *            the value
   */
  public final void set(int index, V value) {
    getEntry(index).setValue(value);
  }
  @Override
  public V remove(Object key) {
    Entry e = removeMap(key);
    if (e != null) {
      V value = e.value;
      removeList(indexOf(e));
      e.clear();
      return value;
    }
    return null;
  }
  /**
   * Removes the entry for the index.
   * 
   * @param index
   *            the index
   * @return the removed value
   */
  public final V remove(int index) {
    Entry e = removeList(index);
    V value = e.value;
    removeMap(e.key);
    e.value = null;
    return value;
  }
  @Override
  public void putAll(Map map) {
    for (Iterator> i = map
        .entrySet().iterator(); i.hasNext();) {
      Map.Entry e = i.next();
      put(e.getKey(), e.getValue());
    }
  }
  @Override
  public final void clear() {
    for (int i = 0; i < mapTable.length; i++) {
      mapTable[i] = null;
    }
    for (int i = 0; i < listTable.length; i++) {
      listTable[i] = null;
    }
    size = 0;
  }
  /**
   * Converts this object to an array.
   * 
   * @return an array
   */
  public final Object[] toArray() {
    Object[] array = new Object[size];
    for (int i = 0; i < array.length; i++) {
      array[i] = get(i);
    }
    return array;
  }
  /**
   * Converts this object to an array.
   * 
   * @param proto
   *            the prototype
   * @return an array
   */
  public final Object[] toArray(final Object proto[]) {
    Object[] array = proto;
    if (proto.length < size) {
      array = (Object[]) Array.newInstance(proto.getClass()
          .getComponentType(), size);
    }
    for (int i = 0; i < array.length; i++) {
      array[i] = get(i);
    }
    if (array.length > size) {
      array[size] = null;
    }
    return array;
  }
  @Override
  @SuppressWarnings("unchecked")
  public final boolean equals(Object o) {
    if (!getClass().isInstance(o)) {
      return false;
    }
    ArrayMap e = (ArrayMap) o;
    if (size != e.size) {
      return false;
    }
    for (int i = 0; i < size; i++) {
      if (!listTable[i].equals(e.listTable[i])) {
        return false;
      }
    }
    return true;
  }
  @Override
  public final Set> entrySet() {
    if (entrySet == null) {
      entrySet = new AbstractSet>() {
        @Override
        public Iterator> iterator() {
          return new ArrayMapIterator();
        }
        @Override
        @SuppressWarnings("unchecked")
        public boolean contains(Object o) {
          if (!(o instanceof Entry)) {
            return false;
          }
          Entry entry = (Entry) o;
          int index = (entry.hashCode & 0x7FFFFFFF) % mapTable.length;
          for (Entry e = mapTable[index]; e != null; e = e.next) {
            if (e.equals(entry)) {
              return true;
            }
          }
          return false;
        }
        @Override
        @SuppressWarnings("unchecked")
        public boolean remove(Object o) {
          if (!(o instanceof Entry)) {
            return false;
          }
          Entry entry = (Entry) o;
          return ArrayMap.this.remove(entry.key) != null;
        }
        @Override
        public int size() {
          return size;
        }
        @Override
        public void clear() {
          ArrayMap.this.clear();
        }
      };
    }
    return entrySet;
  }
  public final void writeExternal(final ObjectOutput out) throws IOException {
    out.writeInt(listTable.length);
    out.writeInt(size);
    for (int i = 0; i < size; i++) {
      out.writeObject(listTable[i].key);
      out.writeObject(listTable[i].value);
    }
  }
  @SuppressWarnings("unchecked")
  public final void readExternal(final ObjectInput in) throws IOException,
      ClassNotFoundException {
    int num = in.readInt();
    mapTable = createArray(num);
    listTable = createArray(num);
    threshold = (int) (num * LOAD_FACTOR);
    int size = in.readInt();
    for (int i = 0; i < size; i++) {
      K key = (K) in.readObject();
      V value = (V) in.readObject();
      put(key, value);
    }
  }
  @Override
  public Object clone() {
    ArrayMap copy = new ArrayMap();
    copy.threshold = threshold;
    copy.mapTable = mapTable;
    copy.listTable = listTable;
    copy.size = size;
    return copy;
  }
  private final int indexOf(final Entry entry) {
    for (int i = 0; i < size; i++) {
      if (listTable[i] == entry) {
        return i;
      }
    }
    return -1;
  }
  private final Entry removeMap(Object key) {
    int hashCode = 0;
    int index = 0;
    if (key != null) {
      hashCode = key.hashCode();
      index = (hashCode & 0x7FFFFFFF) % mapTable.length;
      for (Entry e = mapTable[index], prev = null; e != null; prev = e, e = e.next) {
        if ((e.hashCode == hashCode) && key.equals(e.key)) {
          if (prev != null) {
            prev.next = e.next;
          } else {
            mapTable[index] = e.next;
          }
          return e;
        }
      }
    } else {
      for (Entry e = mapTable[index], prev = null; e != null; prev = e, e = e.next) {
        if ((e.hashCode == hashCode) && e.key == null) {
          if (prev != null) {
            prev.next = e.next;
          } else {
            mapTable[index] = e.next;
          }
          return e;
        }
      }
    }
    return null;
  }
  private final Entry removeList(int index) {
    Entry e = listTable[index];
    int numMoved = size - index - 1;
    if (numMoved > 0) {
      System.arraycopy(listTable, index + 1, listTable, index, numMoved);
    }
    listTable[--size] = null;
    return e;
  }
  private final void ensureCapacity() {
    if (size >= threshold) {
      Entry[] oldTable = listTable;
      int newCapacity = oldTable.length * 2 + 1;
      Entry[] newMapTable = createArray(newCapacity);
      Entry[] newListTable = createArray(newCapacity);
      threshold = (int) (newCapacity * LOAD_FACTOR);
      System.arraycopy(oldTable, 0, newListTable, 0, size);
      for (int i = 0; i < size; i++) {
        Entry old = oldTable[i];
        int index = (old.hashCode & 0x7FFFFFFF) % newCapacity;
        Entry e = old;
        old = old.next;
        e.next = newMapTable[index];
        newMapTable[index] = e;
      }
      mapTable = newMapTable;
      listTable = newListTable;
    }
  }
  private final V swapValue(final Entry entry, final V value) {
    V old = entry.value;
    entry.value = value;
    return old;
  }
  @SuppressWarnings("unchecked")
  private Entry[] createArray(final int length) {
    return new Entry[length];
  }
  private class ArrayMapIterator implements Iterator> {
    private int current = 0;
    private int last = -1;
    public boolean hasNext() {
      return current != size;
    }
    public Map.Entry next() {
      try {
        Entry n = listTable[current];
        last = current++;
        return n;
      } catch (IndexOutOfBoundsException e) {
        throw new NoSuchElementException();
      }
    }
    public void remove() {
      if (last == -1) {
        throw new IllegalStateException();
      }
      ArrayMap.this.remove(last);
      if (last < current) {
        current--;
      }
      last = -1;
    }
  }
  private static class Entry implements Map.Entry, Externalizable {
    private static final long serialVersionUID = 1L;
    transient int hashCode;
    transient K key;
    transient V value;
    transient Entry next;
    /**
     * Constructor.
     * 
     * @param hashCode
     *            the hashCode
     * @param key
     *            the key
     * @param value
     *            the value
     * @param next
     *            the next
     */
    public Entry(final int hashCode, final K key, final V value,
        final Entry next) {
      this.hashCode = hashCode;
      this.key = key;
      this.value = value;
      this.next = next;
    }
    public K getKey() {
      return key;
    }
    public V getValue() {
      return value;
    }
    public V setValue(final V value) {
      V oldValue = value;
      this.value = value;
      return oldValue;
    }
    /**
     * Clears contents.
     */
    public void clear() {
      key = null;
      value = null;
      next = null;
    }
    @Override
    public boolean equals(final Object o) {
      if (this == o) {
        return true;
      }
      Entry e = (Entry) o;
      return (key != null ? key.equals(e.key) : e.key == null)
          && (value != null ? value.equals(e.value) : e.value == null);
    }
    @Override
    public int hashCode() {
      return hashCode;
    }
    @Override
    public String toString() {
      return key + "=" + value;
    }
    public void writeExternal(final ObjectOutput s) throws IOException {
      s.writeInt(hashCode);
      s.writeObject(key);
      s.writeObject(value);
      s.writeObject(next);
    }
    @SuppressWarnings("unchecked")
    public void readExternal(final ObjectInput s) throws IOException,
        ClassNotFoundException {
      hashCode = s.readInt();
      key = (K) s.readObject();
      value = (V) s.readObject();
      next = (Entry) s.readObject();
    }
  }
}