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 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 and if item k1, i1 precedes item k2, i2 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
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 [77]. 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_{1}, n_{2})) where n_{1} and n_{2} are the sizes of the results of split and delete_subsequence and the arguments of conc respectively. Merge takes time O(log((n_{1} + n_{2})/n_{1})) where n_{1} and n_{2} 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 [64].