A.18.30 The Generic Package Containers.Unbounded_Priority_Queues
Static Semantics
{
AI05-0159-1}
The language-defined generic package Containers.Unbounded_Priority_Queues
provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue.
with System;
with Ada.Containers.Synchronized_Queue_Interfaces;
generic
with package Queue_Interfaces
is new Ada.Containers.Synchronized_Queue_Interfaces (<>);
type Queue_Priority
is private;
with function Get_Priority
(Element : Queue_Interfaces.Element_Type)
return Queue_Priority
is <>;
with function Before
(Left, Right : Queue_Priority)
return Boolean
is <>;
Default_Ceiling : System.Any_Priority := System.Priority'Last;
package Ada.Containers.Unbounded_Priority_Queues
is
pragma Preelaborate(Unbounded_Priority_Queues);
package Implementation is
... -- not specified by the language
end Implementation;
protected type Queue
(Ceiling : System.Any_Priority := Default_Ceiling)
with Priority => Ceiling
is
new Queue_Interfaces.Queue
with
overriding
entry Enqueue (New_Item :
in Queue_Interfaces.Element_Type);
overriding
entry Dequeue (Element :
out Queue_Interfaces.Element_Type);
{
AI05-0159-1}
{
AI05-0251-1}
not overriding
procedure Dequeue_Only_High_Priority
(At_Least :
in Queue_Priority;
Element :
in out Queue_Interfaces.Element_Type;
Success :
out Boolean);
overriding
function Current_Use
return Count_Type;
overriding
function Peak_Use
return Count_Type;
private
... -- not specified by the language
end Queue;
private
... -- not specified by the language
end Ada.Containers.Unbounded_Priority_Queues;
{
AI05-0159-1}
The type Queue is used to represent task-safe priority queues.
{
AI05-0159-1}
The capacity for instances of type Queue is unbounded.
{
AI05-0159-1}
Two elements
E1 and
E2 are equivalent if Before(Get_Priority(
E1),
Get_Priority(
E2)) and Before(Get_Priority(
E2), Get_Priority(
E1))
both return False.
{
AI05-0159-1}
{
AI05-0248-1}
The actual functions for Get_Priority and Before are expected to return
the same value each time they are called with the same actuals, and should
not modify their actuals. Before should define a strict weak ordering
relationship (see
A.18). If the actual functions
behave in some other manner, the behavior of Unbounded_Priority_Queues
is unspecified.
{
AI05-0159-1}
Enqueue inserts an item according to the order specified by the Before
function on the result of Get_Priority on the elements; Before should
return True if Left is to be inserted before Right. If the queue already
contains elements equivalent to New_Item, then it is inserted after the
existing equivalent elements.
Ramification: Enqueue never blocks; if
more storage is needed for a new element, it is allocated dynamically.
We don't need to explicitly specify that Queue needs finalization, because
it is visibly protected.
{
AI05-0159-1}
{
AI05-0251-1}
{
AI05-0262-1}
For a call on Dequeue_Only_High_Priority, if the head of the nonempty
queue is
E, and the function Before(At_Least, Get_Priority(
E))
returns False, then
E is assigned to Element and then removed
from the queue, and Success is set to True; otherwise, Success is set
to False and Element is unchanged.
Ramification: {
AI05-0251-1}
Unlike Dequeue, Dequeue_Only_High_Priority is not blocking; it always
returns immediately.
Reason: {
AI05-0251-1}
The use of Before is "backwards" so that it acts like ">="
(it is defined similarly to ">"); thus we dequeue only when
it is False.
Extensions to Ada 2005
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
