Overview of the Library of Data Structures for Java (JDSL) for
instructors
The JDSL is a library of data structures, algorithms, and
interfaces to help teach data structures and algorithms, as well as
object oriented design practices to students. The JDSL allows for
great flexibility, while remaining relatively easy to use, and is
therefore suitable for may different applications.
The JDSL contains many useful interfaces and implementations not found
in other libraries.
The JDSL contains a set of interfaces for implementing tree-based data
structures. These interfaces lay down a very generic framework, and
allow for virtually any implementation of tree to fit within this
framework, from the simple binary tree to the complicated B-tree.
The JDSL contains a very rich framework for implementing graphs.
Through a hierarchy of interfaces, the framework allows for graphs to
implement as little, or as much functionality as necessary, and still be
compatible with many graph algorithms.
The JDSL contains a variety of algorithms that are ready for use.
In addition to basic (and complex) sorting algorithms, the JDSL
contains both tree traversal and graph traversal algorithms.
The JDSL contains two applications of the Proxy design pattern
described in Design Patterns (Gamma et. al., 207) called Positions
(see 3.1) and Locators (see 3.2)
Rather than having a few interfaces for each of the data structure types,
the JDSL spreads the functionality out over a heirarchy of
interfaces, allowing any data structure to fit somewhere within the JDSL. Also, the JDSL introduces the idea of a Comparator (see
3.3), which is an application of the Strategy Pattern
(Gamma et. al.). In addition, many of the algorithms use the template
method pattern (see Data Structures and Algorithms in Java
by Goodrich and Tamassia).
3.1 Positions
A Position is a formalization of the notion of place of an
element relative to others in a data structure. A position is always
defined in terms of its neighbors. A position is also associated with
an element, and the element does not change unless the user changes it
explicitly.
3.2 Locators
A Locator is a mechanism for maintaining the association between
an element and its current position in a container. A locator sticks with a specific element, even if the element changes position in
the container.
3.3 Comparators
A Comparator encapsulates a total ordering of a particular set of
elements, and allows the data structures to hold any kind of element.
This allows a comparator based container (a dictionary or priority
queue) to be written without making assumptions about the elements the
container will hold.
The JDSL was designed to be a teaching tool. It has interfaces
for both simple data structures, and more complicated ones, using
concepts such as positions (see 3.1), locators (see 3.2),
and comparators (see 3.3). Also, the framework provided by
the JDSL helps teach the importance of good object-oriented design
and code reuse to students.