github-advanced-security[bot] commented on code in PR #19138: URL: https://github.com/apache/druid/pull/19138#discussion_r3592659624
########## processing/src/main/java/org/apache/druid/timeline/IntervalTreeMap.java: ########## @@ -0,0 +1,860 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.druid.timeline; + +import com.google.common.base.Predicate; +import org.jetbrains.annotations.NotNull; +import org.jetbrains.annotations.Nullable; +import org.jetbrains.annotations.VisibleForTesting; +import org.joda.time.Interval; + +import java.util.AbstractMap; +import java.util.AbstractSet; +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Locale; +import java.util.Map; +import java.util.NavigableMap; +import java.util.NavigableSet; +import java.util.Set; +import java.util.SortedMap; +import java.util.function.BiConsumer; + +/** + * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree) + * Custom optimizations for faster interval search and additional support for specific joda Interval comparator + * arithmetic used in the project. Additionally, it implements NavigableMap interface with relevant methods for + * traversal of the entries. + * <p> + * <p> + * Multiple different intervals can be added to the tree. It can then be searched to find all intervals matching a given + * interval. The user specifies the match condition, such as encompassing the given interval, overlapping, etc. The + * search can return multiple results as multiple intervals in the tree could match the criteria. + * <p> + * Using the tree, reduces the search time from O(N) iterating through all the intervals, to roughly O(log2(N)). + * Furthermore, a value can be associated with each interval, which is also returned in the search result. + * + * <p> + * The tree is a binary search tree sorted by interval start time. The intervals are stored as nodes in the tree. + * Additional state containing the minimum and maximum interval bounds of the entire subtree under a node is also + * stored in each node. This helps speed up the search for matching intervals by skipping unsuitable subtrees that will + * not contain a matching candidate interval. + * <p> + * To optimize the balancing cost w.r.t the operation time, the tree is not balanced on every modification operation. + * Rather, a configurable imbalance tolerance from the theoretical ideal height of log2(N) is allowed, breaching which + * triggers the rebalance. + * <p> + * Not thread safe. + * <p> + */ +public class IntervalTreeMap<T> extends AbstractMap<Interval, T> implements NavigableMap<Interval, T> +{ + // The compartor for comparing the interval start timnes + private final Comparator<Interval> startComparator; + // The comparator for comparing interval end times + private final Comparator<Interval> endComparator; + + @VisibleForTesting + private Node<T> root; + private int size; + + // Deviation allowed from ideal height for the maximum height on either side of the tree, expressed as a + // percentage of ideal height + private int imbalanceTolerance = 50; + + private final EntrySet entrySet = new EntrySet(); + + public IntervalTreeMap(Comparator<Interval> startComparator, Comparator<Interval> endComparator) + { + this.startComparator = startComparator; + this.endComparator = endComparator; + } + + public int getImbalanceTolerance() + { + return imbalanceTolerance; + } + + public void setImbalanceTolerance(int imbalanceTolerance) + { + this.imbalanceTolerance = imbalanceTolerance; + } + + static class Node<T> implements Map.Entry<Interval, T> + { + Interval interval; + T value; + int height; + // The full interval range of the subtree formed by this Node + Interval range; + Node<T> parent; + Node<T> left; + Node<T> right; + + private static final String PRINT_FORMAT = "{\n" + + "%sinterval = %s\n" + + "%svalue = %s\n" + + "%sheight = %d\n" + + "%srange = %s\n" + + "%sleft = %s\n" + + "%sright = %s\n" + + "%s}"; + + private String print(int level) + { + String prefix = "\t".repeat(level); + String eprefix = "\t".repeat(level - 1); + return String.format(Locale.ENGLISH, PRINT_FORMAT, + prefix, interval, prefix, value, prefix, height, + prefix, range, + prefix, (left != null) ? left.print(level + 1) : null, + prefix, (right != null) ? right.print(level + 1) : null, + eprefix + ); + } + + @Override + public Interval getKey() + { + return interval; + } + + @Override + public T getValue() + { + return value; + } + + @Override + public T setValue(T value) + { + T oldValue = this.value; + this.value = value; + return oldValue; + } + } + + @Override + public T put(Interval interval, T value) + { + //root = insert(root, interval, value); + T oldValue = insert(null, false, interval, value); + checkRebalance(); + return oldValue; + } + + private T insert(Node<T> parent, boolean left, Interval interval, T value) + { + // Passing parent so that when a new node is created, it can be added to parent, and we can still use return value + // for another purpose, namely returning the old value if the key already exists in the tree + Node<T> node; + if (parent == null) { + node = root; + } else if (left) { + node = parent.left; + } else { + node = parent.right; + } + + if (node == null) { + node = new Node<>(); + node.interval = interval; + node.value = value; + node.height = 0; + node.range = interval; + if (root == null) { + root = node; + } else if (left) { + setLeftNode(parent, node); + } else { + setRightNode(parent, node); + } + ++size; + return null; + } + + T oldValue; + + int cmp = compareInterval(interval, node.interval); + + // If exact interval already exists, just replace the value and return + if (cmp == 0) { + oldValue = node.value; + node.value = value; + return oldValue; + } + + if (cmp < 0) { + // Go to the left + oldValue = insert(node, true, interval, value); + } else { + // Go to the right + oldValue = insert(node, false, interval, value); + } + recomputeState(node); + + //return node; + return oldValue; + } + + @Override + public T get(Object key) + { + if (!Interval.class.isAssignableFrom(key.getClass())) { + throw new ClassCastException("key must be an instance of Interval"); + } + Interval interval = (Interval) key; + + T value = null; + Node<T> node = root; + while (node != null) { + int cmp = compareInterval(node.getKey(), interval); + if (cmp == 0) { + value = node.value; + break; + } else if (cmp > 0) { + node = node.left; + } else { + node = node.right; + } + } + return value; + } + + private int compareInterval(Interval interval1, Interval interval2) + { + int cmp = startComparator.compare(interval1, interval2); + if (cmp == 0) { + return endComparator.compare(interval1, interval2); + } + return cmp; + } + + public Map<Interval, T> findEncompassing(Interval interval) + { + return findMatching(i -> i.contains(interval)); + } + + public Map<Interval, T> findOverlapping(Interval interval) + { + return findMatching(i -> i.overlaps(interval)); + } + + /** + * Get all entries matching a given condition + * @param condition The match condition + * + * This condition should not only return true when a node matches the condition but also when a child node range + * matches. It is a convenience method for {@link #forEachMatching(Predicate, Predicate, BiConsumer)} and see the + * method's documentation for more information. It calls the method with rangeCondition set to be same as condition. + */ + public Map<Interval, T> findMatching(Predicate<Interval> condition) + { + Map<Interval, T> result = new HashMap<>(); + forEachMatching(condition, result::put); + return result; + } + + /** + * Find entries matching a given condition by doing a full traversal. + * @param condition The match condition + * + * The method traverses through all the nodes of the tree looking for matches. + */ + public Map<Interval, T> findMatchingFullTraversal(Predicate<Interval> condition) + { + Map<Interval, T> result = new HashMap<>(); + forEachMatchingFullTraversal(condition, result::put); + return result; + } + + /** + * Perform on action for matching nodes. + * @param condition The match condition + * @param action The action + * + * This condition should not only return true when a node matches the condition but also when the child node range + * matches. It is a convenience method for {@link #forEachMatching(Predicate, Predicate, BiConsumer)} and see the + * method's documentation for more information. It calls the method with rangeCondition set to be same as condition. + */ + public void forEachMatching(Predicate<Interval> condition, BiConsumer<Interval, T> action) + { + forEachMatching(condition, condition, action); + } + + /** + * Perform on action for matching nodes by doing a full traversal. + * @param condition The match condition + * @param action The action + * + * The method traverses through all the nodes of the tree looking for matches. + */ + public void forEachMatchingFullTraversal(Predicate<Interval> condition, BiConsumer<Interval, T> action) + { + forEachMatching(condition, null, action); + } + + /** + * Perform an action for matching nodes + * @param condition The condition to match for the node + * @param rangeCondition The condition to check a child node for, to determine whether to traverse the subtree + * @param action The action to perform + * + * The rangeCondition is applied on the interval range of the child node and only if the condition returns true is the + * child subtree traversed. Interval range is the min start time to max end time for all the nodes in the child + * subtree. This is a lookup speedup optimization. If rangeCondition is null, the check is skipped and all the + * children are traversed to find matches. + * + * In some cases such as finding nodes overlapping the given interval or encompassing the given interval, the same + * predicate can be used for condition and rangeCondition. In other situations a full traversal maybe needed and a + * null can be passed in for rangeCondition. There are helper methods for these. + */ + public void forEachMatching(Predicate<Interval> condition, Predicate<Interval> rangeCondition, BiConsumer<Interval, T> action) + { + forEachMatching(root, condition, rangeCondition, action); + } + + private void forEachMatching(Node<T> node, Predicate<Interval> condition, Predicate<Interval> rangeCondition, BiConsumer<Interval, T> action) + { + + if (node == null) { + return; + } + + // Process in-order + + // Search left + if ((node.left != null) && ((rangeCondition == null) || rangeCondition.apply(node.left.range))) { + forEachMatching(node.left, condition, rangeCondition, action); + } + + if (condition.apply(node.interval)) { + action.accept(node.interval, node.value); + } + + // Search right + if (node.right != null && ((rangeCondition == null) || rangeCondition.apply(node.right.range))) { + forEachMatching(node.right, condition, rangeCondition, action); + } + } + + @Override + public T remove(Object key) Review Comment: ## Confusing overloading of methods Method IntervalTreeMap.remove(..) could be confused with overloaded method [remove](1), since dispatch depends on static types. [Show more details](https://github.com/apache/druid/security/code-scanning/11342) -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
