File : a-cbdlli.ads
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT LIBRARY COMPONENTS --
4 -- --
5 -- ADA.CONTAINERS.BOUNDED_DOUBLY_LINKED_LISTS --
6 -- --
7 -- S p e c --
8 -- --
9 -- Copyright (C) 2004-2015, Free Software Foundation, Inc. --
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 -- --
23 -- --
24 -- --
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 Ada.Iterator_Interfaces;
35
36 with Ada.Containers.Helpers;
37 private with Ada.Streams;
38 private with Ada.Finalization;
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.Bounded_Doubly_Linked_Lists is
47 pragma Annotate (CodePeer, Skip_Analysis);
48 pragma Pure;
49 pragma Remote_Types;
50
51 type List (Capacity : Count_Type) is tagged private with
52 Constant_Indexing => Constant_Reference,
53 Variable_Indexing => Reference,
54 Default_Iterator => Iterate,
55 Iterator_Element => Element_Type;
56
57 pragma Preelaborable_Initialization (List);
58
59 type Cursor is private;
60 pragma Preelaborable_Initialization (Cursor);
61
62 Empty_List : constant List;
63
64 No_Element : constant Cursor;
65
66 function Has_Element (Position : Cursor) return Boolean;
67
68 package List_Iterator_Interfaces is new
69 Ada.Iterator_Interfaces (Cursor, Has_Element);
70
71 function "=" (Left, Right : List) return Boolean;
72
73 function Length (Container : List) return Count_Type;
74
75 function Is_Empty (Container : List) return Boolean;
76
77 procedure Clear (Container : in out List);
78
79 function Element (Position : Cursor) return Element_Type;
80
81 procedure Replace_Element
82 (Container : in out List;
83 Position : Cursor;
84 New_Item : Element_Type);
85
86 procedure Query_Element
87 (Position : Cursor;
88 Process : not null access procedure (Element : Element_Type));
89
90 procedure Update_Element
91 (Container : in out List;
92 Position : Cursor;
93 Process : not null access procedure (Element : in out Element_Type));
94
95 type Constant_Reference_Type
96 (Element : not null access constant Element_Type) is private
97 with
98 Implicit_Dereference => Element;
99
100 type Reference_Type
101 (Element : not null access Element_Type) is private
102 with
103 Implicit_Dereference => Element;
104
105 function Constant_Reference
106 (Container : aliased List;
107 Position : Cursor) return Constant_Reference_Type;
108
109 function Reference
110 (Container : aliased in out List;
111 Position : Cursor) return Reference_Type;
112
113 procedure Assign (Target : in out List; Source : List);
114
115 function Copy (Source : List; Capacity : Count_Type := 0) return List;
116
117 procedure Move
118 (Target : in out List;
119 Source : in out List);
120
121 procedure Insert
122 (Container : in out List;
123 Before : Cursor;
124 New_Item : Element_Type;
125 Count : Count_Type := 1);
126
127 procedure Insert
128 (Container : in out List;
129 Before : Cursor;
130 New_Item : Element_Type;
131 Position : out Cursor;
132 Count : Count_Type := 1);
133
134 procedure Insert
135 (Container : in out List;
136 Before : Cursor;
137 Position : out Cursor;
138 Count : Count_Type := 1);
139
140 procedure Prepend
141 (Container : in out List;
142 New_Item : Element_Type;
143 Count : Count_Type := 1);
144
145 procedure Append
146 (Container : in out List;
147 New_Item : Element_Type;
148 Count : Count_Type := 1);
149
150 procedure Delete
151 (Container : in out List;
152 Position : in out Cursor;
153 Count : Count_Type := 1);
154
155 procedure Delete_First
156 (Container : in out List;
157 Count : Count_Type := 1);
158
159 procedure Delete_Last
160 (Container : in out List;
161 Count : Count_Type := 1);
162
163 procedure Reverse_Elements (Container : in out List);
164
165 function Iterate
166 (Container : List)
167 return List_Iterator_Interfaces.Reversible_Iterator'class;
168
169 function Iterate
170 (Container : List;
171 Start : Cursor)
172 return List_Iterator_Interfaces.Reversible_Iterator'class;
173
174 procedure Swap
175 (Container : in out List;
176 I, J : Cursor);
177
178 procedure Swap_Links
179 (Container : in out List;
180 I, J : Cursor);
181
182 procedure Splice
183 (Target : in out List;
184 Before : Cursor;
185 Source : in out List);
186
187 procedure Splice
188 (Target : in out List;
189 Before : Cursor;
190 Source : in out List;
191 Position : in out Cursor);
192
193 procedure Splice
194 (Container : in out List;
195 Before : Cursor;
196 Position : Cursor);
197
198 function First (Container : List) return Cursor;
199
200 function First_Element (Container : List) return Element_Type;
201
202 function Last (Container : List) return Cursor;
203
204 function Last_Element (Container : List) return Element_Type;
205
206 function Next (Position : Cursor) return Cursor;
207
208 procedure Next (Position : in out Cursor);
209
210 function Previous (Position : Cursor) return Cursor;
211
212 procedure Previous (Position : in out Cursor);
213
214 function Find
215 (Container : List;
216 Item : Element_Type;
217 Position : Cursor := No_Element) return Cursor;
218
219 function Reverse_Find
220 (Container : List;
221 Item : Element_Type;
222 Position : Cursor := No_Element) return Cursor;
223
224 function Contains
225 (Container : List;
226 Item : Element_Type) return Boolean;
227
228 procedure Iterate
229 (Container : List;
230 Process : not null access procedure (Position : Cursor));
231
232 procedure Reverse_Iterate
233 (Container : List;
234 Process : not null access procedure (Position : Cursor));
235
236 generic
237 with function "<" (Left, Right : Element_Type) return Boolean is <>;
238 package Generic_Sorting is
239
240 function Is_Sorted (Container : List) return Boolean;
241
242 procedure Sort (Container : in out List);
243
244 procedure Merge (Target, Source : in out List);
245
246 end Generic_Sorting;
247
248 private
249
250 pragma Inline (Next);
251 pragma Inline (Previous);
252
253 use Ada.Containers.Helpers;
254 package Implementation is new Generic_Implementation;
255 use Implementation;
256
257 use Ada.Streams;
258 use Ada.Finalization;
259
260 type Node_Type is record
261 Prev : Count_Type'Base;
262 Next : Count_Type;
263 Element : aliased Element_Type;
264 end record;
265
266 type Node_Array is array (Count_Type range <>) of Node_Type;
267
268 type List (Capacity : Count_Type) is tagged record
269 Nodes : Node_Array (1 .. Capacity) := (others => <>);
270 Free : Count_Type'Base := -1;
271 First : Count_Type := 0;
272 Last : Count_Type := 0;
273 Length : Count_Type := 0;
274 TC : aliased Tamper_Counts;
275 end record;
276
277 procedure Read
278 (Stream : not null access Root_Stream_Type'Class;
279 Item : out List);
280
281 for List'Read use Read;
282
283 procedure Write
284 (Stream : not null access Root_Stream_Type'Class;
285 Item : List);
286
287 for List'Write use Write;
288
289 type List_Access is access all List;
290 for List_Access'Storage_Size use 0;
291
292 type Cursor is record
293 Container : List_Access;
294 Node : Count_Type := 0;
295 end record;
296
297 procedure Read
298 (Stream : not null access Root_Stream_Type'Class;
299 Item : out Cursor);
300
301 for Cursor'Read use Read;
302
303 procedure Write
304 (Stream : not null access Root_Stream_Type'Class;
305 Item : Cursor);
306
307 for Cursor'Write use Write;
308
309 subtype Reference_Control_Type is Implementation.Reference_Control_Type;
310 -- It is necessary to rename this here, so that the compiler can find it
311
312 type Constant_Reference_Type
313 (Element : not null access constant Element_Type) is
314 record
315 Control : Reference_Control_Type :=
316 raise Program_Error with "uninitialized reference";
317 -- The RM says, "The default initialization of an object of
318 -- type Constant_Reference_Type or Reference_Type propagates
319 -- Program_Error."
320 end record;
321
322 procedure Read
323 (Stream : not null access Root_Stream_Type'Class;
324 Item : out Constant_Reference_Type);
325
326 for Constant_Reference_Type'Read use Read;
327
328 procedure Write
329 (Stream : not null access Root_Stream_Type'Class;
330 Item : Constant_Reference_Type);
331
332 for Constant_Reference_Type'Write use Write;
333
334 type Reference_Type (Element : not null access Element_Type) is record
335 Control : Reference_Control_Type :=
336 raise Program_Error with "uninitialized reference";
337 -- The RM says, "The default initialization of an object of
338 -- type Constant_Reference_Type or Reference_Type propagates
339 -- Program_Error."
340 end record;
341
342 procedure Write
343 (Stream : not null access Root_Stream_Type'Class;
344 Item : Reference_Type);
345
346 for Reference_Type'Write use Write;
347
348 procedure Read
349 (Stream : not null access Root_Stream_Type'Class;
350 Item : out Reference_Type);
351
352 for Reference_Type'Read use Read;
353
354 -- Three operations are used to optimize in the expansion of "for ... of"
355 -- loops: the Next(Cursor) procedure in the visible part, and the following
356 -- Pseudo_Reference and Get_Element_Access functions. See Exp_Ch5 for
357 -- details.
358
359 function Pseudo_Reference
360 (Container : aliased List'Class) return Reference_Control_Type;
361 pragma Inline (Pseudo_Reference);
362 -- Creates an object of type Reference_Control_Type pointing to the
363 -- container, and increments the Lock. Finalization of this object will
364 -- decrement the Lock.
365
366 type Element_Access is access all Element_Type with
367 Storage_Size => 0;
368
369 function Get_Element_Access
370 (Position : Cursor) return not null Element_Access;
371 -- Returns a pointer to the element designated by Position.
372
373 Empty_List : constant List := (Capacity => 0, others => <>);
374
375 No_Element : constant Cursor := Cursor'(null, 0);
376
377 type Iterator is new Limited_Controlled and
378 List_Iterator_Interfaces.Reversible_Iterator with
379 record
380 Container : List_Access;
381 Node : Count_Type;
382 end record
383 with Disable_Controlled => not T_Check;
384
385 overriding procedure Finalize (Object : in out Iterator);
386
387 overriding function First (Object : Iterator) return Cursor;
388 overriding function Last (Object : Iterator) return Cursor;
389
390 overriding function Next
391 (Object : Iterator;
392 Position : Cursor) return Cursor;
393
394 overriding function Previous
395 (Object : Iterator;
396 Position : Cursor) return Cursor;
397
398 end Ada.Containers.Bounded_Doubly_Linked_Lists;