Judy::L - Efficient integer to integer map
Read a series of key/value pairs from the standard input, store in a JudyL array, and then print out in sorted order.
use Judy::L qw( Set First Next Last Prev Delete Free ); # Load judy. my $judy; Set( $judy, 123, 345 ); Set( $judy, 324, 456 ); Set( $judy, 234, 567 ); # Print in ascending order. print "ascending\n"; my ( undef, $value , $key ) = First( $judy, 0 ); while ( defined $key ) { print "$key=$value\n"; ( undef, $value, $key ) = Next( $judy, $key ); } # Now in descending order, deleting on the way. print "descending\n"; ( undef, $value, $key ) = Last( $judy, -1 ); while ( defined $key ) { print "$key=$value\n"; Delete( $judy, $key ); ( undef, $value, $key ) = Prev( $judy, $key ); } # Ought to be a no-op since Judy is already empty. Free( $judy );
All functions are exportable by Sub::Exporter.
Judy::L is the equivalent of a sparse array of integers. Memory to support the array is allocated as key/value pairs are inserted, and released as key/value pairs are deleted.
The value may be used as a scalar, or a pointer to a structure or block of data (or even another Judy array). JudySL and JudyHS are implemented on top of JudyL where the values are pointers. See http://perlmonks.org/?node_id=733140 for an example.
Nothing special is required to allocate a Judy::L array. Just start using it.
my $judy; if ( Get( $judy, 10 ) ) { .... }
As with an ordinary array, there are no duplicate keys in a Judy::L array.
Insert/set an $Key and $Value into the Judy::L array $Judy.
$Key
$Value
$Judy
Return $PValue pointing to $Value. Your program can use this pointer to read or modify $Value until the next Set(), Delete(), Free() is executed on $Judy. Examples:
$PValue
Set()
Delete()
Free()
use Judy::L qw( Set ); use Judy::Mem qw( Poke Peek ); $pvalue = Set( $judy, 2, 43 ); Poke( $pvalue, 44 ); 44 == Peek( $pvalue );
Note: Set() and Delete() reorganize the Judy::L array. Therefore, $PValue returned from previous Judy::L calls become invalid and must be re-acquired.
Modifies $Judy to point to allocated Judy::L object.
Delete the $Key/$Value pair from the Judy::L array. Return true if the key was removed.
Get the pointer $PValue and value $Value associated with $Key in the $Judy Judy array.
Return $PValue pointing to $Value and $Value. Return nothing if the $Key was not present.
First(), Next(), Last(), Prev() allow you to search for keys in the array. You may search inclusively or exclusively, in either forward or reverse directions. If successful, $Key is returned set to the found key, $PValue is returned set to a pointer to $Key's $Value and $Value is returned. If unsuccessful, nothing is returned.
First()
Next()
Last()
Prev()
FirstEmpty(), NextEmpty(), LastEmpty(), PrevEmpty() allow you to search for keys that are not present ("empty") in the array. You may search inclusively or exclusively, in either forward or reverse directions. If successful, an $Key is returned set to a not present ("empty") key. If unsuccessful, nothing is returned.
Search (inclusive) for the first key present 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 JudyL array.
$Key = 0
Returns nothing if the search finds nothing.
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 JudyL array, or to locate a "neighbor" of a given key.
# Prints the contents of $judy my ( undef, $value, $key ) = First( $judy, 0 ); while ( defined $key ) { print "$key=$value\n"; ( undef, $value, $key ) = Next( $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 JudyL array.
$Key = -1
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 JudyL array, or to locate a "neighbor" of a given key.
Search (inclusive) for the first key absent 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 key absent that is greater than the passed $Key.
Search (inclusive) for the last key absent that is equal to or less than the passed $Key. (Start with $Key = -1, that is, all ones, to find the last key absent in the array.)
Search (exclusive) for the previous key absent that is less than the passed $Key.
Count the number of keys present in $Judy between $Key1 and $Key2 (inclusive).
$Key1
$Key2
Return the count. A return value of 0 can be valid as a count.
To count all keys present in a Judy::L array, use:
my $count = Count( $judy, 0, -1 );
Locate the $Nth key that is present in $Judy ($Nth = 1 returns the first key present).
$Nth
Return pointer to value, value, and key. Return nothing if there isn't an $Nth element.
Frees an entire Judy::L array. This is much faster than a Next/Delete loop. Return number of bytes freed. $Judy is set to 0.
Next
Delete
Return the number of bytes of memory malloc()'ed by $Judy. This is a very fast routine, and may be used before and after a Set() or Delete() call with little performance impact.
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.