1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.BOUNDED_PRIORITY_QUEUES --
9 -- Copyright (C) 2011, Free Software Foundation, Inc. --
11 -- GNAT is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
19 -- additional permissions described in the GCC Runtime Library Exception, --
20 -- version 3.1, as published by the Free Software Foundation. --
22 -- You should have received a copy of the GNU General Public License and --
23 -- a copy of the GCC Runtime Library Exception along with this program; --
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
25 -- <http://www.gnu.org/licenses/>. --
27 -- This unit was originally developed by Matthew J Heaney. --
28 ------------------------------------------------------------------------------
30 package body Ada.Containers.Bounded_Priority_Queues is
32 package body Implementation is
39 (List : in out List_Type;
40 Element : out Queue_Interfaces.Element_Type)
43 Element := List.Container.First_Element;
44 List.Container.Delete_First;
48 (List : in out List_Type;
49 At_Least : Queue_Priority;
50 Element : in out Queue_Interfaces.Element_Type;
51 Success : out Boolean)
54 -- This operation dequeues a high priority item if it exists in the
55 -- queue. By "high priority" we mean an item whose priority is equal
56 -- or greater than the value At_Least. The generic formal operation
57 -- Before has the meaning "has higher priority than". To dequeue an
58 -- item (meaning that we return True as our Success value), we need
59 -- as our predicate the equivalent of "has equal or higher priority
60 -- than", but we cannot say that directly, so we require some logical
61 -- gymnastics to make it so.
63 -- If E is the element at the head of the queue, and symbol ">"
64 -- refers to the "is higher priority than" function Before, then we
65 -- derive our predicate as follows:
67 -- original: P(E) >= At_Least
68 -- same as: not (P(E) < At_Least)
69 -- same as: not (At_Least > P(E))
70 -- same as: not Before (At_Least, P(E))
72 -- But that predicate needs to be true in order to successfully
73 -- dequeue an item. If it's false, it means no item is dequeued, and
74 -- we return False as the Success value.
77 or else Before (At_Least,
78 Get_Priority (List.Container.First_Element))
84 List.Dequeue (Element);
93 (List : in out List_Type;
94 New_Item : Queue_Interfaces.Element_Type)
96 P : constant Queue_Priority := Get_Priority (New_Item);
98 C : List_Types.Cursor;
104 C := List.Container.First;
105 while Has_Element (C) loop
107 -- ??? why is following commented out ???
108 -- if Before (P, Get_Priority (List.Constant_Reference (C))) then
110 if Before (P, Get_Priority (Element (C))) then
111 List.Container.Insert (C, New_Item);
118 if not Has_Element (C) then
119 List.Container.Append (New_Item);
122 Count := List.Container.Length;
124 if Count > List.Max_Length then
125 List.Max_Length := Count;
133 function First_Element
134 (List : List_Type) return Queue_Interfaces.Element_Type
138 -- Use Constant_Reference for this. ???
140 return List.Container.First_Element;
147 function Length (List : List_Type) return Count_Type is
149 return List.Container.Length;
156 function Max_Length (List : List_Type) return Count_Type is
158 return List.Max_Length;
163 protected body Queue is
169 function Current_Use return Count_Type is
178 entry Dequeue (Element : out Queue_Interfaces.Element_Type)
182 List.Dequeue (Element);
185 --------------------------------
186 -- Dequeue_Only_High_Priority --
187 --------------------------------
189 procedure Dequeue_Only_High_Priority
190 (At_Least : Queue_Priority;
191 Element : in out Queue_Interfaces.Element_Type;
192 Success : out Boolean)
195 List.Dequeue (At_Least, Element, Success);
196 end Dequeue_Only_High_Priority;
202 entry Enqueue (New_Item : Queue_Interfaces.Element_Type)
203 when List.Length < Capacity
206 List.Enqueue (New_Item);
213 function Peak_Use return Count_Type is
215 return List.Max_Length;
220 end Ada.Containers.Bounded_Priority_Queues;