Implementation

We use an algorithm that is easy to understand and describe: we read pairs of items, or tokens, keeping for each token a count of its predecessors and a list of its successors. Tokens with no predecessors can be written out immediately. When we write a token, we decrement the predecessor count of all its successors; decrementing a count to zero means that token can then be written. If we run out of tokens to write before we've dealt with every token, that means there is a loop somewhere.

Here are the details. First we bring in header files and say that we are going to want to use lists of strings:

   #include <String.h>
   #include <List.h>
   #include <Map.h>

Now we define a structure to represent the information we need to store about an object: a count of its predecessors and a list of its successors:

   struct token {
           int predcnt;
           List<String> succ;
   };

A List<String> is a list of String objects.

Having defined a structure with the information we need, we are ready to do some real work. The program first reads pairs of tokens. If both tokens in the pair are identical, we just record that the token exists. Otherwise, we increment the predecessor count of the second one and add the second to the successor list of the first. Here we use the put member function of a list, which appends its argument to the end of the list:

   Map<String,token> m;
   String p, s;
   

   while (cin >> p >> s) {
           if (p == s)
                   (void) m[p];
           else {
                   m[s].predcnt++;
                   m[p].succ.put(s);
           }
   }

We look at each token and make zeroes into a list of the names of the tokens with no predecessors:

   List<String> zeroes;
   

   for (Mapiter<String,token> i = m.first(); i; i.next()){
           if (i.curr()->value.predcnt == 0)
                   zeroes.put(i.curr()->key);
   }

Next we print the tokens on the list. Each time we print a token, we decrement the predecessor count of its successors. If a count reaches zero, we add that token to the list. Along the way, we count how many tokens we print.

To do this, we use the get function, which removes an element from the beginning of a list, places the element in its argument (which is a String& in this case), and returns zero (false) or nonzero (true) to reflect the success of the operation:

   int n = 0;
   

   while (zeroes.get (p)) {
           cout << p << "\ n";
           n++;
           List<String>& t = m[p].succ;
           while (t.get (s)) {
                   if (--m[s].predcnt == 0)
                           zeroes.put (s);
           }
   }

Finally, we check whether we have printed every token:

   if (n != m.size())
           cout << "the ordering contains a loop\ n";