 |
ASE2 CARD CATALOG ENTRY |
|
ASE2 CARD CATALOG ENTRY |
Instructions:
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
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. **************************************************************************
DATE VERSION AUTHOR NOTES ========== ======= ==================== =============== 1989 07 01 1.0.0 William Thomas Wolfe Released to ASR
See Abstract.
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.
Powered by the Generic Web-Based Reuse Library (GWRL)