The Data Structures Library in Java

JDSL Tutorial

Table of Contents
Next Lesson

Lesson 1: Echo

This simple program introduces programming with the JDSL.  The program reads a String, parses the String into words, stores the words in a  Sequence, and outputs the words.

New concepts covered:

The entire file can be viewed by clicking here.
This is a Java application.  The main method is in the Echo class.

The JDSL consists of classes and interfaces for managing and manipulating Containers.  A Container object is simply an object that manages access to other objects.  You are familiar with Containers if you work with arrays or the Java collections.  The JDSL contains a rich variety of Container types and algorithms on these Containers

In this lesson, we introduce the JDSL by studying a simple program that uses a Sequence.  A Sequence is a Container where the elements are stored in a linear order.  Each element has a rank, or an index in the Sequence.    Other libraries refer to Sequences as lists.

Let's look in detail at some important parts of the definition of the Echo class:

    import jdsl.core.api.*;
    import jdsl.core.ref.*;
We use classes and interfaces from these two packages. The package jdsl.core.api contains the interfaces for the fundamental JDSL Containers, including jdsl.core.api.Sequence that we are using here. The package jdsl.core.ref contains reference implementations for the associated Sequences in jdsl.core.api. For example, Sequence is implemented by two classes: NodeSequence that uses a linked list to store the elements and ArraySequence that we use here that uses an array to store the elements.
    private Sequence getWords(String s) {
        Sequence ret = new ArraySequence();
        StringTokenizer st = new StringTokenizer(s);
        while (st.hasMoreTokens()) {
        return ret;
This method is called when the user enters a String.  The goal is to return a Sequence containing the words of the String.  java.util.StringTokenizer is a Java class that provides methods to break strings into tokens.  In this method, the StringTokenizer object does the parsing.  The key line of code here is the call to the insertLast() method.  This method inserts an object at the end of the Sequence.  The Sequence interface also defines methods for insertion at the beginning (InsertFirst()), at a specific rank (InsertAtRank()), and after another element (InsertAfter()).

For this class, it does not matter which Sequence implementation of we choose. When the JDSL offers a choice of implementations, you should choose the implementation that is most appropriate for your application. For example, insertions and deletions on a NodeSequence can be performed in constant time, while random element access takes worst-case linear time. For an ArraySequence, insertions and deletions takes worst-case linear time, while random element access can be performed in constant time. For a complete discussion see the textbook.

    private String concatenate(Sequence s) {
        String ret = "";
        for(ObjectIterator i=s.elements();i.hasNext();)
            ret += (i.nextObject() + " ");
        return ret;
This method is called to create the output String.  The idea is to iterate through the Sequence, concatenating the words to the returned String.  Each Container has an elements() method that returns an ObjectIterator object for stepping through the elements.  Here, we use two methods from the ObjectIterator interface.  The hasNext() method returns a boolean indicating if there are unvisited Objects to return.  The nextObject() method returns the next Object in the iteration.

Iterators in the JDSL are implemented as Snapshot Iterators, that is, when you ask for an Iterator, the elements of the Container are copied to prepare the Iterator.  Changes to the Container during iteration will not be reflected by the Iterator.  This is a JDSL design decision that differs from the java.util.Iterator iterator, where changes to the associated Collection invalidates the Iterator so an exception is thrown on subsequent method calls to the Iterator.

We will continue to work with Sequences in the next lesson, by looking at other Sequence methods, algorithm objects and sorting.

Table of Contents
Next Lesson
Problems, comments?

Last modified: Mon Sep 27 13:37:09 CEST 2004