// -has fast nextElement() and prevElement()
// -design allows for more functions like reordering the list
// -is NOT more compact than LinkedHashSet (probably the opposite)
//  (check out CompactLinkedHashSet for that)
sclass BetterLinkedHashSet<A> extends AbstractSet<A> {
  Map<A, Entry<A>> entries = hashMap();
  Entry<A> head, tail;
  
  sclass Entry<A> {
    A value;
    Entry<A> prev, next;
  }
  
  public bool add(A a) {
    if (entries.containsKey(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.put(a, n);
    true;
  }
  
  public bool remove(O a) {
    ret remove(entries.get(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.value);
    true;
  }
  
  public int size() { ret entries.size(); }
  
  public ItIt<A> iterator() {
    ret new ItIt<A> {
      Entry<A> entry = head;
      public bool hasNext() { ret entry != null; }
      public A next() {
        A a = entry.value;
        entry = entry.next;
        ret a;
      }
    };
  }
  
  public bool contains(O a) {
    ret entries.containsKey(a);
  }
  
  public A prevElement(A a) {
    Entry<A> e = entries.get(a);
    if (e == null || e.prev == null) null;
    ret e.prev.value;
  }
  
  public A nextElement(A a) {
    Entry<A> e = entries.get(a);
    if (e == null || e.next == null) null;
    ret e.next.value;
  }
}