// TreeSet variant allowing multiple elements which are considered

// equal by the comparator but not by eq().

// All operations O(log n) with n being the number of _different_ elements.

sclass TreeSetWithDuplicates<A> extends AbstractSet<A> {

  NavigableSet<Set<A>> internal;

  Comparator<A> comparator;

  int size;

  *() { internal = new TreeSet; }

  *(Comparator<A> *comparator) {

    internal = new TreeSet<Set<A>>((setA, setB) -> {

      ret comparator.compare(main first(setA), main first(setB));

    });

  }

  protected *(NavigableSet<Set<A>> *internal) {}

  // Now using CompactLinkedHashSet

  swappable Set<A> makeInternalSet() { ret new CompactLinkedHashSet; }

  public bool add(A a) {

    Set<A> newSet = addAndReturnCollection(makeInternalSet(), a);

    Set<A> found = navigableSet_find(internal, newSet);

    if (found != null) {

      if (!found.add(a)) false;

    } else

      internal.add(newSet);

    ++size;

    true;

  }

  public bool remove(O a) {

    Set<A> newSet = addAndReturnCollection(makeInternalSet(), (A) a);

    Set<A> found = navigableSet_find(internal, newSet);

    if (found == null) false;

    if (l(found) == 1)

      internal.remove(found);

    else

      found.remove(a);

    --size;

    true;

  }

  A first() {

    ret main first(main first(internal));

  }

  A last() {

    ret main last(main last(internal));

  }

  public ItIt<A> iterator() {

    ret nestedIterator(internal, methodLambda0 iterator);

  }

  public int size() { ret size; }

  // may return null

  Set<A> tiedForFirst() { ret main first(internal); }

  public bool contains(O a) {

    Set<A> newSet = addAndReturnCollection(makeInternalSet(), (A) a);

    ret navigableSet_find(internal, newSet) != null;

  }

}