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 a linearly ordered data type K, called the key type of S, and an information from a data type I, called the information type of S. If K is a user-defined type, you have to provide a compare function (see Section User Defined Parameter Types). The number of items in S is called the size of S. A sorted sequence of size zero is called empty. We use $\langle$k, i$\rangle$ 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 $\langle$k, i$\rangle$ in S and if item $\langle$k1, i1$\rangle$ precedes item $\langle$k2, i2$\rangle$ in S then k1 < k2.

Sorted sequences are a very powerful data type. They can do everything that dictionaries and priority queues can do. They also support many other operations, in particular finger searches and operations conc, split, merge, reverse_items, and delete_subsequence.

The key type K must be linearly ordered. The linear order on K may change over time subject to the condition that the order of the elements that are currently in the sorted sequence remains stable. More precisely, 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. An application of sorted sequences where the linear order on the keys evolves over time is the plane sweep algorithm for line segment intersection. This algorithm sweeps an arrangement of segments by a vertical sweep line and keeps the intersected segments in a sorted sequence sorted according to the y-coordinates of their intersections with the sweep line. For intersecting segments this order depends on the position of the sweep line.

Sorted sequences support finger searches. A finger search takes an item it in a sorted sequence and a key k and searches for the key in the sorted sequence containing the item. The cost of a finger search is proportional to the logarithm of the distance of the key from the start of the search. A finger search does not need to know the sequence containing the item. We use IT to denote the sequence containing it. In a call S.finger_search(it,k) the types of S and IT must agree but S may or may not be the sequence containing it.

#include < LEDA/core/sortseq.h >

Types

sortseq<K,I>::item	the item type seq_item.
sortseq<K,I>::key_type	the key type K.
sortseq<K,I>::inf_type	the information type I.

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) (const K& , const 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

const K&	S.key(seq_item it)	returns the key of item it.
const I&	S.inf(seq_item it)	returns the information of item it.
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(const K& k)	returns the item with key k (nil if there is no such item).
seq_item	S.finger_lookup(const K& k)
		equivalent to S.lookup(k)
seq_item	S.finger_lookup_from_front(const K& k)
		equivalent to S.lookup(k)
seq_item	S.finger_lookup_from_rear(const K& k)
		equivalent to S.lookup(k)
seq_item	S.locate(const K& k)	returns the item $\langle$k1, i$\rangle$ in S such that k1 is minimal with k1 > = k (nil if no such item exists).
seq_item	S.finger_locate(const K& k)
		equivalent to S.locate(k)
seq_item	S.finger_locate_from_front(const K& k)
		equivalent to S.locate(k)
seq_item	S.finger_locate_from_rear(const K& k)
		equivalent to S.locate(k)
seq_item	S.locate_succ(const K& k)	equivalent to S.locate(k)
seq_item	S.succ(const K& k)	equivalent to S.locate(k)
seq_item	S.finger_locate_succ(const K& k)
		equivalent to S.locate(k)
seq_item	S.finger_locate_succ_from_front(const K& k)
		equivalent to S.locate(k)
seq_item	S.finger_locate_succ_from_rear(const K& k)
		equivalent to S.locate(k)
seq_item	S.locate_pred(const K& k)	returns the item $\langle$k1, i$\rangle$ in S such that k1 is maximal with k1 < = k ( nil if no such item exists).
seq_item	S.pred(const K& k)	equivalent to S.locate_pred(k)
seq_item	S.finger_locate_pred(const K& k)
		equivalent to S.locate_pred(k)
seq_item	S.finger_locate_pred_from_front(const K& k)
		equivalent to S.locate_pred(k)
seq_item	S.finger_locate_pred_from_rear(const K& k)
		equivalent to S.locate_pred(k)
seq_item	S.finger_lookup(seq_item it, const K& k)
		equivalent to IT.lookup(k) where IT is the sorted sequence containing it. Precondition S and IT must have the same type
seq_item	S.finger_locate(seq_item it, const K& k)
		equivalent to IT.locate(k) where IT is the sorted sequence containing it. Precondition S and IT must have the same type.
seq_item	S.finger_locate_succ(seq_item it, const K& k)
		equivalent to IT.locate_succ(k) where IT is the sorted sequence containing it. Precondition S and IT must have the same type
seq_item	S.finger_locate_pred(seq_item it, const K& k)
		equivalent to IT.locate_pred(k) where IT is the sorted sequence containing it. Precondition S and IT must have the same type.
seq_item	S.min_item()	returns the item with minimal key (nil if S is empty).
seq_item	S.max_item()	returns the item with maximal key (nil if S is empty).
seq_item	S.succ(seq_item it)	returns the successor item of it in the sequence containing it (nil if there is no such item).
seq_item	S.pred(seq_item x)	returns the predecessor item of it in the sequence containing it (nil if there is no such item).
seq_item	S.insert(const K& k, const I& i)
		associates information i with key k: If there is an item $\langle$k, j$\rangle$ in S then j is replaced by i, else a new item $\langle$k, i$\rangle$ is added to S. In both cases the item is returned.
seq_item	S.insert_at(seq_item it, const K& k, const I& i)
		Like IT.insert(k,i) where IT is the sequence containing item it. Precondition it is an item in IT with key(it) is maximal with key(it) < k or key(it) is minimal with key(it) > k or if key(it)=k then inf(it) is replaced by i. S and IT have the same type.
seq_item	S.insert_at(seq_item it, const K& k, const I& i, int dir)
		Like IT.insert(k,i) where IT is the sequence containing item it. Precondition it is an item in IT with key(it) is maximal with key(it) < k if dir = leda::before or key(it) is minimal with k < key(it) if dir = leda::behind or if key(it)=k then inf(it) is replaced by i. S and IT have the same type.
int	S.size()	returns the size of S.
bool	S.empty()	returns true if S is empty, false otherwise.
void	S.clear()	makes S the empty sorted sequence.
void	S.reverse_items(seq_item a, seq_item b)
		the subsequence of IT from a to b is reversed, where IT is the sequence containing a and b. Precondition a appears before b in IT.
void	S.flip_items(seq_item a, seq_item b)
		equivalent to S.reverse_items(a,b).

void	S.del(const 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 the sequence containing it.
void	S.change_inf(seq_item it, const I& i)
		makes i the information of item it.
void	S.split(seq_item it, sortseq<K,I,seq_impl>& S1, sortseq<K,I,seq_impl>& S2, int dir=leda::behind)
		splits IT at item it, where IT is the sequence containing it, into sequences S1 and S2 and makes IT empty (if distinct from S1 and S2). More precisely, if IT = x1,..., xk-1, it, xk+1,..., xn and dir = leda::behind then S1 = x1,..., xk-1, it and S2 = xk+1,..., xn. If dir = leda::before then S2 starts with it after the split.
void	S.delete_subsequence(seq_item a, seq_item b, sortseq<K,I,seq_impl>& S1)
		deletes the subsequence starting at a and ending at b from the sequence IT containing both and assigns the subsequence to S1. Precondition a and b belong to the same sequence IT, a is equal to or before b and IT and S1 have the same type.

sortseq<K,I,seq_impl>&	S.conc(sortseq<K,I,seq_impl>& S1, int dir = leda::behind)
		appends S1 at the front (dir = leda::before) or rear (dir = leda::behind) end of S, makes S1 empty and returns S. Precondition S.key(S.max$\_$item()) < S1.key(S1.min$\_$item()) if dir = leda::behind and S1.key(S1.max$\_$item()) < S.key(S.min$\_$item() if dir = leda::before.

void	S.merge(sortseq<K,I,seq_impl>& S1)
		merges the sequence S1 into sequence S and makes S1 empty. Precondition all keys are distinct.
void	S.print(ostream& out, string s, char c=' ')
		prints s and all elements of S separated by c onto stream out.
void	S.print(string s, char c=' ')
		equivalent to S.print(cout,s,c).
bool	S == const sortseq<K,I,seq_impl>& S1
		returns true if S agrees with S1 componentwise and false otherwise
sortseq<K,I,seq_impl>*	sortseq<K,I>::my_sortseq(seq_item it)
		returns a pointer to the sortseq containing it. Precondition The type of the sortseq containing it must be sortseq<K,I>.

Iteration

forall_items(it, S) { ``the items of S are successively assigned to it'' }

forall_rev_items(it, S) { ``the items of S are successively assigned to it in reverse order'' }

forall(i, S) { ``the informations of all items of S are successively assigned to i'' }

forall_defined(k, S) { ``the keys of all items of S are successively assigned to k'' }

Implementation

Sorted sequences are implemented by skiplists [79]. Let n denote the current size of the sequence. Operations insert, locate, lookup and del take time O(log n), operations succ, pred, max, min_item, 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. Finger_lookup(x) and finger_locate(x) take time O(log min(d, n - d )) if x is the d-th item in S. Finger_lookup_from_front(x) and finger_locate_from_front(x) take time O(log d ) if x is the d-th item in S. Finger_lookup_from_rear(x) and finger_locate_from_rear(x) take time O(log d ) if x is the n - d-th item in S. Finger_lookup(it,x) and finger_locate(it,x) take time O(log min(d, n - d )) where d is the number of items between it and the item containing x. Note that min(d,n - d) is the smaller of the distances from it to x if sequences are viewed as circularly closed. Split, delete_subsequence and conc take time O(log min(n₁, n₂)) where n₁ and n₂ are the sizes of the results of split and delete_subsequence and the arguments of conc respectively. Merge takes time O(log((n₁ + n₂)/n₁)) where n₁ and n₂ are the sizes of the two arguments. The space requirement of sorted sequences is linear in the length of the sequence (about 25.5n Bytes for a sequence of size n plus the space for the keys and the informations.).

Example

We use a sorted sequence to list all elements in a sequence of strings lying lexicographically between two given search strings.

#include <LEDA/core/sortseq.h>
#include <iostream>

using leda::sortseq;
using leda::string;
using leda::seq_item;
using std::cin;
using std::cout;


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

   cout << "Input a sequence of strings terminated by 'STOP'\n";
   while (cin >> s1 && s1 != "STOP")
     S.insert(s1, 0);

   while(true) {
     cout << "\n\nInput a pair of strings:\n";
     cin >> s1 >> s2;
     cout << "All strings s with " << s1 <<" <= s <= " << s2 << ":";
     if(s2 < s1) continue;
     seq_item last  = S.locate_pred(s2);
     seq_item first = S.locate(s1);
     if ( !first || !last || first == S.succ(last) ) continue;
     seq_item it = first;
     while(true) {
       cout << "\n" << S.key(it);
       if(it == last) break;
       it = S.succ(it);
     }
   }
}

Further examples can be found in section Sorted Sequences of [66].