aweisberg commented on code in PR #4042:
URL: https://github.com/apache/cassandra/pull/4042#discussion_r2114447024
##########
src/java/org/apache/cassandra/utils/IntervalTree.java:
##########
@@ -468,46 +749,140 @@ else if (center.compareTo(searchInterval.max) > 0)
right.searchInternal(searchInterval, results);
}
}
- }
- private class TreeIterator extends AbstractIterator<I>
- {
- private final Deque<IntervalNode> stack = new
ArrayDeque<IntervalNode>();
- private Iterator<I> current;
- TreeIterator(IntervalNode node)
+ private IntervalNode replace(IntervalNode node, List<Pair<I, I>>
replacements)
{
- super();
- gotoMinOf(node);
- }
+ if (node == null || replacements.isEmpty())
+ return node;
- protected I computeNext()
- {
- while (true)
- {
- if (current != null && current.hasNext())
- return current.next();
+ List<Pair<I, I>> leftSegment = new ArrayList<>();
+ List<Pair<I, I>> rightSegment = new ArrayList<>();
+ List<I> newIntersectsLeft = null;
+ List<I> newIntersectsRight = null;
+ int updated = 0;
- IntervalNode node = stack.pollFirst();
- if (node == null)
- return endOfData();
+ for (Pair<I, I> entry : replacements)
+ {
+ I intervalToRemove = entry.left;
+ I intervalToAdd = entry.right;
+ if (node.center.compareTo(intervalToRemove.min) < 0)
+ {
+ rightSegment.add(entry);
+ }
+ else if (node.center.compareTo(intervalToRemove.max) > 0)
+ {
+ leftSegment.add(entry);
+ }
+ else
+ {
+ // only init once if any interval resides in current node
+ if (newIntersectsLeft == null)
+ {
+ newIntersectsLeft = new
ArrayList<>(node.intersectsLeft);
+ newIntersectsRight = new
ArrayList<>(node.intersectsRight);
+ }
+ boolean leftUpdated = false;
+ boolean rightUpdated = false;
+
+ int i = Interval.<C,
D>minOrdering().binarySearchAsymmetric(node.intersectsLeft,
intervalToRemove.min, Op.CEIL);
+ while (i < node.intersectsLeft.size())
+ {
+ if
(node.intersectsLeft.get(i).equals(intervalToRemove))
+ {
+ newIntersectsLeft.set(i, intervalToAdd);
+ leftUpdated = true;
+ break;
+ }
+ i++;
+ }
+
+ int j = Interval.<C,
D>maxOrdering().binarySearchAsymmetric(node.intersectsRight,
intervalToRemove.max, Op.CEIL);
+ while (j < node.intersectsRight.size())
+ {
+ if
(node.intersectsRight.get(j).equals(intervalToRemove))
+ {
+ newIntersectsRight.set(j, intervalToAdd);
+ rightUpdated = true;
+ break;
+ }
+ j++;
+ }
+ assert leftUpdated && rightUpdated : "leftupdated = " +
leftUpdated + ", rightupdated = " + rightUpdated;
+ updated++;
+ }
+ }
- current = node.intersectsLeft.iterator();
+ assert leftSegment.size() + rightSegment.size() + updated ==
replacements.size() :
+ "leftSegment size (" + leftSegment.size() + ") + rightSegment size
(" + rightSegment.size() +
+ ") + updated (" + updated + ") != replacementMap size (" +
replacements.size() + ')';
+ return new IntervalNode(node.center,
+ node.low,
+ node.high,
+ newIntersectsLeft != null ?
newIntersectsLeft : node.intersectsLeft,
+ newIntersectsRight != null ?
newIntersectsRight : node.intersectsRight,
+ replace(node.left, leftSegment),
+ replace(node.right, rightSegment));
+ }
- // We know this is the smaller not returned yet, but before
doing
- // its parent, we must do everyone on it's right.
- gotoMinOf(node.right);
- }
+ private IntervalNode add(Collection<I> intervals)
+ {
+ return add(this, intervals);
}
- private void gotoMinOf(IntervalNode node)
+ private IntervalNode add(IntervalNode root, Collection<I> intervals)
{
- while (node != null)
+ if (intervals.isEmpty())
+ return root;
+
+ if (root == null)
+ {
+ List<I> minSortedIntervals = new ArrayList<>(intervals);
+ Collections.sort(minSortedIntervals, Interval.minOrdering());
+ List<I> maxSortedIntervals = new ArrayList<>(intervals);
+ Collections.sort(maxSortedIntervals, Interval.maxOrdering());
+ return new IntervalNode(minSortedIntervals,
maxSortedIntervals);
+ }
+
+ List<I> leftSegment = new ArrayList<>();
+ List<I> rightSegment = new ArrayList<>();
+ C newLow = root.low;
+ C newHigh = root.high;
+ List<I> newIntersectsLeft = new ArrayList<>(root.intersectsLeft);
+ List<I> newIntersectsRight = new ArrayList<>(root.intersectsRight);
+ for (I i : intervals)
{
- stack.offerFirst(node);
- node = node.left;
+ newLow = newLow.compareTo(i.min) < 0 ? newLow : i.min;
+ newHigh = newHigh.compareTo(i.max) > 0 ? newHigh : i.max;
+ if (i.max.compareTo(root.center) < 0)
+ {
+ leftSegment.add(i);
+ }
+ else if (i.min.compareTo(root.center) > 0)
+ {
+ rightSegment.add(i);
+ }
+ else
+ {
+ int leftIdx = Collections.binarySearch(newIntersectsLeft,
i, Interval.minOrdering());
Review Comment:
Asymmetric solves the problem of the search being on a list of elements that
is not the same type as the key and doesn't compare all the fields. This is
fine when building an entire tree from scratch, but for add/replace there was
the issue of having to deal with duplicates which I recall not allowing.
However identity for detecting duplicates doesn't use object identity it
requires the comparator for the interval to enforce identity so you don't want
to use the asymmetric search in that case because it won't tell you the correct
position and if the interval is already there.
--
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.
To unsubscribe, e-mail: pr-unsubscr...@cassandra.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscr...@cassandra.apache.org
For additional commands, e-mail: pr-h...@cassandra.apache.org
