Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

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

by tye (Sage)
on Aug 20, 2007 at 02:50 UTC ( [id://633695]=note: print w/replies, xml ) Need Help??


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.

- tye        

Replies are listed 'Best First'.
Re^2: what would you like to see in perl5.12? (trees)
by ysth (Canon) on Aug 20, 2007 at 03:42 UTC
    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?

      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/.

      - tye        

Re^2: what would you like to see in perl5.12? (trees)
by Arunbear (Prior) on Aug 10, 2008 at 16:31 UTC
    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
Re^2: what would you like to see in perl5.12? (trees)
by Arunbear (Prior) on Aug 05, 2008 at 13:29 UTC
    What should the 'seek' function do if you seek to a non existent key?

      '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.

      - tye        

        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) ?

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://633695]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (4)
As of 2024-03-29 14:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found