Engr 691-12: Special Topics in Engineering Science
Software Architecture
Fall Semester 2000
Lecture Notes

Ranked Sequence Abstract Data Type

Design Notes on the Ranked Sequence ADT

General Issues

The ranked sequence abstract data type in this case study was inspired, in part, by Chapter 4 of the book Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia (Wiley, 1998) [ go to textbook Web site?]. The design and implementation discussed here was done independently by your instructor.

The very useful Vector class from the Java API implements an ADT similar to the concept of the ranked sequence discussed in this case study.

A ranked sequence is a sequence of elements, each of which has an associated integer rank. The rank is the offset of the element from the beginning of the sequence. The head (i.e., first) element of the sequence has rank 0, the next element has rank 1, and so forth. If there are N elements in the sequence, then the indices are 0 through N-1; there are no "holes" in the sequence.

This ADT must provide operations for accessing, replacing, inserting, and deleting elements at any valid rank in the sequence. If an element is inserted at some rank, then the indices for existing elements at that rank and higher are all increased by one. Deletion is handled in a similar fashion.

The ranked sequence ADT is an unbounded structure. There is no conceptual limit on the length of the sequence. An implementation must extend the length of the sequence as needed.

In an implementation, each element is a Java object; primitive data must be wrapped with instances of the appropriate wrapper classes (e.g., Integer).

ADT Specification

See also the javadoc documentation for the RankedSequence interface or the source code.

Interface Invariant

Once created and initialized properly, each instance contains a valid representation of a ranked sequence.

void insertAtRank(int r, Object e)
0 <= r <= length().
Object e added as element at rank r. Ranks of all elements (if any) with old ranks >= r are increased by one.

void deleteAtRank(int r)
0 <= r < length()
Element at rank r is removed. Ranks of all elements (if any) with old ranks > r are decreased by one.

void replaceAtRank(int r, Object e)
0 <= r < length()
Element at rank r is replaced by object e.
Object elementAtRank(int r)
0 <= r < length()
return = the element at rank r.

int length()
return = the number of elements in the sequence.

boolean isEmpty()
return = true if and only if the sequence contains no elements.

Enumeration elements()
return = an enumeration iterator for the sequence.

Note: The elements() method should be changed to return an object that implements the java.util.Iterator interface to be consistent with the Collections framework of Java 1.2 and beyond. The work described in this document was done with Java 1.1.

Use of Java Features for Specification and Implementation

In contrast to the simpler ADT specifications and implementations we gave for the Stack, Day, and Queue ADTs, in this design we make better use of the facilities of Java. The design and implementation of the Java structures for the ranked sequence ADT:

Alternative Implementations of the ADT

We provide three separate implementations of the RankedSequence ADT:

  1. ArrayRankedSeq, which implements the sequence by a dynamically allocated array of objects.

    This implementation behaves much like the built-in Vector class. Whenever the array used to represent the sequence overflows, it allocates a larger one and copies the previous array into it.

  2. DoubleLinkRankedSeq, which implements the sequence by a doubly linked list.

  3. VectorRankedSeq, which implements the sequence as an adapter of the Vector class from the Java API.

    An adapter is an abstraction (e.g., a class) that adapts one abstraction to behave like another. It translates the operations on the interface of one interface into the appropriate operations on a second abstraction.

    VectorRankedSeq is a class that implements the RankedSequence interface, that is, its instances are instances of the ranked sequence abstraction. However, these operations are implemented directly in terms of similar operations on an instance of the built-in Vector class in the Java API. Thus VectorRankedSeq adapts a Vector to be a RankedSequence.

Iterator Design Issues

In general, it is a dangerous practice to use an iterator while allowing independent modification of the data structure by other parts of the program.

In a sequence iterator, what happens if the base sequence is modified by other parts of the code while an iterator (enumerator) is in use? In particular, what happens if an element of the sequence is inserted, deleted or replaced?

The answer, of course, depends upon how both the base sequence and the iterator are implemented.

Depending upon the implementation details, insertions and deletions of elements might cause some elements to be seem multiple times, others skipped. Some insertions and deletions might be visible to the iterator, others might cause a reorganization of the underlying data structure that makes all subsequent changes invisible. Some insertions and deletions might leave the iterator positioned to an invalid position, outside the sequence or to an element that has been "deleted" from the sequence.

There seems to be several different ways to approach the problem of changes to a data structure while an iterator is in use on that data structure. (We are just considering singly threaded programs here.) These include:

  1. Ignore the problem. Assume the data structure is not modified in any undesirable way while the iterator is in use.

  2. Create a copy of the data structure for use by the iterator. The iterator will then work on a "snapshot" of the data structure at the point it was created.

  3. Give the enumerator direct access to the internal state of the classes that implement the structure. Make it adapt to changes in the internal state as much as possible.

  4. Cause the iterator to abort if an undesirable modification occurs.

  5. Lock the data structure to prevent any undesirable modification.

In the design of the ranked sequence classes, we experimented with two different approaches.

The Java JDK 1.2 includes new kinds of iterators that take approach four above. The data structures in its new Collection hierarchy includes iterators that are fail-fast. If a structure has been modified in an unacceptable way, subsequent calls of the iterator methods will cause an immediate abort.

The Vector has been retrofit to be a member of this hierarchy. Its elements() method, however, continues to return an enumerator with the old semantics.

UP to ENGR 691 Lecture Notes root document?

Copyright © 2000, H. Conrad Cunningham
Last modified: Sun Aug 27 18:38:14 CDT 2000