in reply to Standardized Interface Design for Search tree
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:
So you do things like this:$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.
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.@foo = grep { something } $x->range($a, $b) $y->insert($x->range($a, $b))
Finally, it's nice to be able to insert arrays of things in a single call, rather than looping over them.
Good luck,
/s
|
---|