package org.apache.commons.collections;

import java.util.Collection;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Set;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

/**
 *  Implements a map of objects that is ordered based on the order in which the
 *  mappings are created.  This data structure has fast <I>O(1)</I> search
 *  time, deletion time, and insertion time.  This is accomplished using a
 *  combination of a hashtable and linked list.
 *
 *  @author Michael A. Smith 
 *   [<a href="mailto:michael@iammichael.org">michael@iammichael.org</A>]
 **/
public class OrderedHashMap extends AbstractMap {

  private static class Entry implements Map.Entry {
    private final Object key_;
    private Object value_;
    
    Entry next = null;
    Entry prev = null;

    public Entry(Object key, Object value) {
      this.key_ = key;
      this.value_ = value;
    }

    public Object getKey() { 
      return this.key_; 
    }

    public Object getValue() { 
      return this.value_; 
    }

    public Object setValue(Object value) { 
      Object oldValue = this.value_;
      this.value_ = value; 
      return oldValue;
    }

    public int hashCode() { 
      // per Map.Entry.hashCode() api docs
      return ((getKey() == null ? 0 : getKey().hashCode()) ^
              (getValue()==null ? 0 : getValue().hashCode())); 
    }

    public boolean equals(Object obj) {
      if(obj == null) return false;
      if(obj == this) return true;
      Map.Entry other = (Map.Entry)obj;

      // per Map.Entry.equals(Object api docs)
      return((getKey() == null ?
              other.getKey() == null : getKey().equals(other.getKey()))  &&
             (getValue() == null ?
              other.getValue() == null : getValue().equals(other.getValue())));
    }
    public String toString() {
      return "[" + getKey() + "=" + getValue() + "]";
    }
  }

  private final Entry sentinel = new Entry(null, null);

  private final HashMap entries = new HashMap();

  public OrderedHashMap() {
    sentinel.prev = sentinel;
    sentinel.next = sentinel;
  }

  public OrderedHashMap(Map m) {
    this();
    putAll(m);
  }

  /**
   *  Removes an internal entry from the linked list.  This does not remove it
   *  from the underlying map.
   **/
  private void removeEntry(Entry entry) {
    entry.next.prev = entry.prev;
    entry.prev.next = entry.next;    
  }

  /**
   *  Inserts a new internal entry to the linked list.  This does not add the
   *  entry to the underlying map.
   **/
  private void insertEntry(Entry entry) {
    entry.next = sentinel.next;
    entry.prev = sentinel;
    sentinel.next.prev = entry;
    sentinel.next = entry;
  }

  public int size() {
    return entries.size();
  }

  public boolean isEmpty() {
    return entries.isEmpty();
  }

  public boolean containsKey(Object key) {
    return entries.containsKey(key);
  }

  public boolean containsValue(Object value) {
    return entries.containsValue(value);
  }

  public Object get(Object o) {
    // find entry for the specified key
    Entry entry = (Entry)entries.get(o);
    if(entry == null) return null;
      
    return entry.getValue();
  }

  public Object put(Object key, Object value) {

    Object oldValue = null;

    Entry e = (Entry)entries.get(key);
    if(e != null) {
      // remove from list so the entry gets "moved" to the front of list
      removeEntry(e);

      // update value in map
      oldValue = e.setValue(value);
    } else {
      // add new entry
      e = new Entry(key, value);
      entries.put(key, e);
    }
    // entry in map, but not list

    // add to list
    insertEntry(e);

    return oldValue;
  }

  public Object remove(Object key) {
    Entry e = (Entry)entries.remove(key);
    if(e == null) return null;
    removeEntry(e);
    return e.getValue();
  }

  // use abstract map impl
  //void putAll(Map t)

  public void clear() {
    entries.clear();
    sentinel.next = sentinel;
    sentinel.prev = sentinel;
  }

  public Set keySet() {
    return new AbstractSet() {

      // required impl
      public Iterator iterator() { return new OrderedIterator(KEY); }
      public boolean remove(Object o) {
        return OrderedHashMap.this.remove(o) != null;
      }

      // more efficient impls than abstract set
      public void clear() { OrderedHashMap.this.clear(); }
      public int size() { return OrderedHashMap.this.size(); }
      public boolean isEmpty() { return OrderedHashMap.this.isEmpty(); }

      public boolean contains(Object o) { 
        return OrderedHashMap.this.containsKey(o);
      }

    };
  }

  public Collection values() {
    return new AbstractCollection() {
      // required impl
      public Iterator iterator() { return new OrderedIterator(VALUE); }
      public boolean remove(Object o) {
        for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
          if((pos.getValue() == null && o == null) ||
             (pos.getValue() != null && pos.getValue().equals(o))) {
            OrderedHashMap.this.remove(pos.getKey());
            return true;
          }
        }
        return false;
      }

      // more efficient impls than abstract collection
      public void clear() { OrderedHashMap.this.clear(); }
      public int size() { return OrderedHashMap.this.size(); }
      public boolean isEmpty() { return OrderedHashMap.this.isEmpty(); }

      public boolean contains(Object o) {
        return OrderedHashMap.this.containsValue(o);
      }
    };
  }

  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.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 OrderedHashMap.this.remove(e.getKey()) != null;
      }        

      // more efficient impls than abstract collection
      public void clear() { OrderedHashMap.this.clear(); }
      public int size() { return OrderedHashMap.this.size(); }
      public boolean isEmpty() { return OrderedHashMap.this.isEmpty(); }

      public boolean contains(Object o) {
        return findEntry(o) != null;
      }
    };
  }

  private static final int KEY = 0;
  private static final int VALUE = 1;
  private static final int ENTRY = 2;

  private class OrderedIterator implements Iterator {

    private int returnType;
    private Entry pos = sentinel;
    boolean removable = false;
        
    public OrderedIterator(int returnType) {
      this.returnType = returnType;
    }

    public boolean hasNext() {
      return pos.next != sentinel;
    }

    public Object next() {
      if(pos.next == sentinel) {
        throw new NoSuchElementException();
      }
      pos = pos.next;
      removable = true;
      switch(returnType) {
      case KEY:
        return pos.getKey();
      case VALUE:
        return pos.getValue();
      case ENTRY:
        return pos;
      default:
        throw new Error("bad iterator type");
      }

    }
    
    public void remove() {
      if(!removable) {
        throw new IllegalStateException("remove() must follow next()");
      }
      
      OrderedHashMap.this.remove(pos.getKey());
    }
  }

}