package Heap::Simple;
use Carp;
use strict;
# Switch selecting XS or pure perl
use vars qw($VERSION @ISA @implementors);
$VERSION = "0.13";
unless (@ISA) {
@implementors = qw(Heap::Simple::XS(0.10) Heap::Simple::Perl(0.13))
unless @implementors;
for my $i (@implementors) {
my $plugin = $i;
my $version = $plugin =~ s/\((.+)\)\z// ? $1 : undef;
my $p = "$plugin.pm";
$p =~ s!::!/!g;
if (eval { require $p; 1 }) {
*new = $plugin->can("new") ||
croak "Package '$plugin' does not support 'new'";
if (defined $version) {
if (defined(my $v = $plugin->VERSION)) {
if ($v < $version) {
carp "Need '$plugin' version $version, found version $v";
next;
}
} else {
croak "Could not determine the version of '$plugin'";
}
}
@ISA = ($plugin);
last;
}
}
@ISA || croak "Can't locate ", join(" nor ", @implementors), " in \@INC. This probably means you didn't install any of them. (\@INC contains: @INC)";
}
1;
__END__
=head1 NAME
Heap::Simple - Fast and easy to use classic heaps
=head1 SYNOPSIS
use Heap::Simple;
# Create a heap
my $heap = Heap::Simple->new;
my $heap = Heap::Simple->new(%options);
# Put data in the heap
$heap->insert(@new_elements);
# Put data in a "Object" or "Any" heap with a given key
$heap->key_insert($key1, $element1, $key2, $element2, ...);
# Extract the top value
$element = $heap->extract_top; # croaks on an empty heap
$element = $heap->extract_first; # returns undef on an empty heap
# Get the top value but leave it in the heap
$element = $heap->top; # croaks on an empty heap
$element = $heap->first; # returns undef on an empty heap
# Find the top key in the heap
$top_key = $heap->top_key; # return infinity on an empty heap
# croaks if there's no infinity
$top_key = $heap->first_key; # returns undef on an empty heap
# Ordered extract of all data whose key is not above a given value
@elements = $heap->extract_upto($max_key);
# Ordered extract of all data
@elements = $heap->extract_all;
# Empty the heap
$heap->clear;
# Find the number of elements
$count = $heap->count;
# Get all keys (not sorted)
@keys = $heap->keys;
# Get all values (not sorted)
@values = $heap->values;
# Find the key corresponding to a value
$key = $heap->key($value);
# Get/Set user_data
$user_data = $heap->user_data;
$old_data = $heap->user_data($new_data);
# Get/Set infinity
$infinity = $heap->infinity;
$old_infinity = $heap->infinity($new_data);
# Get the position of a key in an element
$key_index = $heap->key_index;
$key_name = $heap->key_name;
$key_method = $heap->key_method;
$key_function = $heap->key_function;
# Return the value of several things that were set in new:
$wrapped = $heap->wrapped;
$max_count = $heap->max_count;
$can_die = $heap->can_die;
$dirty = $heap->dirty;
$order = $heap->order;
@elements = $heap->elements;
$elements = $heap->elements;
# Move all elements out of each heap in @heaps and into $heap
$heap->absorb(@heaps); # As if doing a repeated $heap->insert
$heap->key_absorb(@heaps); # As if doing a repeated $heap->key_insert
# merge already sorted arrays into a new sorted array
# This doesn't disturb the elements already in the heap
my $merged_aref = $heap->merge_arrays($aref1, $aref2, ...);
# Which class does the actual work ?
$implementation = Heap::Simple->implementation;
=head1 EXAMPLE1
When key and value are kept separate:
use Heap::Simple;
my $heap = Heap::Simple->new(elements => "Any");
$heap->key_insert(8, "bar");
$heap->key_insert(5, "foo");
# This will print foo (5 is the lowest key)
print "First value is ", $heap->extract_top, "\n";
$heap->key_insert(7, "baz");
# This will print baz (7 is the lowest key)
print "Next value is ", $heap->extract_top, "\n";
# This will print bar (8 is now the lowest key)
print "Next value is ", $heap->extract_top, "\n";
=head1 EXAMPLE2
When the key is part of the value:
# This is purely for display, ignore it
use Data::Dumper;
$Data::Dumper::Indent = 0;
$Data::Dumper::Terse = 1;
# Real code starts here
use Heap::Simple;
my $heap = Heap::Simple->new(elements => "Array");
$heap->insert([8, "bar"]);
$heap->insert([5, "foo"]);
# This will print [5, foo] (5 is the lowest key)
print "First value is ", Dumper($heap->extract_top), "\n";
$heap->insert([7, "baz"]);
# This will print [7, baz] (7 is the lowest key)
print "Next value is ", Dumper($heap->extract_top), "\n";
# This will print [8, bar] (8 is now the lowest key)
print "Next value is ", Dumper($heap->extract_top), "\n";
=head1 DESCRIPTION
A heap is a partially sorted structure where it's always easy to extract the
smallest element. If the collection of elements is changing dynamically, a
heap has less overhead than keeping the collection fully sorted.
The order in which equal elements get extracted is unspecified.
The main order relations supported by this module are "<" (numeric compare)
and "lt" (string compare).
The module allows you to manage data where the elements are of several
allowed types, in particular array references, hash references, objects
or just the keys themselves.
So L has a lot of ways to specify element types, but the right
choices follows quite directly from the data you'll put in the heap. If the key
is part of the data (or easily derived from the data), choose an element
type that tells how to get the key out of the data, and insert elements
using L. If the key is independent from the data or
you want to avoid repeated key calculations, use the L element
type and insert elements using L.
The internals of the module do nothing with the elements inserted except
inspecting the key. This means that if you for example store a blessed
object, that's what you will get back on extract. It's also ok to keep
references to the elements around and make changes to them while they are
in the heap as long as you don't change the key.
Heap::Simple itself is just a loader for the code that will actually implement
the functionality mentioned above. You will need to install something like
L or
L to be able to actually do anything.
=head1 EXPORT
None.
=head1 METHODS
All methods that can fail will thrown an exception in case of failure
unless otherwise specified. For example, you don't have to explicitely
check the result of L, it will already thrown an exception in
case of bad arguments.
=over
=item Xmy $heap = Heap::Simple->new
This simplest form creates a new (empty) heap object able to hold numeric keys.
You could for example use this to print a list of numbers from low to high:
use Heap::Simple;
my $heap = Heap::Simple->new;
$heap->insert(8, 3, 14, -1, 3);
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: -1 3 3 8 14
This example is silly of course. You could just as well directly use
L. But in real applications you would do the
inserting interleaved with extracting and always keeping the list sorted
would become inefficient for big lists. That is where you would use a heap.
The examples we give will however be like the one above so you can quickly
see the way in which the methods are supposed to be called.
For some applications this basic usage where you just store numeric keys will
be good enough, but usually you want to be able to store more complex elements.
Several options can help you with that:
=over 2
=item Xorder => $order
$order indicates what operation is used to compare keys. Supported orders are:
=over 2
=item E
Indicates that keys are compared as numbers, and extraction is lowest value
first. This is actually the default order, so the example above could have
used:
my $heap = Heap::Simple->new(order => "<");
and the result would have been exactly the same.
The default infinity for this order is +inf.
=item E
Indicates that keys are compared as numbers, and extraction is highest value
first.
Repeating the example with this order gives:
use Heap::Simple;
my $heap = Heap::Simple->new(order => ">");
$heap->insert(8, 3, 14, -1, 3);
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: 14 8 3 3 -1
The default infinity for this order is -inf.
=item lt
Indicates that the keys are compared as strings, and extraction is lowest
value first. So we could modify the "<" example to:
use Heap::Simple;
my $heap = Heap::Simple->new(order => "lt");
$heap->insert("ate", 8, 3, "zzzz", 14, -1, 3, "at");
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: -1 14 3 3 8 at ate zzzz
Notice how 14 comes before 3 as you would expect in lexical sorting.
The default infinity for this order is "undef" (there is no maximum string)
=item gt
Indicates that the keys are compared as strings, and extraction is highest
value first. The concept of "minimum" again becomes rather confusing.
The standard example now becomes:
use Heap::Simple;
my $heap = Heap::Simple->new(order => "gt");
$heap->insert("ate", 8, 3, "zzzz", 14, -1, 3, "at");
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: zzzz ate at 8 3 3 14 -1
The default infinity for this order is "" (the empty string)
=item X$code_reference
If your keys are completely weird things, ordered neither as numbers nor as
strings and you need a special compare function, you can use this general
ordering type.
Every time two keys need to be compared, the given code reference will be
called like:
$less = $code_reference->($key1, $key2);
This should return a true value if $key1 is smaller than $key2 and a false
value otherwise. $code_reference should imply a total order relation, so it
needs to be transitive.
Since in this case nothing can be determined about the key type, there will
be no infinity by default (even if the keys are numbers).
Example:
use Heap::Simple;
sub more { return $_[0] > $_[1] }
my $heap = Heap::Simple->new(order => \&more);
$heap->insert(8, 3, 14, -1, 3);
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: 14 8 3 3 -1
The code reference will be called many times during normal heap operations
(O(log n) times for a single insert or extract on a size n heap), so only use
this order type within reason. Usually it's better to precalculate some number
or string representation of some sort of key and use normal compares on these.
You can use the L and L to
wrap the precalculated key with the corresponding element, or you can delegate
the key calculation to the L method and use one of the
L, L