Tree Printing Program

• PSOutFile.h
• Main Program Source

I originally expected to use two STL container types, a map for lookup and a set within each node to track that node's children (note that making a set of thingpointers (as opposed to things) requires definition of a custom comparison procedure like pnless). At some point I realized that if node were to inherit from string I could strength-reduce the map into a set of stringpointers that were really upcasts of nodepointers. I originally coded this approach, but found that whenever such a set was being accessed it required a downcast of stringpointer to nodepointer, so I finally recoded it to simply erect the set on nodepointers.

There was a particular problem with looking things up in the node set. Input data is read in standard C string format (I used fgets rather than stream IO because the data strings contain proper names, some of which have embedded spaces). Because the fast (tree-based) lookup method does not take a custom comparison procedure, this code often creates an object just to destroy it again when it finds out that such a node already exists. I understand a putative custom comparison procedure would have to order the nodes in the same manner as the red-black trees are organized, but I would be willing to live with such a caveat, I just want the search target to be a char * flavor string instead of a bstring.h flavor string.

There seemed to be about four basic approaches to this problem.

1. Create a new node and perhaps destroy it almost immediately. Example from the getnode routine:

   	NodeMem *node = new NodeMem(name);
   	NodeSet::iterator nit = set.find(node);
   	if ( set.end() != nit ) {
   		delete node;
   		return(**nit);
   	} else {
   		set.insert(node);
   		return(*node);
   	}
   

   This could be the most expensive approach since we have to do heap allocation to make the new node object.
2. Create a new string and downcast (a pointer to) it to search on it. Example from the findnode routine:

   	string s(name);
   	return( set.find((NodeMem *)&s) ); // **UGLY!!!**
   

   This seems ugly and dangerous, and it only saves us the heap allocation, since we still need to make the string object in the local stack frame.
3. Organize the sets on string pointers and do a lot of downcasting. This was originally tried but rejected due to the unreadability and unmaintainability of the resulting code.
4. Use the generic find algorithm instead of the specialized version for the set container. This would incur significant expense since the specialized find is O(log n) and the generic find would be O(n).

It's a pity I wasn't able to user more polymorphism or more of STL's facilities, but my natural tendancy to optimize seems to have taken over, in that various opportunities to do more work were avoided when a simplification was seen to be possible.