lib/Tie/Hash/Sorted/XS.pm

   1 package Tie::Hash::Sorted::XS;
   2
   3 use 5.014000;
   4 use strict;
   5 use warnings;
   6
   7 use Tree::SizeBalanced;
   8
   9 our $VERSION = '0.000_001';
  10
  11 sub TIEHASH {
  12         my ($class, $tree) = @_;
  13         $tree //= Tree::SizeBalanced::str_any->new;
  14         bless \$tree, $class
  15 }
  16
  17 sub FETCH {
  18         my ($self, $key) = @_;
  19         my ($k, $v) = $$self->find($key);
  20         $v
  21 }
  22
  23 sub STORE {
  24         my ($self, $key, $value) = @_;
  25         $$self->delete($key);
  26         $$self->insert($key, $value);
  27 }
  28
  29 sub DELETE {
  30         my ($self, $key) = @_;
  31         $$self->delete($key);
  32 }
  33
  34 # sub CLEAR unimplemented
  35
  36 sub EXISTS {
  37         my ($self, $key) = @_;
  38         my @list = $$self->find($key);
  39         @list > 0;
  40 }
  41
  42 sub FIRSTKEY {
  43         my ($self) = @_;
  44         $$self->find_min
  45 }
  46
  47 sub NEXTKEY {
  48         my ($self, $lastkey) = @_;
  49         $$self->find_gt($lastkey);
  50 }
  51
  52 sub SCALAR {
  53         my ($self) = @_;
  54         $$self->size
  55 }
  56
  57 1;
  58 __END__
  59
  60 =encoding utf-8
  61
  62 =head1 NAME
  63
  64 Tie::Hash::Sorted::XS - hash with ordered keys backed by binary search tree
  65
  66 =head1 SYNOPSIS
  67
  68   use Tie::Hash::Sorted::XS;
  69
  70   tie my %hash, 'Tie::Hash::Sorted::XS';
  71
  72   $hash{Jim} = 5;
  73   $hash{Bob} = 3;
  74   $hash{Anna} = 7;
  75
  76   my $keys = join ' ', keys %hash;
  77
  78   is $keys, 'Anna Bob Jim', 'keys are ordered';
  79   is $hash{Bob}, 3, 'retrieval works';
  80
  81 =head1 DESCRIPTION
  82
  83 This module is not yet fully implemented. Current limitations include
  84 the CLEAR function not being implemented (meaning it is impossible to
  85 assign a list to a tied hash) and iteration being slow (O(n log n) to
  86 iterate over the whole hash). The latter is due to lack of suitable
  87 methods in the underlying L<Tree::SizeBalanced>.
  88
  89 L<Tree::SizeBalanced> is an implementation of a size-balanced tree, a
  90 kind of self-balanced binary search tree. This is a data structure
  91 similar to a Perl hash that permits O(log n) insertion, deletion, and
  92 random access while keeping the keys sorted.
  93
  94 This module is a C<tie> interface to L<Tree::SizeBalanced>. It allows
  95 one to create a hash that is implemented by a L<Tree::SizeBalanced>.
  96 These hashes should work similarly to regular Perl hashes except that
  97 keys will be ordered, keys can be any objects (not just strings), and
  98 they have different performance characteristics.
  99
 100 The module is used by calling the tie function:
 101
 102 =over
 103
 104 =item B<tie> my %hash, 'Tie::Hash::Sorted::XS'[, I<$tree>]
 105
 106 This ties a brand new hash to a given L<Tree::SizeBalanced> object (or
 107 if none is given, C<< Tree::SizeBalanced::str_any->new >> is used).
 108
 109 Whenever this hash is iterated, the keys will come ordered.
 110
 111 =back
 112
 113 =head1 SEE ALSO
 114
 115 L<Tree::SizeBalanced>, L<http://wcipeg.com/wiki/Size_Balanced_Tree>
 116
 117 =head1 AUTHOR
 118
 119 Marius Gavrilescu, E<lt>marius@ieval.roE<gt>
 120
 121 =head1 COPYRIGHT AND LICENSE
 122
 123 Copyright (C) 2018 by Marius Gavrilescu
 124
 125 This library is free software; you can redistribute it and/or modify
 126 it under the same terms as Perl itself, either Perl version 5.24.3 or,
 127 at your option, any later version of Perl 5 you may have available.
 128
 129
 130 =cut