SequenceBase and Sequence

 Collectionscapable of storing data elements in any order are SequenceBase and Sequence classes. Like SetBase and Set these classes inherit the vast majority of their functionality from MSetBase. Unlike set objects, however, sequence objects must use unsorted Container objects as storage media. Error checks in the SequenceBase and Sequence constructors prevent the use of any Container object which returns TRUE when given the sortedQ() query. Sequence

  

Figure 3.26: Sequence

The main advantage of derivation from MSetBase is illustrated in Figures  and . Since a sequence is a multiset which happens to be stored in an unsorted Container object, it can appear as an operand on either side of the set comparison, set primitive, and set construction methods.

  

Figure 3.27: Another Sequence Example

The methods which differ from those of MSetBase are listed below.

1. Creation

 

SequenceBase<Item,Impl> s;

Create an empty sequence using the unsorted Container class Impl (where Impl contains elements of type Item) as an implementation.

SequenceBase<Item,Impl> s( (Collection<Item>&) c);

Create a sequence using the unsorted Container class Impl (where Impl contains elements of type Item) as an implementation. Initialize the collection with the elements of c such that the same order is maintained. O(n)

SequenceBase<Item,Impl> s( (SequenceBase<Item,Impl>&) ss);

Create an empty sequence using the unsorted Container class Impl (where Impl contains elements of type Item) as an implementation. Use reference counting to share the elements of ss. O(1)

Sequence<Item> s( (Collection<Item>&) c);

Create a set using the implementation specified by DEFAULT_SET_IMPL in MSet.h. Initialize it with the elements of c such that the same order is maintained. O(n)

Sequence<Item> s( (Sequence<Item>&) ss);

Create an empty sequence using the implementation specified by DEFAULT_SET_IMPL in MSet.h. Use reference counting to share the elements of ss. O(1)

2. Operations

void insertAfter (Item e, Item after_item);

If the reference count of store is greater than 1, then other collection objects are also using it as their implementation. Rather than changing its contents, a copy will be made (O(n)), and the reference counts will be updated. Finally, insert e after the first occurrence of after\_item. If there is no such occurrence, a NULL pointer is passed to the Container's insertAfter(Item,ContainerNode*) method. Complexity depends on the storage medium.

void insertBefore (Item e, Item before_item);

Similar to insertAfter() except that e is inserted before the first occurrence of before\_item.

void prepend (Item e);

After considering reference counts as above, call storeprepend(e), which should insert e at the beginning. Note that this usually has the same result as calling insert.

Item element (int i);

Return the ith element, or the last element if i>$\mbox{this-$\gt$size()}$ O(n).

SequenceBase<Item,Impl> subsequence (int i, int j);

Construct a new sequence and initialize it with $s[i] \ldots s[j]$, where s[p] is the pth element of the current sequence. O(n)