Class IntervalTree<V>

  • All Implemented Interfaces:
    Iterable<IntervalTree.Node<V>>

    public class IntervalTree<V>
    extends Object
    implements Iterable<IntervalTree.Node<V>>
    A Red-Black tree with intervals for keys. Not thread-safe, and cannot be made so. 7/24/2008: This was copied from the tedUtils package. IMPORTANT!!! It has been modified to use the Reseq way of handling coordinates (end-inclusive).
    • Constructor Detail

      • IntervalTree

        public IntervalTree()
    • Method Detail

      • size

        public int size()
        Return the number of intervals in the tree.
        Returns:
        The number of intervals.
      • clear

        public void clear()
        Remove all entries.
      • put

        public V put​(int start,
                     int end,
                     V value)
        Put a new interval into the tree (or update the value associated with an existing interval). If the interval is novel, the special sentinel value is returned.
        Parameters:
        start - The interval's start.
        end - The interval's end.
        value - The associated value.
        Returns:
        The old value associated with that interval, or the sentinel.
      • remove

        public V remove​(int start,
                        int end)
        Remove an interval from the tree. If the interval does not exist in the tree the special sentinel value is returned.
        Parameters:
        start - The interval's start.
        end - The interval's end.
        Returns:
        The value associated with that interval, or the sentinel.
      • find

        public IntervalTree.Node<V> find​(int start,
                                         int end)
        Find an interval.
        Parameters:
        start - The interval's start.
        end - The interval's end.
        Returns:
        The Node that represents that interval, or null.
      • findByIndex

        public IntervalTree.Node<V> findByIndex​(int idx)
        Find the nth interval in the tree.
        Parameters:
        idx - The rank of the interval sought (from 0 to size()-1).
        Returns:
        The Node that represents the nth interval.
      • getIndex

        public int getIndex​(int start,
                            int end)
        Find the rank of the specified interval. If the specified interval is not in the tree, then -1 is returned.
        Parameters:
        start - The interval's start.
        end - The interval's end.
        Returns:
        The rank of that interval, or -1.
      • min

        public IntervalTree.Node<V> min()
        Find the least interval in the tree.
        Returns:
        The earliest interval, or null if the tree is empty.
      • min

        public IntervalTree.Node<V> min​(int start,
                                        int end)
        Find the earliest interval in the tree greater than or equal to the specified interval.
        Parameters:
        start - The interval's start.
        end - The interval's end.
        Returns:
        The earliest >= interval, or null if there is none.
      • minOverlapper

        public IntervalTree.Node<V> minOverlapper​(int start,
                                                  int end)
        Find the earliest interval in the tree that overlaps the specified interval.
        Parameters:
        start - The interval's start.
        end - The interval's end.
        Returns:
        The earliest overlapping interval, or null if there is none.
      • max

        public IntervalTree.Node<V> max()
        Find the greatest interval in the tree.
        Returns:
        The latest interval, or null if the tree is empty.
      • max

        public IntervalTree.Node<V> max​(int start,
                                        int end)
        Find the latest interval in the tree less than or equal to the specified interval.
        Parameters:
        start - The interval's start.
        end - The interval's end.
        Returns:
        The latest >= interval, or null if there is none.
      • iterator

        public Iterator<IntervalTree.Node<V>> iterator​(int start,
                                                       int end)
        Return an iterator over all intervals greater than or equal to the specified interval.
        Parameters:
        start - The interval's start.
        end - The interval's end.
        Returns:
        An iterator.
      • overlappers

        public Iterator<IntervalTree.Node<V>> overlappers​(int start,
                                                          int end)
        Return an iterator over all intervals overlapping the specified range.
        Parameters:
        start - The range start.
        end - The range end.
        Returns:
        An iterator.
      • reverseIterator

        public Iterator<IntervalTree.Node<V>> reverseIterator()
        Return an iterator over the entire tree that returns intervals in reverse order.
        Returns:
        An iterator.
      • reverseIterator

        public Iterator<IntervalTree.Node<V>> reverseIterator​(int start,
                                                              int end)
        Return an iterator over all intervals less than or equal to the specified interval, in reverse order.
        Parameters:
        start - The interval's start.
        end - The interval's end.
        Returns:
        An iterator.
      • getSentinel

        public V getSentinel()
        Get the special sentinel value that will be used to signal novelty when putting a new interval into the tree, or to signal "not found" when removing an interval. This is null by default.
        Returns:
        The sentinel value.
      • setSentinel

        public V setSentinel​(V sentinel)
        Set the special sentinel value that will be used to signal novelty when putting a new interval into the tree, or to signal "not found" when removing an interval.
        Parameters:
        sentinel - The new sentinel value.
        Returns:
        The old sentinel value.
      • checkMaxEnds

        public void checkMaxEnds()
        This method is only for debugging. It verifies whether the tree is internally consistent with respect to the mMaxEnd cached on each node.
        Throws:
        IllegalStateException - If an inconsistency is detected.
      • printTree

        public void printTree()
        This method draws a nested picture of the tree on System.out. Useful for debugging.