Annotated Ada Reference Manual (Ada 202y Draft 1)Legal Information
Contents   Index   References   Search   Previous   Next 

A.18.30 The Generic Package Containers.Unbounded_Priority_Queues

Static Semantics

1/3
{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.
2/5
{AI12-0112-1} 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
   with Preelaborate,
        Nonblocking, Global => in out synchronized is
2.a/5
Discussion: {AI12-0112-1} For discussion on the reasons and meaning of the specifications of the Global and Nonblocking aspects of this generic package, see the notes on the specification of the Containers.Vectors package (see A.18.2).
3/3
   package Implementation is
      ... -- not specified by the language
   end Implementation;
4/3
   protected type Queue
        (Ceiling : System.Any_Priority := Default_Ceiling)
           with Priority => Ceiling is
        new Queue_Interfaces.Queue with
5/3
      overriding
      entry Enqueue (New_Item : in Queue_Interfaces.Element_Type);
      overriding
      entry Dequeue (Element : out Queue_Interfaces.Element_Type);
6/3
{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);
7/5
{AI12-0112-1}       overriding
      function Current_Use return Count_Type
         with Nonblocking, Global => null, Use_Formal => null;
      overriding
      function Peak_Use return Count_Type
         with Nonblocking, Global => null, Use_Formal => null;
8/3
   private
      ... -- not specified by the language
   end Queue;
9/3
private
10/3
   ... -- not specified by the language
11/3
end Ada.Containers.Unbounded_Priority_Queues;
12/3
{AI05-0159-1} The type Queue is used to represent task-safe priority queues.
13/3
{AI05-0159-1} The capacity for instances of type Queue is unbounded.
14/3
{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.
15/3
{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.
16/3
{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.
16.a/3
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. 
17/3
{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.
17.a/3
Ramification: {AI05-0251-1} Unlike Dequeue, Dequeue_Only_High_Priority is not blocking; it always returns immediately. 
17.b/3
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

17.c/3
{AI05-0159-1} {AI05-0251-1} The generic package Containers.Unbounded_Priority_Queues is new. 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe