Yukei7 commented on code in PR #4042:
URL: https://github.com/apache/cassandra/pull/4042#discussion_r2072225068
##########
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:
may I ask why we use `Collections.binarySearch` here but
`minOrdering().binarySearchAsymmetric` above?
##########
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);
Review Comment:
line 851-852 maybe let's do the same as line 759-760, and we re-init this
list only when something needs to be changed. then
```
return new IntervalNode(root.center,
newLow,
newHigh,
newIntersectsLeft != null ? newIntersectsLeft :
root.intersectsLeft,
newIntersectsRight != null ? newIntersectsRight :
root.intersectsRight,
add(root.left, leftSegment),
add(root.right, rightSegment));
```
--
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
