github-advanced-security[bot] commented on code in PR #19138: URL: https://github.com/apache/druid/pull/19138#discussion_r2921346381
########## processing/src/main/java/org/apache/druid/timeline/IntervalTree.java: ########## @@ -0,0 +1,797 @@ +/* + * 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.apache.druid.java.util.common.StringUtils; +import org.jetbrains.annotations.NotNull; +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.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 + * <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 IntervalTree<T> extends AbstractMap<Interval, T> implements NavigableMap<Interval, T> +{ + // The compartor for comparing the interval start timnes + Comparator<Interval> startComparator; + // The comparator for comparing interval end times + Comparator<Interval> endComparator; + + @VisibleForTesting + Node<T> root; + int size; + + // Deviation allowed from ideal height for the maximum height on either side of the tree, expressed as a + // percentage of ideal height + int imbalanceTolerance = 50; + + EntrySet entrySet = new EntrySet(); + + public IntervalTree(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}"; + + public String print(int level) + { + String prefix = "\t".repeat(level); + String eprefix = "\t".repeat(level - 1); + return StringUtils.format(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(interval, node.interval); + if (cmp == 0) { + value = node.value; + break; + } + 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)); + } + + public Map<Interval, T> findMatching(Predicate<Interval> condition) + { + Map<Interval, T> result = new HashMap<>(); + forEachMatching(condition, result::put); + return result; + } + + public void forEachMatching(Predicate<Interval> condition, BiConsumer<Interval, T> action) + { + forEachMatching(root, condition, action); + } + + private void forEachMatching(Node<T> node, Predicate<Interval> condition, BiConsumer<Interval, T> action) + { + + if (node == null) { + return; + } + + // Process in-order + + // Search left + if ((node.left != null) && condition.apply(node.left.range)) { + forEachMatching(node.left, condition, action); + } + + if (condition.apply(node.interval)) { + action.accept(node.interval, node.value); + } + + // Search right + if (node.right != null && condition.apply(node.right.range)) { + forEachMatching(node.right, condition, action); + } + } + + @Override + public T remove(Object key) Review Comment: ## Confusing overloading of methods Method IntervalTree.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/10882) -- 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]
