// 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>> 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<CompactLinkedHashSet<A>> *internal) {}
  
  /*swappable*/ CompactLinkedHashSet<A> makeInternalSet() {
    ret new CompactLinkedHashSet;
  }
  
  public bool add(A a) {
    CompactLinkedHashSet<A> newSet = addAndReturnCollection(makeInternalSet(), a);
    CompactLinkedHashSet<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) {
    CompactLinkedHashSet<A> newSet = addAndReturnCollection(makeInternalSet(), (A) a);
    CompactLinkedHashSet<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() {
    var last = internal.last();
    ret last?.last();
  }
  
  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;
  }
}