mikemccand commented on a change in pull request #127:
URL: https://github.com/apache/lucene/pull/127#discussion_r638845672
##########
File path:
lucene/facet/src/java/org/apache/lucene/facet/range/LongRangeCounter.java
##########
@@ -148,170 +91,142 @@ public void add(long v) {
// are guaranteed to find a match because the last
// boundary is Long.MAX_VALUE:
+ long[] boundaries = boundaries();
+
int lo = 0;
int hi = boundaries.length - 1;
while (true) {
int mid = (lo + hi) >>> 1;
- // System.out.println(" cycle lo=" + lo + " hi=" + hi + " mid=" + mid +
" boundary=" +
- // boundaries[mid] + " to " + boundaries[mid+1]);
if (v <= boundaries[mid]) {
if (mid == 0) {
- leafCounts[0]++;
+ processSingleValuedHit(mid);
return;
} else {
hi = mid - 1;
}
} else if (v > boundaries[mid + 1]) {
lo = mid + 1;
} else {
- leafCounts[mid + 1]++;
- // System.out.println(" incr @ " + (mid+1) + "; now " +
leafCounts[mid+1]);
+ processSingleValuedHit(mid + 1);
return;
}
}
}
- /**
- * Fills counts corresponding to the original input ranges, returning the
missing count (how many
- * hits didn't match any ranges).
- */
- public int fillCounts(int[] counts) {
- // System.out.println(" rollup");
- missingCount = 0;
- leafUpto = 0;
- rollup(root, counts, false);
- return missingCount;
- }
+ /** Count a multi-valued doc value */
+ void addMultiValued(long v) {
- private int rollup(LongRangeNode node, int[] counts, boolean sawOutputs) {
- int count;
- sawOutputs |= node.outputs != null;
- if (node.left != null) {
- count = rollup(node.left, counts, sawOutputs);
- count += rollup(node.right, counts, sawOutputs);
- } else {
- // Leaf:
- count = leafCounts[leafUpto];
- leafUpto++;
- if (!sawOutputs) {
- // This is a missing count (no output ranges were
- // seen "above" us):
- missingCount += count;
- }
+ if (rangeCount() == 0) {
+ return; // don't bother if there aren't any requested ranges
+ }
+
+ long[] boundaries = boundaries();
+
+ // First check if we've "advanced" beyond the last elementary interval we
counted for this doc.
+ // If we haven't, there's no sense doing anything else:
+ if (multiValuedDocLastSeenElementaryInterval != -1
+ && v <= boundaries[multiValuedDocLastSeenElementaryInterval]) {
+ return;
}
- if (node.outputs != null) {
- for (int rangeIndex : node.outputs) {
- counts[rangeIndex] += count;
+
+ // Also check if we've already counted the last elementary interval. If
so, there's nothing
+ // else to count for this doc:
+ final int nextCandidateElementaryInterval =
multiValuedDocLastSeenElementaryInterval + 1;
+ if (nextCandidateElementaryInterval == boundaries.length) {
+ return;
+ }
+
+ // Binary search in the range of the next candidate interval up to the
last interval:
+ int lo = nextCandidateElementaryInterval;
+ int hi = boundaries.length - 1;
+ while (true) {
+ int mid = (lo + hi) >>> 1;
+ if (v <= boundaries[mid]) {
+ if (mid == nextCandidateElementaryInterval) {
+ processMultiValuedHit(mid);
+ multiValuedDocLastSeenElementaryInterval = mid;
+ return;
+ } else {
+ hi = mid - 1;
+ }
+ } else if (v > boundaries[mid + 1]) {
+ lo = mid + 1;
+ } else {
+ int idx = mid + 1;
+ processMultiValuedHit(idx);
+ multiValuedDocLastSeenElementaryInterval = idx;
+ return;
}
}
- // System.out.println(" rollup node=" + node.start + " to " + node.end +
": count=" + count);
- return count;
}
- private static LongRangeNode split(int start, int end, List<InclusiveRange>
elementaryIntervals) {
- if (start == end - 1) {
- // leaf
- InclusiveRange range = elementaryIntervals.get(start);
- return new LongRangeNode(range.start, range.end, null, null, start);
- } else {
- int mid = (start + end) >>> 1;
- LongRangeNode left = split(start, mid, elementaryIntervals);
- LongRangeNode right = split(mid, end, elementaryIntervals);
- return new LongRangeNode(left.start, right.end, left, right, -1);
- }
+ /**
+ * Finish processing all documents. This will return the number of docs that
didn't contribute to
+ * any ranges (that weren't already reported when calling
endMultiValuedDoc()).
+ */
+ abstract int finish();
+
+ /** Provide boundary information for elementary intervals (max inclusive
value per interval) */
+ protected abstract long[] boundaries();
+
+ /** Process a single-value "hit" against an elementary interval. */
+ protected abstract void processSingleValuedHit(int elementaryIntervalNum);
+
+ /** Process a multi-value "hit" against an elementary interval. */
+ protected abstract void processMultiValuedHit(int elementaryIntervalNum);
+
+ /** Increment the specified range by one. */
+ protected final void increment(int rangeNum) {
+ countBuffer[rangeNum]++;
}
- private static final class InclusiveRange {
- public final long start;
- public final long end;
+ /** Increment the specified range by the specified count. */
+ protected final void increment(int rangeNum, int count) {
+ countBuffer[rangeNum] += count;
+ }
- public InclusiveRange(long start, long end) {
- assert end >= start;
- this.start = start;
- this.end = end;
+ /** Number of ranges requested by the caller. */
+ protected final int rangeCount() {
+ return countBuffer.length;
+ }
+
+ /** Determine whether-or-not any requested ranges overlap */
+ private static boolean hasOverlappingRanges(LongRange[] ranges) {
+ if (ranges.length == 0) {
+ return false;
}
- @Override
- public String toString() {
- return start + " to " + end;
+ // Copy before sorting so we don't mess with the caller's original ranges:
+ LongRange[] sortedRanges = new LongRange[ranges.length];
+ System.arraycopy(ranges, 0, sortedRanges, 0, ranges.length);
+ Arrays.sort(sortedRanges, Comparator.comparingLong(r -> r.min));
+
+ long previousMax = sortedRanges[0].max;
+ for (int i = 1; i < sortedRanges.length; i++) {
+ // Ranges overlap if the next min is <= the previous max (note that
LongRange models
+ // closed ranges, so equal limit points are considered overlapping):
Review comment:
Thanks!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
