package Bit::Vector::Judy;

use 5.008008;
use strict;
use warnings;

require Exporter;

our @ISA = qw(Exporter);

# Items to export into callers namespace by default. Note: do not export
# names by default without a very good reason. Use EXPORT_OK instead.
# Do not simply export all your public functions/methods/constants.

# This allows declaration	use Bit::Vector::Judy ':all';
# If you do not need this, moving things directly into @EXPORT or @EXPORT_OK
# will save memory.
our %EXPORT_TAGS = ( 'all' => [ qw(
    judy1_init
    judy1_set
    judy1_unset
    judy1_test
    judy1_free
    judy1_count
    judy1_bycount
    judy1_memused
    judy1_first
    judy1_next
    judy1_last
    judy1_prev
    judy1_first_empty
    judy1_next_empty
    judy1_last_empty
    judy1_prev_empty
    judy1_clone
    judy1_and
    judy1_or
    judy1_assign_or
    judy1_assign_andnot
    judy1_assign_and
    judy1_freeze
    judy1_thaw
) ] );

our @EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } );

our @EXPORT = qw(
	
);

our $VERSION = '0.03';

require XSLoader;
XSLoader::load('Bit::Vector::Judy', $VERSION);

# Preloaded methods go here.
sub new {
    my ($class) = @_;
    my $set = 0;
    my $self = \$set;
    bless $self, $class;
    return $self;
}

sub set         { my ($self, $index) = @_;           return judy1_set($$self, $index);             }
sub unset       { my ($self, $index) = @_;           return judy1_unset($$self, $index);           }
sub test        { my ($self, $index) = @_;           return judy1_test($$self, $index);            }
sub DESTROY     { my ($self) = @_;                   return judy1_free($$self);                    }
sub count       { my ($self, $index1, $index2) = @_; return judy1_count($$self, $index1, $index2); }
sub bycount     { my ($self, $nth) = @_;             return judy1_bycount($$self, $nth);           }
sub memused     { my ($self) = @_;                   return judy1_memused($$self);                 }
sub first       { my ($self, $index) = @_;           return judy1_first($$self, $index);           }
sub next        { my ($self, $index) = @_;           return judy1_next($$self, $index);            }
sub last        { my ($self, $index) = @_;           return judy1_last($$self, $index);            }
sub prev        { my ($self, $index) = @_;           return judy1_prev($$self, $index);            }
sub first_empty { my ($self, $index) = @_;           return judy1_first_empty($$self, $index);     }
sub next_empty  { my ($self, $index) = @_;           return judy1_next_empty($$self, $index);      }
sub last_empty  { my ($self, $index) = @_;           return judy1_last_empty($$self, $index);      }
sub freeze      { my ($self) = @_;                   return judy1_freeze($$self);                  }
sub thaw        { my ($self, $str)   = @_;           return judy1_thaw($$self, $str);              }

sub clone {
    my ($self) = @_;
    my $set = judy1_clone($$self);
    my $new = \$set;
    bless $new, ref $self;
    return $new;
}

sub and {
    my ($self, $other) = @_;
    my $set = judy1_and($$self, $$other);
    my $new = \$set;
    bless $new, ref $self;
    return $new;
}

sub or {
    my ($self, $other) = @_;
    my $set = judy1_or($$self, $$other);
    my $new = \$set;
    bless $new, ref $self;
    return $new;
}

sub assign_or {
    my ($self, $other) = @_;
    judy1_assign_or($$self, $$other);
}

sub assign_andnot {
    my ($self, $other) = @_;
    judy1_assign_andnot($$self, $$other);
}

sub assign_and {
    my ($self, $other) = @_;
    judy1_assign_and($$self, $$other);
}


1;
__END__

=head1 NAME

Bit::Vector::Judy - Perl interface to Judy bit vectors

=head1 SYNOPSIS

Function-oriented style:

  use Bit::Vector::Judy ':all';
  $set = 0;
  judy1_set($set, $idx);
  judy1_unset($set, $idx);
  $bool = judy1_test($set, $idx);

  $count = judy1_bycount($set, $nth);
  $idx = judy1_first($set, $idx);
  while (defined($idx = judy1_next($set, $idx))) { ... }
  $idx = judy1_last($set, $idx);
  while (defined($idx = judy1_prev($set, $idx))) { ... }
  $idx = judy1_first_empty($set, $idx);
  while (defined($idx = judy1_next_empty($set, $idx))) { ... }
  $idx = judy1_last_empty($set, $idx);
  while (defined($idx = judy1_prev_empty($set, $idx))) { ... }

  $count = judy1_count($set, $index1, $index2);
  $bytes = judy1_memused($set);

  judy1_free($set);

Object-oriented style:

  use Bit::Vector::Judy;

  $set = Bit::Vector::Judy->new;
  $set->set($idx);
  $set->unset($idx);
  $bool = $set->test($idx);

  $count = $set->bycount($nth);
  $idx = $set->first($idx);
  while (defined($idx = $set->next($idx))) { ... }
  $idx = $set->last($idx);
  while (defined($idx = $set->prev($idx))) { ... }
  $idx = $set->first_empty($idx);
  while (defined($idx = $set->next_empty($idx))) { ... }
  $idx = $set->last_empty($idx);
  while (defined($idx = $set->prev_empty($idx))) { ... }

  $count = $set->count($index1, $index2);
  $bytes = judy1_memused($set);

  $set2 = $set->clone();
  $set3 = $set->and($set2);

=head1 DESCRIPTION

The Bit::Vector::Judy package provides two interface to the bit vector
functions of the Judy library: A simple function-oriented and an
object-oriented one. Note that the parameter $set is modified by these
functions and using multiple variables which refer to the same bit
vector is NOT safe - unless you really know what you are doing, use the
object-oriented interface instead.
parameter. 

=head2 Functions:

=over

=item judy1_init($set)

Initializes $set to an empty set. $set = 0 does exactly the same thing
and is probably preferable.

=item judy1_set($set, $idx)

Set the bit with index $idx (0-based) to 1.

=item judy1_unset($set, $idx)

Set the bit with index $idx (0-based) to 0.

=item judy1_test($set, $idx)

Return the value of the bit with index $idx.

=item judy1_bycount($set, $nth)

Return the index of the $nth (1-based) set bit. If there aren't that
many set bits, undef is returned.

=item judy1_first($set, $idx)

Return the index of the first set bit with index $idx or greater.
Returns undef if not found. To get the first set in the set, call 
judy1_first($set, 0). This is often used to start a loop.
Note that unlike in the C macro J1F(), $idx is NOT
modified in place - the new index is returned instead.

=item judy1_next($set, $idx)

Return the index of the first set bit with index greater than $idx or
undef if not found. This is often used to continue a loop.

=item judy1_last($set, $idx)

Return the index of the last set bit with index less or equal to $idx or
undef if not found. Use $idx -1 to get the last bit in the set.

=item judy1_prev($set, $idx)

Guess!

=item judy1_first_empty, judy1_next_empty, judy1_last_empty, judy1_prev_empty

As above, but search for a bit which is not set.

=item judy1_count($set, $idx1, $idx2);

Count the set bits between index $idx1 and $idx2 (inclusive). To count
the bits in the whole set, use indices 0, -1.

=item judy1_memused($set)

Return the memory used by this set in bytes.

=item judy1_free($set)

Free the set. This function MUST be called or the memory occupied by the
set will leak.

=back

The object-oriented interface is almost the same, except that 
Bit::Vector::Judy->new() is used to create a new bit vector object and
the methods without the prefix judy1_ are called on this object. Also,
you don't have to clean up - when an object goes out of scope, the
DESTROY method is called which frees the memory.

=head2 Convenience methods:

The following functions are not part of the C library. They have been
included for convenience and speed (looping over large sets in Perl
isn't really fast):

=over

=item $set2 = $set->clone()

Create a new set with the same contents.

=item $set3 = $set->and($set2);

Compute the bitwise AND of $set and $set2

=item $set3 = $set->or($set2);

Compute the bitwise OR of $set and $set2

=item $set->assign_or($set2);

Compute the bitwise OR of $set and $set2 and assign it to $set.
This is faster than $set = $set->or($set2).

=item $set->assign_andnot($set2);

Compute the bitwise AND of C<$set> and the negation of C<$set2> and
assign it to C<$set>.
This is a fast way to remove all members of C<$set2> from C<$set>.

=item $set->assign_and($set2);

Compute the bitwise AND of $set and $set2 and assign it to $set.
This is faster than $set = $set->and($set2).

=back

=head2 Serialization

=over

=item $string = $set->freeze()

Serializes a set into a byte string. The format is a like pack format
"w", where the first integer represents the fist index, and every
following is an offset to the previous. (Note: This format may change in
future versions)

=item $set->thaw($string)

Deserializes a byte string created by thaw into $set. This is intended
to be used on an empty set, and does not clear any bits which are
already set, so multiple calls to thaw may be used to assemble a bit
vector from multiple strings.

=back

=head2 EXPORT

None by default.

The tag :all imports all the functions starting with judy1_.


=head1 SEE ALSO

Judy(3), Tie::Judy(3), http://judy.sourceforge.net

=head1 AUTHOR

Peter J. Holzer, E<lt>hjp@hjp.at<gt>

=head1 COPYRIGHT AND LICENSE

Copyright (C) 2007 by Peter J. Holzer

This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself, either Perl version 5.8.8 or,
at your option, any later version of Perl 5 you may have available.

TODO

=over 

=item
Clean up (Warning: The API might change!)

=item 
Add more convenience functions: xor, ...

=item
Variants of existing functions. I almost always call count(0,-1), so 
count() should do the same thing. Also freeze($min, $max) might be
useful for freezing a range.

=back

=cut
