Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
I ran across some of these same issues (and some others) trying to create a Perl wrapper for STL sets and priority queues. My solution was incomplete, and the module never quite made it to CPAN, but maybe the experience could be useful. If anyone wants to take a look at the code, email me (educated underscore foo at yahoo) and I'll be happy to tar it up and send it.

First, implementing the data structure manipulation in C is a big win, as is using C for the comparison function. So when creating an instance of the data structure, you can either pass in a code ref or a special value for the standard number and string comparisons ({NUM,STR}_{LT,GT}). With one of these special values, the C code does the appropriate comparison directly.

Second, I just punted on modifying elements that had already been inserted. This is the wrong decision for heaps, but it makes the interface much simpler, and I had recently been traumatized by Heap::Element. For ordered trees, it's not as bad -- the implementation has to remove the old value and re-insert the new one anyways, so you can just do that yourself (or create a Perl member function to do it). I like your idea of returning a reference, though I probably wouldn't use a real Perl reference. For one thing, it needs to keep some sort of index into your data structure. For another, a tied scalar with a STORE method will look nicer.

Third, arrays are handled naturally in Perl, and RAM is cheap, so I avoided iteration with callbacks. Instead, I provided a range() function to take slices of ordered sets:

$x->range($a, $b) Return all elements $i in $x such that $a <= $i < $b. If $a is undef, treat it as less than all elements in $x. If $b is unde +f, treat it as greater than all elements in $x.
So you do things like this:
@foo = grep { something } $x->range($a, $b) $y->insert($x->range($a, $b))
This leaves efficient joins and splits unaccounted for, of course. I was planning on having a second function just like range() to grab opaque slice objects, which could then be put into existing trees (join) or used to create new ones (split). Then I ran into some wierd XS/Inline::CPP problems and moved on before figuring out what was going on.

Finally, it's nice to be able to insert arrays of things in a single call, rather than looping over them.

Good luck,
/s


In reply to Re: Standardized Interface Design for Search tree by educated_foo
in thread 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? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (5)
As of 2022-12-09 11:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?