Dr. James Freeman > Heap-Priority > Heap::Priority

Download:
Heap-Priority-0.01.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 0.01   Source   Latest Release: Heap-Priority-0.11

NAME

Heap::Priority - Implements a priority queue or stack

SYNOPSIS

    use Heap::Priority;
    my $h = new Heap::Priority;
    $h->add($item,[$priority]); # add an item to the heap
    $next_item = $h->pop;       # get an item back from heap
    $h->fifo;                   # set first in first out ie a queue (default)
    $h->lifo;                   # set last in first out ie a stack
    $h->highest_first;          # set pop() in high to low priority order (default)
    $h->lowest_first;           # set pop() in low to high priority order

    $h->modify_priority($item, $priority);
    $h->delete_item($item,[$priority]);
    $h->delete_priority_level($priority);
    @levels    = $h->get_priority_levels;
    @items     = $h->get_level($priority);
    @all_items = $h->get_heap;
    $h->raise_error(1);
    my $error_string = $h->err_str;

DESCRIPTION

This module implements a priority queue or stack. The main functions are add() and pop() which add and remove from the heap according to the rules you choose. When you add() an item to the heap you can assign a priority level to the item or let the priority level default to 0.

What happens when you call pop() depends on the configuration you choose. By default the highest priority values will be popped off in first in first out order. fifo() and lifo() set First in First Out and Last In First Out respectively. highest_first() and lowest_first() allow you to choose to pop() the highest priority values first or the lowest priority values first.

The internal object model remains constant so you can modify the behavior of pop() with impunity during the life of a heap object.

modify_priority() allows you to change the priority of a item already in the heap. A range of other functions are also available to manipulate the heap.

EFFICIENCY

The algorithm used in this module is only efficient where the number of priority levels is either small in absolute terms or some small fraction of the total number of items. Efficiency drops off over a few thousand priority levels.

OBJECT INTERFACE

This is an OO module. You begin by creating a new heap object

    use Heap::Priority;
    my $h = new Heap::Priority;

You then simply call methods on your heap object:

    $h->add($item, $priority);      # add $item with $priority level
    $h->lifo;                       # set Last In First Out (ie stack)
    my $next_item = $h->pop;        # get the next item off the heap

METHODS

new()

    my $h = new Heap::Priority;

The constructor takes no arguments and simply returns an empty default heap. The default configuration is FIFO (ie a queue) with highest integer priority values popped first

add($item,[$priority])

    $h->add($item, [$priority]);

add() will add $item to the heap. Optionally a an integer $priority level may be assigned (default priority level is 0).

pop()

    my $next_item = $h->pop;

pop() takes no arguments. In default configuration pop() will return those values having the highest integer priority level first in FIFO order. This behavior can be modified using the methods outlined below.

fifo()

    $h->fifo;

Set pop() to work on a First In First Out basis, otherwise known as a queue. This is the default configuration.

lifo()

    $h->lifo;

Set pop() to work on a Last In First Out basis, otherwise known as a stack.

highest_first()

    $h->highest_first;

Set pop() to retrieve items in highest to lowest integer priority order. This is the default configuration.

lowest_first()

    $h->lowest_first;

Set pop() to retrieve items in lowest to highest integer priority order

modify_priority($item,[$priority])

    $h->modify_priority($item, $priority);

This method allows you to modify the priority of an item in the queue/stack. All it actually does is call delete_item($item) and then add($item,$priority) so all the instances of $item in the heap will be removed and replaced with a single instance of $item at $priority level

delete_item($item,[$priority])

    $h->delete_item($item,[$priority]);

This method will delete $item from the heap. If the optional $priority is not supplied all instances $item will be removed from the heap. If $priority is supplied then only instances of $item at that priority level will be removed.

delete_priority_level($priority)

    $h->delete_priority_level($priority);

Delete all items of priority level $priority

get_priority_levels()

    my @levels = $h->get_priority_levels;

Returns list of priority levels in current pop() order in list context and number of priority levels in scalar context

get_level($priority)

    my @items = $h->get_level($priority);

Returns entire priority level in pop() order in list context or number of items at that level in scalar context

get_heap()

    my @all_items = $h->get_heap;

Returns entire heap in pop() order in list context or total number of items on heap in scalar context

raise_error($n)

    $h->raise_error(1);

Set error level $n => 2 = croak, 1 = carp, 0 = silent (default)

err_str()

    $h->err_str;

Return error string if any.

EXPORT

Nothing: it's an OO module.

BUGS

Probably. If you find one let me know...

AUTHOR

Dr James Freeman <jfreeman@tassie.net.au>

syntax highlighting: