// 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<CompactLinkedHashSet<A>> sets;

  Comparator<A> comparator;

  int size;

  *() { this((Comparator<A>) null); }

  *(Comparator<A> *comparator) {

    sets = new TreeSet<CompactLinkedHashSet<A>>(

      comparator == null

        ? (setA, setB) -> cmp(main first(setA), main first(setB))

        : (setA, setB) -> comparator.compare(main first(setA), main first(setB))

    );

  }

  protected *(NavigableSet<CompactLinkedHashSet<A>> *sets) {}

  /*swappable*/ CompactLinkedHashSet<A> makeInnerSet() {

    ret new CompactLinkedHashSet;

  }

  public bool add(A a) {

    var probe = probe(a);

    CompactLinkedHashSet<A> found = navigableSet_find(sets, probe);

    if (found != null) {

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

    } else

      sets.add(probe);

    ++size;

    true;

  }

  public bool remove(O a) {

    CompactLinkedHashSet<A> newSet = makeInnerSet();

    newSet.add((A) a);

    CompactLinkedHashSet<A> found = navigableSet_find(sets, newSet);

    if (found == null) false;

    if (l(found) == 1)

      sets.remove(found);

    else

      found.remove(a);

    --size;

    true;

  }

  A first() {

    ret main first(main first(sets));

  }

  A last() {

    var last = sets.last();

    ret last?.last();

  }

  public ItIt<A> iterator() {

    ret nestedIterator(sets, methodLambda0 iterator);

  }

  public int size() { ret size; }

  // may return null

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

  CompactLinkedHashSet<A> probe(O a) {

    ret addAndReturnCollection(makeInnerSet(), (A) a);

  }

  public bool contains(O a) {

    ret navigableSet_find(sets, probe(a)) != null;

  }

}