NAME

Judy::1 - Efficient integer to bit map

SYNOPSIS

  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";

EXPORT

All functions are exportable by Sub::Exporter.

DESCRIPTION

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.

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).

As with an ordinary array, a Judy::1 array contains no duplicate keys.

DATA TYPES

$Judy - Judy::1 array

$Key - integer

bool - boolean

count - integer

BASIC FUNCTIONS

bool = Set( $Judy, $Key )

Insert/set $Key's bit in the Judy::1 array $Judy. Return true if the bit was previously unset, false otherwise.

bool = Unset( $Judy, $Key )

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.

bool = Delete( $Judy, $Key )

Alias for Unset().

bool = Test( $Judy, $Key )

Test if $Key's bit is set in the Judy::1 array $Judy. Return true if the bit is set, false otherwise.

bool = Get( $Judy, $Key )

Alias for Test().

count = Count( $Judy, $Key1, $Key2 )

Count the number of set bits between $Key1 and $Key2 (inclusive). To count all set bits in a Judy::1 bit array, use:

    $count = Count( $judy, 0, -1 );

Note: The -1 promotes to the maximum integer, that is, all ones.

$Key = Nth( $Judy, $Nth )

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.

Returns nothing if there is not an nth key.

bytes = Free( $Judy )

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.

bytes = MemUsed( $Judy )

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.

Search Functions

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.

$Key = First( $Judy, $Key )

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.

$Key = Next( $Judy, $Key )

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.

$Key = Last( $Judy, $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.

$Key = Prev( $Judy, $Key )

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.

$Key = FirstEmpty( $Judy, $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.)

$Key = NextEmpty( $Judy, $Key )

Search (exclusive) for the next absent key that is greater than the passed $Key.

$Key = LastEmpty( $Judy, $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.)

$Key = PrevEmpty( $Judy, $Key )

Search (exclusive) for the previous absent key that is less than the passed $Key.

MULTIDIMENSIONAL Judy::L

See Judy.

ERRORS & WARNINGS

See Judy.

AUTHOR

See Judy.

cpanm Judy

perl -MCPAN -e shell
install Judy