Judy::1 - Efficient integer to bit map
use Judy::1 qw( Set Get Unset Count MemUsed First ); my $judy; print Set( $judy, 123456 ) ? "ok - bit successfully set at 123456\n" : "not ok - bit already set at 123456\n"; print Get( $judy, 654321 ) ? "not ok - set bit at 654321\n" : "ok - bit not set at 654321\n"; my ( $count ) = Count( $judy, 0, -1 ); print "$count bits set in Judy::1 array\n"; my ( $key ) = First( $judy, 0 ); if ( defined $key ) { print "ok - first bit set is at $key\n"; } else { print "not ok - no bits set in array\n"; } printf "$count Keys used %d bytes of memory\n", MemUsed( $judy ); print Unset( $judy, 123456 ) ? "ok - bit successfully unset at 123456\n" : "not ok - bit was not unset at 123456\n";
All functions are exportable by Sub::Exporter.
Judy::1 is the equivalent of a bit array or bit map. A bit is addressed by an $Key. The array may be sparse, and the $Key may be any native integer. If a key is present, it represents a set bit. If a key is absent, it represents an unset bit.
$Key
Nothing special is required to allocate a Judy::1 array. Just start using it.
my $judy; if ( Get( $judy, 10 ) ) { ... }
Memory to support the array is allocated as bits are set, and released as bits are unset. If the Judy::1 pointer ($Judy) is 0 or undef, all bits are unset (and the Judy::1 array requires no memory).
$Judy
As with an ordinary array, a Judy::1 array contains no duplicate keys.
Insert/set $Key's bit in the Judy::1 array $Judy. Return true if the bit was previously unset, false otherwise.
Unset $Key's bit in the Judy::1 array $Judy; that is, remove $Key from the Judy::1 array. Return true if the bit was previously set, false otherwise.
Alias for Unset().
Unset()
Test if $Key's bit is set in the Judy::1 array $Judy. Return true if the bit is set, false otherwise.
Alias for Test().
Test()
Count the number of set bits between $Key1 and $Key2 (inclusive). To count all set bits in a Judy::1 bit array, use:
$Key1
$Key2
$count = Count( $judy, 0, -1 );
Note: The -1 promotes to the maximum integer, that is, all ones.
Locate the c<$Nth> key that is present in the Judy::1 array $Judy ($Nth = 1 returns the first key present). To refer to the last key in a fully populated array (all keys present, which is rare), use $Nth = 0.
$Nth = 1
$Nth = 0
Returns nothing if there is not an nth key.
Free the entire Judy::1 array $Judy (much faster than using a Next(), Unset() loop). Returns the number of bytes freed. $Judy is set to 0.
Returns the number of bytes of memory currently in use by Judy::1 array $Judy. This is a very fast routine, and may be used after a Set() or Unset() call with little performance impact.
The Judy::1 search functions allow you to search for set or unset bits in the array. You may search inclusively or exclusively, in either forward or reverse directions.
Search (inclusive) for the first set $Key that is equal to or greater than the passed $Key. (Start with $Key = 0 to find the first key in the array.) First() is typically used to begin a sorted-order scan of the keys present in a Judy::1 array.
Search (exclusive) for the next key present that is greater than the passed $Key. Next() is typically used to continue a sorted-order scan of the keys present in a Judy::1 array, or to locate a "neighbor" of a given key.
Search (inclusive) for the last key present that is equal to or less than the passed $Key. (Start with $Key = -1, that is, all ones, to find the last key in the array.) Last() is typically used to begin a reverse-sorted-order scan of the keys present in a Judy::1 array.
Search (exclusive) for the previous key present that is less than the passed $Key. Prev() is typically used to continue a reverse-sorted-order scan of the keys present in a Judy::1 array, or to locate a "neighbor" of a given key.
Search (inclusive) for the first absent key that is equal to or greater than the passed $Key. (Start with $Key = 0 to find the first key absent in the array.)
Search (exclusive) for the next absent key that is greater than the passed $Key.
Search (inclusive) for the last absent key that is equal to or less than the passed $Key. (Start with $Key = -1 to find the last key absent in the array.)
Search (exclusive) for the previous absent key that is less than the passed $Key.
See Judy.
To install Judy, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Judy
CPAN shell
perl -MCPAN -e shell install Judy
For more information on module installation, please visit the detailed CPAN module installation guide.