File : a-crdlli.ads
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT LIBRARY COMPONENTS --
4 -- --
5 -- ADA.CONTAINERS.RESTRICTED_DOUBLY_LINKED_LISTS --
6 -- --
7 -- S p e c --
8 -- --
9 -- Copyright (C) 2004-2015, 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 -- --
19 -- --
20 -- --
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
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).
39
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;
56 -- The default value for list objects declared without an explicit
57 -- initialization expression.
58
59 No_Element : constant Cursor;
60 -- The default value for cursor objects declared without an explicit
61 -- initialization expression.
62
63 function "=" (Left, Right : List) return Boolean;
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.
72
73 procedure Assign (Target : in out List; Source : List);
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.
78
79 function Length (Container : List) return Count_Type;
80 -- Returns the total number of (active) elements in Container
81
82 function Is_Empty (Container : List) return Boolean;
83 -- Returns True if Container.Length is 0
84
85 procedure Clear (Container : in out List);
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").
91
92 function Element (Position : Cursor) return Element_Type;
93 -- If Position equals No_Element, then Constraint_Error is raised.
94 -- Otherwise, function Element returns the element designed by Position.
95
96 procedure Replace_Element
97 (Container : in out List;
98 Position : Cursor;
99 New_Item : Element_Type);
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.
104
105 procedure Query_Element
106 (Position : Cursor;
107 Process : not null access procedure (Element : Element_Type));
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.
111
112 procedure Update_Element
113 (Container : in out List;
114 Position : Cursor;
115 Process : not null access procedure (Element : in out Element_Type));
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.
119
120 procedure Insert
121 (Container : in out List;
122 Before : Cursor;
123 New_Item : Element_Type;
124 Count : Count_Type := 1);
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.
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);
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.
142
143 procedure Insert
144 (Container : in out List;
145 Before : Cursor;
146 Position : out Cursor;
147 Count : Count_Type := 1);
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.
151
152 procedure Prepend
153 (Container : in out List;
154 New_Item : Element_Type;
155 Count : Count_Type := 1);
156 -- Inserts Count elements, all having the value New_Item, prior to the
157 -- first element of Container.
158
159 procedure Append
160 (Container : in out List;
161 New_Item : Element_Type;
162 Count : Count_Type := 1);
163 -- Inserts Count elements, all having the value New_Item, following the
164 -- last element of Container.
165
166 procedure Delete
167 (Container : in out List;
168 Position : in out Cursor;
169 Count : Count_Type := 1);
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.
176
177 procedure Delete_First
178 (Container : in out List;
179 Count : Count_Type := 1);
180 -- Removes the first Count nodes from Container
181
182 procedure Delete_Last
183 (Container : in out List;
184 Count : Count_Type := 1);
185 -- Removes the last Count nodes from Container
186
187 procedure Reverse_Elements (Container : in out List);
188 -- Relinks the nodes in reverse order
189
190 procedure Swap
191 (Container : in out List;
192 I, J : Cursor);
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.
197
198 procedure Swap_Links
199 (Container : in out List;
200 I, J : Cursor);
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.
205
206 procedure Splice
207 (Container : in out List;
208 Before : Cursor;
209 Position : in out Cursor);
210 -- If Before is associated with a list object different from Container,
211 -- then Program_Error is raised. If Position equals No_Element, then
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.
217
218 function First (Container : List) return Cursor;
219 -- If Container is empty, the function returns No_Element. Otherwise, it
220 -- returns a cursor designating the first element.
221
222 function First_Element (Container : List) return Element_Type;
223 -- Equivalent to Element (First (Container))
224
225 function Last (Container : List) return Cursor;
226 -- If Container is empty, the function returns No_Element. Otherwise, it
227 -- returns a cursor designating the last element.
228
229 function Last_Element (Container : List) return Element_Type;
230 -- Equivalent to Element (Last (Container))
231
232 function Next (Position : Cursor) return Cursor;
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.
236
237 procedure Next (Position : in out Cursor);
238 -- Equivalent to Position := Next (Position)
239
240 function Previous (Position : Cursor) return Cursor;
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.
244
245 procedure Previous (Position : in out Cursor);
246 -- Equivalent to Position := Previous (Position)
247
248 function Find
249 (Container : List;
250 Item : Element_Type;
251 Position : Cursor := No_Element) return Cursor;
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
254 -- No_Element, the search starts from the first node. If Position is
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.
258
259 function Reverse_Find
260 (Container : List;
261 Item : Element_Type;
262 Position : Cursor := No_Element) return Cursor;
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
265 -- Position equals No_Element, the search starts from the last node. If
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.
269
270 function Contains
271 (Container : List;
272 Item : Element_Type) return Boolean;
273 -- Equivalent to Container.Find (Item) /= No_Element
274
275 function Has_Element (Position : Cursor) return Boolean;
276 -- Equivalent to Position /= No_Element
277
278 procedure Iterate
279 (Container : List;
280 Process : not null access procedure (Position : Cursor));
281 -- Calls Process with a cursor designating each element of Container, in
282 -- order from Container.First to Container.Last.
283
284 procedure Reverse_Iterate
285 (Container : List;
286 Process : not null access procedure (Position : Cursor));
287 -- Calls Process with a cursor designating each element of Container, in
288 -- order from Container.Last to Container.First.
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;
295 -- Returns False if there exists an element which is less than its
296 -- predecessor.
297
298 procedure Sort (Container : in out List);
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.
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
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
333 Empty_List : constant List := (0, others => <>);
334
335 No_Element : constant Cursor := (null, 0);
336
337 end Ada.Containers.Restricted_Doubly_Linked_Lists;