A pilgrimage of algorithms

Engineering is the art of not constructing; or, to define it rudely but not inaptly, it is the art of doing that well with one dollar which any bungler can do with two. [Arthur Wellington]
Opportunities: problem solving, algorithm versus data structure versus brute force, engineering versus bludgeoning, "additional levels of indirection", time versus space optimization, recursion, C++ STL container classes, container class copy semantics, struct versus pointer-to-struct

The goal
Brute force design and impl
Recursion is your friend
The magic of indirection
Object-oriented version
Header files
Putting structs or pointers in a vector?

At work we needed a "pretty print" utility to take the "flat" output of Unix's "ps" (list processes) command, and present it hierarchically. I found this domain to be very small, and yet very intriguing. Each iteration produced more inspiration than closure. I decided to document several of the algorithms that resulted; with the idea that you can never have too many examples in a Computer Science program for use as demos, case studies, or assignments.

Here is sample output of "ps -ef". The second column is the process' "pid". The third column is the process' parent's pid. Everything after the time column is the command line that initiated the process (with a sequence number artificially prepended).

The output needs to demonstrate the hierarchical nature of the data. All processes that do not have a parent in the input should start at the left edge. Children and grandchildren are then indented. The columns of interest are: pid, parent pid, and command line. So ... where to begin?

Is this domain sophisticated enough to require data structures and/or algorithms? Is time spent on reflection, abtraction, leverage, and elegance time well spent? Or is code cheap, and anything that delays the production of said code an unwarranted diversion?

Is this a 60 lines-of-code kind of problem, or will it require several hundred LOC?

Do we need to wrestle with "time versus space" (i.e. optimization) issues?

Does a binary tree map well to this domain? Is a more robust B-tree preferable? Is a custom list-of-lists the only approach that will work?

If you can only think of one possible solution, then you don't fully understand the problem. [source lost]
To populate a hierarchical "tree", what about searching for the top-most processes, then finding each of their children, then finding each of their children, etc?

What about sorting the data first? Is there any kind of "pre-conditioning" of the data that makes the problem easier? [Notice that a couple parent pids are greater than the corresponding child pid. That seems counter-intuitive. You would assume the parent process has a lower pid number, and then each child process would have a higher pid.]

Brute force design and implementation

Here is a "brute force" design. It started with intuition, and then incrementally evolved as more and more discrepancies in understanding and implementation were identified. Notice that the "populate the hierarchy" section has a loop within a loop. This has been described as "N squared" behavior, and is routinely viewed as uninspired performance.

The complexity of the "report the hierarchy" section is daunting. This is because of "impedance mismatch" between the domain and our low-level programming mentality. If we thought at a higher level, and used tools like state frames, a stack, and recursion, the code would be greatly simplified. That is the goal of the next iteration.

Recursion is your friend

Notice the nature of the tree-like output. As each Node is visited, it reports its struct members, and then delegates to each of its children. This could be characterized as: suspend, descend, return, and resume. That behavior is a perfect match for the technique known as recursive descent.

Recognizing the opportunity to leverage recursion is an enormous win. Once you get over the abstractness of this tool that is foreign to the senses of mere mortals -- the problem practically solves itself.

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult. [C.A.R. Hoare]
 
[from Data Structures & Algorithms by Niklaus Wirth]

The magic of indirection

Instead of iterating through the entire "all" vector to populate every Node, there ought to be a way to: go through the list one time, "look up" each parent, and register each child with its parent. The map container class provides this powerful "look up" capability.

What happens if the "children" member is defined to be of type vector<Node>?   [Hint: the results are very disappointing.]   here

The map container class provides a "level of indirection" that can be used to implement the illusion of magic in the hands of a craftsman. A physical example of indirection would be gears — which can transmit and change the direction, type, speed, or torque of motion.

Compare the "weight" of this design with that of the first design. The savings in size and complexity is striking!

Measuring software productivity by lines of code is like measuring progress on an airplane by how much it weighs. [Bill Gates]

Object-oriented version

The previous recursive design requires very little modification to make it "object oriented": the functions have become "instance methods", and the first argument to each function is no longer necessary.

This is a simplified demonstration of the "gang of four" Composite design pattern.

Header files

Here is header_stuff.h ... 
    #ifndef HEADER_STUFF_H
#define HEADER_STUFF_H

#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <list>
using std::cout;
using std::setw;
using std::ifstream;
using std::string;
using std::stringstream;
using std::vector;
using std::set;
using std::map;
using std::list;

#endif
       
        Here is util_stuff.h ... 
    #ifndef UTIL_STUFF_H
#define UTIL_STUFF_H

string get_token( string& line ) {
   int begin = line.find_first_not_of( ' ' );
   int end = line.find_first_of( ' ', begin );
   string token;
   if (end == string::npos)
   {
      token = line.substr( begin );
      line.clear();
   }
   else
   {
      token = line.substr( begin, end-begin );
      line = line.substr( end+1 );
      begin = line.find_first_not_of( ' ' );
      if (begin == string::npos)
         line.clear();
      else
         line = line.substr( begin );
   }
   return token;
}

Node create_and_init_node( string line ) {
   Node n;
   n.pid = get_token( line );         // 1
   n.pid = get_token( line );         // 2
   n.parent_pid = get_token( line );  // 3
   n.cmd_line = get_token( line );    // 4
   n.cmd_line = get_token( line );    // 5
   n.cmd_line = get_token( line );    // 6
   n.cmd_line = get_token( line );    // 7
   n.cmd_line = line;
   return n;
}

#endif

Putting structs or pointers in a vector?

Below, is a subset of the current domain. When the hierarchy is built from the bottom-up [1], everything works as expected [2]. But, when the hierarchy is built from top-down [3], the results are disappointing [4]. If we changed the design so that the vector holds "pointer to struct" [5], then building top-down works fine [6]. So — let's try to create the smallest possible example of the undesirable behavior. Node is now nothing more than a single int [7]. We put three instances of Node into the vector [8], and change the value of the last instance [9]. "No joy" on good behavior. But, a vector of "pointer to struct" works correctly. Let's try to put some "dye marker" in the code. The line at [10] is called a "constructor" – it is automatically invoked by the compiler whenever an instance of the struct is created. The "static" member at [11] represents a member that is shared by all instances of the struct. static data members must be defined and initialized at global scope [12].

The "Node()" at [13] creates an unnamed temporary instance of Node and passes it to push_back(). It would seem as though there are exactly 5 instances of Node created.

But – this is not the case. "Pass by value" is the default parameter passing mode in C and C++. When a struct or an object is passed, a "copy" is actually created and passed. The programmer does not have any visibility into this automatic behavior, unless she writes a "copy constructor". That has been done at [14].

We now see what was previously unseen - 17 structs are created. 5 hang around, and 12 seem to disappear.

Let's add some embellishment. The output statements have been expanded, and the copy constructor now documents the "original" and the "new" ids.

The reason for many of the copy constructor invocations is the dynamic reallocation of vector memory – but that is beyond the scope of this discussion.

Now that the Node struct has been significantly instrumented, let's see how pushing pointers on the vector behaves. Notice that no copy constructors are called at all.