org.utgenome.gwt.utgb.client.canvas
Class PrioritySearchTree<E>

java.lang.Object
  org.utgenome.gwt.utgb.client.canvas.PrioritySearchTree<E>

All Implemented Interfaces:

Iterable<E>

public class PrioritySearchTree<E>
extends Object
implements Iterable<E>

Priority search tree for efficient 2D search

Author:

leo

Nested Class Summary

class	PrioritySearchTree.Node
static interface	PrioritySearchTree.ResultHandler<E>
static interface	PrioritySearchTree.Visitor<E>

Constructor Summary

PrioritySearchTree()

PrioritySearchTree(int lowerBoundOfX, int upperBoundOfX, int lowerBoundOfY, int upperBoundOfY)

Method Summary

void	clear()
void	depthFirstSearch(PrioritySearchTree.Visitor<E> visitor)
void	insert(E elem, int x, int y) Insert a new node
Iterator<E>	iterator()
List<E>	rangeQuery(int x1, int x2, int upperY) Retrieves elements contained in the specified range, (X:[x1, x2], Y:[ , upperY]).
void	rangeQuery(int x1, int x2, int upperY, PrioritySearchTree.ResultHandler<E> handler)
boolean	remove(E elem, int x, int y) Remove the specified node
int	size()

Methods inherited from class java.lang.Object

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

Constructor Detail

PrioritySearchTree

public PrioritySearchTree()

PrioritySearchTree

public PrioritySearchTree(int lowerBoundOfX,
                          int upperBoundOfX,
                          int lowerBoundOfY,
                          int upperBoundOfY)

Method Detail

iterator

public Iterator<E> iterator()

Specified by:

iterator in interface Iterable<E>

depthFirstSearch

public void depthFirstSearch(PrioritySearchTree.Visitor<E> visitor)

clear

public void clear()

size

public int size()

rangeQuery

public List<E> rangeQuery(int x1,
                          int x2,
                          int upperY)

Retrieves elements contained in the specified range, (X:[x1, x2], Y:[ , upperY]). This query is useful for answering the interval intersection problem.

Parameters:

x1 -

x2 -

upperY -

Returns:

elements contained in the range (X:[x1, x2], Y:[ , upperY])

rangeQuery

public void rangeQuery(int x1,
                       int x2,
                       int upperY,
                       PrioritySearchTree.ResultHandler<E> handler)

insert

public void insert(E elem,
                   int x,
                   int y)

Insert a new node

Parameters:

elem -

remove

public boolean remove(E elem,
                      int x,
                      int y)

Remove the specified node

Parameters:

elem -

Returns:

true if the specified element exists in the tree