Using JDSL


Implementing a Range Tree
 In General
 1D Integer Point Example
Input: A set of data points.
 jdsl.core.api.ObjectIterator
Task: Internally store the data.
jdsl.core.ref.ArraySequence

You might need to convert manually between container types (only once though):
ObjectIterator oi;
ArraySequence s = new ArraySequence();
while(oi.hasNext()) {
  s.insertLast(oi.nextObject());
}
Input: An ordering for those data points.
 jdsl.core.api.Comparator
 jdsl.core.ref.IntegerComparator
Task: Sort the points.
jdsl.core.algo.sorts.ArrayQuickSort

Use the JDSL algorithms to sort your data (this is why we internally store our data as a jdsl.core.api.Sequence):
IntegerComparator comp;
ArrayQuickSort quickSort = new
  ArrayQuickSort();
quickSort.sort(s, comp);
Underlying data structure: A balanced binary tree.
 jdsl.core.api.BinaryTree
 jdsl.core.ref.NodeBinaryTree
Task: Build the data structure recursively
Place the middle point at the root of the tree.  Recursively build the left and right children of this node with the first half and the second half of this sequence.  The leaves will be marked as empty.  See, for example, a balanced binary tree being built in the RangeSearch example.
Input: A query range.
 (Note: 2D objects are defined already in JDSL, for example jdsl.geomobj.api.Rectangle2D defines a 2D range.) Two points marking the minimum and maximum values of the range.
Task: Perform the query.
Search the tree for the leftmost and rightmost points in the range and then return the points inside this range by querying the ArraySequence.
Always remember to:
  • Throw exceptions as necessary: catch JDSL exceptions and throw your own, ensure the input is as expected, etc.
  • Use javadocs to document the purpose, parameters, return values, and exceptions.
  • Use JDSL's jdsl.geomobj.api.GeomTester2D for 2D geometric comparisons and jdsl.geomobj.api.GeomConstructor2D for constructing new 2D geometric objects.  If you need comparisons not provided, extend these interfaces.
  • Demostrate that your algorithm performs correctly (e.g. identically to a simple brute-force implementation) for a large number of randomly generated "typical" problems, in addition to small hand-tests (e.g. ones that test boundary instances).


This page was last updated on