|Don't ask to ask, just ask|
Standardized Interface Design for Search treeby demerphq (Chancellor)
|on Jun 25, 2002 at 10:27 UTC||Need Help??|
demerphq has asked for the
wisdom of the Perl Monks concerning the following question:
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
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.Yves / DeMerphq
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
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.
Writing a good benchmark isnt as easy as it might look.