ch.randelshofer.segmenttree
Class SegmentTree<T extends Segment>

java.lang.Object
  ch.randelshofer.segmenttree.SegmentTree<T>

public class SegmentTree<T extends Segment>
extends java.lang.Object

SegmentTree.

Field Summary

protected java.util.ArrayList<T>	edges
protected SegmentNode<T>	root
protected java.util.ArrayList<java.lang.Integer>	sortedEndpoints

Constructor Summary

SegmentTree(java.util.ArrayList<T> edges)
Constructore for T tree

Method Summary

protected SegmentNode<T>	createTreeNode(int begin, int end)
SegmentNode<T>	getRoot()
boolean	insert(T seg)
static <T extends Segment> void	printSegmentTree(SegmentTree<T> t)
java.util.ArrayList<java.lang.Integer>	rangeQuery(int begin, int end)
boolean	remove(T seg)
java.util.ArrayList<java.lang.Integer>	stabbingQuery(int coord)

Methods inherited from class java.lang.Object

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

Field Detail

edges

protected java.util.ArrayList<T extends Segment> edges

root

protected SegmentNode<T extends Segment> root

sortedEndpoints

protected java.util.ArrayList<java.lang.Integer> sortedEndpoints

Constructor Detail

SegmentTree

public SegmentTree(java.util.ArrayList<T> edges)

Constructore for T tree

Parameters:

edges - all edges in the "world" the tree might contain

Method Detail

insert

public boolean insert(T seg)

remove

public boolean remove(T seg)

getRoot

public SegmentNode<T> getRoot()

createTreeNode

protected SegmentNode<T> createTreeNode(int begin,
                                        int end)

stabbingQuery

public java.util.ArrayList<java.lang.Integer> stabbingQuery(int coord)

rangeQuery

public java.util.ArrayList<java.lang.Integer> rangeQuery(int begin,
                                                         int end)

printSegmentTree

public static <T extends Segment> void printSegmentTree(SegmentTree<T> t)