Java 类com.google.common.collect.RangeSet 实例源码

private QuoteFilter(Map<Symbol, ImmutableRangeSet<Integer>> docIdToBannedRegions) {
  this.docIdToBannedRegions = ImmutableMap.copyOf(docIdToBannedRegions);
  for (RangeSet<Integer> rs : docIdToBannedRegions.values()) {
    for (final Range<Integer> r : rs.asRanges()) {
      checkArgument(r.hasLowerBound());
      checkArgument(r.hasUpperBound());
      checkArgument(r.lowerEndpoint() >= 0);
    }
  }
  // these ensure we can serialize safely
  for (Symbol sym : docIdToBannedRegions.keySet()) {
    final String s = sym.toString();
    checkArgument(!s.isEmpty(), "Document IDs may not be empty");
    checkArgument(!CharMatcher.WHITESPACE.matchesAnyOf(s),
        "Document IDs may not contain whitespace: %s", s);
  }
}

/**
 * Converts zero-indexed, [closed, open) line ranges in the given source file to character ranges.
 */
public static RangeSet<Integer> lineRangesToCharRanges(
        String input, RangeSet<Integer> lineRanges) {
    List<Integer> lines = new ArrayList<>();
    Iterators.addAll(lines, Newlines.lineOffsetIterator(input));
    lines.add(input.length() + 1);

    final RangeSet<Integer> characterRanges = TreeRangeSet.create();
    for (Range<Integer> lineRange :
            lineRanges.subRangeSet(Range.closedOpen(0, lines.size() - 1)).asRanges()) {
        int lineStart = lines.get(lineRange.lowerEndpoint());
        // Exclude the trailing newline. This isn't strictly necessary, but handling blank lines
        // as empty ranges is convenient.
        int lineEnd = lines.get(lineRange.upperEndpoint()) - 1;
        Range<Integer> range = Range.closedOpen(lineStart, lineEnd);
        characterRanges.add(range);
    }
    return characterRanges;
}

/**
 * Emit a list of {@link Replacement}s to convert from input to output.
 *
 * @param input           the input compilation unit
 * @param characterRanges the character ranges to reformat
 * @return a list of {@link Replacement}s, sorted from low index to high index, without overlaps
 * @throws FormatterException if the input string cannot be parsed
 */
public ImmutableList<Replacement> getFormatReplacements(
        String input, Collection<Range<Integer>> characterRanges) throws FormatterException {
    JavaInput javaInput = new JavaInput(input);

    // TODO(cushon): this is only safe because the modifier ordering doesn't affect whitespace,
    // and doesn't change the replacements that are output. This is not true in general for
    // 'de-linting' changes (e.g. import ordering).
    javaInput = ModifierOrderer.reorderModifiers(javaInput, characterRanges);

    String lineSeparator = Newlines.guessLineSeparator(input);
    JavaOutput javaOutput =
            new JavaOutput(lineSeparator, javaInput, new JavaCommentsHelper(lineSeparator, options));
    try {
        format(javaInput, javaOutput, options);
    } catch (FormattingError e) {
        throw new FormatterException(e.diagnostics());
    }
    RangeSet<Integer> tokenRangeSet = javaInput.characterRangesToTokenRanges(characterRanges);
    return javaOutput.getFormatReplacements(tokenRangeSet);
}

private static FrontendClientMetadata createFrontedClientMetadata(final long num) {
    final String index = String.valueOf(num);
    final String indexName = "test_" + index;
    final FrontendIdentifier frontendIdentifier = FrontendIdentifier.create(MemberName.forName(indexName),
            FrontendType.forName(index));
    final ClientIdentifier clientIdentifier = ClientIdentifier.create(frontendIdentifier, num);

    final RangeSet<UnsignedLong> purgedHistories = TreeRangeSet.create();
    purgedHistories.add(Range.closed(UnsignedLong.ZERO, UnsignedLong.ONE));

    final Collection<FrontendHistoryMetadata> currentHistories = Collections.singleton(
        new FrontendHistoryMetadata(num, num, true, ImmutableMap.of(UnsignedLong.ZERO, Boolean.TRUE),
            purgedHistories));

    return new FrontendClientMetadata(clientIdentifier, purgedHistories, currentHistories);
}

private CrontabEntry(
    RangeSet<Integer> minute,
    RangeSet<Integer> hour,
    RangeSet<Integer> dayOfMonth,
    RangeSet<Integer> month,
    RangeSet<Integer> dayOfWeek) {

  checkEnclosed("minute", MINUTE, minute);
  checkEnclosed("hour", HOUR, hour);
  checkEnclosed("dayOfMonth", DAY_OF_MONTH, dayOfMonth);
  checkEnclosed("month", MONTH, month);
  checkEnclosed("dayOfWeek", DAY_OF_WEEK, dayOfWeek);

  this.minute = ImmutableRangeSet.copyOf(minute);
  this.hour = ImmutableRangeSet.copyOf(hour);
  this.dayOfMonth = ImmutableRangeSet.copyOf(dayOfMonth);
  this.month = ImmutableRangeSet.copyOf(month);
  this.dayOfWeek = ImmutableRangeSet.copyOf(dayOfWeek);

  checkArgument(hasWildcardDayOfMonth() || hasWildcardDayOfWeek(),
      "Specifying both dayOfWeek and dayOfMonth is not supported.");
}

private static Predicate<IAssignedTask> buildNonUpdatingTasksFilter(
    final Map<IJobKey, IJobUpdateInstructions> roleJobUpdates) {

  return task -> {
    Optional<IJobUpdateInstructions> update = Optional.fromNullable(
        roleJobUpdates.get(task.getTask().getJob()));

    if (update.isPresent()) {
      IJobUpdateInstructions instructions = update.get();
      RangeSet<Integer> initialInstances = getInstanceIds(instructions.getInitialState());
      RangeSet<Integer> desiredInstances = getInstanceIds(instructions.isSetDesiredState()
          ? ImmutableSet.of(instructions.getDesiredState())
          : ImmutableSet.of());

      int instanceId = task.getInstanceId();
      return !initialInstances.contains(instanceId) && !desiredInstances.contains(instanceId);
    }
    return true;
  };
}

@Override
public void process(JCas jcas) throws AnalysisEngineProcessException {
  Collection<Concept> concepts = TypeUtil.getConcepts(jcas);
  List<QueryConcept> qconcepts = ConceptAbstractQueryGenerator
          .createQueryConceptsFromConceptMentions(jcas, concepts, useType, useWeight);
  // filter tokens that are covered by concept mentions
  RangeSet<Integer> cmentionRanges = TreeRangeSet.create();
  concepts.stream().map(TypeUtil::getConceptMentions).flatMap(Collection::stream)
          .map(cmention -> Range.closedOpen(cmention.getBegin(), cmention.getEnd()))
          .forEach(cmentionRanges::add);
  // create an aquery using all tokens with POS in posTags set
  List<Token> tokens = TypeUtil.getOrderedTokens(jcas).stream().filter(token -> !cmentionRanges
          .encloses(Range.closedOpen(token.getBegin(), token.getEnd()))).collect(toList());
  List<QueryConcept> qconceptTokens = TokenSelectionAbstractQueryGenerator
          .createQueryConceptsFromTokens(jcas, tokens, posTags, stoplist);
  qconceptTokens.addAll(qconcepts);
  AbstractQuery aquery = TypeFactory.createAbstractQuery(jcas, qconceptTokens);
  aquery.addToIndexes();
  // create a backup aquery using only nouns
  List<QueryConcept> qconceptNouns = TokenSelectionAbstractQueryGenerator
          .createQueryConceptsFromTokens(jcas, tokens, nounTags, stoplist);
  qconceptNouns.addAll(qconcepts);
  AbstractQuery aqueryNoun = TypeFactory.createAbstractQuery(jcas, qconceptNouns);
  aqueryNoun.addToIndexes();
}

private void addCmsRanges(RangeSet<Long> ranges, ConcurrentMarkSweepGeneration generation) {
  CompactibleFreeListSpace space = generation._cmsSpace();

  FreeChunk freeChunk = hotspot.getStructs().staticStruct(FreeChunk.class);
  oopDesc oop = hotspot.getStructs().staticStruct(oopDesc.class);
  Klass klass = hotspot.getStructs().staticStruct(Klass.class);

  long minChunkSize = hotspot.alignUp(hotspot.getTypes().getType("FreeChunk").getSize(),
      hotspot.getMinObjAlignmentInBytes());

  ranges.add(Range.closedOpen(space._bottom(), space._end()));
  for (long cur = space._bottom(); cur < space._end();) {
    freeChunk.setAddress(cur);
    if (freeChunk.isFreeChunk(hotspot)) {
      ranges.remove(Range.closedOpen(cur, cur + freeChunk.size(hotspot)));
      cur += freeChunk.size(hotspot);
    } else {
      oop.setAddress(cur);
      oop.getKlass(hotspot, klass);
      cur += Math.max(oop.getObjectSize(hotspot, klass), minChunkSize);
    }
  }
}

/**
 * 1. Build a map of requests identified by ip-date-time(minutes accuracy) this will give us rate / min by ip.
 * 2. Create a range set for ips we do not want to auto block that we can query.
 * 3. Collect the do not auto block range set, the ranges of ips for the manual block list.
 * 4. Get the current violators from the request map that have requests grouped by ip and minutes
 * 5. Filter and Truncate to remove expired IP address and IPs that are on the White or Black manual lists
 *      and ensure that we are under the ip limit for an IP Set
 * 6. Save the violators data.
 * 7. Update the auto block ip set to reflect the current violators data.
 *
 * @param events The Cloud Front log events
 * @param config The Cloud Formation outputs from when this Lambda was created
 * @param bucketName The Bucket that we are operating from
 */
@Override
public void processLogEvents(List<CloudFrontLogEvent> events, CloudFrontLogHandlerConfig config, String bucketName) {

    Map<String, Integer> reqIdCountMap = new HashMap<>();

    // Build a map of requests identified by ip-date-time(minutes accuracy) this will give us rate / min by ip
    events.forEach(cloudFrontLogEvent -> processRequest(cloudFrontLogEvent, reqIdCountMap));
    // Collect the do not auto block range set, the ranges of ips for the manual block and white list.
    RangeSet<Integer> doNotAutoBlockIpRangeSet = getDoNotBlockRangeSet(config);
    // Get the current violators
    Map<String, ViolationMetaData> violators = getCurrentViolators(reqIdCountMap, config);
    // Get and merge in all the currently blocked violators
    violators.putAll(getCurrentlyBlockedIpsAndDateViolatedMap(bucketName));
    // Filter and truncate to remove expired blocks and ensure that we are under the ip limit for an IP Set
    violators = filterAndTruncateViolators(config, doNotAutoBlockIpRangeSet, violators);
    // Save the violators data.
    saveCurrentViolators(violators, bucketName);
    // Update the auto block ip set to reflect the current violators data.
    Map<String, List<String>> summery = processViolators(config, violators);
    // log summery
    logSummery(summery, config);

}

@Test
public void testThatFilterAndTruncateViolatorsFiltersIPsInDoNotBlockRangeSet() {
    config.setRateLimitViolationBlacklistPeriodInMinutes(1);
    RangeSet<Integer> doNotAutoBlockIpRangeSet = TreeRangeSet.create();

    SubnetUtils subnetUtils = new SubnetUtils("50.39.100.193/32");
    subnetUtils.setInclusiveHostCount(true);
    SubnetUtils.SubnetInfo subnetInfo = subnetUtils.getInfo();
    Integer lowIpAsInt = subnetInfo.asInteger(subnetInfo.getLowAddress());
    Integer highIpAsInt = subnetInfo.asInteger(subnetInfo.getHighAddress());
    doNotAutoBlockIpRangeSet.add(Range.closed(lowIpAsInt, highIpAsInt));

    Map<String, ViolationMetaData> violators = new HashMap<>();
    violators.put("50.39.100.193", new ViolationMetaData(new Date(), 2));
    Map<String, ViolationMetaData> actual = processor.filterAndTruncateViolators(config, doNotAutoBlockIpRangeSet,
            violators);

    assertTrue("The violators map should be empty after filtering", actual.size() == 0);
}

@Test
public void testThatFilterAndTruncateViolatorsTruncatesTheLowestOffenders() {
    final int cidrLimit = 2;
    processor.setCidrLimitForIpSetOverride(cidrLimit);
    config.setRateLimitViolationBlacklistPeriodInMinutes(10);

    RangeSet<Integer> rangeSet = TreeRangeSet.create();

    Map<String, ViolationMetaData> violators = new HashMap<>();
    violators.put("50.39.100.193", new ViolationMetaData(new Date(), 3));
    violators.put("50.39.100.191", new ViolationMetaData(new Date(), 1));
    violators.put("50.39.100.192", new ViolationMetaData(new Date(), 2));
    violators.put("50.39.100.194", new ViolationMetaData(new Date(), 4));
    Map<String, ViolationMetaData> actual = processor.filterAndTruncateViolators(config, rangeSet, violators);

    assertTrue("The violators map should be the size of the cidr limit", actual.size() == cidrLimit);
    assertTrue("violators should contain 193 and 194 the highest offenders",
            actual.containsKey("50.39.100.193") && actual.containsKey("50.39.100.194"));
}

/**
 * Return a pair of maps containing the ranges of availability for dimensions and metrics respectively.
 *
 * @param metadata  The metadata that contain segment availability.
 *
 * @return A pair of two maps of range sets. One entry is for dimensions and the other for metrics.
 */
public static Map<Columns, Map<String, RangeSet<DateTime>>> getRangeLists(DataSourceMetadata metadata) {

    final Map<String, RangeSet<DateTime>> dimensionIntervals = new HashMap<>();
    final Map<String, RangeSet<DateTime>> metricIntervals = new HashMap<>();

    metadata.segments.stream()
            .forEach(
                    segment -> {
                        buildRangeSet(segment.getDimensions(), segment.getInterval(), dimensionIntervals);
                        buildRangeSet(segment.getMetrics(), segment.getInterval(), metricIntervals);
                    }
            );

    EnumMap<Columns, Map<String, RangeSet<DateTime>>> intervals = new EnumMap<>(Columns.class);
    intervals.put(DIMENSIONS, dimensionIntervals);
    intervals.put(METRICS, metricIntervals);

    return intervals;
}

public boolean isEmpty() {

        if (!anyLvlSet.isEmpty()) {
            return false;
        }

        for (Map.Entry<Integer, MsLevelRangeSet> lvlMapEntry : lvlMap.entrySet()) {
            MsLevelRangeSet msLevelRangeSet = lvlMapEntry.getValue();
            if (!msLevelRangeSet.anyPrecursorSet.isEmpty()) {
                return false;
            }
            for (Map.Entry<DoubleRange, RangeSet<Integer>> rngMapEntry : msLevelRangeSet.rngMap.entrySet()) {
                if (!rngMapEntry.getValue().isEmpty()) {
                    return false;
                }
            }
        }

        return true;
    }

/**
 * Emit a list of {@link Replacement}s to convert from input to output.
 *
 * @param input the input compilation unit
 * @param characterRanges the character ranges to reformat
 * @return a list of {@link Replacement}s, sorted from low index to high index, without overlaps
 * @throws FormatterException if the input string cannot be parsed
 */
public ImmutableList<Replacement> getFormatReplacements(
    String input, Collection<Range<Integer>> characterRanges) throws FormatterException {
  JavaInput javaInput = new JavaInput(input);

  // TODO(cushon): this is only safe because the modifier ordering doesn't affect whitespace,
  // and doesn't change the replacements that are output. This is not true in general for
  // 'de-linting' changes (e.g. import ordering).
  javaInput = ModifierOrderer.reorderModifiers(javaInput, characterRanges);

  String lineSeparator = Newlines.guessLineSeparator(input);
  JavaOutput javaOutput =
      new JavaOutput(lineSeparator, javaInput, new JavaCommentsHelper(lineSeparator, options));
  try {
    format(javaInput, javaOutput, options);
  } catch (FormattingError e) {
    throw new FormatterException(e.diagnostics());
  }
  RangeSet<Integer> tokenRangeSet = javaInput.characterRangesToTokenRanges(characterRanges);
  return javaOutput.getFormatReplacements(tokenRangeSet);
}

/**
 * Converts zero-indexed, [closed, open) line ranges in the given source file to character ranges.
 */
public static RangeSet<Integer> lineRangesToCharRanges(
    String input, RangeSet<Integer> lineRanges) {
  List<Integer> lines = new ArrayList<>();
  Iterators.addAll(lines, Newlines.lineOffsetIterator(input));
  lines.add(input.length() + 1);

  final RangeSet<Integer> characterRanges = TreeRangeSet.create();
  for (Range<Integer> lineRange :
      lineRanges.subRangeSet(Range.closedOpen(0, lines.size() - 1)).asRanges()) {
    int lineStart = lines.get(lineRange.lowerEndpoint());
    // Exclude the trailing newline. This isn't strictly necessary, but handling blank lines
    // as empty ranges is convenient.
    int lineEnd = lines.get(lineRange.upperEndpoint()) - 1;
    Range<Integer> range = Range.closedOpen(lineStart, lineEnd);
    characterRanges.add(range);
  }
  return characterRanges;
}

/**
 * Filter out the values for which the tokens are not included within the specified range.
 *
 * @param tokens the tokens range
 * @param values the restricted values
 * @return the values for which the tokens are not included within the specified range.
 */
private List<ByteBuffer> filterWithRangeSet(RangeSet<Token> tokens, List<ByteBuffer> values)
{
    List<ByteBuffer> remaining = new ArrayList<>();

    for (ByteBuffer value : values)
    {
        Token token = partitioner.getToken(value);

        if (!tokens.contains(token))
            continue;

        remaining.add(value);
    }
    return remaining;
}

/**
 * Returns the records of this time series that belong to the specified time ranges and are accepted by the 
 * specified filter.
 * 
 * @param timeRanges the time ranges for which the data must be read
 * @throws IOException if an I/O problem occurs
 * @throws HorizonDBException if another problem occurs
 */
public ResourceIterator<Record> read(RangeSet<Field> timeRanges,
                                     Filter<String> recordTypeFilter,
                                     Filter<Record> filter) throws IOException, HorizonDBException {

    Range<Field> span = timeRanges.span();

    final Range<Field> from = this.definition.getPartitionTimeRange(span.lowerEndpoint());
    final Range<Field> to;

    if (from.contains(span.upperEndpoint())) {
        to = from;
    } else {
        to = this.definition.getPartitionTimeRange(span.upperEndpoint());
    }

    KeyValueIterator<PartitionId, TimeSeriesPartition> rangeForRead = 
            this.partitionManager.getRangeForRead(toPartitionId(from), toPartitionId(to), this.definition);

    return new PartitionRecordIterator(timeRanges, rangeForRead, recordTypeFilter, filter);
}

private static String toLengthString(final RangeSet<Integer> ranges) {
    final Iterator<Range<Integer>> it = ranges.asRanges().iterator();
    if (!it.hasNext()) {
        return "";
    }

    final StringBuilder sb = new StringBuilder();
    boolean haveNext;
    do {
        final Range<Integer> current = it.next();
        haveNext = it.hasNext();
        appendRange(sb, current.lowerEndpoint(), current.upperEndpoint(), haveNext);
    } while (haveNext);

    return sb.toString();
}

private static String toRangeString(final RangeSet<?> ranges) {
    final Iterator<? extends Range<?>> it = ranges.asRanges().iterator();
    if (!it.hasNext()) {
        return "";
    }

    final StringBuilder sb = new StringBuilder();
    boolean haveNext;
    do {
        final Range<?> current = it.next();
        haveNext = it.hasNext();
        appendRange(sb, current.lowerEndpoint(), current.upperEndpoint(), haveNext);
    } while (haveNext);

    return sb.toString();
}

final RangeConstraint<N> calculateRangeConstraint(final RangeConstraint<N> baseRangeConstraint) {
    if (ranges == null) {
        return baseRangeConstraint;
    }

    // Run through alternatives and resolve them against the base type
    final RangeSet<N> baseRangeSet = baseRangeConstraint.getAllowedRanges();
    Verify.verify(!baseRangeSet.isEmpty(), "Base type %s does not define constraints", getBaseType());

    final Range<N> baseRange = baseRangeSet.span();
    final List<ValueRange> resolvedRanges = ensureResolvedRanges(ranges, baseRange);

    // Next up, ensure the of boundaries match base constraints
    final RangeSet<N> typedRanges = ensureTypedRanges(resolvedRanges, baseRange.lowerEndpoint().getClass());

    // Now verify if new ranges are strict subset of base ranges
    if (!baseRangeSet.enclosesAll(typedRanges)) {
        throw new InvalidRangeConstraintException(typedRanges,
            "Range constraint %s is not a subset of parent constraint %s", typedRanges, baseRangeSet);
    }

    return new ResolvedRangeConstraint<>(constraint, typedRanges);
}

@Test
public void exceptionTest() {
    final UnresolvedNumber min = UnresolvedNumber.min();
    final UnresolvedNumber max = UnresolvedNumber.max();
    final EnumPair enumPair = EnumPairBuilder.create("enum1", 1).setDescription("description")
            .setReference("reference").setUnknownSchemaNodes(mock(UnknownSchemaNode.class)).build();

    final RangeSet<Integer> rangeset = ImmutableRangeSet.of(Range.closed(1, 2));
    final InvalidRangeConstraintException invalidRangeConstraintException = new InvalidRangeConstraintException(
            rangeset, "error msg", "other important messages");
    assertSame(rangeset, invalidRangeConstraintException.getOffendingRanges());

    final InvalidBitDefinitionException invalidBitDefinitionException = new InvalidBitDefinitionException(
            BIT_A, "error msg", "other important messages");
    assertEquals(invalidBitDefinitionException.getOffendingBit(), BIT_A);

    final InvalidEnumDefinitionException invalidEnumDefinitionException = new InvalidEnumDefinitionException(
            enumPair, "error msg", "other important messages");
    assertEquals(invalidEnumDefinitionException.getOffendingEnum(), enumPair);
}

/** Replaces calls to EXTRACT, FLOOR and CEIL in an expression. */
@VisibleForTesting
public static RexNode replaceTimeUnits(RexBuilder rexBuilder, RexNode e,
    String timeZone) {
  ImmutableSortedSet<TimeUnitRange> timeUnits = extractTimeUnits(e);
  if (!timeUnits.contains(TimeUnitRange.YEAR)) {
    // Case when we have FLOOR or CEIL but no extract on YEAR.
    // Add YEAR as TimeUnit so that FLOOR gets replaced in first iteration
    // with timeUnit YEAR.
    timeUnits = ImmutableSortedSet.<TimeUnitRange>naturalOrder()
        .addAll(timeUnits).add(TimeUnitRange.YEAR).build();
  }
  final Map<String, RangeSet<Calendar>> operandRanges = new HashMap<>();
  for (TimeUnitRange timeUnit : timeUnits) {
    e = e.accept(
        new ExtractShuttle(rexBuilder, timeUnit, operandRanges, timeUnits,
            timeZone));
  }
  return e;
}

private boolean canRewriteExtract(RexNode operand) {
  // We rely on timeUnits being sorted (so YEAR comes before MONTH
  // before HOUR) and unique. If we have seen a predicate on YEAR,
  // operandRanges will not be empty. This checks whether we can rewrite
  // the "extract" condition. For example, in the condition
  //
  //   extract(MONTH from time) = someValue
  //   OR extract(YEAR from time) = someValue
  //
  // we cannot rewrite extract on MONTH.
  if (timeUnit == TimeUnitRange.YEAR) {
    return true;
  }
  final RangeSet<Calendar> calendarRangeSet =
      operandRanges.get(operand.toString());
  if (calendarRangeSet == null || calendarRangeSet.isEmpty()) {
    return false;
  }
  for (Range<Calendar> range : calendarRangeSet.asRanges()) {
    // Cannot reWrite if range does not have an upper or lower bound
    if (!range.hasUpperBound() || !range.hasLowerBound()) {
      return false;
    }
  }
  return true;
}

private RexNode compareFloorCeil(SqlKind comparison, RexNode operand,
    RexLiteral timeLiteral, TimeUnitRange timeUnit, boolean floor) {
  RangeSet<Calendar> rangeSet = operandRanges.get(operand.toString());
  if (rangeSet == null) {
    rangeSet = ImmutableRangeSet.<Calendar>of().complement();
  }
  final RangeSet<Calendar> s2 = TreeRangeSet.create();
  final Calendar c = timestampValue(timeLiteral);
  final Range<Calendar> range = floor
      ? floorRange(timeUnit, comparison, c)
      : ceilRange(timeUnit, comparison, c);
  s2.add(range);
  // Intersect old range set with new.
  s2.removeAll(rangeSet.complement());
  operandRanges.put(operand.toString(), ImmutableRangeSet.copyOf(s2));
  if (range.isEmpty()) {
    return rexBuilder.makeLiteral(false);
  }
  return toRex(operand, range);
}

public P2PBlobRangeSet constrainMaximumSpan(int maximumSpanSize) {
  int currentSize=0;
  RangeSet<Integer> constrainedRange=TreeRangeSet.create();
  for(Range<Integer> r: ranges.asRanges()){
    int sizeOfRange=r.upperEndpoint()-r.lowerEndpoint()+1;
    if(currentSize+sizeOfRange<=maximumSpanSize){
      currentSize+=sizeOfRange;
      constrainedRange.add(r);
    }
    else{
      sizeOfRange=maximumSpanSize-currentSize-1;
      constrainedRange.add(Range.closed(r.lowerEndpoint(), r.lowerEndpoint()+sizeOfRange));
      break;
    }
  }
  return new P2PBlobRangeSet(constrainedRange);
}

private final BitSet convertToBitSet(final RangeSet<Integer> rangeSet) {
    if(rangeSet.isEmpty()) {
        return new BitSet();
    }

    final BitSet bitSet = new BitSet(rangeSet.span().upperEndpoint());

    rangeSet.asRanges().forEach(range -> {
        if(!range.canonical(DiscreteDomain.integers()).isEmpty()) {
            Range<Integer> closedRange = ContiguousSet.create(range, DiscreteDomain.integers()).range();
            bitSet.set(closedRange.lowerEndpoint(), closedRange.upperEndpoint() + 1);
        }
    });

    return bitSet;
}

private String context(final String originalDocText, final Response response) {
  // [1,3], [2,5], [8,10] => [1,5], [8,10]
  final List<CharOffsetSpan> charSpans = justificationSpans(response);
  final List<CharOffsetSpan> unitedSpans = Lists.newArrayList();

  // use RangeSet to do this
  final RangeSet<Integer> disconnected = TreeRangeSet.create();
  for (CharOffsetSpan charSpan : charSpans) {
    int startInclusive = charSpan.startInclusive();
    int endInclusive = charSpan.endInclusive();
    startInclusive = (startInclusive - 100) >= 0 ? startInclusive - 100 : 0;
    endInclusive =
        (endInclusive + 100) < originalDocText.length() ? endInclusive + 100 : endInclusive;
    disconnected.add(Range.closed(startInclusive, endInclusive));
  }
  for (Range<Integer> range : disconnected.asRanges()) {
    unitedSpans.add(CharOffsetSpan.fromOffsetsOnly(range.lowerEndpoint(), range.upperEndpoint()));
  }
  Collections.sort(unitedSpans);
  String justificationsString = "";
  if (unitedSpans.get(0).startInclusive() != 0) {
    justificationsString += "[.....]";
  }
  for (CharOffsetSpan span : unitedSpans) {
    justificationsString +=
        originalDocText.substring(span.startInclusive(), span.endInclusive() + 1);
    justificationsString += "[.....]";
  }
  return justificationsString;
}

/**
 * Runs the Google Java formatter on the given source, with only the given ranges specified.
 */
public List<Replacement> format(
        SnippetKind kind,
        String source,
        List<Range<Integer>> ranges,
        int initialIndent,
        boolean includeComments)
        throws FormatterException {
    RangeSet<Integer> rangeSet = TreeRangeSet.create();
    for (Range<Integer> range : ranges) {
        rangeSet.add(range);
    }
    if (includeComments) {
        if (kind != SnippetKind.COMPILATION_UNIT) {
            throw new IllegalArgumentException(
                    "comment formatting is only supported for compilation units");
        }
        return formatter.getFormatReplacements(source, ranges);
    }
    SnippetWrapper wrapper = snippetWrapper(kind, source, initialIndent);
    ranges = offsetRanges(ranges, wrapper.offset);

    String replacement = formatter.formatSource(wrapper.contents.toString(), ranges);
    replacement =
            replacement.substring(
                    wrapper.offset,
                    replacement.length() - (wrapper.contents.length() - wrapper.offset - source.length()));

    List<Replacement> replacements = toReplacements(source, replacement);
    List<Replacement> filtered = new ArrayList<>();
    for (Replacement r : replacements) {
        if (rangeSet.encloses(r.getReplaceRange())) {
            filtered.add(r);
        }
    }
    return filtered;
}

public RangeSet<Integer> characterRangesToTokenRanges(Collection<Range<Integer>> characterRanges)
        throws FormatterException {
    RangeSet<Integer> tokenRangeSet = TreeRangeSet.create();
    for (Range<Integer> characterRange0 : characterRanges) {
        Range<Integer> characterRange = characterRange0.canonical(DiscreteDomain.integers());
        tokenRangeSet.add(
                characterRangeToTokenRange(
                        characterRange.lowerEndpoint(),
                        characterRange.upperEndpoint() - characterRange.lowerEndpoint()));
    }
    return tokenRangeSet;
}

static EncodedDiscreteResources of(Set<DiscreteResource> resources, DiscreteResourceCodec codec) {
    RangeSet<Integer> rangeSet = TreeRangeSet.create();
    resources.stream()
            .map(x -> x.valueAs(Object.class))
            .flatMap(Tools::stream)
            .map(x -> codec.encode(x))
            .map(Range::singleton)
            .map(x -> x.canonical(DiscreteDomain.integers()))
            .forEach(rangeSet::add);

    return new EncodedDiscreteResources(rangeSet, codec);
}

@Override
public EncodedDiscreteResources read(Kryo kryo, Input input, Class<EncodedDiscreteResources> cls) {
    @SuppressWarnings("unchecked")
    List<ClosedOpenRange> ranges = kryo.readObject(input, ArrayList.class);
    DiscreteResourceCodec codec = (DiscreteResourceCodec) kryo.readClassAndObject(input);

    RangeSet<Integer> rangeSet = TreeRangeSet.create();
    ranges.stream()
            .map(x -> Range.closedOpen(x.lowerBound(), x.upperBound()))
            .forEach(rangeSet::add);
    return new EncodedDiscreteResources(rangeSet, codec);
}

AbstractFrontendHistory(final String persistenceId, final ShardDataTree tree,
    final Map<UnsignedLong, Boolean> closedTransactions, final RangeSet<UnsignedLong> purgedTransactions) {
    this.persistenceId = Preconditions.checkNotNull(persistenceId);
    this.tree = Preconditions.checkNotNull(tree);
    this.closedTransactions = Preconditions.checkNotNull(closedTransactions);
    this.purgedTransactions = Preconditions.checkNotNull(purgedTransactions);
}

public FrontendHistoryMetadata(final long historyId, final long cookie, final boolean closed,
        final Map<UnsignedLong, Boolean> closedTransactions, final RangeSet<UnsignedLong> purgedTransactions) {
    this.historyId = historyId;
    this.cookie = cookie;
    this.closed = closed;
    this.closedTransactions = ImmutableMap.copyOf(closedTransactions);
    this.purgedTransactions = ImmutableRangeSet.copyOf(purgedTransactions);
}

public static FrontendHistoryMetadata readFrom(final DataInput in) throws IOException {
    byte header = WritableObjects.readLongHeader(in);
    final long historyId = WritableObjects.readFirstLong(in, header);
    final long cookie = WritableObjects.readSecondLong(in, header);
    final boolean closed = in.readBoolean();

    header = WritableObjects.readLongHeader(in);
    long ls = WritableObjects.readFirstLong(in, header);
    Verify.verify(ls >= 0 && ls <= Integer.MAX_VALUE);
    final int csize = (int) ls;

    ls = WritableObjects.readSecondLong(in, header);
    Verify.verify(ls >= 0 && ls <= Integer.MAX_VALUE);
    final int psize = (int) ls;

    final Map<UnsignedLong, Boolean> closedTransactions = new HashMap<>(csize);
    for (int i = 0; i < csize; ++i) {
        final UnsignedLong key = UnsignedLong.fromLongBits(WritableObjects.readLong(in));
        final Boolean value = Boolean.valueOf(in.readBoolean());
        closedTransactions.put(key, value);
    }
    final RangeSet<UnsignedLong> purgedTransactions = TreeRangeSet.create();
    for (int i = 0; i < psize; ++i) {
        final byte h = WritableObjects.readLongHeader(in);
        final UnsignedLong l = UnsignedLong.fromLongBits(WritableObjects.readFirstLong(in, h));
        final UnsignedLong u = UnsignedLong.fromLongBits(WritableObjects.readSecondLong(in, h));
        purgedTransactions.add(Range.closed(l, u));
    }

    return new FrontendHistoryMetadata(historyId, cookie, closed, closedTransactions, purgedTransactions);
}

private StandaloneFrontendHistory(final String persistenceId, final ClientIdentifier clientId,
        final ShardDataTree tree, final Map<UnsignedLong, Boolean> closedTransactions,
        final RangeSet<UnsignedLong> purgedTransactions) {
    super(persistenceId, tree, closedTransactions, purgedTransactions);
    this.identifier = new LocalHistoryIdentifier(clientId, 0);
    this.tree = Preconditions.checkNotNull(tree);
}

private static void checkEnclosed(
    String fieldName,
    Range<Integer> fieldEnclosure,
    RangeSet<Integer> field) {

  checkArgument(fieldEnclosure.encloses(field.span()),
      String.format(
          "Bad specification for field %s: span(%s) = %s is not enclosed by boundary %s.",
          fieldName,
          field,
          field.span(),
          fieldEnclosure));
}

private static CrontabEntry from(
    RangeSet<Integer> minute,
    RangeSet<Integer> hour,
    RangeSet<Integer> dayOfMonth,
    RangeSet<Integer> month,
    RangeSet<Integer> dayOfWeek) throws IllegalArgumentException {

  return new CrontabEntry(minute, hour, dayOfMonth, month, dayOfWeek);
}

private String fieldToString(RangeSet<Integer> rangeSet, Range<Integer> coveringRange) {
  if (rangeSet.asRanges().size() == 1 && rangeSet.encloses(coveringRange)) {
    return "*";
  }
  List<String> components = Lists.newArrayList();
  for (Range<Integer> range : rangeSet.asRanges()) {
    ContiguousSet<Integer> set = ContiguousSet.create(range, DiscreteDomain.integers());
    if (set.size() == 1) {
      components.add(set.first().toString());
    } else {
      components.add(set.first() + "-" + set.last());
    }
  }
  return String.join(",", components);
}

private RangeSet<Integer> parseMinute() {
  RangeSet<Integer> minutes = TreeRangeSet.create();
  for (String component : getComponents(rawMinute)) {
    minutes.addAll(parseComponent(MINUTE, component));
  }
  return ImmutableRangeSet.copyOf(minutes);
}

private RangeSet<Integer> parseHour() {
  RangeSet<Integer> hours = TreeRangeSet.create();
  for (String component : getComponents(rawHour)) {
    hours.addAll(parseComponent(HOUR, component));
  }
  return ImmutableRangeSet.copyOf(hours);
}