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).