]>
Commit | Line | Data |
---|---|---|
b5ace3b7 AC |
1 | ------------------------------------------------------------------------------ |
2 | -- -- | |
3 | -- GNAT LIBRARY COMPONENTS -- | |
4 | -- -- | |
15f6d6e7 | 5 | -- ADA.CONTAINERS.RESTRICTED_DOUBLY_LINKED_LISTS -- |
b5ace3b7 AC |
6 | -- -- |
7 | -- S p e c -- | |
8 | -- -- | |
4b490c1e | 9 | -- Copyright (C) 2004-2020, Free Software Foundation, Inc. -- |
b5ace3b7 AC |
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- -- | |
748086b7 | 13 | -- ware Foundation; either version 3, or (at your option) any later ver- -- |
b5ace3b7 AC |
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 -- | |
748086b7 JJ |
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/>. -- | |
b5ace3b7 AC |
26 | -- -- |
27 | -- This unit was originally developed by Matthew J Heaney. -- | |
28 | ------------------------------------------------------------------------------ | |
29 | ||
1ed69f61 AC |
30 | -- The doubly-linked list container provides constant-time insertion and |
31 | -- deletion at all positions, and allows iteration in both the forward and | |
32 | -- reverse directions. This list form allocates storage for all nodes | |
33 | -- statically (there is no dynamic allocation), and a discriminant is used to | |
34 | -- specify the capacity. This container is also "restricted", meaning that | |
35 | -- even though it does raise exceptions (as described below), it does not use | |
36 | -- internal exception handlers. No state changes are made that would need to | |
37 | -- be reverted (in the event of an exception), and so as a consequence, this | |
38 | -- container cannot detect tampering (of cursors or elements). | |
15f6d6e7 | 39 | |
b5ace3b7 AC |
40 | generic |
41 | type Element_Type is private; | |
42 | ||
43 | with function "=" (Left, Right : Element_Type) | |
44 | return Boolean is <>; | |
45 | ||
46 | package Ada.Containers.Restricted_Doubly_Linked_Lists is | |
47 | pragma Pure; | |
48 | ||
49 | type List (Capacity : Count_Type) is tagged limited private; | |
50 | pragma Preelaborable_Initialization (List); | |
51 | ||
52 | type Cursor is private; | |
53 | pragma Preelaborable_Initialization (Cursor); | |
54 | ||
55 | Empty_List : constant List; | |
1ed69f61 AC |
56 | -- The default value for list objects declared without an explicit |
57 | -- initialization expression. | |
b5ace3b7 AC |
58 | |
59 | No_Element : constant Cursor; | |
1ed69f61 AC |
60 | -- The default value for cursor objects declared without an explicit |
61 | -- initialization expression. | |
b5ace3b7 AC |
62 | |
63 | function "=" (Left, Right : List) return Boolean; | |
1ed69f61 AC |
64 | -- If Left denotes the same list object as Right, then equality returns |
65 | -- True. If the length of Left is different from the length of Right, then | |
66 | -- it returns False. Otherwise, list equality iterates over Left and Right, | |
67 | -- comparing the element of Left to the corresponding element of Right | |
68 | -- using the generic actual equality operator for elements. If the elements | |
69 | -- compare False, then the iteration terminates and list equality returns | |
70 | -- False. Otherwise, if all elements return True, then list equality | |
71 | -- returns True. | |
b5ace3b7 AC |
72 | |
73 | procedure Assign (Target : in out List; Source : List); | |
1ed69f61 AC |
74 | -- If Target denotes the same list object as Source, the operation does |
75 | -- nothing. If Target.Capacity is less than Source.Length, then it raises | |
76 | -- Constraint_Error. Otherwise, it clears Target, and then inserts each | |
77 | -- element of Source into Target. | |
b5ace3b7 AC |
78 | |
79 | function Length (Container : List) return Count_Type; | |
1ed69f61 | 80 | -- Returns the total number of (active) elements in Container |
b5ace3b7 AC |
81 | |
82 | function Is_Empty (Container : List) return Boolean; | |
1ed69f61 | 83 | -- Returns True if Container.Length is 0 |
b5ace3b7 AC |
84 | |
85 | procedure Clear (Container : in out List); | |
1ed69f61 AC |
86 | -- Deletes all elements from Container. Note that this is a bounded |
87 | -- container and so the element is not "deallocated" in the same sense that | |
88 | -- an unbounded form would deallocate the element. Rather, the node is | |
89 | -- relinked off of the active part of the list and onto the inactive part | |
90 | -- of the list (the storage from which new elements are "allocated"). | |
b5ace3b7 AC |
91 | |
92 | function Element (Position : Cursor) return Element_Type; | |
1ed69f61 AC |
93 | -- If Position equals No_Element, then Constraint_Error is raised. |
94 | -- Otherwise, function Element returns the element designed by Position. | |
b5ace3b7 AC |
95 | |
96 | procedure Replace_Element | |
97 | (Container : in out List; | |
98 | Position : Cursor; | |
99 | New_Item : Element_Type); | |
1ed69f61 AC |
100 | -- If Position equals No_Element, then Constraint_Error is raised. If |
101 | -- Position is associated with a list object different from Container, | |
102 | -- Program_Error is raised. Otherwise, the element designated by Position | |
103 | -- is assigned the value New_Item. | |
b5ace3b7 AC |
104 | |
105 | procedure Query_Element | |
106 | (Position : Cursor; | |
107 | Process : not null access procedure (Element : Element_Type)); | |
1ed69f61 AC |
108 | -- If Position equals No_Element, then Constraint_Error is raised. |
109 | -- Otherwise, it calls Process with (a constant view of) the element | |
110 | -- designated by Position as the parameter. | |
b5ace3b7 AC |
111 | |
112 | procedure Update_Element | |
113 | (Container : in out List; | |
114 | Position : Cursor; | |
115 | Process : not null access procedure (Element : in out Element_Type)); | |
1ed69f61 AC |
116 | -- If Position equals No_Element, then Constraint_Error is raised. |
117 | -- Otherwise, it calls Process with (a variable view of) the element | |
118 | -- designated by Position as the parameter. | |
b5ace3b7 AC |
119 | |
120 | procedure Insert | |
121 | (Container : in out List; | |
122 | Before : Cursor; | |
123 | New_Item : Element_Type; | |
124 | Count : Count_Type := 1); | |
1ed69f61 AC |
125 | -- Inserts Count new elements, all with the value New_Item, into Container, |
126 | -- immediately prior to the position specified by Before. If Before has the | |
127 | -- value No_Element, this is interpreted to mean that the elements are | |
128 | -- appended to the list. If Before is associated with a list object | |
129 | -- different from Container, then Program_Error is raised. If there are | |
130 | -- fewer than Count nodes available, then Constraint_Error is raised. | |
b5ace3b7 AC |
131 | |
132 | procedure Insert | |
133 | (Container : in out List; | |
134 | Before : Cursor; | |
135 | New_Item : Element_Type; | |
136 | Position : out Cursor; | |
137 | Count : Count_Type := 1); | |
1ed69f61 AC |
138 | -- Inserts elements into Container as described above, but with the |
139 | -- difference that cursor Position is returned, which designates the first | |
140 | -- of the new elements inserted. If Count is 0, Position returns the value | |
141 | -- Before. | |
b5ace3b7 AC |
142 | |
143 | procedure Insert | |
144 | (Container : in out List; | |
145 | Before : Cursor; | |
146 | Position : out Cursor; | |
147 | Count : Count_Type := 1); | |
1ed69f61 AC |
148 | -- Inserts elements in Container as described above, but with the |
149 | -- difference that the new elements are initialized to the default value | |
150 | -- for objects of type Element_Type. | |
b5ace3b7 AC |
151 | |
152 | procedure Prepend | |
153 | (Container : in out List; | |
154 | New_Item : Element_Type; | |
155 | Count : Count_Type := 1); | |
1ed69f61 AC |
156 | -- Inserts Count elements, all having the value New_Item, prior to the |
157 | -- first element of Container. | |
b5ace3b7 AC |
158 | |
159 | procedure Append | |
160 | (Container : in out List; | |
161 | New_Item : Element_Type; | |
162 | Count : Count_Type := 1); | |
1ed69f61 AC |
163 | -- Inserts Count elements, all having the value New_Item, following the |
164 | -- last element of Container. | |
b5ace3b7 AC |
165 | |
166 | procedure Delete | |
167 | (Container : in out List; | |
168 | Position : in out Cursor; | |
169 | Count : Count_Type := 1); | |
1ed69f61 AC |
170 | -- If Position equals No_Element, Constraint_Error is raised. If Position |
171 | -- is associated with a list object different from Container, then | |
172 | -- Program_Error is raised. Otherwise, the Count nodes starting from | |
173 | -- Position are removed from Container ("removed" meaning that the nodes | |
174 | -- are unlinked from the active nodes of the list and relinked to inactive | |
175 | -- storage). On return, Position is set to No_Element. | |
b5ace3b7 AC |
176 | |
177 | procedure Delete_First | |
178 | (Container : in out List; | |
179 | Count : Count_Type := 1); | |
1ed69f61 | 180 | -- Removes the first Count nodes from Container |
b5ace3b7 AC |
181 | |
182 | procedure Delete_Last | |
183 | (Container : in out List; | |
184 | Count : Count_Type := 1); | |
1ed69f61 | 185 | -- Removes the last Count nodes from Container |
b5ace3b7 AC |
186 | |
187 | procedure Reverse_Elements (Container : in out List); | |
1ed69f61 | 188 | -- Relinks the nodes in reverse order |
b5ace3b7 AC |
189 | |
190 | procedure Swap | |
191 | (Container : in out List; | |
192 | I, J : Cursor); | |
1ed69f61 AC |
193 | -- If I or J equals No_Element, then Constraint_Error is raised. If I or J |
194 | -- is associated with a list object different from Container, then | |
195 | -- Program_Error is raised. Otherwise, Swap exchanges (copies) the values | |
196 | -- of the elements (on the nodes) designated by I and J. | |
b5ace3b7 AC |
197 | |
198 | procedure Swap_Links | |
199 | (Container : in out List; | |
200 | I, J : Cursor); | |
1ed69f61 AC |
201 | -- If I or J equals No_Element, then Constraint_Error is raised. If I or J |
202 | -- is associated with a list object different from Container, then | |
203 | -- Program_Error is raised. Otherwise, Swap exchanges (relinks) the nodes | |
204 | -- designated by I and J. | |
b5ace3b7 AC |
205 | |
206 | procedure Splice | |
207 | (Container : in out List; | |
208 | Before : Cursor; | |
209 | Position : in out Cursor); | |
1ed69f61 | 210 | -- If Before is associated with a list object different from Container, |
03a72cd3 | 211 | -- then Program_Error is raised. If Position equals No_Element, then |
1ed69f61 AC |
212 | -- Constraint_Error is raised; if it associated with a list object |
213 | -- different from Container, then Program_Error is raised. Otherwise, the | |
214 | -- node designated by Position is relinked immediately prior to Before. If | |
215 | -- Before equals No_Element, this is interpreted to mean to move the node | |
216 | -- designed by Position to the last end of the list. | |
b5ace3b7 AC |
217 | |
218 | function First (Container : List) return Cursor; | |
1ed69f61 AC |
219 | -- If Container is empty, the function returns No_Element. Otherwise, it |
220 | -- returns a cursor designating the first element. | |
b5ace3b7 AC |
221 | |
222 | function First_Element (Container : List) return Element_Type; | |
1ed69f61 | 223 | -- Equivalent to Element (First (Container)) |
b5ace3b7 AC |
224 | |
225 | function Last (Container : List) return Cursor; | |
1ed69f61 AC |
226 | -- If Container is empty, the function returns No_Element. Otherwise, it |
227 | -- returns a cursor designating the last element. | |
b5ace3b7 AC |
228 | |
229 | function Last_Element (Container : List) return Element_Type; | |
1ed69f61 | 230 | -- Equivalent to Element (Last (Container)) |
b5ace3b7 AC |
231 | |
232 | function Next (Position : Cursor) return Cursor; | |
1ed69f61 AC |
233 | -- If Position equals No_Element or Last (Container), the function returns |
234 | -- No_Element. Otherwise, it returns a cursor designating the node that | |
235 | -- immediately follows the node designated by Position. | |
b5ace3b7 AC |
236 | |
237 | procedure Next (Position : in out Cursor); | |
1ed69f61 | 238 | -- Equivalent to Position := Next (Position) |
b5ace3b7 AC |
239 | |
240 | function Previous (Position : Cursor) return Cursor; | |
1ed69f61 AC |
241 | -- If Position equals No_Element or First (Container), the function returns |
242 | -- No_Element. Otherwise, it returns a cursor designating the node that | |
243 | -- immediately precedes the node designated by Position. | |
b5ace3b7 AC |
244 | |
245 | procedure Previous (Position : in out Cursor); | |
1ed69f61 | 246 | -- Equivalent to Position := Previous (Position) |
b5ace3b7 AC |
247 | |
248 | function Find | |
249 | (Container : List; | |
250 | Item : Element_Type; | |
251 | Position : Cursor := No_Element) return Cursor; | |
1ed69f61 AC |
252 | -- Searches for the node whose element is equal to Item, starting from |
253 | -- Position and continuing to the last end of the list. If Position equals | |
f3d0f304 | 254 | -- No_Element, the search starts from the first node. If Position is |
1ed69f61 AC |
255 | -- associated with a list object different from Container, then |
256 | -- Program_Error is raised. If no node is found having an element equal to | |
257 | -- Item, then Find returns No_Element. | |
b5ace3b7 AC |
258 | |
259 | function Reverse_Find | |
260 | (Container : List; | |
261 | Item : Element_Type; | |
262 | Position : Cursor := No_Element) return Cursor; | |
1ed69f61 AC |
263 | -- Searches in reverse for the node whose element is equal to Item, |
264 | -- starting from Position and continuing to the first end of the list. If | |
f3d0f304 | 265 | -- Position equals No_Element, the search starts from the last node. If |
1ed69f61 AC |
266 | -- Position is associated with a list object different from Container, then |
267 | -- Program_Error is raised. If no node is found having an element equal to | |
268 | -- Item, then Reverse_Find returns No_Element. | |
b5ace3b7 AC |
269 | |
270 | function Contains | |
271 | (Container : List; | |
272 | Item : Element_Type) return Boolean; | |
1ed69f61 | 273 | -- Equivalent to Container.Find (Item) /= No_Element |
b5ace3b7 AC |
274 | |
275 | function Has_Element (Position : Cursor) return Boolean; | |
1ed69f61 | 276 | -- Equivalent to Position /= No_Element |
b5ace3b7 AC |
277 | |
278 | procedure Iterate | |
279 | (Container : List; | |
280 | Process : not null access procedure (Position : Cursor)); | |
1ed69f61 AC |
281 | -- Calls Process with a cursor designating each element of Container, in |
282 | -- order from Container.First to Container.Last. | |
b5ace3b7 AC |
283 | |
284 | procedure Reverse_Iterate | |
285 | (Container : List; | |
286 | Process : not null access procedure (Position : Cursor)); | |
1ed69f61 AC |
287 | -- Calls Process with a cursor designating each element of Container, in |
288 | -- order from Container.Last to Container.First. | |
b5ace3b7 AC |
289 | |
290 | generic | |
291 | with function "<" (Left, Right : Element_Type) return Boolean is <>; | |
292 | package Generic_Sorting is | |
293 | ||
294 | function Is_Sorted (Container : List) return Boolean; | |
1ed69f61 AC |
295 | -- Returns False if there exists an element which is less than its |
296 | -- predecessor. | |
b5ace3b7 AC |
297 | |
298 | procedure Sort (Container : in out List); | |
1ed69f61 AC |
299 | -- Sorts the elements of Container (by relinking nodes), according to |
300 | -- the order specified by the generic formal less-than operator, such | |
301 | -- that smaller elements are first in the list. The sort is stable, | |
302 | -- meaning that the relative order of elements is preserved. | |
b5ace3b7 AC |
303 | |
304 | end Generic_Sorting; | |
305 | ||
306 | private | |
307 | ||
308 | type Node_Type is limited record | |
309 | Prev : Count_Type'Base; | |
310 | Next : Count_Type; | |
311 | Element : Element_Type; | |
312 | end record; | |
313 | ||
314 | type Node_Array is array (Count_Type range <>) of Node_Type; | |
315 | ||
316 | type List (Capacity : Count_Type) is tagged limited record | |
317 | Nodes : Node_Array (1 .. Capacity) := (others => <>); | |
318 | Free : Count_Type'Base := -1; | |
319 | First : Count_Type := 0; | |
320 | Last : Count_Type := 0; | |
321 | Length : Count_Type := 0; | |
322 | end record; | |
323 | ||
b5ace3b7 AC |
324 | type List_Access is access all List; |
325 | for List_Access'Storage_Size use 0; | |
326 | ||
327 | type Cursor is | |
328 | record | |
329 | Container : List_Access; | |
330 | Node : Count_Type := 0; | |
331 | end record; | |
332 | ||
a18e3d62 AC |
333 | Empty_List : constant List := (0, others => <>); |
334 | ||
b5ace3b7 AC |
335 | No_Element : constant Cursor := (null, 0); |
336 | ||
337 | end Ada.Containers.Restricted_Doubly_Linked_Lists; |