com.google.common.collect.Range#intersection ( )源码实例Demo

/**
 * get overlapping MZ range (lowerBound - mzTol and upperbound+ mzTol)
 * 
 * @param mzTol
 * @param a
 * @param b
 * @return
 */
public static Range<Double> getOverlapMZ(MZTolerance mzTol, DataPoint[] a, DataPoint[] b) {
  Range<Double> ra = getMZRange(a);
  Range<Double> rb = getMZRange(b);

  // no overlap
  if (!ra.isConnected(rb))
    return Range.singleton(0d);

  Range<Double> intersect = ra.intersection(rb);
  // add mzTol
  double min = intersect.lowerEndpoint();
  min = mzTol.getToleranceRange(min).lowerEndpoint();
  double max = intersect.upperEndpoint();
  max = mzTol.getToleranceRange(max).upperEndpoint();
  return Range.closed(min, max);

}
 

/**
 * Execute intersection method by safe mode.
 *
 * @param range range
 * @param connectedRange connected range
 * @return the intersection result of two ranges
 */
public static Range<Comparable<?>> safeIntersection(final Range<Comparable<?>> range, final Range<Comparable<?>> connectedRange) {
    try {
        return range.intersection(connectedRange);
    } catch (final ClassCastException ex) {
        Comparable<?> rangeLowerEndpoint = range.hasLowerBound() ? range.lowerEndpoint() : null;
        Comparable<?> rangeUpperEndpoint = range.hasUpperBound() ? range.upperEndpoint() : null;
        Comparable<?> connectedRangeLowerEndpoint = connectedRange.hasLowerBound() ? connectedRange.lowerEndpoint() : null;
        Comparable<?> connectedRangeUpperEndpoint = connectedRange.hasUpperBound() ? connectedRange.upperEndpoint() : null;
        Class<?> clazz = getTargetNumericType(Lists.newArrayList(rangeLowerEndpoint, rangeUpperEndpoint, connectedRangeLowerEndpoint, connectedRangeUpperEndpoint));
        if (clazz == null) {
            throw ex;
        }
        Range<Comparable<?>> newRange = createTargetNumericTypeRange(range, clazz);
        Range<Comparable<?>> newConnectedRange = createTargetNumericTypeRange(connectedRange, clazz);
        return newRange.intersection(newConnectedRange);
    }
}
 

/**
 * get overlapping MZ range (lowerBound - mzTol and upperbound+ mzTol)
 * 
 * @param mzTol
 * @param a
 * @param b
 * @return
 */
public static Range<Double> getOverlapMZ(MZTolerance mzTol, DataPoint[] a, DataPoint[] b) {
  Range<Double> ra = getMZRange(a);
  Range<Double> rb = getMZRange(b);

  // no overlap
  if (!ra.isConnected(rb))
    return Range.singleton(0d);

  Range<Double> intersect = ra.intersection(rb);
  // add mzTol
  double min = intersect.lowerEndpoint();
  min = mzTol.getToleranceRange(min).lowerEndpoint();
  double max = intersect.upperEndpoint();
  max = mzTol.getToleranceRange(max).upperEndpoint();
  return Range.closed(min, max);

}
 

/** Weakens a term so that it checks only what is not implied by predicates.
 *
 * <p>The term is broken into "ref comparison constant",
 * for example "$0 &lt; 5".
 *
 * <p>Examples:
 * <ul>
 *
 * <li>{@code residue($0 < 10, [$0 < 5])} returns {@code true}
 *
 * <li>{@code residue($0 < 10, [$0 < 20, $0 > 0])} returns {@code $0 < 10}
 * </ul>
 */
private <C extends Comparable<C>> Range<C> residue(RexNode ref, Range<C> r0, List<RexNode> predicates,
        Class<C> clazz) {
    for (RexNode predicate : predicates) {
        switch (predicate.getKind()) {
        case EQUALS:
        case LESS_THAN:
        case LESS_THAN_OR_EQUAL:
        case GREATER_THAN:
        case GREATER_THAN_OR_EQUAL:
            final RexCall call = (RexCall) predicate;
            if (call.getOperands().get(0).equals(ref) && call.getOperands().get(1) instanceof RexLiteral) {
                final RexLiteral literal = (RexLiteral) call.getOperands().get(1);
                final C c1 = literal.getValueAs(clazz);
                final Range<C> r1 = range(predicate.getKind(), c1);
                if (r0.encloses(r1)) {
                    // Given these predicates, term is always satisfied.
                    // e.g. r0 is "$0 < 10", r1 is "$0 < 5"
                    return Range.all();
                }
                if (r0.isConnected(r1)) {
                    return r0.intersection(r1);
                }
                // Ranges do not intersect. Return null meaning the empty range.
                return null;
            }
        }
    }
    return r0;
}
 

/** Weakens a term so that it checks only what is not implied by predicates.
 *
 * <p>The term is broken into "ref comparison constant",
 * for example "$0 &lt; 5".
 *
 * <p>Examples:
 * <ul>
 *
 * <li>{@code residue($0 < 10, [$0 < 5])} returns {@code true}
 *
 * <li>{@code residue($0 < 10, [$0 < 20, $0 > 0])} returns {@code $0 < 10}
 * </ul>
 */
private <C extends Comparable<C>> Range<C> residue(RexNode ref, Range<C> r0,
    List<RexNode> predicates, Class<C> clazz) {
  for (RexNode predicate : predicates) {
    switch (predicate.getKind()) {
    case EQUALS:
    case LESS_THAN:
    case LESS_THAN_OR_EQUAL:
    case GREATER_THAN:
    case GREATER_THAN_OR_EQUAL:
      final RexCall call = (RexCall) predicate;
      if (call.operands.get(0).equals(ref)
          && call.operands.get(1) instanceof RexLiteral) {
        final RexLiteral literal = (RexLiteral) call.operands.get(1);
        final C c1 = literal.getValueAs(clazz);
        final Range<C> r1 = range(predicate.getKind(), c1);
        if (r0.encloses(r1)) {
          // Given these predicates, term is always satisfied.
          // e.g. r0 is "$0 < 10", r1 is "$0 < 5"
          return Range.all();
        }
        if (r0.isConnected(r1)) {
          return r0.intersection(r1);
        }
        // Ranges do not intersect. Return null meaning the empty range.
        return null;
      }
    }
  }
  return r0;
}
 

/**
 * For a given FileWork, calculate how many bytes are available on each on node endpoint
 *
 * @param work the FileWork to calculate endpoint bytes for
 * @throws IOException
 */
public EndpointByteMap getEndpointByteMap(FileWork work) throws IOException {
  Stopwatch watch = Stopwatch.createStarted();



  ImmutableRangeMap<Long,FileBlockLocation> blockMap = getBlockMap(work.getFileAttributes());
  EndpointByteMapImpl endpointByteMap = new EndpointByteMapImpl();
  long start = work.getStart();
  long end = start + work.getLength();
  Range<Long> rowGroupRange = Range.closedOpen(start, end);

  // Find submap of ranges that intersect with the rowGroup
  ImmutableRangeMap<Long,FileBlockLocation> subRangeMap = blockMap.subRangeMap(rowGroupRange);

  // Iterate through each block in this submap and get the host for the block location
  for (Map.Entry<Range<Long>,FileBlockLocation> block : subRangeMap.asMapOfRanges().entrySet()) {
    List<String> hosts = block.getValue().getHosts();
    Range<Long> blockRange = block.getKey();
    Range<Long> intersection = rowGroupRange.intersection(blockRange);
    long bytes = intersection.upperEndpoint() - intersection.lowerEndpoint();

    // For each host in the current block location, add the intersecting bytes to the corresponding endpoint
    for (String host : hosts) {
      NodeEndpoint endpoint = getNodeEndpoint(host);
      if (endpoint != null) {
        endpointByteMap.add(HostAndPort.fromHost(endpoint.getAddress()), bytes);
      } else {
        logger.debug("Failure finding SabotNode running on host {}.  Skipping affinity to that host.", host);
      }
    }
  }

  logger.debug("FileWork group ({},{}) max bytes {}", work.getFileAttributes().getPath(), work.getStart(), endpointByteMap.getMaxBytes());

  logger.debug("Took {} ms to set endpoint bytes", watch.stop().elapsed(TimeUnit.MILLISECONDS));
  return endpointByteMap;
}
 

/**
 * Returns an {@link Iterable} of {@link DateTime}s of every recurrence of this particular
 * time of year within a given {@link Range} (usually one spanning many years).
 *
 * <p>WARNING: This can return a potentially very large {@link Iterable} if {@code END_OF_TIME}
 * is used as the upper endpoint of the range.
 */
public Iterable<DateTime> getInstancesInRange(Range<DateTime> range) {
  // In registry world, all dates are within START_OF_TIME and END_OF_TIME, so restrict any
  // ranges without bounds to our notion of zero-to-infinity.
  Range<DateTime> normalizedRange = range.intersection(Range.closed(START_OF_TIME, END_OF_TIME));
  Range<Integer> yearRange = Range.closed(
      normalizedRange.lowerEndpoint().getYear(),
      normalizedRange.upperEndpoint().getYear());
  return ContiguousSet.create(yearRange, integers())
      .stream()
      .map(this::getDateTimeWithYear)
      .filter(normalizedRange)
      .collect(toImmutableList());
}
 

/** Weakens a term so that it checks only what is not implied by predicates.
 *
 * <p>The term is broken into "ref comparison constant",
 * for example "$0 &lt; 5".
 *
 * <p>Examples:
 * <ul>
 *
 * <li>{@code residue($0 < 10, [$0 < 5])} returns {@code true}
 *
 * <li>{@code residue($0 < 10, [$0 < 20, $0 > 0])} returns {@code $0 < 10}
 * </ul>
 */
private <C extends Comparable<C>> Range<C> residue(RexNode ref, Range<C> r0,
    List<RexNode> predicates, Class<C> clazz) {
  Range<C> result = r0;
  for (RexNode predicate : predicates) {
    switch (predicate.getKind()) {
    case EQUALS:
    case LESS_THAN:
    case LESS_THAN_OR_EQUAL:
    case GREATER_THAN:
    case GREATER_THAN_OR_EQUAL:
      final RexCall call = (RexCall) predicate;
      if (call.operands.get(0).equals(ref)
          && call.operands.get(1) instanceof RexLiteral) {
        final RexLiteral literal = (RexLiteral) call.operands.get(1);
        final C c1 = literal.getValueAs(clazz);
        final Range<C> r1 = range(predicate.getKind(), c1);
        if (result.encloses(r1)) {
          // Given these predicates, term is always satisfied.
          // e.g. r0 is "$0 < 10", r1 is "$0 < 5"
          result = Range.all();
          continue;
        }
        if (result.isConnected(r1)) {
          result = result.intersection(r1);
          continue;
        }
        // Ranges do not intersect. Return null meaning the empty range.
        return null;
      }
    }
  }
  return result;
}
 

/**
 * remove from self the elements that exist in other
 * @return
 */
public static <C extends Comparable<?>> List<Range<C>> remove(Range<C> self, Range<C> other) {

    // mimic the following logic in guava 18:
    //        RangeSet<C> rangeSet = TreeRangeSet.create();
    //        rangeSet.add(self);
    //        rangeSet.remove(other);
    //        return Lists.newArrayList(rangeSet.asRanges());

    if (other == null || !self.isConnected(other)) {
        return Collections.singletonList(self);
    }

    Range<C> share = self.intersection(other);
    if (share.isEmpty()) {
        return Collections.singletonList(self);
    }

    List<Range<C>> ret = Lists.newArrayList();

    //see left part
    if (!self.hasLowerBound()) {
        if (share.hasLowerBound()) {
            if (share.lowerBoundType() == BoundType.CLOSED) {
                ret.add(Range.lessThan(share.lowerEndpoint()));
            } else {
                ret.add(Range.atMost(share.lowerEndpoint()));
            }
        }
    } else {
        if (self.lowerEndpoint() != share.lowerEndpoint()) {
            if (self.lowerBoundType() == BoundType.CLOSED) {
                if (share.lowerBoundType() == BoundType.CLOSED) {
                    ret.add(Range.closedOpen(self.lowerEndpoint(), share.lowerEndpoint()));
                } else {
                    ret.add(Range.closed(self.lowerEndpoint(), share.lowerEndpoint()));
                }
            } else {
                if (share.lowerBoundType() == BoundType.CLOSED) {
                    ret.add(Range.open(self.lowerEndpoint(), share.lowerEndpoint()));
                } else {
                    ret.add(Range.openClosed(self.lowerEndpoint(), share.lowerEndpoint()));
                }
            }
        } else {
            if (self.lowerBoundType() == BoundType.CLOSED && share.lowerBoundType() == BoundType.OPEN) {
                ret.add(Range.closed(self.lowerEndpoint(), share.lowerEndpoint()));
            }
        }
    }

    //see right part 
    if (!self.hasUpperBound()) {
        if (share.hasUpperBound()) {
            if (share.upperBoundType() == BoundType.CLOSED) {
                ret.add(Range.greaterThan(share.upperEndpoint()));
            } else {
                ret.add(Range.atLeast(share.upperEndpoint()));
            }
        }
    } else {
        if (self.upperEndpoint() != share.upperEndpoint()) {
            if (self.upperBoundType() == BoundType.CLOSED) {
                if (share.upperBoundType() == BoundType.CLOSED) {
                    ret.add(Range.openClosed(share.upperEndpoint(), self.upperEndpoint()));
                } else {
                    ret.add(Range.closed(share.upperEndpoint(), self.upperEndpoint()));
                }
            } else {
                if (share.upperBoundType() == BoundType.CLOSED) {
                    ret.add(Range.open(share.upperEndpoint(), self.upperEndpoint()));
                } else {
                    ret.add(Range.closedOpen(share.upperEndpoint(), self.upperEndpoint()));
                }
            }
        } else {
            if (self.upperBoundType() == BoundType.CLOSED && share.upperBoundType() == BoundType.OPEN) {
                ret.add(Range.closed(self.upperEndpoint(), share.upperEndpoint()));
            }
        }
    }

    return ret;

}
 

private static Range<Long> extractTsConditionInternal(TupleFilter filter, TblColRef colRef) {
    if (filter == null) {
        return Range.all();
    }

    if (filter instanceof LogicalTupleFilter) {
        if (filter.getOperator() == TupleFilter.FilterOperatorEnum.AND) {
            Range<Long> ret = Range.all();
            for (TupleFilter child : filter.getChildren()) {
                Range childRange = extractTsConditionInternal(child, colRef);
                if (childRange != null) {
                    if (ret.isConnected(childRange) && !ret.intersection(childRange).isEmpty()) {
                        ret = ret.intersection(childRange);
                    } else {
                        return null;
                    }
                } else {
                    return null;
                }
            }
            return ret.isEmpty() ? null : ret;
        } else {
            //for conditions like date > DATE'2000-11-11' OR date < DATE '1999-01-01'
            //we will use Ranges.all() rather than two ranges to represent them
            return Range.all();
        }
    }

    if (filter instanceof CompareTupleFilter) {
        CompareTupleFilter compareTupleFilter = (CompareTupleFilter) filter;
        if (compareTupleFilter.getColumn() == null)// column will be null at filters like " 1<>1"
            return Range.all();

        if (compareTupleFilter.getColumn().equals(colRef)) {
            Object firstValue = compareTupleFilter.getFirstValue();
            long t;
            switch (compareTupleFilter.getOperator()) {
            case EQ:
                t = DateFormat.stringToMillis((String) firstValue);
                return Range.closed(t, t);
            case LT:
                t = DateFormat.stringToMillis((String) firstValue);
                return Range.lessThan(t);
            case LTE:
                t = DateFormat.stringToMillis((String) firstValue);
                return Range.atMost(t);
            case GT:
                t = DateFormat.stringToMillis((String) firstValue);
                return Range.greaterThan(t);
            case GTE:
                t = DateFormat.stringToMillis((String) firstValue);
                return Range.atLeast(t);
            case NEQ:
            case IN://not handled for now
                break;
            default:
            }
        }
    }
    return Range.all();
}
 

private void schedule(Node node) {
  Logger logger = GPLogger.getLogger(this);
  GPLogger.debug(logger, "Scheduling node %s", node);
  Range<Date> startRange = Range.all();
  Range<Date> endRange = Range.all();

  Range<Date> weakStartRange = Range.all();
  Range<Date> weakEndRange = Range.all();

  List<Date> subtaskRanges = Lists.newArrayList();
  List<DependencyEdge> incoming = node.getIncoming();
  GPLogger.debug(logger, ".. #incoming edges=%d", incoming.size());
  for (DependencyEdge edge : incoming) {
    if (!edge.refresh()) {
      continue;
    }
    if (edge instanceof ImplicitSubSuperTaskDependency) {
      subtaskRanges.add(edge.getStartRange().upperEndpoint());
      subtaskRanges.add(edge.getEndRange().lowerEndpoint());
    } else {
      if (edge.isWeak()) {
        weakStartRange = weakStartRange.intersection(edge.getStartRange());
        weakEndRange = weakEndRange.intersection(edge.getEndRange());
      } else {
        startRange = startRange.intersection(edge.getStartRange());
        endRange = endRange.intersection(edge.getEndRange());
      }
    }
    if (startRange.isEmpty() || endRange.isEmpty()) {
      GPLogger.logToLogger("both start and end ranges were calculated as empty for task=" + node.getTask() + ". Skipping it");
    }
  }
  GPLogger.debug(logger, "..Ranges: start=%s end=%s weakStart=%s weakEnd=%s", startRange, endRange, weakStartRange, weakEndRange);

  Range<Date> subtasksSpan = subtaskRanges.isEmpty() ?
      Range.closed(node.getTask().getStart().getTime(), node.getTask().getEnd().getTime()) : Range.encloseAll(subtaskRanges);
  Range<Date> subtreeStartUpwards = subtasksSpan.span(Range.downTo(node.getTask().getStart().getTime(), BoundType.CLOSED));
  Range<Date> subtreeEndDownwards = subtasksSpan.span(Range.upTo(node.getTask().getEnd().getTime(), BoundType.CLOSED));
  GPLogger.debug(logger, "..Subtasks span=%s", subtasksSpan);

  if (!startRange.equals(Range.all())) {
    startRange = startRange.intersection(weakStartRange);
  } else if (!weakStartRange.equals(Range.all())) {
    startRange = weakStartRange.intersection(subtreeStartUpwards);
  }
  if (!endRange.equals(Range.all())) {
    endRange = endRange.intersection(weakEndRange);
  } else if (!weakEndRange.equals(Range.all())) {
    endRange = weakEndRange.intersection(subtreeEndDownwards);
  }
  if (node.getTask().getThirdDateConstraint() == TaskImpl.EARLIESTBEGIN && node.getTask().getThird() != null) {
    startRange = startRange.intersection(Range.downTo(node.getTask().getThird().getTime(), BoundType.CLOSED));
    GPLogger.debug(logger, ".. applying earliest start=%s. Now start range=%s", node.getTask().getThird(), startRange);
  }
  if (!subtaskRanges.isEmpty()) {
    startRange = startRange.intersection(subtasksSpan);
    endRange = endRange.intersection(subtasksSpan);
  }
  GPLogger.debug(logger, ".. finally, start range=%s", startRange);
  if (startRange.hasLowerBound()) {
    modifyTaskStart(node.getTask(), startRange.lowerEndpoint());
  }
  if (endRange.hasUpperBound()) {
    GPCalendarCalc cal = node.getTask().getManager().getCalendar();
    Date endDate = endRange.upperEndpoint();
    TimeUnit timeUnit = node.getTask().getDuration().getTimeUnit();
    if (DayMask.WORKING == (cal.getDayMask(endDate) & DayMask.WORKING)) {
      // in case if calculated end date falls on first day after holidays (say, on Monday)
      // we'll want to modify it a little bit, so that it falls on that holidays start
      // If we don't do this, it will be done automatically the next time task activities are recalculated,
      // and thus task end date will keep changing
      Date closestWorkingEndDate = cal.findClosest(
          endDate, timeUnit, GPCalendarCalc.MoveDirection.BACKWARD, GPCalendar.DayType.WORKING);
      Date closestNonWorkingEndDate = cal.findClosest(
          endDate, timeUnit, GPCalendarCalc.MoveDirection.BACKWARD, GPCalendar.DayType.NON_WORKING, closestWorkingEndDate);
      // If there is a non-working date between current task end and closest working date
      // then we're really just after holidays
      if (closestNonWorkingEndDate != null && closestWorkingEndDate.before(closestNonWorkingEndDate)) {
        // we need to adjust-right closest working date to position to the very beginning of the holidays interval
        Date nonWorkingPeriodStart = timeUnit.adjustRight(closestWorkingEndDate);
        if (nonWorkingPeriodStart.after(node.getTask().getStart().getTime())) {
          endDate = nonWorkingPeriodStart;
        }
      }
    }
    modifyTaskEnd(node.getTask(), endDate);
  }
}