CSC 132 chap 3: array sequence class

ADT for a sequenced collection

Items stored in same sequence in which they are added to collection.

Items may be accessed sequentially, but not randomly, one at a time.

Items may be inserted into the sequence at any desired position, one at a time.

Items may be removed from the sequence at any desired position, one at a time.

Capacity is expanded as needed.

Specification of textbook class DoubleArraySeq:

public DoubleArraySeq()

public DoubleArraySeq(int initialCapacity)

// returns count of items
public int size()

// Is there a "current" item right now?
public boolean isCurrent()

// make first item, if there is one, the "current" one
public void start()

// returns "current" value. Precond: isCurrent is true.
public double getCurrent()

// moves "current" to next item. Precond: isCurrent is true.
// If already last item, postcond: isCurrent will return false.
public void advance()

// insert new item into sequence before "current" item and
// make it the "current" one.

// If isCurrent is false, place item at front of sequence.
public void addBefore(double element)

// insert new item into sequence after "current" item and
// make it the "current" one.
// If isCurrent is false, place item at end of sequence.
public void addAfter(double element)

// remove "current" item. Precond: isCurrent is true.

// If this was last item, Postcond: isCurrent is false.
// Otherwise, next item in sequence will be "current" one.
public boolean removeCurrent()

// place contents of addend sequence at end of this sequence.
// Precond: addend not null
public void addAll(DoubleArraySeq addend)

public int getCapacity()
public void ensureCapacity(int minimumCapacity)
public void trimToSize()
public Object clone()
public static DoubleArraySeq concatenation(DoubleArraySeq s1, DoubleArraySeq s2)

Required instance variables:

Array to hold values
Count of items
Current index

What do you think the ADT invariants would be?

Example client code sequence:

DoubleArraySeq collect = new DoubleArraySeq();
collect.addAfter(3.2);
collect.addAfter(4.7);
collect.addAfter(-2.9);
collect.addAfter(5.4);
for (collect.start(); collect.isCurrent(); collect.advance())
	System.out.println(collect.getCurrent()); 
// what was output of above loop?
 
collect.start();
collect.addAfter(6.8); 
// where was it inserted? What is Big-O running time?
 
collect.advance();
collect.removeCurrent(); 
// which value was removed? How is sequence "mended"? Big-O?
 
collect.addBefore(7.3); 
// where was it added? What is Big-O running time?

Sequential access is one-way using "advance". Suppose we wanted to add another method "retreat" that moves "current" in the opposite direction?

What would be its precondition?
What would be its postcondition?
What if the first item is the "current" one when retreat is called?

[ Lectures | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Last reviewed: 15 September 2000

Peter Sanderson ( PeteSanderson@smsu.edu )