Package io.keikaiex.util

Class IntervalTree<T>

java.lang.Object

io.keikaiex.util.RBTree<Integer,Integer>

io.keikaiex.util.IntervalTree<T>

All Implemented Interfaces:

Serializable

public class IntervalTree<T>
extends RBTree<Integer,Integer>

An extensible Interval Tree that you can keep payload of type [T] in Interval. https://en.wikipedia.org/wiki/Interval_tree

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor	Description
IntervalTree(int maxLimit)

Method Summary

Modifier and Type	Method	Description
protected boolean	canDeleteNode(io.keikaiex.util.RBNode<Integer,Integer> n, Object ctx)
Collection<Interval<T>>	contained(Interval<T> interval)
Collection<Interval<T>>	contains(Interval<T> interval)
Interval<T>	deleteInterval(Interval<T> interval, Object context)
protected void	fixUp(List<io.keikaiex.util.RBTree.Traversal<Integer,Integer>> lineal)
protected void	insertDuplicate(io.keikaiex.util.RBNode<Integer,Integer> original, io.keikaiex.util.RBNode<Integer,Integer> newone, Object context)
Interval<T>	insertInterval(Interval<T> interval, Object context)
protected void	insertLeft(io.keikaiex.util.RBNode<Integer,Integer> parent, io.keikaiex.util.RBNode<Integer,Integer> child)
protected void	insertRight(io.keikaiex.util.RBNode<Integer,Integer> parent, io.keikaiex.util.RBNode<Integer,Integer> child)
protected void	leftJumpUp(io.keikaiex.util.RBNode<Integer,Integer> g)
Collection<Interval<T>>	overlaps(Interval<T> interval)
protected void	replaceNode(io.keikaiex.util.RBNode<Integer,Integer> target, io.keikaiex.util.RBNode<Integer,Integer> substitute)
protected void	rightJumpUp(io.keikaiex.util.RBNode<Integer,Integer> g)
protected void	rotateLeft(io.keikaiex.util.RBNode<Integer,Integer> g)
protected void	rotateRight(io.keikaiex.util.RBNode<Integer,Integer> g)
Interval<T>	searchInterval(Interval<T> interval)

Methods inherited from class io.keikaiex.util.RBTree

delete, insert, isEmpty, search

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

IntervalTree

public IntervalTree(int maxLimit)

Method Detail

insertInterval

public Interval<T> insertInterval(Interval<T> interval,
                                  Object context)

deleteInterval

public Interval<T> deleteInterval(Interval<T> interval,
                                  Object context)

searchInterval

public Interval<T> searchInterval(Interval<T> interval)

contains

public Collection<Interval<T>> contains(Interval<T> interval)

contained

public Collection<Interval<T>> contained(Interval<T> interval)

overlaps

public Collection<Interval<T>> overlaps(Interval<T> interval)

insertDuplicate

protected void insertDuplicate(io.keikaiex.util.RBNode<Integer,Integer> original,
                               io.keikaiex.util.RBNode<Integer,Integer> newone,
                               Object context)

Overrides:

insertDuplicate in class RBTree<Integer,Integer>

insertLeft

protected void insertLeft(io.keikaiex.util.RBNode<Integer,Integer> parent,
                          io.keikaiex.util.RBNode<Integer,Integer> child)

Overrides:

insertLeft in class RBTree<Integer,Integer>

insertRight

protected void insertRight(io.keikaiex.util.RBNode<Integer,Integer> parent,
                           io.keikaiex.util.RBNode<Integer,Integer> child)

Overrides:

insertRight in class RBTree<Integer,Integer>

rightJumpUp

protected void rightJumpUp(io.keikaiex.util.RBNode<Integer,Integer> g)

Overrides:

rightJumpUp in class RBTree<Integer,Integer>

leftJumpUp

protected void leftJumpUp(io.keikaiex.util.RBNode<Integer,Integer> g)

Overrides:

leftJumpUp in class RBTree<Integer,Integer>

rotateRight

protected void rotateRight(io.keikaiex.util.RBNode<Integer,Integer> g)

Overrides:

rotateRight in class RBTree<Integer,Integer>

rotateLeft

protected void rotateLeft(io.keikaiex.util.RBNode<Integer,Integer> g)

Overrides:

rotateLeft in class RBTree<Integer,Integer>

fixUp

protected void fixUp(List<io.keikaiex.util.RBTree.Traversal<Integer,Integer>> lineal)

Overrides:

fixUp in class RBTree<Integer,Integer>

replaceNode

protected void replaceNode(io.keikaiex.util.RBNode<Integer,Integer> target,
                           io.keikaiex.util.RBNode<Integer,Integer> substitute)

canDeleteNode

protected boolean canDeleteNode(io.keikaiex.util.RBNode<Integer,Integer> n,
                                Object ctx)