Sorted Sequences ( sortseq )

Definition

An instance S of the parameterized data type sortseq<K,I> is a sequence of items ( seq$\_$item). Every item contains a key from the linearly ordered data type K, called the key type of S, and an information from data type I, called the information type of S. The number of items in S is called the size of S. A sorted sequence of size zero is called empty. We use <k, i > to denote a seq$\_$item with key k and information i (called the information associated with key k). For each k in K there is at most one item <k, i > in S.

The linear order on K may be time-dependent, e.g., in an algorithm that sweeps an arrangement of lines by a vertical sweep line we may want to order the lines by the y-coordinates of their intersections with the sweep line. However, whenever an operation (except for reverse_items) is applied to a sorted sequence S, the keys of S must form an increasing sequence according to the currently valid linear order on K. For operation reverse_items this must hold after the execution of the operation.

#include < LEDA/sortseq.h >

Creation

sortseq<K,I>	S	creates an instance S of type sortseq<K,I> based on the linear order defined by the global compare function and and initializes it to the empty sorted sequence.
sortseq<K,I>	S(int (*cmp)(K, K ))	creates an instance S of type sortseq<K,I> based on the linear order defined by the compare function cmp and initializes it with the empty sorted sequence.

Operations

K	S.key(seq_item it)	returns the key of item it. Precondition: it is an item in S.
I	S.inf(seq_item it)	returns the information of item it. Precondition: it is an item in S.
I&	S[seq_item it]	returns a reference to the information of item it. Precondition: it is an item in S.
seq_item	S.lookup(K k)	returns the item with key k (nil if no such item exists in S).
seq_item	S.insert(K k, I i)	associates information i with key k: If there is an item <k, j > in S then j is replaced by i, else a new item <k, i > is added to S. In both cases the item is returned.
seq_item	S.insert_at(seq_item it, K k, I i)
		Like insert(k, i), the item it gives the position of the item <k, i > in the sequence. Precondition: it is an item in S with either key(it) is maximal with key(it) < = k or key(it) is minimal with key(it) > = k.
seq_item	S.locate_succ(K k)	returns the item <k', i > in S such that k' is minimal with k' > = k (nil if no such item exists).
seq_item	S.locate_pred(K k)	returns the item <k', i > in S such that k' is maximal with k' < = k (nil if no such item exists).
seq_item	S.locate(K k)	returns S.locate_succ(Kk).
seq_item	S.locate(K k, bool& equal)
		returns the item <k', i > in S such that k' is minimal with k' > = k (nil if no such item exists) and equal = (k' = = k).
seq_item	S.succ(seq_item it)	returns the successor item of it, i.e., the item <k, i > in S such that k is minimal with k > key(it) (nil if no such item exists). Precondition: it is an item in S.
seq_item	S.pred(seq_item it)	returns the predecessor item of it, i.e., the item <k, i > in S such that k is maximal with k < key(it) (nil if no such item exists). Precondition: it is an item in S.
seq_item	S.min()	returns the item with minimal key (nil if S is empty).
seq_item	S.max()	returns the item with maximal key (nil if S is empty).
void	S.del(K k)	removes the item with key k from S (null operation if no such item exists).
void	S.del_item(seq_item it)	removes the item it from S. Precondition: it is an item in S.
void	S.change_inf(seq_item it, I i)
		makes i the information of item it. Precondition: it is an item in S.
void	S.reverse_items(seq_item it1, seq_item it2)
		the subsequence of S from it1 to it2 is reversed. Precondition: it1 appears before it2 in S.
void	S.split(seq_item it, sortseq<K,I>& S1, sortseq<K,I>& S2)
		splits S at item it into sequences S1 and S2 and makes S empty. More precisely, if S = x1,..., xk - 1, it, xk + 1,..., xn then S1 = x1,..., xk - 1, it and S2 = xk + 1,..., xn. Precondition: it is an item in S.
sortseq<K,I>&	S.conc(sortseq<K,I>& S1)	appends S1 to S, makes S1 empty and returns S. Precondition: S.key(S.max()) < S1.key(S1.min()).
void	S.clear()	makes S the empty sorted sequence.
int	S.size()	returns the size of S.
bool	S.empty()	returns true if S is empty, false otherwise.

Implementation

Sorted sequences are implemented by skiplists. Operations lookup, locate, insert, del, split, conc take time O(log n), operations succ, pred, max, min, key, inf, insert_at and del_item take time O(1). Clear takes time O(n) and reverse_items O(l), where l is the length of the reversed subsequence. The space requirement is O(n). Here n is the current size of the sequence.

Example

We use a sorted sequence to list all elements in a sequence of strings lying lexicographically between two given search strings. We first read a sequence of strings terminated by "stop" and then a pair of search strings. We output all strings that lie lexicographically between the two search strings (inclusive).

#include <LEDA/sortseq.h>

main()
{ 
 sortseq<string,int> S;
 string s1,s2;

 while ( cin >> s1 &&  s1 != "stop" )  S.insert(s1,0);

 while ( cin >> s1 >> s2 )
 { 
   seq_item start = S.locate_succ(s1);
   seq_item stop  = S.locate_pred(s2);

   if (start != nil && stop != nil && S.key(start) <= S.key(stop))
     for (seq_item it = start; it != stop; it = S.succ(it))
        cout << S.key(it) << endl; 
  }

}