demerphq has asked for the wisdom of the Perl Monks concerning the following question:

Hello All,

Recently I have been working on a set of perl implementations of common data structures/algorithms (2-3 Trees, Treaps, Binary Tree's etc). I started this mostly in order to bone up my own understanding of these interesting algorithms (some of them I encountered earlier during school, etc) however as I proceded I decided that it might be useful to produce tutorials based on my work and to publish them to CPAN for use by others. However I have now reached a point of quandry. How to define/design the interface so that it is

  1. Intuitive
  2. Easy to use
  3. Extensible
  4. Powerful
  5. Transparent
  6. Efficient
  7. Understandable
A data structure/algorithm normally (well, in OO terms anyway) has two distinct components. That of the primary object, and that of "nodes" or "elements" that exist within the primary object. The primary object defines the ways to manipulate the data structure and the nodes define how the end user puts information into the data structure.

In my case I am looking at defining an interface for search trees. Defining the primary objects interface is relatively straight forward at first glance, there are a set of common methods that need to be provided
Find an element in the strucutre and return it
Add an element to the structure
Delete an element from the structure
Join two data structures together
Split a data stucture into two parts, usually by some key
Traverse the data structure, passing over each element it contains, perhaps with some form of callback for each element
Such algorithms/data structures use a "key" which determines where in the data structure an element goes. As well, normally some method is required to determine the ordering relationship between keys. When the data structure is hard coded to deal with numbers or alphanumerics the implementation is trivial. However things get more interesting when trying to provide a general interface. If the user wants to store complex items in the data structure (a not unreasable desire) there arise the problem of how do you determine the ordering relationship? How do you provide a means for a given nodes contents in the structure to change over time? (this is particularly important in Heaps for example).

The Heap:: heirarchy uses inheiretance to do this. Every item that is added to the data structure needs to inheiret from Heap::Element and must implement two methods, one for the heaps own use, and one a comparison function. This approach while satisfying 3 and 4 of my requirements (it is powerful and extensible) doesnt seem IMO to satisfy the rest. In my experience it is annoying and time consuming to implement quickly, it isnt very intuitive (many a time I have had to OO fairly simple constructs that I normally wouldnt have except to use the modules) and it really isnt that efficient.

My partial solution to this has been to use Perls functional capabilites to implement the comparison requirement. Thus when creating a new object the user supplies a CODE ref responsible for the comparison. However what do when you need to support altering a node efficiently? Should the insert routines return a reference to a node? Should I just use inheiretance as the Heap modules do? Is there any way that I could provide multiple options, such as functional or OO approaches?

Please accept my apologies if my question is not super well defined. Perls TMTOWTDI has left me with so many implementation routes that I really cant decide what the various monks think would be a useful interface.

I really would appreciate virtually any thoughts that you all might have on this matter.

Yves / DeMerphq
Writing a good benchmark isnt as easy as it might look.