package edu.stanford.nlp.util;import java.util.*;/** ArrayMap: A map that is backed by an Array *  @author Dan Klein */public final class ArrayMap extends AbstractMap {  Entry[] entryArray;  int capacity;  int size;    final class Entry implements Map.Entry {    Object key;    Object value;    public Object getKey() { return key; }    public Object getValue() { return value; }    public Object setValue(Object o) {      Object old = value;      value = o;      return old;    }    public int hashCode() {     return (getKey()==null ? 0 : getKey().hashCode()) ^       (getValue()==null ? 0 : getValue().hashCode());    }    public boolean equals(Object o) {      Entry e = (Entry)o;      return	(getKey()==null ? e.getKey()==null : getKey().equals(e.getKey()))  &&	(getValue()==null ? e.getValue()==null : getValue().equals(e.getValue()));    }     Entry(Object key, Object value) {      this.key = key;      this.value = value;    }  }  ArrayMap() {    size = 0;    capacity = 2;    entryArray = new Entry[2];  }  ArrayMap(int capacity) {    size = 0;    this.capacity = capacity;    entryArray = new Entry[2];  }  public Set entrySet() {    //throw new java.lang.UnsupportedOperationException();    return new HashSet(Arrays.asList(entryArray));  }  public int size() { return size; }  public boolean isEmpty() { return size > 0; }  private void resize() {    Object[] oldEntryArray = entryArray;    int newSize = size+1;    entryArray = new Entry[newSize];    System.arraycopy(oldEntryArray, 0, entryArray, 0, size);    size = newSize;  }  public Object put(Object key, Object val) {    for(int i=0; i<size; i++) {      if (key.equals(entryArray[i].getKey()))	return entryArray[i].setValue(val);    }    if (capacity <= size)      resize();    entryArray[size] = new Entry(key, val);    return null;  }  public Object get(Object key) {    for(int i=0; i<size; i++) {      if(key==null? entryArray[i].getKey()==null:key.equals(entryArray[i].getKey()))	return entryArray[i].getValue();    }    return null;  }  public Object remove(Object key) {    for(int i=0; i<size; i++) {      if(key==null? entryArray[i].getKey()==null:key.equals(entryArray[i].getKey())) {	Object value = entryArray[i].getValue();	if (size > 1)	  entryArray[i] = entryArray[size-1];	size--;	return value;      }    }    return null;  }  protected int hashCodeCache = 0;  public int hashCode() {    if (hashCodeCache == 0) {      int hashCode = 0;      for(int i=0; i<size; i++) {	hashCode += entryArray[i].hashCode();      }      hashCodeCache = hashCode;    }    return hashCodeCache;  }  public boolean equals(Object o) {    Map m = (Map)o;    for(int i=0; i<size; i++) {      Object mVal = m.get(entryArray[i].getKey());      if (mVal == null) {	if (entryArray[i] != null)	  return false;	else	  continue;      }      if(!m.get(entryArray[i].getKey()).equals(entryArray[i].getValue()))	return false;    }    return true;  }}