TreeJuxtaposer
Class RangeTree

java.lang.Object
  |
  +--TreeJuxtaposer.RangeTree

public class RangeTree

extends java.lang.Object

A class representing a two-dimensional orthogonal range tree. RangeTree is a class that can answer range query in time (log n)^2. It implements the data structure of 2D range tree. Nodes of this tree are objects of type RangeNode.

Author:

Yunhong Zhou

See Also:

RangeNode, Tree2Tree, AccordionDrawer.Tree, AccordionDrawer.TreeNode

Field Summary

(package private) int	element
(package private) RangeNode	root

Constructor Summary

RangeTree(Point[] A, int dim)
Constructor: calls RangeTreeBuild to build the tree

RangeTree(Tree treeA, Tree treeB, Tree2Tree t2t)
constructor: builds a 2D RangeTree data structure.

Method Summary

(package private) RangeNode	build1D(Point[] A, int start, int end) builds a 1D range tree using points from A[start] to A[end].
RangeNode	build2D(Point[] A, int start, int end) builds a 2D range tree using points from A[start] to A[end].
(package private) void	Build2DRangeTree(Point[] A, int dim)
private RangeNode	findSplitRangeNode(int low, int high) Find a RangeNode with element in the range [low, high].
int	getElement()
RangeNode	getRoot()
boolean	isEmpty()
static void	mergeSort(Point[] A, int dim) This implements a regular merge sort algorithm.
private static void	ms_conq(Point[] A, int start, int mid, int end, int dim) the conquer procedure merges two sorted parts together.
private static void	ms_divide(Point[] A, int start, int end, int dim) the divide procedure divides the array into two parts, sort them separately, and then merge the two sorted parts together.
private int	query1D(int ylow, int yhigh) the function queries in Y coordinate and return the total number of points in a given interval range.
int	query2D(int xlow, int xhigh, int ylow, int yhigh) Query2D returns the total number of points contained in the window [xlow, xhigh] X [ylow, yhigh].
private static int	reportSubRangeTree(RangeNode l) will report all the leaves decedant to RangeNode l.

Methods inherited from class java.lang.Object

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

Field Detail

root

RangeNode root

element

int element

Constructor Detail

RangeTree

public RangeTree(Tree treeA,
                 Tree treeB,
                 Tree2Tree t2t)

constructor: builds a 2D RangeTree data structure. Given two trees, in the first step the constructor computes the total number of common nodes for these trees, and in the second step it extracts all the common nodes from these two trees and stores it into a data structure called nodes, and in the third step the constructor calls another function RangeTreeBuild to build the range tree using nodes.

Parameters:

treeA - the first tree

treeB - the second tree

t2t - we're using the function getBestCorrNode of class Tree2Tree

RangeTree

public RangeTree(Point[] A,
                 int dim)

Constructor: calls RangeTreeBuild to build the tree

Parameters:

dim - dim = 0 represents a 2D range tree, dim = 1 represents a 1D range tree. This notation is not intuitive.

A - an array of points

Method Detail

Build2DRangeTree

void Build2DRangeTree(Point[] A,
                      int dim)

Parameters:

dim - dim = 0 represents a 2D range tree, dim = 1 represents a 1D range tree. This notation is not intuitive.

A - an array of points

isEmpty

public boolean isEmpty()

getRoot

public RangeNode getRoot()

Returns:

root

getElement

public int getElement()

Returns:

element

build1D

RangeNode build1D(Point[] A,
                  int start,
                  int end)

builds a 1D range tree using points from A[start] to A[end]. Assume the A is sorted by Y coordinate. This will set the elemnt of the leaf(Y coordinate).

Parameters:

A - a list of points

start - the start position from array A

end - the end position from array A

build2D

public RangeNode build2D(Point[] A,
                         int start,
                         int end)

builds a 2D range tree using points from A[start] to A[end]. First build an array for the associated 1D tree, and then sort the array by Y coordinate, and create an associated tree by build1D. Seting children by calling the function recursively.

Parameters:

A - an array of points

start - the start position from the array

end - the end position from the array

findSplitRangeNode

private RangeNode findSplitRangeNode(int low,
                                     int high)

Find a RangeNode with element in the range [low, high]. This function is used for query process.

Parameters:

low - the lowest value of the range

high - the highest value of the range

query2D

public int query2D(int xlow,
                   int xhigh,
                   int ylow,
                   int yhigh)

Query2D returns the total number of points contained in the window [xlow, xhigh] X [ylow, yhigh]. If find a childless point in [xlow, xhigh], then check its Y coordinate. First check left side of split leaf, then the right side. If left is good, then all the right side is good too. if left is not good, go a little right.

Parameters:

xlow - the leftmost value of x coordinate

xhigh - the rightmost value of x coordinate

ylow - the lowest value of y coordinate

yhigh - the highest value of y coordinate

Returns:

the total number of points contained in the window range

query1D

private int query1D(int ylow,
                    int yhigh)

the function queries in Y coordinate and return the total number of points in a given interval range.

Parameters:

ylow - the lowest value of Y coordinate

yhigh - the highest value of Y coordinate

Returns:

the total number of points in the range [ylow, yhigh]

See Also:

query2D(int, int, int, int)

reportSubRangeTree

private static int reportSubRangeTree(RangeNode l)

will report all the leaves decedant to RangeNode l. This function is called during the query process when we find that the whole subtree under l is contained in the query window.

Parameters:

l - should be 1D RangeNode

mergeSort

public static void mergeSort(Point[] A,
                             int dim)

This implements a regular merge sort algorithm. It is added as a static method, so no additional class is needed.

Parameters:

A - an array to be sorted

dim - the corresponding coordinate that sorting is based on

ms_divide

private static void ms_divide(Point[] A,
                              int start,
                              int end,
                              int dim)

the divide procedure divides the array into two parts, sort them separately, and then merge the two sorted parts together.

Parameters:

A - the array to be sorted

start - the start position of the array

end - the end position of the array

dim - the corresponding coordinate that sorting is based on

ms_conq

private static void ms_conq(Point[] A,
                            int start,
                            int mid,
                            int end,
                            int dim)

the conquer procedure merges two sorted parts together. The mid value partitions the array into two parts: [low, mid] and [mid+1, end], each part is already sorted.

Parameters:

A - the array to be sorted

start - the start position of the array

end - the end position of the array

mid - the mid value

dim - the corresponding coordinate that sorting is based on