sclass FreeList {
  MultiSetMap<Int, IntRange> byLength = multiSetMap_innerCustomCompactTreeSet_outerTreeMap(intRangeComparator());
  CompactTreeSet<IntRange> inOrder = new(intRangeComparator());
  int totalFree;
  bool changed;
  
  void add(IntRange r) {
    if (empty(r)) ret;
    // only special case here is merging with previous and/or following entry
    IntRange before = inOrder.floor(r), after = inOrder.ceiling(r);
    deb()?.printVars("FreeList add", +r, +before, +after);
    
    if (before != null && before.end >= r.start) {
      if (before.end > r.start)
        failWithVars("You are adding free ranges twice!!", +before, +r);
      r = IntRange(before.start, r.end);
      deb()?.printVars("FreeList merge", +r, +before);
      remove(before);
    }
    if (after != null && after.start <= r.end) {
      if (after.start < r.end)
        failWithVars("You are adding free ranges twice!!", +r, +after);
      r = IntRange(r.start, after.end);
      deb()?.printVars("FreeList merge", +r, +after);
      remove(after);
    }
      
    internalAdd(r);
    deb()?.print("FreeList add done", asList());
  }
  
  /*bool canAdd(IntRange r) { // what?
    IntRange before = inOrder.floor(r), after = inOrder.ceil(r);
    ret (before == null || before.end <= r.start)
      && (after == null || after.start >= r.end);
  }*/
  
  bool canRemove(IntRange r) {
    IntRange r2 = inOrder.floor(r);
    ret r2 != null && r2.end >= r.end;
  }
  
  void internalAdd(IntRange r) {
    if (r.isEmpty()) ret;
    inOrder.add(r);
    byLength.add(r.length(), r);
    totalFree += r.length();
    set changed;
  }
  
  void remove(IntRange r) {
    if (empty(r)) ret;
    IntRange r2 = inOrder.floor(r);
    if (r2 == null) fail("User error");
    if (eq(r, r2)) {
      deb()?.printVars("FreeList easy remove", r2);
      inOrder.remove(r2);
      byLength.remove(r2.length(), r2);
      totalFree -= r2.length();
      set changed;
      ret;
    }
    
    // remove full range, add back left and right remainders
    deb()?.printVars("FreeList remove", +r, +r2);
    remove(r2);
    add(IntRange(r2.start, r.start));
    add(IntRange(r.end, r2.end));
    deb()?.print("FreeList remove done", asList());
  }
  
  IntRange findFreeSpace(int minSize) {
    Map.Entry<Int, Set<IntRange>> e = ((NavigableMap) byLength.data).ceilingEntry(minSize);
    deb()?.printVars("FreeList findFreeSpace", +minSize, e := mapEntryToPair(e));
    ret e == null ? null : first(e.getValue());
  }
  
  int totalFree() { ret totalFree; }
  
  void clear {
    byLength.clear();
    inOrder.clear();
    totalFree = 0;
    changed = false;
  }
  
  IntRange highestFreeRange() { ret last(inOrder); }
  
  L<IntRange> asList() { ret cloneList(inOrder); }
  
  static FreeList fromSortedList(L<IntRange> l) {
    new FreeList fl;
    fOr (IntRange r : l)
      fl.internalAdd(r);
    ret fl;
  }
  
  int[] toIntArray() {
    ret intRangesToIntArray_startAndLength(inOrder);
  }
  
  static FreeList fromIntArray(int[] a) {
    ret fromSortedList(intArrayToIntRanges_startAndLength(a));
  }
  
  int size() { ret l(inOrder); }
  
  L<IntPair> lengthStats() { ret map toIntPair(multiSetMapToMultiSetPairs(byLength)); }
  
  void sanityTest {
    assertEquals((long) totalFree, totalIntRangesLength(inOrder));
    int longestFree = intMax(intRangeLengths(inOrder));
    if (longestFree > 0)
      if (findFreeSpace(longestFree) == null)
        fail("Can't find space of size " + longestFree);
  }
}