// -has fast nextElement() and prevElement()
// -design allows for more functions like reordering the list
// -Saves up to 34% in space over LinkedHashSet
//    (e.g. 22% for a set of 1,000 Ints)
sclass CompactLinkedHashSet<A> extends AbstractSet<A> {
  new UnsynchronizedCompactHashSet<Entry<A>> entries;
  Entry<A> head, tail;
  
  sclass Entry<A> {
    A value;
    Entry<A> prev, next;
    
    public int hashCode() {
      ret _hashCode(value);
    }
    
    // "magic" equals function for CompactHashSet lookup without temp object
    public bool equals(O o) {
      ret o == this || eq(value, o);
    }
  }
  
  public bool add(A a) {
    if (entries.contains(a)) false;
    new Entry<A> n;
    n.value = a;
    n.prev = tail;
    if (tail != null) tail.next = n;
    tail = n;
    if (head == null) head = n;
    entries.add(n);
    true;
  }
  
  public bool remove(O a) {
    ret remove(entries.find(a));
  }
  
  public bool remove(Entry<A> node) {
    if (node == null) false;
    if (node.next != null) node.next.prev = node.prev; else tail = node.prev;
    if (node.prev != null) node.prev.next = node.next; else head = node.next;
    entries.remove(node);
    true;
  }
  
  public int size() { ret entries.size(); }
  
  public ItIt<A> iterator() {
    ret new ItIt<A> {
      Entry<A> entry = head, prev = null;
      public bool hasNext() { ret entry != null; }
      public A next() {
        A a = entry.value;
        prev = entry;
        entry = entry.next;
        ret a;
      }
      
      // untested
      public void remove() {
        if (prev == null) throw new IllegalStateException;
        CompactLinkedHashSet.this.remove(prev);
        prev = null;
      }
    };
  }
  
  public void clear() {
    entries.clear();
    head = tail = null;
  }
  
  public bool contains(O a) {
    ret entries.contains(a);
  }
  
  public A find(O o) {
    Entry<A> e = entries.find(o);
    ret e?.value;
  }
  
  public A prevElement(A a) {
    Entry<A> e = entries.find(a);
    if (e == null || e.prev == null) null;
    ret e.prev.value;
  }
  
  public A nextElement(A a) {
    Entry<A> e = entries.find(a);
    if (e == null || e.next == null) null;
    ret e.next.value;
  }
  
  public A first() { ret head?.value; }
  public A last() { ret tail?.value; }
  
  bool removeIfSame(O o) {
    A value = find(o);
    if (value == o) {
      remove(value);
      true;
    }
    false;
  }
}