Mercurial > hg > CbC > CbC_gcc
comparison gcc/ada/libgnat/a-crdlli.ads @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
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-2017, 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 -- 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/>. -- | |
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; |