@VisibleForTesting
  static SortedMap<OffsetRange, Integer> computeOverlappingRanges(Iterable<OffsetRange> ranges) {
    ImmutableSortedMap.Builder<OffsetRange, Integer> rval =
        ImmutableSortedMap.orderedBy(OffsetRangeComparator.INSTANCE);
    List<OffsetRange> sortedRanges = Lists.newArrayList(ranges);
    if (sortedRanges.isEmpty()) {
      return rval.build();
    }
    Collections.sort(sortedRanges, OffsetRangeComparator.INSTANCE);

    // Stores ranges in smallest 'from' and then smallest 'to' order
    // e.g. [2, 7), [3, 4), [3, 5), [3, 5), [3, 6), [4, 0)
    PriorityQueue<OffsetRange> rangesWithSameFrom =
        new PriorityQueue<>(OffsetRangeComparator.INSTANCE);
    Iterator<OffsetRange> iterator = sortedRanges.iterator();

    // Stored in reverse sorted order so that when we iterate and re-add them back to
    // overlappingRanges they are stored in sorted order from smallest to largest range.to
    List<OffsetRange> rangesToProcess = new ArrayList<>();
    while (iterator.hasNext()) {
      OffsetRange current = iterator.next();
      // Skip empty ranges
      if (current.getFrom() == current.getTo()) {
        continue;
      }

      // If the current range has a different 'from' then a prior range then we must produce
      // ranges in [rangesWithSameFrom.from, current.from)
      while (!rangesWithSameFrom.isEmpty()
          && rangesWithSameFrom.peek().getFrom() != current.getFrom()) {
        rangesToProcess.addAll(rangesWithSameFrom);
        Collections.sort(rangesToProcess, OffsetRangeComparator.INSTANCE);
        rangesWithSameFrom.clear();

        int i = 0;
        long lastTo = rangesToProcess.get(i).getFrom();
        // Output all the ranges that are strictly less then current.from
        // e.g. current.to := 7 for [3, 4), [3, 5), [3, 5), [3, 6) will produce
        // [3, 4) := 4
        // [4, 5) := 3
        // [5, 6) := 1
        for (; i < rangesToProcess.size(); ++i) {
          if (rangesToProcess.get(i).getTo() > current.getFrom()) {
            break;
          }
          // Output only the first of any subsequent duplicate ranges
          if (i == 0 || rangesToProcess.get(i - 1).getTo() != rangesToProcess.get(i).getTo()) {
            rval.put(
                new OffsetRange(lastTo, rangesToProcess.get(i).getTo()),
                rangesToProcess.size() - i);
            lastTo = rangesToProcess.get(i).getTo();
          }
        }

        // We exitted the loop with 'to' > current.from, we must add the range [lastTo,
        // current.from) if it is non-empty
        if (lastTo < current.getFrom() && i != rangesToProcess.size()) {
          rval.put(new OffsetRange(lastTo, current.getFrom()), rangesToProcess.size() - i);
        }

        // The remaining ranges have a 'to' that is greater then 'current.from' and will overlap
        // with current so add them back to rangesWithSameFrom with the updated 'from'
        for (; i < rangesToProcess.size(); ++i) {
          rangesWithSameFrom.add(
              new OffsetRange(current.getFrom(), rangesToProcess.get(i).getTo()));
        }

        rangesToProcess.clear();
      }
      rangesWithSameFrom.add(current);
    }

    // Process the last chunk of overlapping ranges
    while (!rangesWithSameFrom.isEmpty()) {
      // This range always represents the range with with the smallest 'to'
      OffsetRange current = rangesWithSameFrom.remove();

      rangesToProcess.addAll(rangesWithSameFrom);
      Collections.sort(rangesToProcess, OffsetRangeComparator.INSTANCE);
      rangesWithSameFrom.clear();

      rval.put(current, rangesToProcess.size() + 1 /* include current */);

      // Shorten all the remaining ranges such that they start with current.to
      for (OffsetRange rangeWithDifferentFrom : rangesToProcess) {
        // Skip any duplicates of current
        if (rangeWithDifferentFrom.getTo() > current.getTo()) {
          rangesWithSameFrom.add(new OffsetRange(current.getTo(), rangeWithDifferentFrom.getTo()));
        }
      }
      rangesToProcess.clear();
    }
    return rval.build();
  }
@Test
  public void testRandomRanges() {
    Random random =
        new Random(123892154890L); // use an arbitrary seed to make this test deterministic
    for (int i = 0; i < 1000; ++i) {
      List<OffsetRange> ranges = new ArrayList<>();
      for (int j = 0; j < 20; ++j) {
        long start = random.nextInt(10);
        ranges.add(range(start, start + random.nextInt(10) + 1));
        Map<OffsetRange, Integer> nonOverlappingRangesToNumElementsPerPosition =
            computeOverlappingRanges(ranges);
        assertNonEmptyRangesAndPositions(ranges, nonOverlappingRangesToNumElementsPerPosition);
      }
    }
  }