Initial commit

[tie-hash-sorted-xs.git] / lib / Tie / Hash / Sorted / XS.pm

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