Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
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
Find an element in the strucutre and return it
insert
Add an element to the structure
delete
Delete an element from the structure
join
Join two data structures together
split
Split a data stucture into two parts, usually by some key
traversal
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.

In reply to Standardized Interface Design for Search tree by demerphq

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having a coffee break in the Monastery: (4)
As of 2024-03-29 13:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found