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