]>
Commit | Line | Data |
---|---|---|
579fda56 AC |
1 | ------------------------------------------------------------------------------ |
2 | -- -- | |
3 | -- GNAT LIBRARY COMPONENTS -- | |
4 | -- -- | |
516f608f | 5 | -- ADA.CONTAINERS.UNBOUNDED_PRIORITY_QUEUES -- |
579fda56 AC |
6 | -- -- |
7 | -- S p e c -- | |
8 | -- -- | |
f24ea912 | 9 | -- Copyright (C) 2011-2016, Free Software Foundation, Inc. -- |
579fda56 AC |
10 | -- -- |
11 | -- This specification is derived from the Ada Reference Manual for use with -- | |
12 | -- GNAT. The copyright notice above, and the license provisions that follow -- | |
13 | -- apply solely to the contents of the part following the private keyword. -- | |
14 | -- -- | |
15 | -- GNAT is free software; you can redistribute it and/or modify it under -- | |
16 | -- terms of the GNU General Public License as published by the Free Soft- -- | |
17 | -- ware Foundation; either version 3, or (at your option) any later ver- -- | |
18 | -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- | |
19 | -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- | |
20 | -- or FITNESS FOR A PARTICULAR PURPOSE. -- | |
21 | -- -- | |
22 | -- As a special exception under Section 7 of GPL version 3, you are granted -- | |
23 | -- additional permissions described in the GCC Runtime Library Exception, -- | |
24 | -- version 3.1, as published by the Free Software Foundation. -- | |
25 | -- -- | |
26 | -- You should have received a copy of the GNU General Public License and -- | |
27 | -- a copy of the GCC Runtime Library Exception along with this program; -- | |
28 | -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- | |
29 | -- <http://www.gnu.org/licenses/>. -- | |
30 | -- -- | |
31 | -- This unit was originally developed by Matthew J Heaney. -- | |
32 | ------------------------------------------------------------------------------ | |
33 | ||
34 | with System; | |
f24ea912 | 35 | with Ada.Containers.Ordered_Sets; |
579fda56 | 36 | with Ada.Containers.Synchronized_Queue_Interfaces; |
579fda56 AC |
37 | |
38 | generic | |
39 | with package Queue_Interfaces is | |
40 | new Ada.Containers.Synchronized_Queue_Interfaces (<>); | |
41 | ||
42 | type Queue_Priority is private; | |
43 | ||
44 | with function Get_Priority | |
45 | (Element : Queue_Interfaces.Element_Type) return Queue_Priority is <>; | |
46 | ||
47 | with function Before | |
48 | (Left, Right : Queue_Priority) return Boolean is <>; | |
49 | ||
50 | Default_Ceiling : System.Any_Priority := System.Priority'Last; | |
51 | ||
52 | package Ada.Containers.Unbounded_Priority_Queues is | |
6031f544 | 53 | pragma Annotate (CodePeer, Skip_Analysis); |
579fda56 AC |
54 | pragma Preelaborate; |
55 | ||
ea10ca9c | 56 | package Implementation is |
df177175 | 57 | |
ea10ca9c | 58 | -- All identifiers in this unit are implementation defined |
df177175 | 59 | |
ea10ca9c | 60 | pragma Implementation_Defined; |
579fda56 | 61 | |
f24ea912 AC |
62 | -- We use an ordered set to hold the queue elements. This gives O(lg N) |
63 | -- performance in the worst case for Enqueue and Dequeue. | |
64 | -- Sequence_Number is used to distinguish equivalent items. Each Enqueue | |
65 | -- uses a higher Sequence_Number, so that a new item is placed after | |
66 | -- already-enqueued equivalent items. | |
67 | -- | |
68 | -- At any time, the first set element is the one to be dequeued next (if | |
69 | -- the queue is not empty). | |
579fda56 | 70 | |
f24ea912 AC |
71 | type Set_Elem is record |
72 | Sequence_Number : Count_Type; | |
73 | Item : Queue_Interfaces.Element_Type; | |
74 | end record; | |
579fda56 | 75 | |
f24ea912 AC |
76 | function "=" (X, Y : Queue_Interfaces.Element_Type) return Boolean is |
77 | (not Before (Get_Priority (X), Get_Priority (Y)) | |
78 | and then not Before (Get_Priority (Y), Get_Priority (X))); | |
79 | -- Elements are equal if neither is Before the other | |
579fda56 | 80 | |
f24ea912 AC |
81 | function "=" (X, Y : Set_Elem) return Boolean is |
82 | (X.Sequence_Number = Y.Sequence_Number and then X.Item = Y.Item); | |
83 | -- Set_Elems are equal if the elements are equal, and the | |
84 | -- Sequence_Numbers are equal. This is passed to Ordered_Sets. | |
579fda56 | 85 | |
f24ea912 AC |
86 | function "<" (X, Y : Set_Elem) return Boolean is |
87 | (if X.Item = Y.Item | |
88 | then X.Sequence_Number < Y.Sequence_Number | |
89 | else Before (Get_Priority (X.Item), Get_Priority (Y.Item))); | |
90 | -- If the items are equal, Sequence_Number breaks the tie. Otherwise, | |
91 | -- use Before. This is passed to Ordered_Sets. | |
579fda56 | 92 | |
f24ea912 AC |
93 | pragma Suppress (Container_Checks); |
94 | package Sets is new Ada.Containers.Ordered_Sets (Set_Elem); | |
579fda56 | 95 | |
579fda56 AC |
96 | end Implementation; |
97 | ||
f24ea912 AC |
98 | use Implementation, Implementation.Sets; |
99 | ||
579fda56 | 100 | protected type Queue (Ceiling : System.Any_Priority := Default_Ceiling) |
b2c28399 AC |
101 | with |
102 | Priority => Ceiling | |
103 | is new Queue_Interfaces.Queue with | |
579fda56 | 104 | |
b2c28399 | 105 | overriding entry Enqueue (New_Item : Queue_Interfaces.Element_Type); |
579fda56 | 106 | |
b2c28399 | 107 | overriding entry Dequeue (Element : out Queue_Interfaces.Element_Type); |
579fda56 | 108 | |
885c4871 AC |
109 | -- The priority queue operation Dequeue_Only_High_Priority had been a |
110 | -- protected entry in early drafts of AI05-0159, but it was discovered | |
111 | -- that that operation as specified was not in fact implementable. The | |
112 | -- operation was changed from an entry to a protected procedure per the | |
113 | -- ARG meeting in Edinburgh (June 2011), with a different signature and | |
114 | -- semantics. | |
579fda56 | 115 | |
885c4871 AC |
116 | procedure Dequeue_Only_High_Priority |
117 | (At_Least : Queue_Priority; | |
118 | Element : in out Queue_Interfaces.Element_Type; | |
119 | Success : out Boolean); | |
579fda56 | 120 | |
b2c28399 | 121 | overriding function Current_Use return Count_Type; |
885c4871 | 122 | |
b2c28399 | 123 | overriding function Peak_Use return Count_Type; |
579fda56 AC |
124 | |
125 | private | |
f24ea912 AC |
126 | Q_Elems : Set; |
127 | -- Elements of the queue | |
128 | ||
129 | Max_Length : Count_Type := 0; | |
130 | -- The current length of the queue is the Length of Q_Elems. This is the | |
131 | -- maximum value of that, so far. Updated by Enqueue. | |
132 | ||
133 | Next_Sequence_Number : Count_Type := 0; | |
134 | -- Steadily increasing counter | |
579fda56 AC |
135 | end Queue; |
136 | ||
137 | end Ada.Containers.Unbounded_Priority_Queues; |