Priority Queue

Ulrich Hoffmann <uho@xlerb.de>

Version 1.0.0 - 2016-02-21

This package provides an implementation of priority queues for standard Forth-94 and Forth-2012 compliant systems.

A priority queue is an abstract data type that allows to store items along with a priority and to retrieve these items in order of their prioriority.

Installation

To use the priority queue data structure, just INCLUDE priority-queue.fs on any standard system. This makes the defining word Priority-Queue: and the priotioty queue accessor words available. After loading you still have a standard system.

The items that are stored in the queues are double cell values, the priority along with a single cell value, that can be either the value of interest itself or a pointer to the data.

Documentation

See the file glossary.md for a description of the defined words.

Example usage

Here are some examples how to use priority queues (actually from the unit tests):

Test,_that 

   10 Priority-Queue: q  \ define priority queue of size 10

   \ fill queue with some items
   10 ( prio )  100 ( val )  q q-append
   20 ( prio )  200 ( val )  q q-append
   30 ( prio )  300 ( val )  q q-append

   \ insert new value at appropriate position according to its priority 
   25 ( prio )  250 ( val ) q q!

   \ retrieve priorities and values in priority order (lowest first)
   q q@   ( 10 100 )
   q q@   ( ... 20 200 )
   q q@   ( ... 25 250 )
   q q@   ( ... 30 300 )

has 

   10 100   20 200   25 250    30 300

as_result.


Test,_that  ( priority queues raise an error on underflow )

   3 Priority-Queue: q  \ define priority queue of size 3

   \ fetch empty priority queue
   q ' q-drop catch  nip

has

   #Q-UNDERFLOW

as_result.


Test,_that ( priority queues raise an error on overflow )

   3 Priority-Queue: q  \ define priority queue of size 3

   \ fill priority queue with more items than it can hold
   1 10 q ' q-append catch  ( ok )
   2 20 q ' q-append catch  ( ok ) 
   3 30 q ' q-append catch  ( ok )
   4 40 q ' q-append catch  ( 4 40 q err ) nip nip nip  

has

   0 0 0 #Q-OVERFLOW 

as_result.

Bug Reports

Please send bug reports, improvements and suggestions to Ulrich Hoffmann <uho@xlerb.de>

Conformance

This program conforms to Forth-94 and Forth-2012

May the Forth be with you!