--- /dev/null
+Revision history for Perl extension Tie::Hash::Sorted::XS.
+
+0.000_001 2018-02-24T19:02+00:00
+ - Initial release
--- /dev/null
+Changes
+Makefile.PL
+MANIFEST
+README
+t/Tie-Hash-Sorted-XS.t
+lib/Tie/Hash/Sorted/XS.pm
--- /dev/null
+use ExtUtils::MakeMaker;
+use strict;
+use warnings;
+
+WriteMakefile(
+ NAME => 'Tie::Hash::Sorted::XS',
+ VERSION_FROM => 'lib/Tie/Hash/Sorted/XS.pm',
+ ABSTRACT_FROM => 'lib/Tie/Hash/Sorted/XS.pm',
+ AUTHOR => 'Marius Gavrilescu <marius@ieval.ro>',
+ MIN_PERL_VERSION => '5.14.0',
+ LICENSE => 'perl',
+ SIGN => 1,
+ PREREQ_PM => {
+ qw/Tree::SizeBalanced 0/,
+ },
+ META_ADD => {
+ dynamic_config => 0,
+ resources => {
+ repository => 'https://git.ieval.ro/?p=tie-hash-sorted-xs.git',
+ },
+ }
+);
--- /dev/null
+Tie-Hash-Sorted-XS version 0.000_001
+====================================
+
+This module is not yet fully implemented. Current limitations include
+the CLEAR function not being implemented (meaning it is impossible to
+assign a list to a tied hash) and iteration being slow (O(n log n) to
+iterate over the whole hash). The latter is due to lack of suitable
+methods in the underlying Tree::SizeBalanced.
+
+Tree::SizeBalanced is an implementation of a size-balanced tree, a
+kind of self-balanced binary search tree. This is a data structure
+similar to a Perl hash that permits O(log n) insertion, deletion, and
+random access while keeping the keys sorted.
+
+This module is a tie interface to Tree::SizeBalanced. It allows one to
+create a hash that is implemented by a Tree::SizeBalanced.
+These hashes should work similarly to regular Perl hashes except that
+keys will be ordered, keys can be any objects (not just strings), and
+they have different performance characteristics.
+
+INSTALLATION
+
+To install this module type the following:
+
+ perl Makefile.PL
+ make
+ make test
+ make install
+
+DEPENDENCIES
+
+This module requires these other modules and libraries:
+
+* Tie::Hash::Sorted::XS
+
+COPYRIGHT AND LICENCE
+
+Copyright (C) 2018 by Marius Gavrilescu
+
+This library is free software; you can redistribute it and/or modify
+it under the same terms as Perl itself, either Perl version 5.24.3 or,
+at your option, any later version of Perl 5 you may have available.
+
+
--- /dev/null
+package Tie::Hash::Sorted::XS;
+
+use 5.014000;
+use strict;
+use warnings;
+
+use Tree::SizeBalanced;
+
+our $VERSION = '0.000_001';
+
+sub TIEHASH {
+ my ($class, $tree) = @_;
+ $tree //= Tree::SizeBalanced::str_any->new;
+ bless \$tree, $class
+}
+
+sub FETCH {
+ my ($self, $key) = @_;
+ my ($k, $v) = $$self->find($key);
+ $v
+}
+
+sub STORE {
+ my ($self, $key, $value) = @_;
+ $$self->delete($key);
+ $$self->insert($key, $value);
+}
+
+sub DELETE {
+ my ($self, $key) = @_;
+ $$self->delete($key);
+}
+
+# sub CLEAR unimplemented
+
+sub EXISTS {
+ my ($self, $key) = @_;
+ my @list = $$self->find($key);
+ @list > 0;
+}
+
+sub FIRSTKEY {
+ my ($self) = @_;
+ $$self->find_min
+}
+
+sub NEXTKEY {
+ my ($self, $lastkey) = @_;
+ $$self->find_gt($lastkey);
+}
+
+sub SCALAR {
+ my ($self) = @_;
+ $$self->size
+}
+
+1;
+__END__
+
+=encoding utf-8
+
+=head1 NAME
+
+Tie::Hash::Sorted::XS - hash with ordered keys backed by binary search tree
+
+=head1 SYNOPSIS
+
+ use Tie::Hash::Sorted::XS;
+
+ tie my %hash, 'Tie::Hash::Sorted::XS';
+
+ $hash{Jim} = 5;
+ $hash{Bob} = 3;
+ $hash{Anna} = 7;
+
+ my $keys = join ' ', keys %hash;
+
+ is $keys, 'Anna Bob Jim', 'keys are ordered';
+ is $hash{Bob}, 3, 'retrieval works';
+
+=head1 DESCRIPTION
+
+This module is not yet fully implemented. Current limitations include
+the CLEAR function not being implemented (meaning it is impossible to
+assign a list to a tied hash) and iteration being slow (O(n log n) to
+iterate over the whole hash). The latter is due to lack of suitable
+methods in the underlying L<Tree::SizeBalanced>.
+
+L<Tree::SizeBalanced> is an implementation of a size-balanced tree, a
+kind of self-balanced binary search tree. This is a data structure
+similar to a Perl hash that permits O(log n) insertion, deletion, and
+random access while keeping the keys sorted.
+
+This module is a C<tie> interface to L<Tree::SizeBalanced>. It allows
+one to create a hash that is implemented by a L<Tree::SizeBalanced>.
+These hashes should work similarly to regular Perl hashes except that
+keys will be ordered, keys can be any objects (not just strings), and
+they have different performance characteristics.
+
+The module is used by calling the tie function:
+
+=over
+
+=item B<tie> my %hash, 'Tie::Hash::Sorted::XS'[, I<$tree>]
+
+This ties a brand new hash to a given L<Tree::SizeBalanced> object (or
+if none is given, C<< Tree::SizeBalanced::str_any->new >> is used).
+
+Whenever this hash is iterated, the keys will come ordered.
+
+=back
+
+=head1 SEE ALSO
+
+L<Tree::SizeBalanced>, L<http://wcipeg.com/wiki/Size_Balanced_Tree>
+
+=head1 AUTHOR
+
+Marius Gavrilescu, E<lt>marius@ieval.roE<gt>
+
+=head1 COPYRIGHT AND LICENSE
+
+Copyright (C) 2018 by Marius Gavrilescu
+
+This library is free software; you can redistribute it and/or modify
+it under the same terms as Perl itself, either Perl version 5.24.3 or,
+at your option, any later version of Perl 5 you may have available.
+
+
+=cut
--- /dev/null
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+use Test::More tests => 5;
+BEGIN { use_ok('Tie::Hash::Sorted::XS') };
+
+tie my %hash, 'Tie::Hash::Sorted::XS';
+
+$hash{Jim} = 5;
+$hash{Bob} = 3;
+$hash{Anna} = 7;
+
+my $keys = join ' ', keys %hash;
+
+is $keys, 'Anna Bob Jim', 'keys are ordered';
+is $hash{Bob}, 3, 'retrieval works';
+
+
+tie my %refhash, 'Tie::Hash::Sorted::XS', Tree::SizeBalanced::any_int->new(sub { $$a <=> $$b });
+$refhash{\5} = 1;
+my $three = 3;
+$refhash{\$three} = 2;
+my $tworef = \2;
+$refhash{$tworef} = 3;
+
+my $values = '';
+for (keys %refhash) {
+ $values .= $refhash{$_} . ' ';
+}
+chop $values;
+
+my @keys = keys %refhash;
+is ref($keys[0]), 'SCALAR', 'non-string keys work';
+is $values, '3 2 1', 'values of refhash'
projects / tie-hash-sorted-xs.git / commitdiff