Re: what would you like to see in perl5.12? (trees)

[tye]

in reply to what would you like to see in perl5.12?

An efficient sorted hash that you use just like a hash but that is implemented as a balanced tree (sorted by key strings). I'm so tired of working around not having this or just using a different language in order to get it (most other languages have it).

The only script-visible changes would be the module you include to say you want sorted hashes and the function it exports so you 'seek' the each operator.

[ysth]

The only script-visible changes would be the module you include to say you want sorted hashes

It'd make more sense to me to have a :btree attribute on the hash declaration (does that mean lexical hashes only? maybe). Would the attribute take an optional comparison function?

and the function it exports so you 'seek' the each operator.

I'd put that in Hash::Util. Is that seek to a particular key value, or seek to key N?

[tye]

It'd seek to a particular key value. There are certainly trees that would also allow seeking to a particular index. I don't care whether there is a way to override the default comparison function (just cmp).

Yes, using an attribute for this would be fine.

Update: s/<=>/cmp/.

[Arunbear]

What should the 'seek' function do if you seek to a non existent key?

[tye]

'seek' doesn't care whether the key exists or not. It just arranges for the next use of each (actually, adding a way to reverse 'each' would be prudent as well) finds the earliest key greater than or equal to the key given to 'seek'. For convenience of interface, 'seek' might return something which might be different depending on whether the requested key exists or not, but those are details best left to the (unknown) implementor.

[Arunbear]

But say you have a hash like

%capital = (
    France  => 'Paris',
    England => 'London',
    Hungary => 'Budapest',
);

and you seek to 'Russia'. Should the next call to each behave as if all the elements had been read (i.e. return end-of-hash) ?

[Arunbear]

I've added seekable and reversible hash iteration to Tree::RB. Here is an example:

use strict;
use warnings;
use feature 'say';
use Tree::RB;

my $tied = tie(my %capital, 'Tree::RB');
%capital = (
    France  => 'Paris',
    England => 'London',
    Hungary => 'Budapest',
    Ireland => 'Dublin',
    Egypt   => 'Cairo',
    Germany => 'Berlin',
);

say 'Countries starting from Germany:';
$tied->hseek('Germany');
while(my ($key, $val) = each %capital) {
    say "key: $key, val: $val";
} 

say "\nCountries in reverse:";
$tied->hseek({-reverse=> 1});
while(my ($key, $val) = each %capital) {
    say "key: $key, val: $val";
} 

Output:

Countries starting from Germany:
key: Germany, val: Berlin
key: Hungary, val: Budapest
key: Ireland, val: Dublin

Countries in reverse:
key: Ireland, val: Dublin
key: Hungary, val: Budapest
key: Germany, val: Berlin
key: France, val: Paris
key: England, val: London
key: Egypt, val: Cairo