pirvtech commented on code in PR #19138: URL: https://github.com/apache/druid/pull/19138#discussion_r3687103794
########## processing/src/main/java/org/apache/druid/timeline/IntervalTreeMap.java: ########## @@ -0,0 +1,875 @@ +/* + * 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.VisibleForTesting; +import org.joda.time.Interval; +import org.joda.time.base.BaseInterval; + +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; + + private int imbalanceTolerance; + + private final EntrySet entrySet = new EntrySet(); + + public IntervalTreeMap() + { + this(Comparator.comparingLong(BaseInterval::getStartMillis), + Comparator.comparingLong(BaseInterval::getEndMillis)); + } + + public IntervalTreeMap(Comparator<Interval> startComparator, Comparator<Interval> endComparator) + { + this(startComparator, endComparator, 50); + } + + public IntervalTreeMap(Comparator<Interval> startComparator, Comparator<Interval> endComparator, int imbalanceTolerance) + { + this.startComparator = startComparator; + this.endComparator = endComparator; + this.imbalanceTolerance = imbalanceTolerance; + } + + /** + * Returns the allowed tolerance between the right and left branches of the tree before triggering a rebalance. + * The tolerance is expressed as a percentage deviation from ideal tree height. + * @return The imbalance tolerance + */ + public int getImbalanceTolerance() + { + return imbalanceTolerance; + } + + public void setImbalanceTolerance(int imbalanceTolerance) Review Comment: It can be modified after construction to change the threshold. -- 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]
