// -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;

  }

}