Class Seq<T>

java.lang.Object
  extended by Seq<T>
Direct Known Subclasses:
Seq0, Seq2

public abstract class Seq<T>
extends java.lang.Object

Implements a generic sequence that can be split, spliced, reversed, or tested for equality.

Note

This class requires two subclasses. All documentation is here. Use

new Seq0<whatever>()

to create an empty sequence and

new Seq2<whatever>( <<instance of your generic type>>, <<some Seq<whatever>>> )

to add an element to the front of a sequence or

new Seq2<whatever>( <<instance of your generic type>> )

to create a singleton sequence. See the state of the Seq class.

Warning

This is a rather low level abstraction and is not foolproof. If you create a "circular" sequence or use two iterators to alter one sequence, you must be prepared for the consequences.

Examples of Usage

The following code obtains integers from a scanner and then prints them on one line.

Seq<Integer> seq = new Seq0<Integer>();
while( scan.hasNextInt() ) 
seq = new Seq2<Integer>( scan.nextInt(), seq );
seq = seq.reverse();
System.out.println(seq);

The following code replaces the value in the the element of the sequence which would be indexed by 4 if it were an array. (That is to say the fifth element of the sequence.) It is assumed that the sequence has such an element.

Seq<Integer>.SeqIterator i = seq.iterator();
while( i.count()<4 ) i.next();
i.setFirst(10);

The following method will look for a value in a sequence and remove the first one found returning the first element of the new sequence.

public static <T> Seq<T>
  removeFirstOccurence(Seq seq, T removeMe) 
{
    Seq.SeqIterator i = seq.iterator();
    if( !i.hasNext() ) return seq;
    if( removeMe==i.next() ) {
        i.split();
        return i.peek();
    }
    while(i.hasNext() && !i.peek().getFirst().equals(removeMe)) {
       i.next();
    }
    if( i.hasNext() ) {
        Seq.SeqIterator j = i.split();
        i.next();
        j.splice(i.peek());
    }
    return seq;
}

Implementation Notes:

1) The Seq, Seq0, and Seq2 classes were created to illustrate how object orientation uses subclassing to eliminate branching. The only if statements I permitted myself were to prevent misuse of the methods. The fact that empty sequences must be handled differently than nonempty sequences is taken care of using a subclass Seq0 for empty classes and a subclass Seq2 for nonempty classes.

2) A secondary goal was to illustrate uses of recursion. The implementation of toString() is a particular example of this: the recursion gathers information as it "reads" the sequence and fills an array of chars as it comes back.

3) Normally one would want the empty sequence to be unique. Implementing that way requires the use of a static which conflicts with Java's generics. Accordingly, this implementation permits many empty sequences and overrides equals to make them all equal. An added benefit is that you can compare two sequences for equality. The comparison will make use of the equals method of the generic type.

4) Seq2 uses the standard car,cdr way of implementing a sequence as a list. If you want something more esoteric, you can probably get it by creating an alternative to Seq2 and leaving both Seq and Seq0 unchanged.


Nested Class Summary
 class Seq.SeqIterator
          An iterator class capable of mutating the sequence.
 
Constructor Summary
Seq()
           
 
Method Summary
abstract  Seq<T> copy()
          Accessor that copies the sequence.
abstract  T getFirst()
          Accessor returning the first element in sequence.
protected abstract  Seq<T> getSubseq()
           
abstract  boolean isEmpty()
          Accessor testing emptyness.
 Seq.SeqIterator iterator()
          Create an iterator over the elements of the sequence.
abstract  int length()
          Accessor determining length.
 Seq<T> reverse()
          Accessor that returns a copy in of the sequence in reverse order.
protected abstract  Seq<T> reverseRecurs(Seq<T> buildMe)
           
abstract  void setFirst(T t)
          Mutator that resets the first value of the sequence.
protected abstract  void setSubseq(Seq<T> new_subseq)
           
 java.lang.String toString()
          String representation obtained applying each elements toString.
protected abstract  char[] toStringRecurs(int where)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

Seq

public Seq()
Method Detail

isEmpty

public abstract boolean isEmpty()
Accessor testing emptyness.

Returns:
true iff the sequence is empty

length

public abstract int length()
Accessor determining length.

Returns:
an int giving the length of the sequence

setFirst

public abstract void setFirst(T t)
Mutator that resets the first value of the sequence.

Parameters:
t - a generic value to replace the first in the sequence

getFirst

public abstract T getFirst()
Accessor returning the first element in sequence.

Returns:
the first element of the seqeunce.

iterator

public Seq.SeqIterator iterator()
Create an iterator over the elements of the sequence. The iterator is capable of mutating the sequence.

Returns:
an iterator

copy

public abstract Seq<T> copy()
Accessor that copies the sequence.

Returns:
a clone

reverse

public Seq<T> reverse()
Accessor that returns a copy in of the sequence in reverse order.

Returns:
a copy with the order of the elements reversed

toString

public java.lang.String toString()
String representation obtained applying each elements toString.

Overrides:
toString in class java.lang.Object
Returns:
a String representation of the sequence

toStringRecurs

protected abstract char[] toStringRecurs(int where)

reverseRecurs

protected abstract Seq<T> reverseRecurs(Seq<T> buildMe)

getSubseq

protected abstract Seq<T> getSubseq()

setSubseq

protected abstract void setSubseq(Seq<T> new_subseq)