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 private with Ada.Finalization;
35 private with Ada.Streams;
38 type Element_Type (<>) is private;
40 with function "=" (Left, Right : Element_Type) return Boolean is <>;
42 package Ada.Containers.Indefinite_Multiway_Trees is
46 type Tree is tagged private;
47 pragma Preelaborable_Initialization (Tree);
49 type Cursor is private;
50 pragma Preelaborable_Initialization (Cursor);
52 Empty_Tree : constant Tree;
54 No_Element : constant Cursor;
56 function Equal_Subtree
57 (Left_Position : Cursor;
58 Right_Position : Cursor) return Boolean;
60 function "=" (Left, Right : Tree) return Boolean;
62 function Is_Empty (Container : Tree) return Boolean;
64 function Node_Count (Container : Tree) return Count_Type;
66 function Subtree_Node_Count (Position : Cursor) return Count_Type;
68 function Depth (Position : Cursor) return Count_Type;
70 function Is_Root (Position : Cursor) return Boolean;
72 function Is_Leaf (Position : Cursor) return Boolean;
74 function Root (Container : Tree) return Cursor;
76 procedure Clear (Container : in out Tree);
78 function Element (Position : Cursor) return Element_Type;
80 procedure Replace_Element
81 (Container : in out Tree;
83 New_Item : Element_Type);
85 procedure Query_Element
87 Process : not null access procedure (Element : Element_Type));
89 procedure Update_Element
90 (Container : in out Tree;
92 Process : not null access procedure (Element : in out Element_Type));
94 procedure Assign (Target : in out Tree; Source : Tree);
96 function Copy (Source : Tree) return Tree;
98 procedure Move (Target : in out Tree; Source : in out Tree);
100 procedure Delete_Leaf
101 (Container : in out Tree;
102 Position : in out Cursor);
104 procedure Delete_Subtree
105 (Container : in out Tree;
106 Position : in out Cursor);
109 (Container : in out Tree;
114 Item : Element_Type) return Cursor;
116 -- This version of the AI:
117 -- 10-06-02 AI05-0136-1/07
118 -- declares Find_In_Subtree this way:
120 -- function Find_In_Subtree
121 -- (Container : Tree;
122 -- Item : Element_Type;
123 -- Position : Cursor) return Cursor;
125 -- It seems that the Container parameter is there by mistake, but we need
126 -- an official ruling from the ARG. ???
128 function Find_In_Subtree
130 Item : Element_Type) return Cursor;
132 -- This version of the AI:
133 -- 10-06-02 AI05-0136-1/07
134 -- declares Ancestor_Find this way:
136 -- function Ancestor_Find
137 -- (Container : Tree;
138 -- Item : Element_Type;
139 -- Position : Cursor) return Cursor;
141 -- It seems that the Container parameter is there by mistake, but we need
142 -- an official ruling from the ARG. ???
144 function Ancestor_Find
146 Item : Element_Type) return Cursor;
150 Item : Element_Type) return Boolean;
152 function Has_Element (Position : Cursor) return Boolean;
156 Process : not null access procedure (Position : Cursor));
158 procedure Iterate_Subtree
160 Process : not null access procedure (Position : Cursor));
162 function Child_Count (Parent : Cursor) return Count_Type;
164 function Child_Depth (Parent, Child : Cursor) return Count_Type;
166 procedure Insert_Child
167 (Container : in out Tree;
170 New_Item : Element_Type;
171 Count : Count_Type := 1);
173 procedure Insert_Child
174 (Container : in out Tree;
177 New_Item : Element_Type;
178 Position : out Cursor;
179 Count : Count_Type := 1);
181 procedure Prepend_Child
182 (Container : in out Tree;
184 New_Item : Element_Type;
185 Count : Count_Type := 1);
187 procedure Append_Child
188 (Container : in out Tree;
190 New_Item : Element_Type;
191 Count : Count_Type := 1);
193 procedure Delete_Children
194 (Container : in out Tree;
197 procedure Copy_Subtree
198 (Target : in out Tree;
203 procedure Splice_Subtree
204 (Target : in out Tree;
207 Source : in out Tree;
208 Position : in out Cursor);
210 procedure Splice_Subtree
211 (Container : in out Tree;
216 procedure Splice_Children
217 (Target : in out Tree;
218 Target_Parent : Cursor;
220 Source : in out Tree;
221 Source_Parent : Cursor);
223 procedure Splice_Children
224 (Container : in out Tree;
225 Target_Parent : Cursor;
227 Source_Parent : Cursor);
229 function Parent (Position : Cursor) return Cursor;
231 function First_Child (Parent : Cursor) return Cursor;
233 function First_Child_Element (Parent : Cursor) return Element_Type;
235 function Last_Child (Parent : Cursor) return Cursor;
237 function Last_Child_Element (Parent : Cursor) return Element_Type;
239 function Next_Sibling (Position : Cursor) return Cursor;
241 function Previous_Sibling (Position : Cursor) return Cursor;
243 procedure Next_Sibling (Position : in out Cursor);
245 procedure Previous_Sibling (Position : in out Cursor);
247 -- This version of the AI:
248 -- 10-06-02 AI05-0136-1/07
249 -- declares Iterate_Children this way:
251 -- procedure Iterate_Children
252 -- (Container : Tree;
254 -- Process : not null access procedure (Position : Cursor));
256 -- It seems that the Container parameter is there by mistake, but we need
257 -- an official ruling from the ARG. ???
259 procedure Iterate_Children
261 Process : not null access procedure (Position : Cursor));
263 procedure Reverse_Iterate_Children
265 Process : not null access procedure (Position : Cursor));
270 type Tree_Node_Access is access all Tree_Node_Type;
272 type Children_Type is record
273 First : Tree_Node_Access;
274 Last : Tree_Node_Access;
277 type Element_Access is access Element_Type;
279 type Tree_Node_Type is record
280 Parent : Tree_Node_Access;
281 Prev : Tree_Node_Access;
282 Next : Tree_Node_Access;
283 Children : Children_Type;
284 Element : Element_Access;
287 use Ada.Finalization;
289 -- The Count component of type Tree represents the number of nodes that
290 -- have been (dynamically) allocated. It does not include the root node
291 -- itself. As implementors, we decide to cache this value, so that the
292 -- selector function Node_Count can execute in O(1) time, in order to be
293 -- consistent with the behavior of the Length selector function for other
294 -- standard container library units. This does mean, however, that the
295 -- two-container forms for Splice_XXX (that move subtrees across tree
296 -- containers) will execute in O(n) time, because we must count the number
297 -- of nodes in the subtree(s) that get moved. (We resolve the tension
298 -- between Node_Count and Splice_XXX in favor of Node_Count, under the
299 -- assumption that Node_Count is the more common operation).
301 type Tree is new Controlled with record
302 Root : aliased Tree_Node_Type;
305 Count : Count_Type := 0;
308 overriding procedure Adjust (Container : in out Tree);
310 overriding procedure Finalize (Container : in out Tree) renames Clear;
315 (Stream : not null access Root_Stream_Type'Class;
318 for Tree'Write use Write;
321 (Stream : not null access Root_Stream_Type'Class;
322 Container : out Tree);
324 for Tree'Read use Read;
326 type Tree_Access is access all Tree;
327 for Tree_Access'Storage_Size use 0;
329 type Cursor is record
330 Container : Tree_Access;
331 Node : Tree_Node_Access;
335 (Stream : not null access Root_Stream_Type'Class;
338 for Cursor'Write use Write;
341 (Stream : not null access Root_Stream_Type'Class;
342 Position : out Cursor);
344 for Cursor'Read use Read;
346 Empty_Tree : constant Tree := (Controlled with others => <>);
348 No_Element : constant Cursor := (others => <>);
350 end Ada.Containers.Indefinite_Multiway_Trees;