]>
Commit | Line | Data |
---|---|---|
4c2d6a70 AC |
1 | ------------------------------------------------------------------------------ |
2 | -- -- | |
3 | -- GNAT LIBRARY COMPONENTS -- | |
4 | -- -- | |
15f6d6e7 | 5 | -- ADA.CONTAINERS.INDEFINITE_DOUBLY_LINKED_LISTS -- |
4c2d6a70 AC |
6 | -- -- |
7 | -- S p e c -- | |
8 | -- -- | |
db222ead | 9 | -- Copyright (C) 2004-2015, Free Software Foundation, Inc. -- |
4c2d6a70 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- -- | |
748086b7 | 17 | -- ware Foundation; either version 3, or (at your option) any later ver- -- |
4c2d6a70 AC |
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 -- | |
748086b7 JJ |
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/>. -- | |
4c2d6a70 AC |
30 | -- -- |
31 | -- This unit was originally developed by Matthew J Heaney. -- | |
32 | ------------------------------------------------------------------------------ | |
33 | ||
3a613a36 | 34 | with Ada.Iterator_Interfaces; |
833eaa8a | 35 | |
15f6d6e7 | 36 | private with Ada.Finalization; |
3c24c853 | 37 | private with Ada.Streams; |
4c2d6a70 AC |
38 | |
39 | generic | |
4c2d6a70 AC |
40 | type Element_Type (<>) is private; |
41 | ||
42 | with function "=" (Left, Right : Element_Type) | |
43 | return Boolean is <>; | |
44 | ||
45 | package Ada.Containers.Indefinite_Doubly_Linked_Lists is | |
009186e0 | 46 | pragma Preelaborate; |
f97ccb3a | 47 | pragma Remote_Types; |
4c2d6a70 | 48 | |
833eaa8a | 49 | type List is tagged private with |
3a613a36 AC |
50 | Constant_Indexing => Constant_Reference, |
51 | Variable_Indexing => Reference, | |
52 | Default_Iterator => Iterate, | |
53 | Iterator_Element => Element_Type; | |
54 | ||
3837bc7f | 55 | pragma Preelaborable_Initialization (List); |
4c2d6a70 AC |
56 | |
57 | type Cursor is private; | |
3837bc7f | 58 | pragma Preelaborable_Initialization (Cursor); |
4c2d6a70 AC |
59 | |
60 | Empty_List : constant List; | |
61 | ||
62 | No_Element : constant Cursor; | |
833eaa8a | 63 | |
3a613a36 AC |
64 | function Has_Element (Position : Cursor) return Boolean; |
65 | ||
66 | package List_Iterator_Interfaces is new | |
67 | Ada.Iterator_Interfaces (Cursor, Has_Element); | |
4c2d6a70 AC |
68 | |
69 | function "=" (Left, Right : List) return Boolean; | |
70 | ||
71 | function Length (Container : List) return Count_Type; | |
72 | ||
73 | function Is_Empty (Container : List) return Boolean; | |
74 | ||
75 | procedure Clear (Container : in out List); | |
76 | ||
2368f04e MH |
77 | function Element (Position : Cursor) return Element_Type; |
78 | ||
79 | procedure Replace_Element | |
80 | (Container : in out List; | |
81 | Position : Cursor; | |
82 | New_Item : Element_Type); | |
4c2d6a70 AC |
83 | |
84 | procedure Query_Element | |
85 | (Position : Cursor; | |
86 | Process : not null access procedure (Element : Element_Type)); | |
87 | ||
88 | procedure Update_Element | |
2368f04e MH |
89 | (Container : in out List; |
90 | Position : Cursor; | |
91 | Process : not null access procedure (Element : in out Element_Type)); | |
4c2d6a70 | 92 | |
c9423ca3 AC |
93 | type Constant_Reference_Type |
94 | (Element : not null access constant Element_Type) is private | |
95 | with | |
96 | Implicit_Dereference => Element; | |
97 | ||
c9423ca3 AC |
98 | type Reference_Type |
99 | (Element : not null access Element_Type) is private | |
100 | with | |
101 | Implicit_Dereference => Element; | |
102 | ||
c9423ca3 AC |
103 | function Constant_Reference |
104 | (Container : aliased List; | |
105 | Position : Cursor) return Constant_Reference_Type; | |
794b9b72 | 106 | pragma Inline (Constant_Reference); |
c9423ca3 AC |
107 | |
108 | function Reference | |
109 | (Container : aliased in out List; | |
110 | Position : Cursor) return Reference_Type; | |
794b9b72 | 111 | pragma Inline (Reference); |
c9423ca3 | 112 | |
a31945d7 AC |
113 | procedure Assign (Target : in out List; Source : List); |
114 | ||
115 | function Copy (Source : List) return List; | |
116 | ||
4c2d6a70 AC |
117 | procedure Move |
118 | (Target : in out List; | |
119 | Source : in out List); | |
120 | ||
2368f04e | 121 | procedure Insert |
4c2d6a70 | 122 | (Container : in out List; |
2368f04e | 123 | Before : Cursor; |
4c2d6a70 AC |
124 | New_Item : Element_Type; |
125 | Count : Count_Type := 1); | |
126 | ||
2368f04e | 127 | procedure Insert |
4c2d6a70 | 128 | (Container : in out List; |
2368f04e | 129 | Before : Cursor; |
4c2d6a70 | 130 | New_Item : Element_Type; |
2368f04e | 131 | Position : out Cursor; |
4c2d6a70 AC |
132 | Count : Count_Type := 1); |
133 | ||
2368f04e | 134 | procedure Prepend |
4c2d6a70 | 135 | (Container : in out List; |
4c2d6a70 AC |
136 | New_Item : Element_Type; |
137 | Count : Count_Type := 1); | |
138 | ||
2368f04e | 139 | procedure Append |
4c2d6a70 | 140 | (Container : in out List; |
4c2d6a70 | 141 | New_Item : Element_Type; |
4c2d6a70 AC |
142 | Count : Count_Type := 1); |
143 | ||
144 | procedure Delete | |
145 | (Container : in out List; | |
146 | Position : in out Cursor; | |
147 | Count : Count_Type := 1); | |
148 | ||
149 | procedure Delete_First | |
150 | (Container : in out List; | |
151 | Count : Count_Type := 1); | |
152 | ||
153 | procedure Delete_Last | |
154 | (Container : in out List; | |
155 | Count : Count_Type := 1); | |
156 | ||
2368f04e | 157 | procedure Reverse_Elements (Container : in out List); |
4c2d6a70 | 158 | |
2368f04e | 159 | procedure Swap (Container : in out List; I, J : Cursor); |
4c2d6a70 AC |
160 | |
161 | procedure Swap_Links (Container : in out List; I, J : Cursor); | |
162 | ||
163 | procedure Splice | |
164 | (Target : in out List; | |
165 | Before : Cursor; | |
166 | Source : in out List); | |
167 | ||
168 | procedure Splice | |
169 | (Target : in out List; | |
170 | Before : Cursor; | |
2368f04e MH |
171 | Source : in out List; |
172 | Position : in out Cursor); | |
4c2d6a70 AC |
173 | |
174 | procedure Splice | |
7cdc672b MH |
175 | (Container : in out List; |
176 | Before : Cursor; | |
3837bc7f | 177 | Position : Cursor); |
4c2d6a70 AC |
178 | |
179 | function First (Container : List) return Cursor; | |
180 | ||
181 | function First_Element (Container : List) return Element_Type; | |
182 | ||
183 | function Last (Container : List) return Cursor; | |
184 | ||
185 | function Last_Element (Container : List) return Element_Type; | |
186 | ||
2368f04e MH |
187 | function Next (Position : Cursor) return Cursor; |
188 | ||
189 | procedure Next (Position : in out Cursor); | |
190 | ||
191 | function Previous (Position : Cursor) return Cursor; | |
192 | ||
193 | procedure Previous (Position : in out Cursor); | |
4c2d6a70 AC |
194 | |
195 | function Find | |
196 | (Container : List; | |
197 | Item : Element_Type; | |
198 | Position : Cursor := No_Element) return Cursor; | |
199 | ||
200 | function Reverse_Find | |
201 | (Container : List; | |
202 | Item : Element_Type; | |
203 | Position : Cursor := No_Element) return Cursor; | |
204 | ||
2368f04e MH |
205 | function Contains |
206 | (Container : List; | |
207 | Item : Element_Type) return Boolean; | |
4c2d6a70 | 208 | |
4c2d6a70 AC |
209 | procedure Iterate |
210 | (Container : List; | |
211 | Process : not null access procedure (Position : Cursor)); | |
212 | ||
213 | procedure Reverse_Iterate | |
214 | (Container : List; | |
215 | Process : not null access procedure (Position : Cursor)); | |
216 | ||
833eaa8a AC |
217 | function Iterate |
218 | (Container : List) | |
3a613a36 AC |
219 | return List_Iterator_Interfaces.Reversible_Iterator'class; |
220 | ||
833eaa8a AC |
221 | function Iterate |
222 | (Container : List; | |
223 | Start : Cursor) | |
3a613a36 AC |
224 | return List_Iterator_Interfaces.Reversible_Iterator'class; |
225 | ||
2368f04e MH |
226 | generic |
227 | with function "<" (Left, Right : Element_Type) return Boolean is <>; | |
228 | package Generic_Sorting is | |
229 | ||
230 | function Is_Sorted (Container : List) return Boolean; | |
231 | ||
232 | procedure Sort (Container : in out List); | |
233 | ||
234 | procedure Merge (Target, Source : in out List); | |
235 | ||
236 | end Generic_Sorting; | |
237 | ||
4c2d6a70 | 238 | private |
f97ccb3a BD |
239 | |
240 | pragma Inline (Next); | |
241 | pragma Inline (Previous); | |
242 | ||
4c2d6a70 AC |
243 | type Node_Type; |
244 | type Node_Access is access Node_Type; | |
245 | ||
246 | type Element_Access is access Element_Type; | |
247 | ||
248 | type Node_Type is | |
8704d4b3 | 249 | limited record |
4c2d6a70 AC |
250 | Element : Element_Access; |
251 | Next : Node_Access; | |
252 | Prev : Node_Access; | |
253 | end record; | |
254 | ||
4c2d6a70 | 255 | use Ada.Finalization; |
3c24c853 | 256 | use Ada.Streams; |
4c2d6a70 AC |
257 | |
258 | type List is | |
259 | new Controlled with record | |
260 | First : Node_Access; | |
261 | Last : Node_Access; | |
262 | Length : Count_Type := 0; | |
8704d4b3 MH |
263 | Busy : Natural := 0; |
264 | Lock : Natural := 0; | |
4c2d6a70 AC |
265 | end record; |
266 | ||
607d0635 | 267 | overriding procedure Adjust (Container : in out List); |
4c2d6a70 | 268 | |
607d0635 | 269 | overriding procedure Finalize (Container : in out List) renames Clear; |
4c2d6a70 | 270 | |
4c2d6a70 | 271 | procedure Read |
3837bc7f | 272 | (Stream : not null access Root_Stream_Type'Class; |
4c2d6a70 AC |
273 | Item : out List); |
274 | ||
275 | for List'Read use Read; | |
276 | ||
277 | procedure Write | |
3837bc7f | 278 | (Stream : not null access Root_Stream_Type'Class; |
4c2d6a70 AC |
279 | Item : List); |
280 | ||
281 | for List'Write use Write; | |
282 | ||
ef992452 | 283 | type List_Access is access all List; |
4c2d6a70 AC |
284 | for List_Access'Storage_Size use 0; |
285 | ||
286 | type Cursor is | |
287 | record | |
288 | Container : List_Access; | |
289 | Node : Node_Access; | |
290 | end record; | |
291 | ||
2368f04e | 292 | procedure Read |
3837bc7f | 293 | (Stream : not null access Root_Stream_Type'Class; |
2368f04e MH |
294 | Item : out Cursor); |
295 | ||
296 | for Cursor'Read use Read; | |
297 | ||
298 | procedure Write | |
3837bc7f | 299 | (Stream : not null access Root_Stream_Type'Class; |
2368f04e MH |
300 | Item : Cursor); |
301 | ||
302 | for Cursor'Write use Write; | |
303 | ||
794b9b72 AC |
304 | type Reference_Control_Type is |
305 | new Controlled with record | |
306 | Container : List_Access; | |
307 | end record; | |
308 | ||
309 | overriding procedure Adjust (Control : in out Reference_Control_Type); | |
310 | pragma Inline (Adjust); | |
311 | ||
312 | overriding procedure Finalize (Control : in out Reference_Control_Type); | |
313 | pragma Inline (Finalize); | |
314 | ||
3c24c853 | 315 | type Constant_Reference_Type |
db222ead | 316 | (Element : not null access constant Element_Type) is |
794b9b72 | 317 | record |
db222ead AC |
318 | Control : Reference_Control_Type := |
319 | raise Program_Error with "uninitialized reference"; | |
320 | -- The RM says, "The default initialization of an object of | |
321 | -- type Constant_Reference_Type or Reference_Type propagates | |
322 | -- Program_Error." | |
794b9b72 | 323 | end record; |
3c24c853 MH |
324 | |
325 | procedure Write | |
326 | (Stream : not null access Root_Stream_Type'Class; | |
327 | Item : Constant_Reference_Type); | |
328 | ||
329 | for Constant_Reference_Type'Write use Write; | |
330 | ||
331 | procedure Read | |
332 | (Stream : not null access Root_Stream_Type'Class; | |
333 | Item : out Constant_Reference_Type); | |
334 | ||
335 | for Constant_Reference_Type'Read use Read; | |
336 | ||
337 | type Reference_Type | |
db222ead | 338 | (Element : not null access Element_Type) is |
794b9b72 | 339 | record |
db222ead AC |
340 | Control : Reference_Control_Type := |
341 | raise Program_Error with "uninitialized reference"; | |
342 | -- The RM says, "The default initialization of an object of | |
343 | -- type Constant_Reference_Type or Reference_Type propagates | |
344 | -- Program_Error." | |
794b9b72 | 345 | end record; |
3c24c853 MH |
346 | |
347 | procedure Write | |
348 | (Stream : not null access Root_Stream_Type'Class; | |
349 | Item : Reference_Type); | |
350 | ||
351 | for Reference_Type'Write use Write; | |
352 | ||
353 | procedure Read | |
354 | (Stream : not null access Root_Stream_Type'Class; | |
355 | Item : out Reference_Type); | |
356 | ||
357 | for Reference_Type'Read use Read; | |
358 | ||
7d2e68b3 JM |
359 | Empty_List : constant List := List'(Controlled with null, null, 0, 0, 0); |
360 | ||
4c2d6a70 AC |
361 | No_Element : constant Cursor := Cursor'(null, null); |
362 | ||
e2441021 AC |
363 | type Iterator is new Limited_Controlled and |
364 | List_Iterator_Interfaces.Reversible_Iterator with | |
365 | record | |
366 | Container : List_Access; | |
367 | Node : Node_Access; | |
368 | end record; | |
369 | ||
370 | overriding procedure Finalize (Object : in out Iterator); | |
371 | ||
372 | overriding function First (Object : Iterator) return Cursor; | |
373 | overriding function Last (Object : Iterator) return Cursor; | |
374 | ||
375 | overriding function Next | |
376 | (Object : Iterator; | |
377 | Position : Cursor) return Cursor; | |
378 | ||
379 | overriding function Previous | |
380 | (Object : Iterator; | |
381 | Position : Cursor) return Cursor; | |
382 | ||
4c2d6a70 | 383 | end Ada.Containers.Indefinite_Doubly_Linked_Lists; |