Like the class dictionary, the class sortseq follows the item container concept. Here, the items are of the type seq_item.

As a first example, we once more want to make use of our program for counting strings. This time, however, we want to give the user the possibility to interactively query the strings that he has input in the following way: He can enter two strings s1 and s2, and the program will output all strings lying between these two strings. This clarifies the main use of a sorted sequence: keeping data records sorted according to a key and iterating over a range between two keys.

For this we exploit the special ability of the class sortseq to be able to iterate over the containers in the order given according to the keys. This is also possible for a dictionary or for a d_array, in which the key type also must be a linearly ordered one, but there one can only iterate, by means of the forall macros, over all keys from the front to behind, beginning with the first one; there, it is not possible to start at a certain key in the middle. This is different with the class sortseq: Since the containers are linked together, the iteration can be started at every container (which, for example, we have found by a previous search) and stopped at every other container. Of course, a sortseq can also be traversed from behind to the front.

In a sortseq, the search for a certain key by means of the method

seq_item it = S.lookup(k);

returns an item referring to the container with the corresponding key, and nil, if no such container exists.

After such a search, an item referring to the previous and the following container, respectively, can be obtained by means of the methods

S.pred(it);
S.succ(it);

The methods

S.min_item();
S.max_item();

return an item referring to the container which stands in the leftmost or rightmost position in the linear sequence; being the leftmost or rightmost, it contains the smallest or largest key, respectively. Figure 3.7 clarifies this.

Figure 3.7. Items and containers in an sorted sequence

At first, the following program lets the user enter strings until it discovers the input STOP as an end marker; during this process, it counts which string occurred how often. After this, the user can enter two strings s1 and s2 in a non-terminating loop; the program then outputs all strings (together with their frequencies) that lie in the lexicographical order between s1 and s2.

#include <LEDA/sortseq.h>
#include <LEDA/string.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 s;

  cout << "Input a sequence of strings terminated by 'STOP'\n"; 
  while (cin >> s && s != "STOP") {
    seq_item it;
    if((it = S.lookup(s)) == nil)
      S.insert(s, 1);
    else 
      S.change_inf(it, S.inf(it) + 1);
  }

  string s1, s2;

  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 first_it = S.locate(s1); // minimal key >= s1
    seq_item last_it  = S.locate_pred(s2); // maximal key <= s2
    if ( !first_it || !last_it || first_it == S.succ(last_it) ) {
      cout << "\n(List is empty.)";
      continue; 
    }
    seq_item it = first_it; 
    while(true) { 
      cout << "\n" << S.key(it) << " " << S.inf(it);
      if(it == last_it) break;
      it = S.succ(it);
    }
  }
}

An example run that creates the sortseq of Figure 3.7 looks as follows:

Input a sequence of strings terminated by 'STOP'
Karin Julia Marion Hanne Karin Julia Karin Julia
Hanne Marion Julia Julia Andrea
Miriam Julia Julia Hanne Andrea Karin Hanne
STOP


Input a pair of strings:
Joachim
Ziegler
All strings s with 'Joachim' <= s <= 'Ziegler':
Julia 7
Karin 4
Marion 2
Miriam 1

Input a pair of strings:
Antje
Dorothee
All strings s with 'Antje' <= s <= 'Dorothee':
(List is empty.)

The program searches in the sortseq by means of lookup(). If the string s searched for is not yet contained in the sorted sequence, the key-value pair (s,1) is inserted by

S.insert(s, 1);

s was just recognized in the input for the first time. If, in contrast, s is already a key of the sortseq, then the value associated to it, that is its frequency, must be increased by 1. This is done via the item that was returned by lookup().

S.inf(it);

returns the value belonging to an item it, and by

S.change_inf(it, new_v);

this value can be set to any value new_v.

An input of STOP ends the collecting of the strings. After this, the user can enter two strings s1 and s2, again and again in a loop. The program outputs all strings that lexicographically lie between these two strings. If s2 is lexicographically smaller than s1, then nothing has to be done. Otherwise the sortseq is searched for s1 by means of

it = S.locate(s1);

The difference between lookup() and locate() is the following: locate() does not simply return nil in the case that the key k searched for is not available; rather, it returns an item referring to the container whose key is the smallest key k' that is greater than or equal to k according to the linear order; so the item points to the position in front of which k would be inserted. Only if such a k' does not exist, nil is returned. Therefore dear Julia is found in the above search for Joachim and not simply nothing.

On the other hand, a search for a key k with

it = S.locate_pred(k);

returns an item it referring to the container whose key k' is the largest key that is less than or equal to k. Good Miriam is therefore found in the above search for Ziegler.

As already said, these methods return nil only when there is no key with the corresponding characteristic. Then, of course, nothing has to be done in the above program because the resulting list is empty. (Then first_it or last_it or both are nil.) The same holds true if first_it references the container that stands next to the right of the container that last_it refers to, that is, if both items “cross-over with references”, so to speak. This is the case in the above example with Antje and Dorothee.

By means of

S.key(it);

the key of a container can be accessed (via an item referring to it).

If insert() is invoked with a pair (k,i') and the key k already is part of a pair (k,i) of the sorted sequence, then i is replaced by i' in this pair. This is never the case in the example program, though.