1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.INDEFINITE_MULTIWAY_TREES --
9 -- Copyright (C) 2004-2011, Free Software Foundation, Inc. --
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. --
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. --
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. --
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/>. --
31 -- This unit was originally developed by Matthew J Heaney. --
32 ------------------------------------------------------------------------------
34 with Ada.Iterator_Interfaces;
35 private with Ada.Finalization;
36 private with Ada.Streams;
39 type Element_Type (<>) is private;
41 with function "=" (Left, Right : Element_Type) return Boolean is <>;
43 package Ada.Containers.Indefinite_Multiway_Trees is
47 type Tree is tagged private
48 with Constant_Indexing => Constant_Reference,
49 Variable_Indexing => Reference,
50 Default_Iterator => Iterate,
51 Iterator_Element => Element_Type;
53 pragma Preelaborable_Initialization (Tree);
55 type Cursor is private;
56 pragma Preelaborable_Initialization (Cursor);
58 Empty_Tree : constant Tree;
60 No_Element : constant Cursor;
61 function Has_Element (Position : Cursor) return Boolean;
63 package Tree_Iterator_Interfaces is new
64 Ada.Iterator_Interfaces (Cursor, Has_Element);
66 function Equal_Subtree
67 (Left_Position : Cursor;
68 Right_Position : Cursor) return Boolean;
70 function "=" (Left, Right : Tree) return Boolean;
72 function Is_Empty (Container : Tree) return Boolean;
74 function Node_Count (Container : Tree) return Count_Type;
76 function Subtree_Node_Count (Position : Cursor) return Count_Type;
78 function Depth (Position : Cursor) return Count_Type;
80 function Is_Root (Position : Cursor) return Boolean;
82 function Is_Leaf (Position : Cursor) return Boolean;
84 function Root (Container : Tree) return Cursor;
86 procedure Clear (Container : in out Tree);
88 function Element (Position : Cursor) return Element_Type;
90 procedure Replace_Element
91 (Container : in out Tree;
93 New_Item : Element_Type);
95 procedure Query_Element
97 Process : not null access procedure (Element : Element_Type));
99 procedure Update_Element
100 (Container : in out Tree;
102 Process : not null access procedure (Element : in out Element_Type));
104 type Constant_Reference_Type
105 (Element : not null access constant Element_Type) is private
106 with Implicit_Dereference => Element;
109 (Element : not null access Element_Type) is private
110 with Implicit_Dereference => Element;
112 procedure Assign (Target : in out Tree; Source : Tree);
114 function Copy (Source : Tree) return Tree;
116 procedure Move (Target : in out Tree; Source : in out Tree);
118 procedure Delete_Leaf
119 (Container : in out Tree;
120 Position : in out Cursor);
122 procedure Delete_Subtree
123 (Container : in out Tree;
124 Position : in out Cursor);
127 (Container : in out Tree;
132 Item : Element_Type) return Cursor;
134 -- This version of the AI:
135 -- 10-06-02 AI05-0136-1/07
136 -- declares Find_In_Subtree this way:
138 -- function Find_In_Subtree
139 -- (Container : Tree;
140 -- Item : Element_Type;
141 -- Position : Cursor) return Cursor;
143 -- It seems that the Container parameter is there by mistake, but we need
144 -- an official ruling from the ARG. ???
146 function Find_In_Subtree
148 Item : Element_Type) return Cursor;
150 -- This version of the AI:
151 -- 10-06-02 AI05-0136-1/07
152 -- declares Ancestor_Find this way:
154 -- function Ancestor_Find
155 -- (Container : Tree;
156 -- Item : Element_Type;
157 -- Position : Cursor) return Cursor;
159 -- It seems that the Container parameter is there by mistake, but we need
160 -- an official ruling from the ARG. ???
162 function Ancestor_Find
164 Item : Element_Type) return Cursor;
168 Item : Element_Type) return Boolean;
172 Process : not null access procedure (Position : Cursor));
174 procedure Iterate_Subtree
176 Process : not null access procedure (Position : Cursor));
178 function Iterate (Container : Tree)
179 return Tree_Iterator_Interfaces.Forward_Iterator'Class;
181 function Iterate_Subtree (Position : Cursor)
182 return Tree_Iterator_Interfaces.Forward_Iterator'Class;
184 function Iterate_Children
187 return Tree_Iterator_Interfaces.Reversible_Iterator'Class;
189 function Child_Count (Parent : Cursor) return Count_Type;
191 function Child_Depth (Parent, Child : Cursor) return Count_Type;
193 procedure Insert_Child
194 (Container : in out Tree;
197 New_Item : Element_Type;
198 Count : Count_Type := 1);
200 procedure Insert_Child
201 (Container : in out Tree;
204 New_Item : Element_Type;
205 Position : out Cursor;
206 Count : Count_Type := 1);
208 procedure Prepend_Child
209 (Container : in out Tree;
211 New_Item : Element_Type;
212 Count : Count_Type := 1);
214 procedure Append_Child
215 (Container : in out Tree;
217 New_Item : Element_Type;
218 Count : Count_Type := 1);
220 procedure Delete_Children
221 (Container : in out Tree;
224 procedure Copy_Subtree
225 (Target : in out Tree;
230 procedure Splice_Subtree
231 (Target : in out Tree;
234 Source : in out Tree;
235 Position : in out Cursor);
237 procedure Splice_Subtree
238 (Container : in out Tree;
243 procedure Splice_Children
244 (Target : in out Tree;
245 Target_Parent : Cursor;
247 Source : in out Tree;
248 Source_Parent : Cursor);
250 procedure Splice_Children
251 (Container : in out Tree;
252 Target_Parent : Cursor;
254 Source_Parent : Cursor);
256 function Parent (Position : Cursor) return Cursor;
258 function First_Child (Parent : Cursor) return Cursor;
260 function First_Child_Element (Parent : Cursor) return Element_Type;
262 function Last_Child (Parent : Cursor) return Cursor;
264 function Last_Child_Element (Parent : Cursor) return Element_Type;
266 function Next_Sibling (Position : Cursor) return Cursor;
268 function Previous_Sibling (Position : Cursor) return Cursor;
270 procedure Next_Sibling (Position : in out Cursor);
272 procedure Previous_Sibling (Position : in out Cursor);
274 -- This version of the AI:
275 -- 10-06-02 AI05-0136-1/07
276 -- declares Iterate_Children this way:
278 -- procedure Iterate_Children
279 -- (Container : Tree;
281 -- Process : not null access procedure (Position : Cursor));
283 -- It seems that the Container parameter is there by mistake, but we need
284 -- an official ruling from the ARG. ???
286 procedure Iterate_Children
288 Process : not null access procedure (Position : Cursor));
290 procedure Reverse_Iterate_Children
292 Process : not null access procedure (Position : Cursor));
297 type Tree_Node_Access is access all Tree_Node_Type;
299 type Children_Type is record
300 First : Tree_Node_Access;
301 Last : Tree_Node_Access;
304 type Element_Access is access Element_Type;
306 type Tree_Node_Type is record
307 Parent : Tree_Node_Access;
308 Prev : Tree_Node_Access;
309 Next : Tree_Node_Access;
310 Children : Children_Type;
311 Element : Element_Access;
314 use Ada.Finalization;
316 -- The Count component of type Tree represents the number of nodes that
317 -- have been (dynamically) allocated. It does not include the root node
318 -- itself. As implementors, we decide to cache this value, so that the
319 -- selector function Node_Count can execute in O(1) time, in order to be
320 -- consistent with the behavior of the Length selector function for other
321 -- standard container library units. This does mean, however, that the
322 -- two-container forms for Splice_XXX (that move subtrees across tree
323 -- containers) will execute in O(n) time, because we must count the number
324 -- of nodes in the subtree(s) that get moved. (We resolve the tension
325 -- between Node_Count and Splice_XXX in favor of Node_Count, under the
326 -- assumption that Node_Count is the more common operation).
328 type Tree is new Controlled with record
329 Root : aliased Tree_Node_Type;
332 Count : Count_Type := 0;
335 overriding procedure Adjust (Container : in out Tree);
337 overriding procedure Finalize (Container : in out Tree) renames Clear;
342 (Stream : not null access Root_Stream_Type'Class;
345 for Tree'Write use Write;
348 (Stream : not null access Root_Stream_Type'Class;
349 Container : out Tree);
351 for Tree'Read use Read;
353 type Tree_Access is access all Tree;
354 for Tree_Access'Storage_Size use 0;
356 type Cursor is record
357 Container : Tree_Access;
358 Node : Tree_Node_Access;
362 (Stream : not null access Root_Stream_Type'Class;
365 for Cursor'Write use Write;
368 (Stream : not null access Root_Stream_Type'Class;
369 Position : out Cursor);
371 for Cursor'Read use Read;
373 type Constant_Reference_Type
374 (Element : not null access constant Element_Type) is null record;
377 (Stream : not null access Root_Stream_Type'Class;
378 Item : out Constant_Reference_Type);
380 for Constant_Reference_Type'Read use Read;
383 (Stream : not null access Root_Stream_Type'Class;
384 Item : Constant_Reference_Type);
386 for Constant_Reference_Type'Write use Write;
389 (Element : not null access Element_Type) is null record;
392 (Stream : not null access Root_Stream_Type'Class;
393 Item : out Reference_Type);
395 for Reference_Type'Read use Read;
398 (Stream : not null access Root_Stream_Type'Class;
399 Item : Reference_Type);
401 for Reference_Type'Write use Write;
403 function Constant_Reference
404 (Container : aliased Tree;
405 Position : Cursor) return Constant_Reference_Type;
408 (Container : aliased Tree;
409 Position : Cursor) return Reference_Type;
411 Empty_Tree : constant Tree := (Controlled with others => <>);
413 No_Element : constant Cursor := (others => <>);
415 end Ada.Containers.Indefinite_Multiway_Trees;