From f0a0540239edfa94f727190d35ffe4e7814a8844 Mon Sep 17 00:00:00 2001
From: Marius Gavrilescu <marius@ieval.ro>
Date: Sat, 24 Feb 2018 19:02:05 +0000
Subject: [PATCH 1/1] Initial commit

---
 Changes                   |   4 ++
 MANIFEST                  |   6 ++
 Makefile.PL               |  22 +++++++
 README                    |  44 +++++++++++++
 lib/Tie/Hash/Sorted/XS.pm | 130 ++++++++++++++++++++++++++++++++++++++
 t/Tie-Hash-Sorted-XS.t    |  35 ++++++++++
 6 files changed, 241 insertions(+)
 create mode 100644 Changes
 create mode 100644 MANIFEST
 create mode 100644 Makefile.PL
 create mode 100644 README
 create mode 100644 lib/Tie/Hash/Sorted/XS.pm
 create mode 100644 t/Tie-Hash-Sorted-XS.t

diff --git a/Changes b/Changes
new file mode 100644
index 0000000..b00e035
--- /dev/null
+++ b/Changes
@@ -0,0 +1,4 @@
+Revision history for Perl extension Tie::Hash::Sorted::XS.
+
+0.000_001 2018-02-24T19:02+00:00
+ - Initial release
diff --git a/MANIFEST b/MANIFEST
new file mode 100644
index 0000000..d298900
--- /dev/null
+++ b/MANIFEST
@@ -0,0 +1,6 @@
+Changes
+Makefile.PL
+MANIFEST
+README
+t/Tie-Hash-Sorted-XS.t
+lib/Tie/Hash/Sorted/XS.pm
diff --git a/Makefile.PL b/Makefile.PL
new file mode 100644
index 0000000..ccc6936
--- /dev/null
+++ b/Makefile.PL
@@ -0,0 +1,22 @@
+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',
+		},
+	}
+);
diff --git a/README b/README
new file mode 100644
index 0000000..171fb92
--- /dev/null
+++ b/README
@@ -0,0 +1,44 @@
+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.
+
+
diff --git a/lib/Tie/Hash/Sorted/XS.pm b/lib/Tie/Hash/Sorted/XS.pm
new file mode 100644
index 0000000..2867209
--- /dev/null
+++ b/lib/Tie/Hash/Sorted/XS.pm
@@ -0,0 +1,130 @@
+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
diff --git a/t/Tie-Hash-Sorted-XS.t b/t/Tie-Hash-Sorted-XS.t
new file mode 100644
index 0000000..46431fb
--- /dev/null
+++ b/t/Tie-Hash-Sorted-XS.t
@@ -0,0 +1,35 @@
+#!/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'
-- 
2.39.2