🚀 go-pugleaf

In the recent discussion on pointer comparisons, Fergus Hendersson
suggested adding a standard library function ptrcmp() instead of
extending the definitions of "<" and ">" for pointers.  I think we
also agreed on a reasonable relationship between ptrcmp() and the
relational operators.

While I think ptrcmp() is better than nothing, I still think extending
the definition of the relational operators is far better.  Consider
this template class (the code may be wrong, I'm just inventing an
almost real example for the purpose of discussion):

	template <class T>
	class Tree {
	private:
		struct Node {
			T element;
			Node* left;
			Node* right;
			Node(const T& e) : element(e),left(0),right(0) {}
			~Node() { delete left; delete right; }
		};
		Node* root;
		T& InsertElement(Node*& root, const T& element);
	public:
		Tree() : root(0) {}
		~Tree() { delete root; }
		T& Insert(const T& e) { return InsertElement(root, e); }
	};

Most of the template class Tree is a skeleton around InsertElement()
which is the function that actually does the job:

	template <class T>
	T& Tree<T>::InsertElement(Node*& root, const T& element)
	{
		if (root == 0) {
			root = new Node(element);
			return root->element;
		}
		if (element < root->element)
			return InsertElement(root->left, element);
		if (root->element < element)
			return InsertElement(root->right, element);
		return root->element;
	}

Note that a copy of the element argument is inserted into the tree,
and that InsertElement() always returns a reference to this copy.

Now, here's the problem: this implementation works fine for all
element types that have an "operator < ()" including plain built-in
types and many user-defined types.  However, it is not guaranteed to
work with pointer elements for reasons we have discussed before.

They way around this problem is to make a specialization for pointers:

	void*& Tree<void*>::InsertElement(Node*& root, const void*& element)
	{
		if (root == 0) {
			root = new Node(element);
			return root->element;
		}
		if (ptrcmp(element, root->element) < 0)		// ****
			return InsertElement(root->left, element);
		if (ptrcmp(root->element, element) < 0)		// ****
			return InsertElement(root->right, element);
		return root->element;
	}

The changes are marked with ****, and the function signature is also
changed, of course.  We must also make a specialized Tree class for
pointers to do the appropriate type casting to/from void*.

	template <class T>
	class PtrTree : private Tree<void*> {
	public:
		PtrTree() {}
		~PtrTree {}
		T*& Insert(const T*& e)
			{ return (T*&) Tree<void*>::Insert(e); }
	};

I think this covers it all, but I'm not quite sure if the derivation
should be public instead.  In any case, here are a few pros and cons:

1.  It can be done with a minimal change to the language (adding a
standard library function).  It can also be done in a non-portable way
without the library function.

2.  In the general case we cannot use the trick of converting to a
long integer, but it could be used in the specialization for void*.

3.  The programmer using class Tree must remember to use a different
class for pointers.  There is no type checking that prevents the user
from using Tree<Foo*> -- it will compile fine but produce the wrong
results on some machines.

4.  The implementor and maintainer of similar classes must remember to
handle pointers in a special way.  The public interface of each data
structure must be replicated, and each class requires at least a
specialization for void*.

I regard (3) is biggest problem, in particular as there is no way (as
far as I know) to diagnose the problem.   It may work fine on some
machines, and then break when you port the code to a new machine or a
new memory model on the same machine.

I think (4) is a lesser problem because you only have to get it right
every time you write or modify a general data structure, not every
time you use it.  I think the handling of pointers adds a significant
complexity to a rather simple data structure "right out of the
textbook."

Any comments or suggestions would be welcome.  I would be particularly
happy if you could show that I have described a problem that in fact
does not exist if you use a suitable programming style.

Dag Bruck
--
Department of Automatic Control		E-mail: dag@control.lth.se
Lund Institute of Technology
P. O. Box 118				Phone:	+46 46-104287
S-221 00 Lund, SWEDEN			Fax:    +46 46-138118