1------------------------------------------------------------------------------ 2-- -- 3-- GNAT LIBRARY COMPONENTS -- 4-- -- 5-- ADA.CONTAINERS.BOUNDED_MULTIWAY_TREES -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 2011-2012, 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-- 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/>. -- 30-- -- 31-- This unit was originally developed by Matthew J Heaney. -- 32------------------------------------------------------------------------------ 33 34with Ada.Iterator_Interfaces; 35private with Ada.Streams; 36 37generic 38 type Element_Type is private; 39 40 with function "=" (Left, Right : Element_Type) return Boolean is <>; 41 42package Ada.Containers.Bounded_Multiway_Trees is 43 pragma Pure; 44 pragma Remote_Types; 45 46 type Tree (Capacity : Count_Type) is tagged private 47 with Constant_Indexing => Constant_Reference, 48 Variable_Indexing => Reference, 49 Default_Iterator => Iterate, 50 Iterator_Element => Element_Type; 51 pragma Preelaborable_Initialization (Tree); 52 53 type Cursor is private; 54 pragma Preelaborable_Initialization (Cursor); 55 56 Empty_Tree : constant Tree; 57 58 No_Element : constant Cursor; 59 function Has_Element (Position : Cursor) return Boolean; 60 61 package Tree_Iterator_Interfaces is new 62 Ada.Iterator_Interfaces (Cursor, Has_Element); 63 64 function Equal_Subtree 65 (Left_Position : Cursor; 66 Right_Position : Cursor) return Boolean; 67 68 function "=" (Left, Right : Tree) return Boolean; 69 70 function Is_Empty (Container : Tree) return Boolean; 71 72 function Node_Count (Container : Tree) return Count_Type; 73 74 function Subtree_Node_Count (Position : Cursor) return Count_Type; 75 76 function Depth (Position : Cursor) return Count_Type; 77 78 function Is_Root (Position : Cursor) return Boolean; 79 80 function Is_Leaf (Position : Cursor) return Boolean; 81 82 function Root (Container : Tree) return Cursor; 83 84 procedure Clear (Container : in out Tree); 85 86 function Element (Position : Cursor) return Element_Type; 87 88 procedure Replace_Element 89 (Container : in out Tree; 90 Position : Cursor; 91 New_Item : Element_Type); 92 93 procedure Query_Element 94 (Position : Cursor; 95 Process : not null access procedure (Element : Element_Type)); 96 97 procedure Update_Element 98 (Container : in out Tree; 99 Position : Cursor; 100 Process : not null access procedure (Element : in out Element_Type)); 101 102 type Constant_Reference_Type 103 (Element : not null access constant Element_Type) is private 104 with Implicit_Dereference => Element; 105 106 type Reference_Type 107 (Element : not null access Element_Type) is private 108 with Implicit_Dereference => Element; 109 110 function Constant_Reference 111 (Container : aliased Tree; 112 Position : Cursor) return Constant_Reference_Type; 113 114 function Reference 115 (Container : aliased in out Tree; 116 Position : Cursor) return Reference_Type; 117 118 procedure Assign (Target : in out Tree; Source : Tree); 119 120 function Copy (Source : Tree; Capacity : Count_Type := 0) return Tree; 121 122 procedure Move (Target : in out Tree; Source : in out Tree); 123 124 procedure Delete_Leaf 125 (Container : in out Tree; 126 Position : in out Cursor); 127 128 procedure Delete_Subtree 129 (Container : in out Tree; 130 Position : in out Cursor); 131 132 procedure Swap 133 (Container : in out Tree; 134 I, J : Cursor); 135 136 function Find 137 (Container : Tree; 138 Item : Element_Type) return Cursor; 139 140 -- This version of the AI: 141 -- 10-06-02 AI05-0136-1/07 142 -- declares Find_In_Subtree this way: 143 -- 144 -- function Find_In_Subtree 145 -- (Container : Tree; 146 -- Item : Element_Type; 147 -- Position : Cursor) return Cursor; 148 -- 149 -- It seems that the Container parameter is there by mistake, but we need 150 -- an official ruling from the ARG. ??? 151 152 function Find_In_Subtree 153 (Position : Cursor; 154 Item : Element_Type) return Cursor; 155 156 -- This version of the AI: 157 -- 10-06-02 AI05-0136-1/07 158 -- declares Ancestor_Find this way: 159 -- 160 -- function Ancestor_Find 161 -- (Container : Tree; 162 -- Item : Element_Type; 163 -- Position : Cursor) return Cursor; 164 -- 165 -- It seems that the Container parameter is there by mistake, but we need 166 -- an official ruling from the ARG. ??? 167 168 function Ancestor_Find 169 (Position : Cursor; 170 Item : Element_Type) return Cursor; 171 172 function Contains 173 (Container : Tree; 174 Item : Element_Type) return Boolean; 175 176 procedure Iterate 177 (Container : Tree; 178 Process : not null access procedure (Position : Cursor)); 179 180 procedure Iterate_Subtree 181 (Position : Cursor; 182 Process : not null access procedure (Position : Cursor)); 183 184 function Iterate (Container : Tree) 185 return Tree_Iterator_Interfaces.Forward_Iterator'Class; 186 187 function Iterate_Subtree (Position : Cursor) 188 return Tree_Iterator_Interfaces.Forward_Iterator'Class; 189 190 function Iterate_Children 191 (Container : Tree; 192 Parent : Cursor) 193 return Tree_Iterator_Interfaces.Reversible_Iterator'Class; 194 195 function Child_Count (Parent : Cursor) return Count_Type; 196 197 function Child_Depth (Parent, Child : Cursor) return Count_Type; 198 199 procedure Insert_Child 200 (Container : in out Tree; 201 Parent : Cursor; 202 Before : Cursor; 203 New_Item : Element_Type; 204 Count : Count_Type := 1); 205 206 procedure Insert_Child 207 (Container : in out Tree; 208 Parent : Cursor; 209 Before : Cursor; 210 New_Item : Element_Type; 211 Position : out Cursor; 212 Count : Count_Type := 1); 213 214 procedure Insert_Child 215 (Container : in out Tree; 216 Parent : Cursor; 217 Before : Cursor; 218 Position : out Cursor; 219 Count : Count_Type := 1); 220 221 procedure Prepend_Child 222 (Container : in out Tree; 223 Parent : Cursor; 224 New_Item : Element_Type; 225 Count : Count_Type := 1); 226 227 procedure Append_Child 228 (Container : in out Tree; 229 Parent : Cursor; 230 New_Item : Element_Type; 231 Count : Count_Type := 1); 232 233 procedure Delete_Children 234 (Container : in out Tree; 235 Parent : Cursor); 236 237 procedure Copy_Subtree 238 (Target : in out Tree; 239 Parent : Cursor; 240 Before : Cursor; 241 Source : Cursor); 242 243 procedure Splice_Subtree 244 (Target : in out Tree; 245 Parent : Cursor; 246 Before : Cursor; 247 Source : in out Tree; 248 Position : in out Cursor); 249 250 procedure Splice_Subtree 251 (Container : in out Tree; 252 Parent : Cursor; 253 Before : Cursor; 254 Position : Cursor); 255 256 procedure Splice_Children 257 (Target : in out Tree; 258 Target_Parent : Cursor; 259 Before : Cursor; 260 Source : in out Tree; 261 Source_Parent : Cursor); 262 263 procedure Splice_Children 264 (Container : in out Tree; 265 Target_Parent : Cursor; 266 Before : Cursor; 267 Source_Parent : Cursor); 268 269 function Parent (Position : Cursor) return Cursor; 270 271 function First_Child (Parent : Cursor) return Cursor; 272 273 function First_Child_Element (Parent : Cursor) return Element_Type; 274 275 function Last_Child (Parent : Cursor) return Cursor; 276 277 function Last_Child_Element (Parent : Cursor) return Element_Type; 278 279 function Next_Sibling (Position : Cursor) return Cursor; 280 281 function Previous_Sibling (Position : Cursor) return Cursor; 282 283 procedure Next_Sibling (Position : in out Cursor); 284 285 procedure Previous_Sibling (Position : in out Cursor); 286 287 -- This version of the AI: 288 289 -- 10-06-02 AI05-0136-1/07 290 291 -- declares Iterate_Children this way: 292 293 -- procedure Iterate_Children 294 -- (Container : Tree; 295 -- Parent : Cursor; 296 -- Process : not null access procedure (Position : Cursor)); 297 298 -- It seems that the Container parameter is there by mistake, but we need 299 -- an official ruling from the ARG. ??? 300 301 procedure Iterate_Children 302 (Parent : Cursor; 303 Process : not null access procedure (Position : Cursor)); 304 305 procedure Reverse_Iterate_Children 306 (Parent : Cursor; 307 Process : not null access procedure (Position : Cursor)); 308 309private 310 use Ada.Streams; 311 312 No_Node : constant Count_Type'Base := -1; 313 -- Need to document all global declarations such as this ??? 314 315 -- Following decls also need much more documentation ??? 316 317 type Children_Type is record 318 First : Count_Type'Base; 319 Last : Count_Type'Base; 320 end record; 321 322 type Tree_Node_Type is record 323 Parent : Count_Type'Base; 324 Prev : Count_Type'Base; 325 Next : Count_Type'Base; 326 Children : Children_Type; 327 end record; 328 329 type Tree_Node_Array is array (Count_Type range <>) of Tree_Node_Type; 330 type Element_Array is array (Count_Type range <>) of aliased Element_Type; 331 332 type Tree (Capacity : Count_Type) is tagged record 333 Nodes : Tree_Node_Array (0 .. Capacity) := (others => <>); 334 Elements : Element_Array (1 .. Capacity) := (others => <>); 335 Free : Count_Type'Base := No_Node; 336 Busy : Integer := 0; 337 Lock : Integer := 0; 338 Count : Count_Type := 0; 339 end record; 340 341 procedure Write 342 (Stream : not null access Root_Stream_Type'Class; 343 Container : Tree); 344 345 for Tree'Write use Write; 346 347 procedure Read 348 (Stream : not null access Root_Stream_Type'Class; 349 Container : out Tree); 350 351 for Tree'Read use Read; 352 353 type Tree_Access is access all Tree; 354 for Tree_Access'Storage_Size use 0; 355 356 type Cursor is record 357 Container : Tree_Access; 358 Node : Count_Type'Base := No_Node; 359 end record; 360 361 procedure Read 362 (Stream : not null access Root_Stream_Type'Class; 363 Position : out Cursor); 364 for Cursor'Read use Read; 365 366 procedure Write 367 (Stream : not null access Root_Stream_Type'Class; 368 Position : Cursor); 369 for Cursor'Write use Write; 370 371 type Constant_Reference_Type 372 (Element : not null access constant Element_Type) is null record; 373 374 procedure Write 375 (Stream : not null access Root_Stream_Type'Class; 376 Item : Constant_Reference_Type); 377 for Constant_Reference_Type'Write use Write; 378 379 procedure Read 380 (Stream : not null access Root_Stream_Type'Class; 381 Item : out Constant_Reference_Type); 382 for Constant_Reference_Type'Read use Read; 383 384 type Reference_Type 385 (Element : not null access Element_Type) is null record; 386 387 procedure Write 388 (Stream : not null access Root_Stream_Type'Class; 389 Item : Reference_Type); 390 for Reference_Type'Write use Write; 391 392 procedure Read 393 (Stream : not null access Root_Stream_Type'Class; 394 Item : out Reference_Type); 395 for Reference_Type'Read use Read; 396 397 Empty_Tree : constant Tree := (Capacity => 0, others => <>); 398 399 No_Element : constant Cursor := Cursor'(others => <>); 400 401end Ada.Containers.Bounded_Multiway_Trees; 402