1------------------------------------------------------------------------------ 2-- -- 3-- GNAT LIBRARY COMPONENTS -- 4-- -- 5-- ADA.CONTAINERS.BOUNDED_PRIORITY_QUEUES -- 6-- -- 7-- B o d y -- 8-- -- 9-- Copyright (C) 2011-2018, Free Software Foundation, Inc. -- 10-- -- 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. -- 17-- -- 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. -- 21-- -- 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/>. -- 26-- -- 27-- This unit was originally developed by Matthew J Heaney. -- 28------------------------------------------------------------------------------ 29 30package body Ada.Containers.Bounded_Priority_Queues is 31 32 package body Implementation is 33 34 ------------- 35 -- Dequeue -- 36 ------------- 37 38 procedure Dequeue 39 (List : in out List_Type; 40 Element : out Queue_Interfaces.Element_Type) 41 is 42 begin 43 Element := List.Container.First_Element; 44 List.Container.Delete_First; 45 end Dequeue; 46 47 procedure Dequeue 48 (List : in out List_Type; 49 At_Least : Queue_Priority; 50 Element : in out Queue_Interfaces.Element_Type; 51 Success : out Boolean) 52 is 53 begin 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. 62 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: 66 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)) 71 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. 75 76 if List.Length = 0 77 or else Before (At_Least, 78 Get_Priority (List.Container.First_Element)) 79 then 80 Success := False; 81 return; 82 end if; 83 84 List.Dequeue (Element); 85 Success := True; 86 end Dequeue; 87 88 ------------- 89 -- Enqueue -- 90 ------------- 91 92 procedure Enqueue 93 (List : in out List_Type; 94 New_Item : Queue_Interfaces.Element_Type) 95 is 96 P : constant Queue_Priority := Get_Priority (New_Item); 97 98 C : List_Types.Cursor; 99 use List_Types; 100 101 Count : Count_Type; 102 103 begin 104 C := List.Container.First; 105 while Has_Element (C) loop 106 107 -- ??? why is following commented out ??? 108 -- if Before (P, Get_Priority (List.Constant_Reference (C))) then 109 110 if Before (P, Get_Priority (Element (C))) then 111 List.Container.Insert (C, New_Item); 112 exit; 113 end if; 114 115 Next (C); 116 end loop; 117 118 if not Has_Element (C) then 119 List.Container.Append (New_Item); 120 end if; 121 122 Count := List.Container.Length; 123 124 if Count > List.Max_Length then 125 List.Max_Length := Count; 126 end if; 127 end Enqueue; 128 129 ------------------- 130 -- First_Element -- 131 ------------------- 132 133 function First_Element 134 (List : List_Type) return Queue_Interfaces.Element_Type 135 is 136 begin 137 138 -- Use Constant_Reference for this. ??? 139 140 return List.Container.First_Element; 141 end First_Element; 142 143 ------------ 144 -- Length -- 145 ------------ 146 147 function Length (List : List_Type) return Count_Type is 148 begin 149 return List.Container.Length; 150 end Length; 151 152 ---------------- 153 -- Max_Length -- 154 ---------------- 155 156 function Max_Length (List : List_Type) return Count_Type is 157 begin 158 return List.Max_Length; 159 end Max_Length; 160 161 end Implementation; 162 163 protected body Queue is 164 165 ------------------ 166 -- Current_Use -- 167 ------------------ 168 169 function Current_Use return Count_Type is 170 begin 171 return List.Length; 172 end Current_Use; 173 174 -------------- 175 -- Dequeue -- 176 -------------- 177 178 entry Dequeue (Element : out Queue_Interfaces.Element_Type) 179 when List.Length > 0 180 is 181 begin 182 List.Dequeue (Element); 183 end Dequeue; 184 185 -------------------------------- 186 -- Dequeue_Only_High_Priority -- 187 -------------------------------- 188 189 procedure Dequeue_Only_High_Priority 190 (At_Least : Queue_Priority; 191 Element : in out Queue_Interfaces.Element_Type; 192 Success : out Boolean) 193 is 194 begin 195 List.Dequeue (At_Least, Element, Success); 196 end Dequeue_Only_High_Priority; 197 198 -------------- 199 -- Enqueue -- 200 -------------- 201 202 entry Enqueue (New_Item : Queue_Interfaces.Element_Type) 203 when List.Length < Capacity 204 is 205 begin 206 List.Enqueue (New_Item); 207 end Enqueue; 208 209 --------------- 210 -- Peak_Use -- 211 --------------- 212 213 function Peak_Use return Count_Type is 214 begin 215 return List.Max_Length; 216 end Peak_Use; 217 218 end Queue; 219 220end Ada.Containers.Bounded_Priority_Queues; 221