The Data Structures Library in Java

JDSL Tutorial

Previous Lesson
Table of Contents
Next Lesson


Lesson 2: Sequence Fun

In the previous lesson we learned about JDSL Sequences.  In this lesson we look in more depth at sequences.  Like the Echo application in Lesson 1, this application starts with the user entering a string that is parsed into words.  We add functions to sort and permute the word Sequence.

New concepts covered:


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

The JDSL contains a number of built-in functions for manipulating sequences.  In this lesson, we look at a few.  First, we'll look in detail at some important parts of the definition of the SequenceFun class:

    import jdsl.core.api.*;
    import jdsl.core.ref.*;
    import jdsl.core.algo.sorts.*;
We are using classes and an interface from the jdsl.core.algo.sorts package. The classes and interfaces in this package provide sort algorithms for sequences. In the JDSL, the container provides methods for insertion, deletion, modification, and querying of its structure and elements. All other algorithms are implemented in algorithm objects defined outside the container. Typically, you pass the container plus other information to the algorithm object, which then performs the algorithm. We will see this in action in this program.
    private void sort(Sequence seq) {
        // This object will do the sorting.
        SortObject sorter = new ArrayQuickSort();
        // Sort in alphabetical order.
        sorter.sort(seq, new ComparableComparator());
    }
This is all there is to sorting a Sequence.  You create a SortObject, then call its (only) method: sort().  After the method is called the Sequence is modified so that the elements are in sorted order. The ordering of the elements is defined by the Comparator object, which we will look at in a moment.

The jdsl.core.algo.sorts package contains a number of sorting classes. Each implements a different sorting algorithm and is optimized for a particular sequence implementation. The ArrayQuickSort class implements quicksort and is optimized for ArraySequence implementations. It will work correctly, but less efficiently, for other Sequence implementations (e.g. NodeSequence).

A sequence can be sorted in a number of different ways.  For example, you might want to order a sequence of people by their age, name, or height. The Comparator interface is used to define an ordering on objects.  The interface has a number of methods, the most important being compare(Object obj1, Object obj2) that returns a negative integer if x1<x2, 0 if x1=x2, and a positive integer if x1>x2.   Let's look at the compare method that defines an alphabetical ordering of strings that is not from our program, but demonstrates the idea:

    public int compare (String x1, String x2) throws ClassCastException {
        return  x1.compareTo(x2);
    }
The compare method is defined in terms of the String.compareTo() method defined in the java.lang.String class.  The rest of the methods of the Comparator interface are tests:  isComparable(), isGreaterThan(), isLessThan(), isEqualTo(), and isGreaterThanOrEqualTo().

The JDSL contains two special Comparator classes that make it easy to use java comparisons with the JDSL.  The jdsl.core.ref.ComparableComparator orders objects that implement the java.lang.Comparable interface.  We can use that class here, since String implements Comparable.  There also is a jdsl.core.ref.ComparatorExtender, that produces a jdsl.core.api.Comparator from a java.util.Comparator.

Additionally, there is a special Comparator factory called ComparatorReverser that takes a Comparator and produces a new Comparator for a reverse order from the original Comparator. The ComparatorReverser is used in the following method, to sort the Sequence in reverse order:

    private void reverseSort(Sequence seq) {
        // This object will do the sorting. 
        SortObject sorter = new ArrayQuickSort();
        // Sort in alphabetical order. 
        sorter.sort(seq, new ComparatorReverser(new ComparableComparator()));
    }
The demo program's permute(.) method demonstrates two more features of the JDSL Sequence:

    protected void permute(Sequence s) {
        Random rnd = new java.util.Random();
        for(int i=s.size()-1;i>0;i--) {
           int j=rnd.nextInt(i+1);
           if(j<i)
                s.swapElements(s.atRank(i),s.atRank(j));
        }
    }

This method randomly permutes a Sequence.  It iterates from the end of the sequence, selecting a random element to swap.  The method atRank(int i) returns the Position at rank i (see Lesson 3).  The swapElements() method swaps the elements at the two ranks.

We will continue to work with Sequences in the next lesson.  In particular we look at Positions, a concept that is new in the JDSL.  A Position gives a handle to the internal structure of the Sequence, without violating encapsulation.  This feature makes a number of operations convenient and efficient.


Previous Lesson
Table of Contents
Next Lesson
Problems, comments?

Last modified: Sat Apr 19 16:53:34 CEST 2003