RFC - inplace upgrade for Tie::SortHash

All:
I was going to suggest Tie::SortHash as a possible solution to this node requesting help when sorting hashes, but decided not to. I looked under the hood and saw that it was using deprecated pseudo hashes. It has been nearly three years since this module was touched. I have contacted Casey, the author, to see if they plan on updating it. I would like to see one of ~~three~~ two things happen:

Casey update the module, possibly with input

I take over maintenance of the module

~~I upload a new module that does the same thing only more~~

I have enclosed my proposed first draft of code as well as some comparisons with the original. Please provide your feedback on the code as well as any other advice that might be helpful.

package Tie::SortHash;
use strict;

use constant HASH      => 0;
use constant LOOKUP    => 1;
use constant ARRAY     => 2;
use constant SORT      => 3;
use constant CHANGED   => 4;

use vars qw($VERSION);

$VERSION = '1.02';

sub TIEHASH {
    my $class = shift;
    my $hash = shift || {};
    my $sort = shift || q($a cmp $b || $a <=> $b);
    my $self = bless [], $class;
    $self->_Build($hash, $sort);
    return $self;
}

sub FETCH {
    my($self, $key) = @_;
    $self->[HASH]{$key};
}

sub STORE {
    my($self, $key, $value) = @_;
    $self->[HASH]{$key} = $value;
    $self->[CHANGED] = 1;
}

sub EXISTS {
    my($self, $key) = @_;
    return exists $self->[HASH]{$key};
}

sub DELETE {
    my($self, $key) = @_;
    delete $self->[HASH]{$key};
    splice(@{$self->[ARRAY]}, $self->[LOOKUP]{$key}, 1);
    delete $self->[LOOKUP]{$key};
}

sub FIRSTKEY {
    my $self = shift;
    $self->_ReOrder if $self->[CHANGED];
    $self->_Iterate;
}

sub NEXTKEY {
    my ($self, $lastkey) = @_;
    $self->_ReOrder if $self->[CHANGED];
    $self->_Iterate($self->[LOOKUP]{$lastkey});
}

sub CLEAR {
    my $self = shift;
    $self->[HASH] = {};
    $self->[CHANGED] = 1;
}

sub DESTROY {
}

sub _Build {
    my ($self, $hash, $sort) = @_;
    @{$self->[HASH]}{keys %$hash} = values %$hash;
    $self->sortblock($sort);
    $self->_ReOrder;
}

sub _ReOrder {
    my $self = shift;
    $self->[LOOKUP] = ();
    $self->[ARRAY] = ();
    my $index = 0;
    my $hash = $self->[HASH];
    for my $key (eval $self->[SORT]) {
        $self->[LOOKUP]{$key} = $index;
        $self->[ARRAY][$index] = $key;
        $index++;
    } 
    $self->[CHANGED] = 0;
}

sub _Iterate {
    my ($self, $index) = @_;
    $index = -1 unless defined $index;
    $index++;
    defined $self->[ARRAY][$index] ? $self->[ARRAY][$index] : undef;
}

sub sortblock {
    my($self, $sort) = @_;
    my $hash = $self->[HASH];
    $sort =~ s/\$hash/\$hash->/g;
    $self->[SORT] = "sort { $sort } keys %\$hash";
    eval $self->[SORT];
    die $@ if $@;
    $self->[CHANGED] = 1;
}

1;
[download]

Comparisons

Original uses pseudo hashes, proposed replacement does not

Original sorts hash every time each/keys/values is called. Proposed only when needed.

Both modules use eval to allow arbitrary sort routines

Original module should be much slower

Original module should consume far less memory

Original uses a manual form of garbage collection for delete, proposed module does not.

Thanks in advance. I will by flying to Dallas tomorrow (10 Aug 03), so I apologize in advance for not being able to reply immediately.

Comment on RFC - inplace upgrade for Tie::SortHash Download Code

Replies are listed 'Best First'.
Re: RFC - inplace upgrade for Tie::SortHash by belg4mit (Prior) on Aug 10, 2003 at 02:22 UTC
Interesting use of constant, I kind of like it. I would make a wrapper for tie-ing so that you could provide a sub protoyped to accept an optional block so you can change sort/eval definition system. If no sort is specified it should do a default sort (not even the current "smart" default you have coded). ~~Update, for how to use coderef en lieu of eval.~~ ~~`sub sortblock { my($self, $sort) = @_; local *hash = %{$self->[HASH]}; sort $self->[SORT] keys %hash; $self->[CHANGED] = 1; }`~~ ~~[download]~~ `-- I'm not belgian but I play one on TV.`	[reply] [d/l]
Re: Re: RFC - inplace upgrade for Tie::SortHash by Limbic~Region (Chancellor) on Aug 10, 2003 at 02:39 UTC
belg4mit, I tried for the better part of an hour trying to figure out how to do one of the following with no luck: Get rid of the eval all together Prefer not to use eval, but allow it for backwards compatability The issue is that you are creating a sort routine for a %hash that is defined in the module, not the calling script. I don't see how to get around this even with your suggestion and updated code. The smart sort came from the original module - I left it for backwards compatability. Cheers - L~R Update: I figured out how to do the second one. eval is now only used for backwards compatability if the calling script uses the old q($a cmp $b) syntax instead of a code ref: Read more... (3 kB)	[reply] [d/l]
Re: RFC - inplace upgrade for Tie::SortHash by demerphq (Chancellor) on Aug 10, 2003 at 14:18 UTC
I cant help but wonder if your use of autovivification to create the various elements of the object is dangerous. I wouldnt do it personally. I have a feeling at least some of your code will die if somebody calls the wrong function at the wrong time. For instance, when I turn warnings on (why arent you using them?!) the following snippet produces warnings and also doesnt work as expected: `tie my %hash,'Tie::SortHash',{a=>1,b=>2}; delete $hash{'x'}; print join "\t",keys %hash;` [download] `Use of uninitialized value in splice at D:\Temp\tie_sorthash.pl line 4 +3. b` [download] Where did the 'a' key go? Also delete() doesnt set the CHANGED flag, and will not play nicely with keys. (It should always be possible to delete the last visited key while iterating the hash without disrupting the hash.) `sub _ReOrder { my $self = shift; $self->[LOOKUP] = (); $self->[ARRAY] = ();` [download] If you intend to set these two to undef then I can think of more obvious ways. Otherwise this is a bug. `defined $self->[ARRAY][$index] ? $self->[ARRAY][$index] : undef;` [download] What exactly is the purpose of this line? Isnt the conditional totally redundant? I think you need to revisit the code and build up a big set of tests. I have a feeling there are other whammies in there as well. Another question I have is why the iterator requires a hash lookup each time? --- demerphq _{<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...}	[reply] [d/l] [select]
Re: Re: RFC - inplace upgrade for Tie::SortHash by Limbic~Region (Chancellor) on Sep 05, 2003 at 04:51 UTC
demerphq, I really appreciated your comments. I haven't touched this for almost a month. I was waiting on the module author to return my emails, which did not happen. Today I decided to start over. I would like to address the points you made on the previous code: I cant help but wonder if your use of autovivification to create the various elements of the object is dangerous The code creates a new hash from an old hash. It is only dangerous to the extent that I trusted that what I was being passed was a hash reference without testing it. Why arent you using warnings?! The warnings were not turned on because the original module author did not use them. Where did the 'a' key go? Code I added to optimize the iteration created an array with the hash keys in order. I figured another optimization would be to delete the array element without going through the sort routine again. The problem was that I didn't first verify that the key being deleted actually existed. The 'a' disapeared because it happened to be the 0 index - the result of an undefined variable Also delete() doesnt set the CHANGED flag, and will not play nicely with keys. (It should always be possible to delete the last visited key while iterating the hash without disrupting the hash.) Correct - it doesn't set the changed flag. It accomplishes the same thing by deleting the array element described above. I do not believe there would be any disruption with deleting a key while iterating other than your discovery of deleting a key that doesn't exist. If you intend to set these two to undef then I can think of more obvious ways. Otherwise this is a bug. `defined $self->[ARRAY][$index] ? $self->[ARRAY][$index] : undef; What exactly is the purpose of this line? Isnt the conditional totally + redundant?` [download] The code is correct as written. The conditional is designed to detect when you have fallen off the end of the array and return undef. I am not sure what is more obvious in undef'ing the arrays then what I used? I think you need to revisit the code and build up a big set of tests. I have a feeling there are other whammies in there as well. I indeed did find lots of whammies today when I went back over the code. A few I introduced when I tried to "fix", in my opinion, very bad code. The rest were already there. Another question I have is why the iterator requires a hash lookup each time? I use an array with the hash keys in order. The problem is that I am only aware of the last key. I use the hash lookup to get the index of that element in the array. Getting the next key is then a simple matter of adding 1. Later, when I have time to build up a test suite and finish the POD, I will re-post an RFC that outlines my questions and concerns. In the interim, here is the new non-backwards compatible code. Read more... (5 kB) Cheers - L~R	[reply] [d/l] [select]
Re: Re: Re: RFC - inplace upgrade for Tie::SortHash by demerphq (Chancellor) on Sep 05, 2003 at 16:56 UTC
Today I decided to start over. I would like to address the points you made on the previous code: Hmm, im not up for responding completely yet, so you can expect a /msg that this reply has been updated. However, there is one point id like to address: The code is correct as written. ... `defined $self->[ARRAY][$index] ? $self->[ARRAY][$index] : undef;` [download] Except that its misleading as hell. It is _exactly_ equivelent to `$self->[ARRAY][$index]` [download] Except that it makes a reader wonder what magic specialness is going on, and is marginally slower. If nothing special is happening then it should be changed to the latter IMO --- demerphq _{<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...}	[reply] [d/l] [select]
Re: Re: Re: Re: RFC - inplace upgrade for Tie::SortHash by Limbic~Region (Chancellor) on Sep 05, 2003 at 17:01 UTC
Re: Re: Re: Re: Re: RFC - inplace upgrade for Tie::SortHash by demerphq (Chancellor) on Sep 05, 2003 at 22:26 UTC
Some notes below your chosen depth have not been shown here
Re: RFC - inplace upgrade for Tie::SortHash by perrin (Chancellor) on Aug 10, 2003 at 02:33 UTC
Hmmm. Why not Tie::IxHash? That's what I've always used.	[reply]
Re: Re: RFC - inplace upgrade for Tie::SortHash by Limbic~Region (Chancellor) on Aug 10, 2003 at 02:38 UTC
perrin, Because it just preserves the insertion order and allows you to do a simple sort by value or keys. It doesn't allow an arbitrary sort of a complex hash. It also doesn't allow re-ordering on the fly. Cheers - L~R	[reply]


Syntactic Confectionery Delight
	PerlMonks