PAL CARD CATALOG ENTRY

SHORT DESCRIPTION

Creates and manipulates a prioritized queue


MOVEMENT WITHIN THE PAL CARD CATALOG
Move to top-level taxonomy
Move to keyword list

ASSET PROFILE

UNIT NAME
Generic_Priority_Queue (GPRIQUEUE)
VERSION
1.0.0
REVIEW CODE
RI; CS(Verdix Ada/SUN); AR; C1 1.0 A
INET ADDRESS
cpscada@citron.cs.clemson.edu
or ...!gatech!hubcap!citron!cpscada
AUTHOR
William Thomas Wolfe
for the Clemson Ada Software Repository
Department of Computer Science, Clemson University
Clemson, SC 29634-1906 (1-803-654-3444)
RIGHTS
ACM-STYLE COPYRIGHT
COPYRIGHT
(c) Clemson University (1989)
DATE CREATED
Dec 1988
DATE RELEASED
July 1, 1989
DATE LAST UPDATED
July 1, 1989
LOCATION
ASR
AdaNET
ENVIRONMENT
Telesoft TeleGen2 / Sun-3
Verdix Ada / SUN-3
LIMITATIONS
Not documented in PAL database
CERTIFICATION
Ada System Certifier_1 1.0
Date/Time of Processing: Thursday  26 May       1994 12:48:43Pm
Overall Assessment of System: OK
Classification of System: A
Basis of Classification --
Syntax Errors                               PASS
Completeness                                PASS
Independence from External Libraries        PASS
Independence from a Specific Ada Compiler   PASS

Number of ...
Files               2
Library Units       2
Lines            1140
Statements        442
Comments          213

FILE LISTING

Directory Display


languages/ada/asr/components/gpriqueue:
  File Name                 Size
  ---------                 ----
  gpriqueue.zip           10,658


Totals
  ==============  ==============
    1 Files               10,658

ABSTRACT

A priority queue is a queue in which one attaches a specific priority
to enqueued items, seeking to always remove the enqueued item having
the highest priority.  It is possible to insert, delete, purge, and
modify the priority of items. The purge operation can target priority
ranges as well as specific enqueued items.  Multiple occurrences of an
item are permitted.  The queue is unbounded, dynamically expanding and
contracting to contain any arbitrary number of items.  Queues can be
merged, assigned, destroyed, and so on.  The various operations are
either O(1), O(log2 n), or O(n); see the detailed package
specification.

This implementation is for sequential use only, but can be readily
modified as per Booch (Software Components With Ada, pages 203-205) if
instances of the priority queue are to be shared by several tasks.

Our representation is as follows: A priority queue is a binomial
forest (see CACM, Vol. 21, No. 4, pages 309-314).  The type
PRIORITY_QUEUE points to the root node of the smallest binomial tree
in the forest.  The SIBLING of this node points to the next larger
tree in the forest.  The sibling of the largest tree in the forest is
null.  At the root level, the SIBLING field points to the leftward
sibling of a given binomial tree in a forest.  At any other level, the
SIBLING field points to the rightward sibling of a given child, in the
traditional manner.

This implementation has been carefully hand-optimized, and should be
VERY fast, with little room for improvement.

**************************************************************************
This is part of the Clemson University Computer Science Department's
Ada Software Repository, and is copyrighted (C) 1989 by Clemson University.
Permission to copy without fee all or part of this software is granted,
provided that the copies are not made or distributed for direct commercial
advantage, and that this copyright notice is not deleted or modified.  To
copy otherwise, or to republish, requires a fee and/or specific permission.
>> All bug reporters receive a free updated copy once the bug's corrected!
E-mail: cpscada@citron.cs.clemson.edu or ...!gatech!hubcap!citron!cpscada.
**************************************************************************


REVISION HISTORY

   DATE       VERSION         AUTHOR                NOTES 
==========    =======   ====================     ===============
1989 07 01     1.0.0    William Thomas Wolfe     Released to ASR


RELEASE NOTICE

See Abstract.


DISCLAIMER

	This software and its documentation are provided "AS IS" and
without any expressed or implied warranties whatsoever.  No warranties
as to performance, merchantability, or fitness for a particular
purpose exist.
	The user is advised to test the software thoroughly before
relying on it.  The user must assume the entire risk and liability of
using this software.  In no event shall any person or organization of
people be held responsible for any direct, indirect, consequential or
inconsequential damages or lost profits.