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);

  }

}