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

# 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`.

See Judy.

See Judy.

See Judy.