1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.BOUNDED_MULTIWAY_TREES --
9 -- Copyright (C) 2011-2024, Free Software Foundation, Inc. --
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. --
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. --
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/>. --
27 -- This unit was originally developed by Matthew J Heaney. --
28 ------------------------------------------------------------------------------
30 with Ada
.Finalization
;
31 with System
; use type System
.Address
;
32 with System
.Put_Images
;
34 package body Ada
.Containers
.Bounded_Multiway_Trees
with
38 pragma Warnings
(Off
, "variable ""Busy*"" is not referenced");
39 pragma Warnings
(Off
, "variable ""Lock*"" is not referenced");
40 -- See comment in Ada.Containers.Helpers
48 type Root_Iterator
is abstract new Limited_Controlled
and
49 Tree_Iterator_Interfaces
.Forward_Iterator
with
51 Container
: Tree_Access
;
55 overriding
procedure Finalize
(Object
: in out Root_Iterator
);
57 -----------------------
58 -- Subtree_Iterator --
59 -----------------------
61 type Subtree_Iterator
is new Root_Iterator
with null record;
63 overriding
function First
(Object
: Subtree_Iterator
) return Cursor
;
65 overriding
function Next
66 (Object
: Subtree_Iterator
;
67 Position
: Cursor
) return Cursor
;
73 type Child_Iterator
is new Root_Iterator
and
74 Tree_Iterator_Interfaces
.Reversible_Iterator
with null record;
76 overriding
function First
(Object
: Child_Iterator
) return Cursor
;
78 overriding
function Next
79 (Object
: Child_Iterator
;
80 Position
: Cursor
) return Cursor
;
82 overriding
function Last
(Object
: Child_Iterator
) return Cursor
;
84 overriding
function Previous
85 (Object
: Child_Iterator
;
86 Position
: Cursor
) return Cursor
;
88 -----------------------
89 -- Local Subprograms --
90 -----------------------
92 procedure Initialize_Node
(Container
: in out Tree
; Index
: Count_Type
);
93 procedure Initialize_Root
(Container
: in out Tree
);
95 procedure Allocate_Node
96 (Container
: in out Tree
;
97 Initialize_Element
: not null access procedure (Index
: Count_Type
);
98 New_Node
: out Count_Type
);
100 procedure Allocate_Node
101 (Container
: in out Tree
;
102 New_Item
: Element_Type
;
103 New_Node
: out Count_Type
);
105 procedure Allocate_Node
106 (Container
: in out Tree
;
107 Stream
: not null access Root_Stream_Type
'Class;
108 New_Node
: out Count_Type
);
110 procedure Deallocate_Node
111 (Container
: in out Tree
;
114 procedure Deallocate_Children
115 (Container
: in out Tree
;
116 Subtree
: Count_Type
;
117 Count
: in out Count_Type
);
119 procedure Deallocate_Subtree
120 (Container
: in out Tree
;
121 Subtree
: Count_Type
;
122 Count
: in out Count_Type
);
124 function Equal_Children
126 Left_Subtree
: Count_Type
;
128 Right_Subtree
: Count_Type
) return Boolean;
130 function Equal_Subtree
132 Left_Subtree
: Count_Type
;
134 Right_Subtree
: Count_Type
) return Boolean;
136 procedure Iterate_Children
138 Subtree
: Count_Type
;
139 Process
: not null access procedure (Position
: Cursor
));
141 procedure Iterate_Subtree
143 Subtree
: Count_Type
;
144 Process
: not null access procedure (Position
: Cursor
));
146 procedure Copy_Children
148 Source_Parent
: Count_Type
;
149 Target
: in out Tree
;
150 Target_Parent
: Count_Type
;
151 Count
: in out Count_Type
);
153 procedure Copy_Subtree
155 Source_Subtree
: Count_Type
;
156 Target
: in out Tree
;
157 Target_Parent
: Count_Type
;
158 Target_Subtree
: out Count_Type
;
159 Count
: in out Count_Type
);
161 function Find_In_Children
163 Subtree
: Count_Type
;
164 Item
: Element_Type
) return Count_Type
;
166 function Find_In_Subtree
168 Subtree
: Count_Type
;
169 Item
: Element_Type
) return Count_Type
;
173 Parent
: Count_Type
) return Count_Type
;
175 function Subtree_Node_Count
177 Subtree
: Count_Type
) return Count_Type
;
179 function Is_Reachable
181 From
, To
: Count_Type
) return Boolean;
183 function Root_Node
(Container
: Tree
) return Count_Type
;
185 procedure Remove_Subtree
186 (Container
: in out Tree
;
187 Subtree
: Count_Type
);
189 procedure Insert_Subtree_Node
190 (Container
: in out Tree
;
191 Subtree
: Count_Type
'Base;
193 Before
: Count_Type
'Base);
195 procedure Insert_Subtree_List
196 (Container
: in out Tree
;
197 First
: Count_Type
'Base;
198 Last
: Count_Type
'Base;
200 Before
: Count_Type
'Base);
202 procedure Splice_Children
203 (Container
: in out Tree
;
204 Target_Parent
: Count_Type
;
205 Before
: Count_Type
'Base;
206 Source_Parent
: Count_Type
);
208 procedure Splice_Children
209 (Target
: in out Tree
;
210 Target_Parent
: Count_Type
;
211 Before
: Count_Type
'Base;
212 Source
: in out Tree
;
213 Source_Parent
: Count_Type
);
215 procedure Splice_Subtree
216 (Target
: in out Tree
;
218 Before
: Count_Type
'Base;
219 Source
: in out Tree
;
220 Position
: in out Count_Type
); -- source on input, target on output
226 function "=" (Left
, Right
: Tree
) return Boolean is
228 if Left
.Count
/= Right
.Count
then
232 if Left
.Count
= 0 then
236 return Equal_Children
238 Left_Subtree
=> Root_Node
(Left
),
240 Right_Subtree
=> Root_Node
(Right
));
247 procedure Allocate_Node
248 (Container
: in out Tree
;
249 Initialize_Element
: not null access procedure (Index
: Count_Type
);
250 New_Node
: out Count_Type
)
253 if Container
.Free
>= 0 then
254 New_Node
:= Container
.Free
;
255 pragma Assert
(New_Node
in Container
.Elements
'Range);
257 -- We always perform the assignment first, before we change container
258 -- state, in order to defend against exceptions duration assignment.
260 Initialize_Element
(New_Node
);
262 Container
.Free
:= Container
.Nodes
(New_Node
).Next
;
265 -- A negative free store value means that the links of the nodes in
266 -- the free store have not been initialized. In this case, the nodes
267 -- are physically contiguous in the array, starting at the index that
268 -- is the absolute value of the Container.Free, and continuing until
269 -- the end of the array (Nodes'Last).
271 New_Node
:= abs Container
.Free
;
272 pragma Assert
(New_Node
in Container
.Elements
'Range);
274 -- As above, we perform this assignment first, before modifying any
277 Initialize_Element
(New_Node
);
279 Container
.Free
:= Container
.Free
- 1;
281 if abs Container
.Free
> Container
.Capacity
then
286 Initialize_Node
(Container
, New_Node
);
289 procedure Allocate_Node
290 (Container
: in out Tree
;
291 New_Item
: Element_Type
;
292 New_Node
: out Count_Type
)
294 procedure Initialize_Element
(Index
: Count_Type
);
296 procedure Initialize_Element
(Index
: Count_Type
) is
298 Container
.Elements
(Index
) := New_Item
;
299 end Initialize_Element
;
302 Allocate_Node
(Container
, Initialize_Element
'Access, New_Node
);
305 procedure Allocate_Node
306 (Container
: in out Tree
;
307 Stream
: not null access Root_Stream_Type
'Class;
308 New_Node
: out Count_Type
)
310 procedure Initialize_Element
(Index
: Count_Type
);
312 procedure Initialize_Element
(Index
: Count_Type
) is
314 Element_Type
'Read (Stream
, Container
.Elements
(Index
));
315 end Initialize_Element
;
318 Allocate_Node
(Container
, Initialize_Element
'Access, New_Node
);
325 function Ancestor_Find
327 Item
: Element_Type
) return Cursor
332 if Checks
and then Position
= No_Element
then
333 raise Constraint_Error
with "Position cursor has no element";
336 -- AI-0136 says to raise PE if Position equals the root node. This does
337 -- not seem correct, as this value is just the limiting condition of the
338 -- search. For now we omit this check, pending a ruling from the ARG.
341 -- if Checks and then Is_Root (Position) then
342 -- raise Program_Error with "Position cursor designates root";
345 R
:= Root_Node
(Position
.Container
.all);
348 if Position
.Container
.Elements
(N
) = Item
then
349 return Cursor
'(Position.Container, N);
352 N := Position.Container.Nodes (N).Parent;
362 procedure Append_Child
363 (Container : in out Tree;
365 New_Item : Element_Type;
366 Count : Count_Type := 1)
368 Nodes : Tree_Node_Array renames Container.Nodes;
369 First, Last : Count_Type;
372 TC_Check (Container.TC);
374 if Checks and then Parent = No_Element then
375 raise Constraint_Error with "Parent cursor has no element";
378 if Checks and then Parent.Container /= Container'Unrestricted_Access then
379 raise Program_Error with "Parent cursor not in container";
386 if Checks and then Container.Count > Container.Capacity - Count then
388 with "requested count exceeds available storage";
391 if Container.Count = 0 then
392 Initialize_Root (Container);
395 Allocate_Node (Container, New_Item, First);
396 Nodes (First).Parent := Parent.Node;
399 for J in Count_Type'(2) .. Count
loop
400 Allocate_Node
(Container
, New_Item
, Nodes
(Last
).Next
);
401 Nodes
(Nodes
(Last
).Next
).Parent
:= Parent
.Node
;
402 Nodes
(Nodes
(Last
).Next
).Prev
:= Last
;
404 Last
:= Nodes
(Last
).Next
;
408 (Container
=> Container
,
411 Parent
=> Parent
.Node
,
412 Before
=> No_Node
); -- means "insert at end of list"
414 Container
.Count
:= Container
.Count
+ Count
;
421 procedure Assign
(Target
: in out Tree
; Source
: Tree
) is
422 Target_Count
: Count_Type
;
425 if Target
'Address = Source
'Address then
429 if Checks
and then Target
.Capacity
< Source
.Count
then
430 raise Capacity_Error
-- ???
431 with "Target capacity is less than Source count";
434 Target
.Clear
; -- Checks busy bit
436 if Source
.Count
= 0 then
440 Initialize_Root
(Target
);
442 -- Copy_Children returns the number of nodes that it allocates, but it
443 -- does this by incrementing the count value passed in, so we must
444 -- initialize the count before calling Copy_Children.
450 Source_Parent
=> Root_Node
(Source
),
452 Target_Parent
=> Root_Node
(Target
),
453 Count
=> Target_Count
);
455 pragma Assert
(Target_Count
= Source
.Count
);
456 Target
.Count
:= Source
.Count
;
463 function Child_Count
(Parent
: Cursor
) return Count_Type
is
465 if Parent
= No_Element
then
468 elsif Parent
.Container
.Count
= 0 then
469 pragma Assert
(Is_Root
(Parent
));
473 return Child_Count
(Parent
.Container
.all, Parent
.Node
);
479 Parent
: Count_Type
) return Count_Type
481 NN
: Tree_Node_Array
renames Container
.Nodes
;
482 CC
: Children_Type
renames NN
(Parent
).Children
;
485 Node
: Count_Type
'Base;
491 Result
:= Result
+ 1;
492 Node
:= NN
(Node
).Next
;
502 function Child_Depth
(Parent
, Child
: Cursor
) return Count_Type
is
507 if Checks
and then Parent
= No_Element
then
508 raise Constraint_Error
with "Parent cursor has no element";
511 if Checks
and then Child
= No_Element
then
512 raise Constraint_Error
with "Child cursor has no element";
515 if Checks
and then Parent
.Container
/= Child
.Container
then
516 raise Program_Error
with "Parent and Child in different containers";
519 if Parent
.Container
.Count
= 0 then
520 pragma Assert
(Is_Root
(Parent
));
521 pragma Assert
(Child
= Parent
);
527 while N
/= Parent
.Node
loop
528 Result
:= Result
+ 1;
529 N
:= Parent
.Container
.Nodes
(N
).Parent
;
531 if Checks
and then N
< 0 then
532 raise Program_Error
with "Parent is not ancestor of Child";
543 procedure Clear
(Container
: in out Tree
) is
544 Container_Count
: constant Count_Type
:= Container
.Count
;
548 TC_Check
(Container
.TC
);
550 if Container_Count
= 0 then
554 Container
.Count
:= 0;
556 -- Deallocate_Children returns the number of nodes that it deallocates,
557 -- but it does this by incrementing the count value that is passed in,
558 -- so we must first initialize the count return value before calling it.
563 (Container
=> Container
,
564 Subtree
=> Root_Node
(Container
),
567 pragma Assert
(Count
= Container_Count
);
570 ------------------------
571 -- Constant_Reference --
572 ------------------------
574 function Constant_Reference
575 (Container
: aliased Tree
;
576 Position
: Cursor
) return Constant_Reference_Type
579 if Checks
and then Position
.Container
= null then
580 raise Constraint_Error
with
581 "Position cursor has no element";
584 if Checks
and then Position
.Container
/= Container
'Unrestricted_Access
586 raise Program_Error
with
587 "Position cursor designates wrong container";
590 if Checks
and then Position
.Node
= Root_Node
(Container
) then
591 raise Program_Error
with "Position cursor designates root";
594 -- Implement Vet for multiway tree???
595 -- pragma Assert (Vet (Position),
596 -- "Position cursor in Constant_Reference is bad");
599 TC
: constant Tamper_Counts_Access
:=
600 Container
.TC
'Unrestricted_Access;
602 return R
: constant Constant_Reference_Type
:=
603 (Element
=> Container
.Elements
(Position
.Node
)'Unchecked_Access,
604 Control
=> (Controlled
with TC
))
609 end Constant_Reference
;
617 Item
: Element_Type
) return Boolean
620 return Find
(Container
, Item
) /= No_Element
;
629 Capacity
: Count_Type
:= 0) return Tree
631 C
: constant Count_Type
:=
632 (if Capacity
= 0 then Source
.Count
635 if Checks
and then C
< Source
.Count
then
636 raise Capacity_Error
with "Capacity too small";
639 return Target
: Tree
(Capacity
=> C
) do
640 Initialize_Root
(Target
);
642 if Source
.Count
= 0 then
648 Source_Parent
=> Root_Node
(Source
),
650 Target_Parent
=> Root_Node
(Target
),
651 Count
=> Target
.Count
);
653 pragma Assert
(Target
.Count
= Source
.Count
);
661 procedure Copy_Children
663 Source_Parent
: Count_Type
;
664 Target
: in out Tree
;
665 Target_Parent
: Count_Type
;
666 Count
: in out Count_Type
)
668 S_Nodes
: Tree_Node_Array
renames Source
.Nodes
;
669 S_Node
: Tree_Node_Type
renames S_Nodes
(Source_Parent
);
671 T_Nodes
: Tree_Node_Array
renames Target
.Nodes
;
672 T_Node
: Tree_Node_Type
renames T_Nodes
(Target_Parent
);
674 pragma Assert
(T_Node
.Children
.First
<= 0);
675 pragma Assert
(T_Node
.Children
.Last
<= 0);
677 T_CC
: Children_Type
;
681 -- We special-case the first allocation, in order to establish the
682 -- representation invariants for type Children_Type.
684 C
:= S_Node
.Children
.First
;
686 if C
<= 0 then -- source parent has no children
694 Target_Parent
=> Target_Parent
,
695 Target_Subtree
=> T_CC
.First
,
698 T_CC
.Last
:= T_CC
.First
;
700 -- The representation invariants for the Children_Type list have been
701 -- established, so we can now copy the remaining children of Source.
703 C
:= S_Nodes
(C
).Next
;
709 Target_Parent
=> Target_Parent
,
710 Target_Subtree
=> T_Nodes
(T_CC
.Last
).Next
,
713 T_Nodes
(T_Nodes
(T_CC
.Last
).Next
).Prev
:= T_CC
.Last
;
714 T_CC
.Last
:= T_Nodes
(T_CC
.Last
).Next
;
716 C
:= S_Nodes
(C
).Next
;
719 -- We add the newly-allocated children to their parent list only after
720 -- the allocation has succeeded, in order to preserve invariants of the
723 T_Node
.Children
:= T_CC
;
730 procedure Copy_Subtree
731 (Target
: in out Tree
;
736 Target_Subtree
: Count_Type
;
737 Target_Count
: Count_Type
;
740 if Checks
and then Parent
= No_Element
then
741 raise Constraint_Error
with "Parent cursor has no element";
744 if Checks
and then Parent
.Container
/= Target
'Unrestricted_Access then
745 raise Program_Error
with "Parent cursor not in container";
748 if Before
/= No_Element
then
749 if Checks
and then Before
.Container
/= Target
'Unrestricted_Access then
750 raise Program_Error
with "Before cursor not in container";
754 Before
.Container
.Nodes
(Before
.Node
).Parent
/= Parent
.Node
756 raise Constraint_Error
with "Before cursor not child of Parent";
760 if Source
= No_Element
then
764 if Checks
and then Is_Root
(Source
) then
765 raise Constraint_Error
with "Source cursor designates root";
768 if Target
.Count
= 0 then
769 Initialize_Root
(Target
);
772 -- Copy_Subtree returns a count of the number of nodes that it
773 -- allocates, but it works by incrementing the value that is passed
774 -- in. We must therefore initialize the count value before calling
780 (Source
=> Source
.Container
.all,
781 Source_Subtree
=> Source
.Node
,
783 Target_Parent
=> Parent
.Node
,
784 Target_Subtree
=> Target_Subtree
,
785 Count
=> Target_Count
);
788 (Container
=> Target
,
789 Subtree
=> Target_Subtree
,
790 Parent
=> Parent
.Node
,
791 Before
=> Before
.Node
);
793 Target
.Count
:= Target
.Count
+ Target_Count
;
796 procedure Copy_Subtree
798 Source_Subtree
: Count_Type
;
799 Target
: in out Tree
;
800 Target_Parent
: Count_Type
;
801 Target_Subtree
: out Count_Type
;
802 Count
: in out Count_Type
)
804 T_Nodes
: Tree_Node_Array
renames Target
.Nodes
;
807 -- First we allocate the root of the target subtree.
810 (Container
=> Target
,
811 New_Item
=> Source
.Elements
(Source_Subtree
),
812 New_Node
=> Target_Subtree
);
814 T_Nodes
(Target_Subtree
).Parent
:= Target_Parent
;
817 -- We now have a new subtree (for the Target tree), containing only a
818 -- copy of the corresponding element in the Source subtree. Next we copy
819 -- the children of the Source subtree as children of the new Target
824 Source_Parent
=> Source_Subtree
,
826 Target_Parent
=> Target_Subtree
,
830 -------------------------
831 -- Deallocate_Children --
832 -------------------------
834 procedure Deallocate_Children
835 (Container
: in out Tree
;
836 Subtree
: Count_Type
;
837 Count
: in out Count_Type
)
839 Nodes
: Tree_Node_Array
renames Container
.Nodes
;
840 Node
: Tree_Node_Type
renames Nodes
(Subtree
); -- parent
841 CC
: Children_Type
renames Node
.Children
;
845 while CC
.First
> 0 loop
847 CC
.First
:= Nodes
(C
).Next
;
849 Deallocate_Subtree
(Container
, C
, Count
);
853 end Deallocate_Children
;
855 ---------------------
856 -- Deallocate_Node --
857 ---------------------
859 procedure Deallocate_Node
860 (Container
: in out Tree
;
863 NN
: Tree_Node_Array
renames Container
.Nodes
;
864 pragma Assert
(X
> 0);
865 pragma Assert
(X
<= NN
'Last);
867 N
: Tree_Node_Type
renames NN
(X
);
868 pragma Assert
(N
.Parent
/= X
); -- node is active
871 -- The tree container actually contains two lists: one for the "active"
872 -- nodes that contain elements that have been inserted onto the tree,
873 -- and another for the "inactive" nodes of the free store, from which
874 -- nodes are allocated when a new child is inserted in the tree.
876 -- We desire that merely declaring a tree object should have only
877 -- minimal cost; specially, we want to avoid having to initialize the
878 -- free store (to fill in the links), especially if the capacity of the
879 -- tree object is large.
881 -- The head of the free list is indicated by Container.Free. If its
882 -- value is non-negative, then the free store has been initialized in
883 -- the "normal" way: Container.Free points to the head of the list of
884 -- free (inactive) nodes, and the value 0 means the free list is
885 -- empty. Each node on the free list has been initialized to point to
886 -- the next free node (via its Next component), and the value 0 means
887 -- that this is the last node of the free list.
889 -- If Container.Free is negative, then the links on the free store have
890 -- not been initialized. In this case the link values are implied: the
891 -- free store comprises the components of the node array started with
892 -- the absolute value of Container.Free, and continuing until the end of
893 -- the array (Nodes'Last).
895 -- We prefer to lazy-init the free store (in fact, we would prefer to
896 -- not initialize it at all, because such initialization is an O(n)
897 -- operation). The time when we need to actually initialize the nodes in
898 -- the free store is when the node that becomes inactive is not at the
899 -- end of the active list. The free store would then be discontigous and
900 -- so its nodes would need to be linked in the traditional way.
902 -- It might be possible to perform an optimization here. Suppose that
903 -- the free store can be represented as having two parts: one comprising
904 -- the non-contiguous inactive nodes linked together in the normal way,
905 -- and the other comprising the contiguous inactive nodes (that are not
906 -- linked together, at the end of the nodes array). This would allow us
907 -- to never have to initialize the free store, except in a lazy way as
908 -- nodes become inactive. ???
910 -- When an element is deleted from the list container, its node becomes
911 -- inactive, and so we set its Parent and Prev components to an
912 -- impossible value (the index of the node itself), to indicate that it
913 -- is now inactive. This provides a useful way to detect a dangling
916 N
.Parent
:= X
; -- Node is deallocated (not on active list)
919 if Container
.Free
>= 0 then
920 -- The free store has previously been initialized. All we need to do
921 -- here is link the newly-free'd node onto the free list.
923 N
.Next
:= Container
.Free
;
926 elsif X
+ 1 = abs Container
.Free
then
927 -- The free store has not been initialized, and the node becoming
928 -- inactive immediately precedes the start of the free store. All
929 -- we need to do is move the start of the free store back by one.
931 N
.Next
:= X
; -- Not strictly necessary, but marginally safer
932 Container
.Free
:= Container
.Free
+ 1;
935 -- The free store has not been initialized, and the node becoming
936 -- inactive does not immediately precede the free store. Here we
937 -- first initialize the free store (meaning the links are given
938 -- values in the traditional way), and then link the newly-free'd
939 -- node onto the head of the free store.
941 -- See the comments above for an optimization opportunity. If the
942 -- next link for a node on the free store is negative, then this
943 -- means the remaining nodes on the free store are physically
944 -- contiguous, starting at the absolute value of that index value.
947 Container
.Free
:= abs Container
.Free
;
949 if Container
.Free
> Container
.Capacity
then
953 for J
in Container
.Free
.. Container
.Capacity
- 1 loop
954 NN
(J
).Next
:= J
+ 1;
957 NN
(Container
.Capacity
).Next
:= 0;
960 NN
(X
).Next
:= Container
.Free
;
965 ------------------------
966 -- Deallocate_Subtree --
967 ------------------------
969 procedure Deallocate_Subtree
970 (Container
: in out Tree
;
971 Subtree
: Count_Type
;
972 Count
: in out Count_Type
)
975 Deallocate_Children
(Container
, Subtree
, Count
);
976 Deallocate_Node
(Container
, Subtree
);
978 end Deallocate_Subtree
;
980 ---------------------
981 -- Delete_Children --
982 ---------------------
984 procedure Delete_Children
985 (Container
: in out Tree
;
991 TC_Check
(Container
.TC
);
993 if Checks
and then Parent
= No_Element
then
994 raise Constraint_Error
with "Parent cursor has no element";
997 if Checks
and then Parent
.Container
/= Container
'Unrestricted_Access then
998 raise Program_Error
with "Parent cursor not in container";
1001 if Container
.Count
= 0 then
1002 pragma Assert
(Is_Root
(Parent
));
1006 -- Deallocate_Children returns a count of the number of nodes that it
1007 -- deallocates, but it works by incrementing the value that is passed
1008 -- in. We must therefore initialize the count value before calling
1009 -- Deallocate_Children.
1013 Deallocate_Children
(Container
, Parent
.Node
, Count
);
1014 pragma Assert
(Count
<= Container
.Count
);
1016 Container
.Count
:= Container
.Count
- Count
;
1017 end Delete_Children
;
1023 procedure Delete_Leaf
1024 (Container
: in out Tree
;
1025 Position
: in out Cursor
)
1030 TC_Check
(Container
.TC
);
1032 if Checks
and then Position
= No_Element
then
1033 raise Constraint_Error
with "Position cursor has no element";
1036 if Checks
and then Position
.Container
/= Container
'Unrestricted_Access
1038 raise Program_Error
with "Position cursor not in container";
1041 if Checks
and then Is_Root
(Position
) then
1042 raise Program_Error
with "Position cursor designates root";
1045 if Checks
and then not Is_Leaf
(Position
) then
1046 raise Constraint_Error
with "Position cursor does not designate leaf";
1050 Position
:= No_Element
;
1052 Remove_Subtree
(Container
, X
);
1053 Container
.Count
:= Container
.Count
- 1;
1055 Deallocate_Node
(Container
, X
);
1058 --------------------
1059 -- Delete_Subtree --
1060 --------------------
1062 procedure Delete_Subtree
1063 (Container
: in out Tree
;
1064 Position
: in out Cursor
)
1070 TC_Check
(Container
.TC
);
1072 if Checks
and then Position
= No_Element
then
1073 raise Constraint_Error
with "Position cursor has no element";
1076 if Checks
and then Position
.Container
/= Container
'Unrestricted_Access
1078 raise Program_Error
with "Position cursor not in container";
1081 if Checks
and then Is_Root
(Position
) then
1082 raise Program_Error
with "Position cursor designates root";
1086 Position
:= No_Element
;
1088 Remove_Subtree
(Container
, X
);
1090 -- Deallocate_Subtree returns a count of the number of nodes that it
1091 -- deallocates, but it works by incrementing the value that is passed
1092 -- in. We must therefore initialize the count value before calling
1093 -- Deallocate_Subtree.
1097 Deallocate_Subtree
(Container
, X
, Count
);
1098 pragma Assert
(Count
<= Container
.Count
);
1100 Container
.Count
:= Container
.Count
- Count
;
1107 function Depth
(Position
: Cursor
) return Count_Type
is
1108 Result
: Count_Type
;
1109 N
: Count_Type
'Base;
1112 if Position
= No_Element
then
1116 if Is_Root
(Position
) then
1123 N
:= Position
.Container
.Nodes
(N
).Parent
;
1124 Result
:= Result
+ 1;
1134 function Element
(Position
: Cursor
) return Element_Type
is
1136 if Checks
and then Position
.Container
= null then
1137 raise Constraint_Error
with "Position cursor has no element";
1140 if Checks
and then Position
.Node
= Root_Node
(Position
.Container
.all)
1142 raise Program_Error
with "Position cursor designates root";
1145 return Position
.Container
.Elements
(Position
.Node
);
1148 --------------------
1149 -- Equal_Children --
1150 --------------------
1152 function Equal_Children
1154 Left_Subtree
: Count_Type
;
1156 Right_Subtree
: Count_Type
) return Boolean
1158 L_NN
: Tree_Node_Array
renames Left_Tree
.Nodes
;
1159 R_NN
: Tree_Node_Array
renames Right_Tree
.Nodes
;
1161 Left_Children
: Children_Type
renames L_NN
(Left_Subtree
).Children
;
1162 Right_Children
: Children_Type
renames R_NN
(Right_Subtree
).Children
;
1164 L
, R
: Count_Type
'Base;
1167 if Child_Count
(Left_Tree
, Left_Subtree
)
1168 /= Child_Count
(Right_Tree
, Right_Subtree
)
1173 L
:= Left_Children
.First
;
1174 R
:= Right_Children
.First
;
1176 if not Equal_Subtree
(Left_Tree
, L
, Right_Tree
, R
) then
1191 function Equal_Subtree
1192 (Left_Position
: Cursor
;
1193 Right_Position
: Cursor
) return Boolean
1196 if Checks
and then Left_Position
= No_Element
then
1197 raise Constraint_Error
with "Left cursor has no element";
1200 if Checks
and then Right_Position
= No_Element
then
1201 raise Constraint_Error
with "Right cursor has no element";
1204 if Left_Position
= Right_Position
then
1208 if Is_Root
(Left_Position
) then
1209 if not Is_Root
(Right_Position
) then
1213 if Left_Position
.Container
.Count
= 0 then
1214 return Right_Position
.Container
.Count
= 0;
1217 if Right_Position
.Container
.Count
= 0 then
1221 return Equal_Children
1222 (Left_Tree
=> Left_Position
.Container
.all,
1223 Left_Subtree
=> Left_Position
.Node
,
1224 Right_Tree
=> Right_Position
.Container
.all,
1225 Right_Subtree
=> Right_Position
.Node
);
1228 if Is_Root
(Right_Position
) then
1232 return Equal_Subtree
1233 (Left_Tree
=> Left_Position
.Container
.all,
1234 Left_Subtree
=> Left_Position
.Node
,
1235 Right_Tree
=> Right_Position
.Container
.all,
1236 Right_Subtree
=> Right_Position
.Node
);
1239 function Equal_Subtree
1241 Left_Subtree
: Count_Type
;
1243 Right_Subtree
: Count_Type
) return Boolean
1246 if Left_Tree
.Elements
(Left_Subtree
) /=
1247 Right_Tree
.Elements
(Right_Subtree
)
1252 return Equal_Children
1253 (Left_Tree
=> Left_Tree
,
1254 Left_Subtree
=> Left_Subtree
,
1255 Right_Tree
=> Right_Tree
,
1256 Right_Subtree
=> Right_Subtree
);
1263 procedure Finalize
(Object
: in out Root_Iterator
) is
1265 Unbusy
(Object
.Container
.TC
);
1274 Item
: Element_Type
) return Cursor
1279 if Container
.Count
= 0 then
1283 Node
:= Find_In_Children
(Container
, Root_Node
(Container
), Item
);
1289 return Cursor
'(Container'Unrestricted_Access, Node);
1296 overriding function First (Object : Subtree_Iterator) return Cursor is
1298 if Object.Subtree = Root_Node (Object.Container.all) then
1299 return First_Child (Root (Object.Container.all));
1301 return Cursor'(Object
.Container
, Object
.Subtree
);
1305 overriding
function First
(Object
: Child_Iterator
) return Cursor
is
1307 return First_Child
(Cursor
'(Object.Container, Object.Subtree));
1314 function First_Child (Parent : Cursor) return Cursor is
1315 Node : Count_Type'Base;
1318 if Checks and then Parent = No_Element then
1319 raise Constraint_Error with "Parent cursor has no element";
1322 if Parent.Container.Count = 0 then
1323 pragma Assert (Is_Root (Parent));
1327 Node := Parent.Container.Nodes (Parent.Node).Children.First;
1333 return Cursor'(Parent
.Container
, Node
);
1336 -------------------------
1337 -- First_Child_Element --
1338 -------------------------
1340 function First_Child_Element
(Parent
: Cursor
) return Element_Type
is
1342 return Element
(First_Child
(Parent
));
1343 end First_Child_Element
;
1345 ----------------------
1346 -- Find_In_Children --
1347 ----------------------
1349 function Find_In_Children
1351 Subtree
: Count_Type
;
1352 Item
: Element_Type
) return Count_Type
1354 N
: Count_Type
'Base;
1355 Result
: Count_Type
;
1358 N
:= Container
.Nodes
(Subtree
).Children
.First
;
1360 Result
:= Find_In_Subtree
(Container
, N
, Item
);
1366 N
:= Container
.Nodes
(N
).Next
;
1370 end Find_In_Children
;
1372 ---------------------
1373 -- Find_In_Subtree --
1374 ---------------------
1376 function Find_In_Subtree
1378 Item
: Element_Type
) return Cursor
1380 Result
: Count_Type
;
1383 if Checks
and then Position
= No_Element
then
1384 raise Constraint_Error
with "Position cursor has no element";
1387 -- Commented-out pending ruling by ARG. ???
1389 -- if Checks and then
1390 -- Position.Container /= Container'Unrestricted_Access
1392 -- raise Program_Error with "Position cursor not in container";
1395 if Position
.Container
.Count
= 0 then
1396 pragma Assert
(Is_Root
(Position
));
1400 if Is_Root
(Position
) then
1401 Result
:= Find_In_Children
1402 (Container
=> Position
.Container
.all,
1403 Subtree
=> Position
.Node
,
1407 Result
:= Find_In_Subtree
1408 (Container
=> Position
.Container
.all,
1409 Subtree
=> Position
.Node
,
1417 return Cursor
'(Position.Container, Result);
1418 end Find_In_Subtree;
1420 function Find_In_Subtree
1422 Subtree : Count_Type;
1423 Item : Element_Type) return Count_Type
1426 if Container.Elements (Subtree) = Item then
1430 return Find_In_Children (Container, Subtree, Item);
1431 end Find_In_Subtree;
1433 ------------------------
1434 -- Get_Element_Access --
1435 ------------------------
1437 function Get_Element_Access
1438 (Position : Cursor) return not null Element_Access is
1440 return Position.Container.Elements (Position.Node)'Access;
1441 end Get_Element_Access;
1447 function Has_Element (Position : Cursor) return Boolean is
1449 if Position = No_Element then
1453 return Position.Node /= Root_Node (Position.Container.all);
1456 ---------------------
1457 -- Initialize_Node --
1458 ---------------------
1460 procedure Initialize_Node
1461 (Container : in out Tree;
1465 Container.Nodes (Index) :=
1469 Children => (others => 0));
1470 end Initialize_Node;
1472 ---------------------
1473 -- Initialize_Root --
1474 ---------------------
1476 procedure Initialize_Root (Container : in out Tree) is
1478 Initialize_Node (Container, Root_Node (Container));
1479 end Initialize_Root;
1485 procedure Insert_Child
1486 (Container : in out Tree;
1489 New_Item : Element_Type;
1490 Count : Count_Type := 1)
1495 Insert_Child (Container, Parent, Before, New_Item, Position, Count);
1498 procedure Insert_Child
1499 (Container : in out Tree;
1502 New_Item : Element_Type;
1503 Position : out Cursor;
1504 Count : Count_Type := 1)
1506 Nodes : Tree_Node_Array renames Container.Nodes;
1511 TC_Check (Container.TC);
1513 if Checks and then Parent = No_Element then
1514 raise Constraint_Error with "Parent cursor has no element";
1517 if Checks and then Parent.Container /= Container'Unrestricted_Access then
1518 raise Program_Error with "Parent cursor not in container";
1521 if Before /= No_Element then
1522 if Checks and then Before.Container /= Container'Unrestricted_Access
1524 raise Program_Error with "Before cursor not in container";
1528 Before.Container.Nodes (Before.Node).Parent /= Parent.Node
1530 raise Constraint_Error with "Parent cursor not parent of Before";
1535 Position := No_Element; -- Need ruling from ARG ???
1539 if Checks and then Container.Count > Container.Capacity - Count then
1540 raise Capacity_Error
1541 with "requested count exceeds available storage";
1544 if Container.Count = 0 then
1545 Initialize_Root (Container);
1548 Allocate_Node (Container, New_Item, First);
1549 Nodes (First).Parent := Parent.Node;
1552 for J in Count_Type'(2) .. Count
loop
1553 Allocate_Node
(Container
, New_Item
, Nodes
(Last
).Next
);
1554 Nodes
(Nodes
(Last
).Next
).Parent
:= Parent
.Node
;
1555 Nodes
(Nodes
(Last
).Next
).Prev
:= Last
;
1557 Last
:= Nodes
(Last
).Next
;
1561 (Container
=> Container
,
1564 Parent
=> Parent
.Node
,
1565 Before
=> Before
.Node
);
1567 Container
.Count
:= Container
.Count
+ Count
;
1569 Position
:= Cursor
'(Parent.Container, First);
1572 procedure Insert_Child
1573 (Container : in out Tree;
1576 Position : out Cursor;
1577 Count : Count_Type := 1)
1579 Nodes : Tree_Node_Array renames Container.Nodes;
1583 pragma Warnings (Off);
1584 Default_Initialized_Item : Element_Type;
1585 pragma Unmodified (Default_Initialized_Item);
1586 -- OK to reference, see below
1589 TC_Check (Container.TC);
1591 if Checks and then Parent = No_Element then
1592 raise Constraint_Error with "Parent cursor has no element";
1595 if Checks and then Parent.Container /= Container'Unrestricted_Access then
1596 raise Program_Error with "Parent cursor not in container";
1599 if Before /= No_Element then
1600 if Checks and then Before.Container /= Container'Unrestricted_Access
1602 raise Program_Error with "Before cursor not in container";
1606 Before.Container.Nodes (Before.Node).Parent /= Parent.Node
1608 raise Constraint_Error with "Parent cursor not parent of Before";
1613 Position := No_Element; -- Need ruling from ARG ???
1617 if Checks and then Container.Count > Container.Capacity - Count then
1618 raise Capacity_Error
1619 with "requested count exceeds available storage";
1622 if Container.Count = 0 then
1623 Initialize_Root (Container);
1626 -- There is no explicit element provided, but in an instance the element
1627 -- type may be a scalar with a Default_Value aspect, or a composite
1628 -- type with such a scalar component, or components with default
1629 -- initialization, so insert the specified number of possibly
1630 -- initialized elements at the given position.
1632 Allocate_Node (Container, Default_Initialized_Item, First);
1633 Nodes (First).Parent := Parent.Node;
1636 for J in Count_Type'(2) .. Count
loop
1638 (Container
, Default_Initialized_Item
, Nodes
(Last
).Next
);
1639 Nodes
(Nodes
(Last
).Next
).Parent
:= Parent
.Node
;
1640 Nodes
(Nodes
(Last
).Next
).Prev
:= Last
;
1642 Last
:= Nodes
(Last
).Next
;
1646 (Container
=> Container
,
1649 Parent
=> Parent
.Node
,
1650 Before
=> Before
.Node
);
1652 Container
.Count
:= Container
.Count
+ Count
;
1654 Position
:= Cursor
'(Parent.Container, First);
1655 pragma Warnings (On);
1658 -------------------------
1659 -- Insert_Subtree_List --
1660 -------------------------
1662 procedure Insert_Subtree_List
1663 (Container : in out Tree;
1664 First : Count_Type'Base;
1665 Last : Count_Type'Base;
1666 Parent : Count_Type;
1667 Before : Count_Type'Base)
1669 NN : Tree_Node_Array renames Container.Nodes;
1670 N : Tree_Node_Type renames NN (Parent);
1671 CC : Children_Type renames N.Children;
1674 -- This is a simple utility operation to insert a list of nodes
1675 -- (First..Last) as children of Parent. The Before node specifies where
1676 -- the new children should be inserted relative to existing children.
1679 pragma Assert (Last <= 0);
1683 pragma Assert (Last > 0);
1684 pragma Assert (Before <= 0 or else NN (Before).Parent = Parent);
1686 if CC.First <= 0 then -- no existing children
1688 NN (CC.First).Prev := 0;
1690 NN (CC.Last).Next := 0;
1692 elsif Before <= 0 then -- means "insert after existing nodes"
1693 NN (CC.Last).Next := First;
1694 NN (First).Prev := CC.Last;
1696 NN (CC.Last).Next := 0;
1698 elsif Before = CC.First then
1699 NN (Last).Next := CC.First;
1700 NN (CC.First).Prev := Last;
1702 NN (CC.First).Prev := 0;
1705 NN (NN (Before).Prev).Next := First;
1706 NN (First).Prev := NN (Before).Prev;
1707 NN (Last).Next := Before;
1708 NN (Before).Prev := Last;
1710 end Insert_Subtree_List;
1712 -------------------------
1713 -- Insert_Subtree_Node --
1714 -------------------------
1716 procedure Insert_Subtree_Node
1717 (Container : in out Tree;
1718 Subtree : Count_Type'Base;
1719 Parent : Count_Type;
1720 Before : Count_Type'Base)
1723 -- This is a simple wrapper operation to insert a single child into the
1724 -- Parent's children list.
1727 (Container => Container,
1732 end Insert_Subtree_Node;
1738 function Is_Empty (Container : Tree) return Boolean is
1740 return Container.Count = 0;
1747 function Is_Leaf (Position : Cursor) return Boolean is
1749 if Position = No_Element then
1753 if Position.Container.Count = 0 then
1754 pragma Assert (Is_Root (Position));
1758 return Position.Container.Nodes (Position.Node).Children.First <= 0;
1765 function Is_Reachable
1767 From, To : Count_Type) return Boolean
1769 Idx : Count_Type'Base := From;
1776 Idx := Container.Nodes (Idx).Parent;
1786 function Is_Root (Position : Cursor) return Boolean is
1789 (if Position.Container = null then False
1790 else Position.Node = Root_Node (Position.Container.all));
1799 Process : not null access procedure (Position : Cursor))
1801 Busy : With_Busy (Container.TC'Unrestricted_Access);
1803 if Container.Count = 0 then
1808 (Container => Container,
1809 Subtree => Root_Node (Container),
1810 Process => Process);
1813 function Iterate (Container : Tree)
1814 return Tree_Iterator_Interfaces.Forward_Iterator'Class
1817 return Iterate_Subtree (Root (Container));
1820 ----------------------
1821 -- Iterate_Children --
1822 ----------------------
1824 procedure Iterate_Children
1826 Process : not null access procedure (Position : Cursor))
1829 if Checks and then Parent = No_Element then
1830 raise Constraint_Error with "Parent cursor has no element";
1833 if Parent.Container.Count = 0 then
1834 pragma Assert (Is_Root (Parent));
1840 NN : Tree_Node_Array renames Parent.Container.Nodes;
1841 Busy : With_Busy (Parent.Container.TC'Unrestricted_Access);
1844 C := NN (Parent.Node).Children.First;
1846 Process (Cursor'(Parent
.Container
, Node
=> C
));
1850 end Iterate_Children
;
1852 procedure Iterate_Children
1854 Subtree
: Count_Type
;
1855 Process
: not null access procedure (Position
: Cursor
))
1857 NN
: Tree_Node_Array
renames Container
.Nodes
;
1858 N
: Tree_Node_Type
renames NN
(Subtree
);
1862 -- This is a helper function to recursively iterate over all the nodes
1863 -- in a subtree, in depth-first fashion. This particular helper just
1864 -- visits the children of this subtree, not the root of the subtree
1865 -- itself. This is useful when starting from the ultimate root of the
1866 -- entire tree (see Iterate), as that root does not have an element.
1868 C
:= N
.Children
.First
;
1870 Iterate_Subtree
(Container
, C
, Process
);
1873 end Iterate_Children
;
1875 function Iterate_Children
1878 return Tree_Iterator_Interfaces
.Reversible_Iterator
'Class
1880 C
: constant Tree_Access
:= Container
'Unrestricted_Access;
1882 if Checks
and then Parent
= No_Element
then
1883 raise Constraint_Error
with "Parent cursor has no element";
1886 if Checks
and then Parent
.Container
/= C
then
1887 raise Program_Error
with "Parent cursor not in container";
1890 return It
: constant Child_Iterator
:=
1891 Child_Iterator
'(Limited_Controlled with
1893 Subtree => Parent.Node)
1897 end Iterate_Children;
1899 ---------------------
1900 -- Iterate_Subtree --
1901 ---------------------
1903 function Iterate_Subtree
1905 return Tree_Iterator_Interfaces.Forward_Iterator'Class
1907 C : constant Tree_Access := Position.Container;
1909 if Checks and then Position = No_Element then
1910 raise Constraint_Error with "Position cursor has no element";
1913 -- Implement Vet for multiway trees???
1914 -- pragma Assert (Vet (Position), "bad subtree cursor");
1916 return It : constant Subtree_Iterator :=
1917 (Limited_Controlled with
1919 Subtree => Position.Node)
1923 end Iterate_Subtree;
1925 procedure Iterate_Subtree
1927 Process : not null access procedure (Position : Cursor))
1930 if Checks and then Position = No_Element then
1931 raise Constraint_Error with "Position cursor has no element";
1934 if Position.Container.Count = 0 then
1935 pragma Assert (Is_Root (Position));
1940 T : Tree renames Position.Container.all;
1941 Busy : With_Busy (T.TC'Unrestricted_Access);
1943 if Is_Root (Position) then
1944 Iterate_Children (T, Position.Node, Process);
1946 Iterate_Subtree (T, Position.Node, Process);
1949 end Iterate_Subtree;
1951 procedure Iterate_Subtree
1953 Subtree : Count_Type;
1954 Process : not null access procedure (Position : Cursor))
1957 -- This is a helper function to recursively iterate over all the nodes
1958 -- in a subtree, in depth-first fashion. It first visits the root of the
1959 -- subtree, then visits its children.
1961 Process (Cursor'(Container
'Unrestricted_Access, Subtree
));
1962 Iterate_Children
(Container
, Subtree
, Process
);
1963 end Iterate_Subtree
;
1969 overriding
function Last
(Object
: Child_Iterator
) return Cursor
is
1971 return Last_Child
(Cursor
'(Object.Container, Object.Subtree));
1978 function Last_Child (Parent : Cursor) return Cursor is
1979 Node : Count_Type'Base;
1982 if Checks and then Parent = No_Element then
1983 raise Constraint_Error with "Parent cursor has no element";
1986 if Parent.Container.Count = 0 then
1987 pragma Assert (Is_Root (Parent));
1991 Node := Parent.Container.Nodes (Parent.Node).Children.Last;
1997 return Cursor'(Parent
.Container
, Node
);
2000 ------------------------
2001 -- Last_Child_Element --
2002 ------------------------
2004 function Last_Child_Element
(Parent
: Cursor
) return Element_Type
is
2006 return Element
(Last_Child
(Parent
));
2007 end Last_Child_Element
;
2013 procedure Move
(Target
: in out Tree
; Source
: in out Tree
) is
2015 if Target
'Address = Source
'Address then
2019 TC_Check
(Source
.TC
);
2021 Target
.Assign
(Source
);
2029 overriding
function Next
2030 (Object
: Subtree_Iterator
;
2031 Position
: Cursor
) return Cursor
2034 if Position
.Container
= null then
2038 if Checks
and then Position
.Container
/= Object
.Container
then
2039 raise Program_Error
with
2040 "Position cursor of Next designates wrong tree";
2043 pragma Assert
(Object
.Container
.Count
> 0);
2044 pragma Assert
(Position
.Node
/= Root_Node
(Object
.Container
.all));
2047 Nodes
: Tree_Node_Array
renames Object
.Container
.Nodes
;
2051 Node
:= Position
.Node
;
2053 if Nodes
(Node
).Children
.First
> 0 then
2054 return Cursor
'(Object.Container, Nodes (Node).Children.First);
2057 while Node /= Object.Subtree loop
2058 if Nodes (Node).Next > 0 then
2059 return Cursor'(Object
.Container
, Nodes
(Node
).Next
);
2062 Node
:= Nodes
(Node
).Parent
;
2069 overriding
function Next
2070 (Object
: Child_Iterator
;
2071 Position
: Cursor
) return Cursor
2074 if Position
.Container
= null then
2078 if Checks
and then Position
.Container
/= Object
.Container
then
2079 raise Program_Error
with
2080 "Position cursor of Next designates wrong tree";
2083 pragma Assert
(Object
.Container
.Count
> 0);
2084 pragma Assert
(Position
.Node
/= Root_Node
(Object
.Container
.all));
2086 return Next_Sibling
(Position
);
2093 function Next_Sibling
(Position
: Cursor
) return Cursor
is
2095 if Position
= No_Element
then
2099 if Position
.Container
.Count
= 0 then
2100 pragma Assert
(Is_Root
(Position
));
2105 T
: Tree
renames Position
.Container
.all;
2106 NN
: Tree_Node_Array
renames T
.Nodes
;
2107 N
: Tree_Node_Type
renames NN
(Position
.Node
);
2114 return Cursor
'(Position.Container, N.Next);
2118 procedure Next_Sibling (Position : in out Cursor) is
2120 Position := Next_Sibling (Position);
2127 function Node_Count (Container : Tree) return Count_Type is
2129 -- Container.Count is the number of nodes we have actually allocated. We
2130 -- cache the value specifically so this Node_Count operation can execute
2131 -- in O(1) time, which makes it behave similarly to how the Length
2132 -- selector function behaves for other containers.
2134 -- The cached node count value only describes the nodes we have
2135 -- allocated; the root node itself is not included in that count. The
2136 -- Node_Count operation returns a value that includes the root node
2137 -- (because the RM says so), so we must add 1 to our cached value.
2139 return 1 + Container.Count;
2146 function Parent (Position : Cursor) return Cursor is
2148 if Position = No_Element then
2152 if Position.Container.Count = 0 then
2153 pragma Assert (Is_Root (Position));
2158 T : Tree renames Position.Container.all;
2159 NN : Tree_Node_Array renames T.Nodes;
2160 N : Tree_Node_Type renames NN (Position.Node);
2163 if N.Parent < 0 then
2164 pragma Assert (Position.Node = Root_Node (T));
2168 return Cursor'(Position
.Container
, N
.Parent
);
2176 procedure Prepend_Child
2177 (Container
: in out Tree
;
2179 New_Item
: Element_Type
;
2180 Count
: Count_Type
:= 1)
2182 Nodes
: Tree_Node_Array
renames Container
.Nodes
;
2183 First
, Last
: Count_Type
;
2186 TC_Check
(Container
.TC
);
2188 if Checks
and then Parent
= No_Element
then
2189 raise Constraint_Error
with "Parent cursor has no element";
2192 if Checks
and then Parent
.Container
/= Container
'Unrestricted_Access then
2193 raise Program_Error
with "Parent cursor not in container";
2200 if Checks
and then Container
.Count
> Container
.Capacity
- Count
then
2201 raise Capacity_Error
2202 with "requested count exceeds available storage";
2205 if Container
.Count
= 0 then
2206 Initialize_Root
(Container
);
2209 Allocate_Node
(Container
, New_Item
, First
);
2210 Nodes
(First
).Parent
:= Parent
.Node
;
2213 for J
in Count_Type
'(2) .. Count loop
2214 Allocate_Node (Container, New_Item, Nodes (Last).Next);
2215 Nodes (Nodes (Last).Next).Parent := Parent.Node;
2216 Nodes (Nodes (Last).Next).Prev := Last;
2218 Last := Nodes (Last).Next;
2222 (Container => Container,
2225 Parent => Parent.Node,
2226 Before => Nodes (Parent.Node).Children.First);
2228 Container.Count := Container.Count + Count;
2235 overriding function Previous
2236 (Object : Child_Iterator;
2237 Position : Cursor) return Cursor
2240 if Position.Container = null then
2244 if Checks and then Position.Container /= Object.Container then
2245 raise Program_Error with
2246 "Position cursor of Previous designates wrong tree";
2249 return Previous_Sibling (Position);
2252 ----------------------
2253 -- Previous_Sibling --
2254 ----------------------
2256 function Previous_Sibling (Position : Cursor) return Cursor is
2258 if Position = No_Element then
2262 if Position.Container.Count = 0 then
2263 pragma Assert (Is_Root (Position));
2268 T : Tree renames Position.Container.all;
2269 NN : Tree_Node_Array renames T.Nodes;
2270 N : Tree_Node_Type renames NN (Position.Node);
2277 return Cursor'(Position
.Container
, N
.Prev
);
2279 end Previous_Sibling
;
2281 procedure Previous_Sibling
(Position
: in out Cursor
) is
2283 Position
:= Previous_Sibling
(Position
);
2284 end Previous_Sibling
;
2286 ----------------------
2287 -- Pseudo_Reference --
2288 ----------------------
2290 function Pseudo_Reference
2291 (Container
: aliased Tree
'Class) return Reference_Control_Type
2293 TC
: constant Tamper_Counts_Access
:= Container
.TC
'Unrestricted_Access;
2295 return R
: constant Reference_Control_Type
:= (Controlled
with TC
) do
2298 end Pseudo_Reference
;
2304 procedure Query_Element
2306 Process
: not null access procedure (Element
: Element_Type
))
2309 if Checks
and then Position
= No_Element
then
2310 raise Constraint_Error
with "Position cursor has no element";
2313 if Checks
and then Is_Root
(Position
) then
2314 raise Program_Error
with "Position cursor designates root";
2318 T
: Tree
renames Position
.Container
.all'Unrestricted_Access.all;
2319 Lock
: With_Lock
(T
.TC
'Unrestricted_Access);
2321 Process
(Element
=> T
.Elements
(Position
.Node
));
2330 (S
: in out Ada
.Strings
.Text_Buffers
.Root_Buffer_Type
'Class; V
: Tree
)
2332 use System
.Put_Images
;
2334 procedure Rec
(Position
: Cursor
);
2335 -- Recursive routine operating on cursors
2337 procedure Rec
(Position
: Cursor
) is
2338 First_Time
: Boolean := True;
2342 for X
in Iterate_Children
(V
, Position
) loop
2344 First_Time
:= False;
2349 Element_Type
'Put_Image (S
, Element
(X
));
2350 if Child_Count
(X
) > 0 then
2351 Simple_Array_Between
(S
);
2360 if First_Child
(Root
(V
)) = No_Element
then
2364 Rec
(First_Child
(Root
(V
)));
2373 (Stream
: not null access Root_Stream_Type
'Class;
2374 Container
: out Tree
)
2376 procedure Read_Children
(Subtree
: Count_Type
);
2378 function Read_Subtree
2379 (Parent
: Count_Type
) return Count_Type
;
2381 NN
: Tree_Node_Array
renames Container
.Nodes
;
2383 Total_Count
: Count_Type
'Base;
2384 -- Value read from the stream that says how many elements follow
2386 Read_Count
: Count_Type
'Base;
2387 -- Actual number of elements read from the stream
2393 procedure Read_Children
(Subtree
: Count_Type
) is
2394 Count
: Count_Type
'Base;
2395 -- number of child subtrees
2400 Count_Type
'Read (Stream
, Count
);
2402 if Checks
and then Count
< 0 then
2403 raise Program_Error
with "attempt to read from corrupt stream";
2410 CC
.First
:= Read_Subtree
(Parent
=> Subtree
);
2411 CC
.Last
:= CC
.First
;
2413 for J
in Count_Type
'(2) .. Count loop
2414 NN (CC.Last).Next := Read_Subtree (Parent => Subtree);
2415 NN (NN (CC.Last).Next).Prev := CC.Last;
2416 CC.Last := NN (CC.Last).Next;
2419 -- Now that the allocation and reads have completed successfully, it
2420 -- is safe to link the children to their parent.
2422 NN (Subtree).Children := CC;
2429 function Read_Subtree
2430 (Parent : Count_Type) return Count_Type
2432 Subtree : Count_Type;
2435 Allocate_Node (Container, Stream, Subtree);
2436 Container.Nodes (Subtree).Parent := Parent;
2438 Read_Count := Read_Count + 1;
2440 Read_Children (Subtree);
2445 -- Start of processing for Read
2448 Container.Clear; -- checks busy bit
2450 Count_Type'Read (Stream, Total_Count);
2452 if Checks and then Total_Count < 0 then
2453 raise Program_Error with "attempt to read from corrupt stream";
2456 if Total_Count = 0 then
2460 if Checks and then Total_Count > Container.Capacity then
2461 raise Capacity_Error -- ???
2462 with "node count in stream exceeds container capacity";
2465 Initialize_Root (Container);
2469 Read_Children (Root_Node (Container));
2471 if Checks and then Read_Count /= Total_Count then
2472 raise Program_Error with "attempt to read from corrupt stream";
2475 Container.Count := Total_Count;
2479 (Stream : not null access Root_Stream_Type'Class;
2480 Position : out Cursor)
2483 raise Program_Error with "attempt to read tree cursor from stream";
2487 (Stream : not null access Root_Stream_Type'Class;
2488 Item : out Reference_Type)
2491 raise Program_Error with "attempt to stream reference";
2495 (Stream : not null access Root_Stream_Type'Class;
2496 Item : out Constant_Reference_Type)
2499 raise Program_Error with "attempt to stream reference";
2507 (Container : aliased in out Tree;
2508 Position : Cursor) return Reference_Type
2511 if Checks and then Position.Container = null then
2512 raise Constraint_Error with
2513 "Position cursor has no element";
2516 if Checks and then Position.Container /= Container'Unrestricted_Access
2518 raise Program_Error with
2519 "Position cursor designates wrong container";
2522 if Checks and then Position.Node = Root_Node (Container) then
2523 raise Program_Error with "Position cursor designates root";
2526 -- Implement Vet for multiway tree???
2527 -- pragma Assert (Vet (Position),
2528 -- "Position cursor in Constant_Reference is bad");
2531 TC : constant Tamper_Counts_Access :=
2532 Container.TC'Unrestricted_Access;
2534 return R : constant Reference_Type :=
2535 (Element => Container.Elements (Position.Node)'Unchecked_Access,
2536 Control => (Controlled with TC))
2543 --------------------
2544 -- Remove_Subtree --
2545 --------------------
2547 procedure Remove_Subtree
2548 (Container : in out Tree;
2549 Subtree : Count_Type)
2551 NN : Tree_Node_Array renames Container.Nodes;
2552 N : Tree_Node_Type renames NN (Subtree);
2553 CC : Children_Type renames NN (N.Parent).Children;
2556 -- This is a utility operation to remove a subtree node from its
2557 -- parent's list of children.
2559 if CC.First = Subtree then
2560 pragma Assert (N.Prev <= 0);
2562 if CC.Last = Subtree then
2563 pragma Assert (N.Next <= 0);
2569 NN (CC.First).Prev := 0;
2572 elsif CC.Last = Subtree then
2573 pragma Assert (N.Next <= 0);
2575 NN (CC.Last).Next := 0;
2578 NN (N.Prev).Next := N.Next;
2579 NN (N.Next).Prev := N.Prev;
2583 ----------------------
2584 -- Replace_Element --
2585 ----------------------
2587 procedure Replace_Element
2588 (Container : in out Tree;
2590 New_Item : Element_Type)
2593 TE_Check (Container.TC);
2595 if Checks and then Position = No_Element then
2596 raise Constraint_Error with "Position cursor has no element";
2599 if Checks and then Position.Container /= Container'Unrestricted_Access
2601 raise Program_Error with "Position cursor not in container";
2604 if Checks and then Is_Root (Position) then
2605 raise Program_Error with "Position cursor designates root";
2608 Container.Elements (Position.Node) := New_Item;
2609 end Replace_Element;
2611 ------------------------------
2612 -- Reverse_Iterate_Children --
2613 ------------------------------
2615 procedure Reverse_Iterate_Children
2617 Process : not null access procedure (Position : Cursor))
2620 if Checks and then Parent = No_Element then
2621 raise Constraint_Error with "Parent cursor has no element";
2624 if Parent.Container.Count = 0 then
2625 pragma Assert (Is_Root (Parent));
2630 NN : Tree_Node_Array renames Parent.Container.Nodes;
2631 Busy : With_Busy (Parent.Container.TC'Unrestricted_Access);
2635 C := NN (Parent.Node).Children.Last;
2637 Process (Cursor'(Parent
.Container
, Node
=> C
));
2641 end Reverse_Iterate_Children
;
2647 function Root
(Container
: Tree
) return Cursor
is
2649 return (Container
'Unrestricted_Access, Root_Node
(Container
));
2656 function Root_Node
(Container
: Tree
) return Count_Type
is
2657 pragma Unreferenced
(Container
);
2663 ---------------------
2664 -- Splice_Children --
2665 ---------------------
2667 procedure Splice_Children
2668 (Target
: in out Tree
;
2669 Target_Parent
: Cursor
;
2671 Source
: in out Tree
;
2672 Source_Parent
: Cursor
)
2675 TC_Check
(Target
.TC
);
2676 TC_Check
(Source
.TC
);
2678 if Checks
and then Target_Parent
= No_Element
then
2679 raise Constraint_Error
with "Target_Parent cursor has no element";
2682 if Checks
and then Target_Parent
.Container
/= Target
'Unrestricted_Access
2685 with "Target_Parent cursor not in Target container";
2688 if Before
/= No_Element
then
2689 if Checks
and then Before
.Container
/= Target
'Unrestricted_Access then
2691 with "Before cursor not in Target container";
2695 Target
.Nodes
(Before
.Node
).Parent
/= Target_Parent
.Node
2697 raise Constraint_Error
2698 with "Before cursor not child of Target_Parent";
2702 if Checks
and then Source_Parent
= No_Element
then
2703 raise Constraint_Error
with "Source_Parent cursor has no element";
2706 if Checks
and then Source_Parent
.Container
/= Source
'Unrestricted_Access
2709 with "Source_Parent cursor not in Source container";
2712 if Source
.Count
= 0 then
2713 pragma Assert
(Is_Root
(Source_Parent
));
2717 if Target
'Address = Source
'Address then
2718 if Target_Parent
= Source_Parent
then
2722 if Checks
and then Is_Reachable
(Container
=> Target
,
2723 From
=> Target_Parent
.Node
,
2724 To
=> Source_Parent
.Node
)
2726 raise Constraint_Error
2727 with "Source_Parent is ancestor of Target_Parent";
2731 (Container
=> Target
,
2732 Target_Parent
=> Target_Parent
.Node
,
2733 Before
=> Before
.Node
,
2734 Source_Parent
=> Source_Parent
.Node
);
2739 if Target
.Count
= 0 then
2740 Initialize_Root
(Target
);
2745 Target_Parent
=> Target_Parent
.Node
,
2746 Before
=> Before
.Node
,
2748 Source_Parent
=> Source_Parent
.Node
);
2749 end Splice_Children
;
2751 procedure Splice_Children
2752 (Container
: in out Tree
;
2753 Target_Parent
: Cursor
;
2755 Source_Parent
: Cursor
)
2758 TC_Check
(Container
.TC
);
2760 if Checks
and then Target_Parent
= No_Element
then
2761 raise Constraint_Error
with "Target_Parent cursor has no element";
2765 Target_Parent
.Container
/= Container
'Unrestricted_Access
2768 with "Target_Parent cursor not in container";
2771 if Before
/= No_Element
then
2772 if Checks
and then Before
.Container
/= Container
'Unrestricted_Access
2775 with "Before cursor not in container";
2779 Container
.Nodes
(Before
.Node
).Parent
/= Target_Parent
.Node
2781 raise Constraint_Error
2782 with "Before cursor not child of Target_Parent";
2786 if Checks
and then Source_Parent
= No_Element
then
2787 raise Constraint_Error
with "Source_Parent cursor has no element";
2791 Source_Parent
.Container
/= Container
'Unrestricted_Access
2794 with "Source_Parent cursor not in container";
2797 if Target_Parent
= Source_Parent
then
2801 pragma Assert
(Container
.Count
> 0);
2803 if Checks
and then Is_Reachable
(Container
=> Container
,
2804 From
=> Target_Parent
.Node
,
2805 To
=> Source_Parent
.Node
)
2807 raise Constraint_Error
2808 with "Source_Parent is ancestor of Target_Parent";
2812 (Container
=> Container
,
2813 Target_Parent
=> Target_Parent
.Node
,
2814 Before
=> Before
.Node
,
2815 Source_Parent
=> Source_Parent
.Node
);
2816 end Splice_Children
;
2818 procedure Splice_Children
2819 (Container
: in out Tree
;
2820 Target_Parent
: Count_Type
;
2821 Before
: Count_Type
'Base;
2822 Source_Parent
: Count_Type
)
2824 NN
: Tree_Node_Array
renames Container
.Nodes
;
2825 CC
: constant Children_Type
:= NN
(Source_Parent
).Children
;
2826 C
: Count_Type
'Base;
2829 -- This is a utility operation to remove the children from Source parent
2830 -- and insert them into Target parent.
2832 NN
(Source_Parent
).Children
:= Children_Type
'(others => 0);
2834 -- Fix up the Parent pointers of each child to designate its new Target
2839 NN (C).Parent := Target_Parent;
2844 (Container => Container,
2847 Parent => Target_Parent,
2849 end Splice_Children;
2851 procedure Splice_Children
2852 (Target : in out Tree;
2853 Target_Parent : Count_Type;
2854 Before : Count_Type'Base;
2855 Source : in out Tree;
2856 Source_Parent : Count_Type)
2858 S_NN : Tree_Node_Array renames Source.Nodes;
2859 S_CC : Children_Type renames S_NN (Source_Parent).Children;
2861 Target_Count, Source_Count : Count_Type;
2862 T, S : Count_Type'Base;
2865 -- This is a utility operation to copy the children from the Source
2866 -- parent and insert them as children of the Target parent, and then
2867 -- delete them from the Source. (This is not a true splice operation,
2868 -- but it is the best we can do in a bounded form.) The Before position
2869 -- specifies where among the Target parent's exising children the new
2870 -- children are inserted.
2872 -- Before we attempt the insertion, we must count the sources nodes in
2873 -- order to determine whether the target have enough storage
2874 -- available. Note that calculating this value is an O(n) operation.
2876 -- Here is an optimization opportunity: iterate of each children the
2877 -- source explicitly, and keep a running count of the total number of
2878 -- nodes. Compare the running total to the capacity of the target each
2879 -- pass through the loop. This is more efficient than summing the counts
2880 -- of child subtree (which is what Subtree_Node_Count does) and then
2881 -- comparing that total sum to the target's capacity. ???
2883 -- Here is another possibility. We currently treat the splice as an
2884 -- all-or-nothing proposition: either we can insert all of children of
2885 -- the source, or we raise exception with modifying the target. The
2886 -- price for not causing side-effect is an O(n) determination of the
2887 -- source count. If we are willing to tolerate side-effect, then we
2888 -- could loop over the children of the source, counting that subtree and
2889 -- then immediately inserting it in the target. The issue here is that
2890 -- the test for available storage could fail during some later pass,
2891 -- after children have already been inserted into target. ???
2893 Source_Count := Subtree_Node_Count (Source, Source_Parent) - 1;
2895 if Source_Count = 0 then
2899 if Checks and then Target.Count > Target.Capacity - Source_Count then
2900 raise Capacity_Error -- ???
2901 with "Source count exceeds available storage on Target";
2904 -- Copy_Subtree returns a count of the number of nodes it inserts, but
2905 -- it does this by incrementing the value passed in. Therefore we must
2906 -- initialize the count before calling Copy_Subtree.
2914 Source_Subtree => S,
2916 Target_Parent => Target_Parent,
2917 Target_Subtree => T,
2918 Count => Target_Count);
2921 (Container => Target,
2923 Parent => Target_Parent,
2929 pragma Assert (Target_Count = Source_Count);
2930 Target.Count := Target.Count + Target_Count;
2932 -- As with Copy_Subtree, operation Deallocate_Children returns a count
2933 -- of the number of nodes it deallocates, but it works by incrementing
2934 -- the value passed in. We must therefore initialize the count before
2939 Deallocate_Children (Source, Source_Parent, Source_Count);
2940 pragma Assert (Source_Count = Target_Count);
2942 Source.Count := Source.Count - Source_Count;
2943 end Splice_Children;
2945 --------------------
2946 -- Splice_Subtree --
2947 --------------------
2949 procedure Splice_Subtree
2950 (Target : in out Tree;
2953 Source : in out Tree;
2954 Position : in out Cursor)
2957 TC_Check (Target.TC);
2958 TC_Check (Source.TC);
2960 if Checks and then Parent = No_Element then
2961 raise Constraint_Error with "Parent cursor has no element";
2964 if Checks and then Parent.Container /= Target'Unrestricted_Access then
2965 raise Program_Error with "Parent cursor not in Target container";
2968 if Before /= No_Element then
2969 if Checks and then Before.Container /= Target'Unrestricted_Access then
2970 raise Program_Error with "Before cursor not in Target container";
2973 if Checks and then Target.Nodes (Before.Node).Parent /= Parent.Node
2975 raise Constraint_Error with "Before cursor not child of Parent";
2979 if Checks and then Position = No_Element then
2980 raise Constraint_Error with "Position cursor has no element";
2983 if Checks and then Position.Container /= Source'Unrestricted_Access then
2984 raise Program_Error with "Position cursor not in Source container";
2987 if Checks and then Is_Root (Position) then
2988 raise Program_Error with "Position cursor designates root";
2991 if Target'Address = Source'Address then
2992 if Target.Nodes (Position.Node).Parent = Parent.Node then
2993 if Before = No_Element then
2994 if Target.Nodes (Position.Node).Next <= 0 then -- last child
2998 elsif Position.Node = Before.Node then
3001 elsif Target.Nodes (Position.Node).Next = Before.Node then
3006 if Checks and then Is_Reachable (Container => Target,
3007 From => Parent.Node,
3008 To => Position.Node)
3010 raise Constraint_Error with "Position is ancestor of Parent";
3013 Remove_Subtree (Target, Position.Node);
3015 Target.Nodes (Position.Node).Parent := Parent.Node;
3016 Insert_Subtree_Node (Target, Position.Node, Parent.Node, Before.Node);
3021 if Target.Count = 0 then
3022 Initialize_Root (Target);
3027 Parent => Parent.Node,
3028 Before => Before.Node,
3030 Position => Position.Node); -- modified during call
3032 Position.Container := Target'Unrestricted_Access;
3035 procedure Splice_Subtree
3036 (Container : in out Tree;
3042 TC_Check (Container.TC);
3044 if Checks and then Parent = No_Element then
3045 raise Constraint_Error with "Parent cursor has no element";
3048 if Checks and then Parent.Container /= Container'Unrestricted_Access then
3049 raise Program_Error with "Parent cursor not in container";
3052 if Before /= No_Element then
3053 if Checks and then Before.Container /= Container'Unrestricted_Access
3055 raise Program_Error with "Before cursor not in container";
3058 if Checks and then Container.Nodes (Before.Node).Parent /= Parent.Node
3060 raise Constraint_Error with "Before cursor not child of Parent";
3064 if Checks and then Position = No_Element then
3065 raise Constraint_Error with "Position cursor has no element";
3068 if Checks and then Position.Container /= Container'Unrestricted_Access
3070 raise Program_Error with "Position cursor not in container";
3073 if Checks and then Is_Root (Position) then
3075 -- Should this be PE instead? Need ARG confirmation. ???
3077 raise Constraint_Error with "Position cursor designates root";
3080 if Container.Nodes (Position.Node).Parent = Parent.Node then
3081 if Before = No_Element then
3082 if Container.Nodes (Position.Node).Next <= 0 then -- last child
3086 elsif Position.Node = Before.Node then
3089 elsif Container.Nodes (Position.Node).Next = Before.Node then
3094 if Checks and then Is_Reachable (Container => Container,
3095 From => Parent.Node,
3096 To => Position.Node)
3098 raise Constraint_Error with "Position is ancestor of Parent";
3101 Remove_Subtree (Container, Position.Node);
3102 Container.Nodes (Position.Node).Parent := Parent.Node;
3103 Insert_Subtree_Node (Container, Position.Node, Parent.Node, Before.Node);
3106 procedure Splice_Subtree
3107 (Target : in out Tree;
3108 Parent : Count_Type;
3109 Before : Count_Type'Base;
3110 Source : in out Tree;
3111 Position : in out Count_Type) -- Source on input, Target on output
3113 Source_Count : Count_Type := Subtree_Node_Count (Source, Position);
3114 pragma Assert (Source_Count >= 1);
3116 Target_Subtree : Count_Type;
3117 Target_Count : Count_Type;
3120 -- This is a utility operation to do the heavy lifting associated with
3121 -- splicing a subtree from one tree to another. Note that "splicing"
3122 -- is a bit of a misnomer here in the case of a bounded tree, because
3123 -- the elements must be copied from the source to the target.
3125 if Checks and then Target.Count > Target.Capacity - Source_Count then
3126 raise Capacity_Error -- ???
3127 with "Source count exceeds available storage on Target";
3130 -- Copy_Subtree returns a count of the number of nodes it inserts, but
3131 -- it does this by incrementing the value passed in. Therefore we must
3132 -- initialize the count before calling Copy_Subtree.
3138 Source_Subtree => Position,
3140 Target_Parent => Parent,
3141 Target_Subtree => Target_Subtree,
3142 Count => Target_Count);
3144 pragma Assert (Target_Count = Source_Count);
3146 -- Now link the newly-allocated subtree into the target.
3149 (Container => Target,
3150 Subtree => Target_Subtree,
3154 Target.Count := Target.Count + Target_Count;
3156 -- The manipulation of the Target container is complete. Now we remove
3157 -- the subtree from the Source container.
3159 Remove_Subtree (Source, Position); -- unlink the subtree
3161 -- As with Copy_Subtree, operation Deallocate_Subtree returns a count of
3162 -- the number of nodes it deallocates, but it works by incrementing the
3163 -- value passed in. We must therefore initialize the count before
3168 Deallocate_Subtree (Source, Position, Source_Count);
3169 pragma Assert (Source_Count = Target_Count);
3171 Source.Count := Source.Count - Source_Count;
3173 Position := Target_Subtree;
3176 ------------------------
3177 -- Subtree_Node_Count --
3178 ------------------------
3180 function Subtree_Node_Count (Position : Cursor) return Count_Type is
3182 if Position = No_Element then
3186 if Position.Container.Count = 0 then
3187 pragma Assert (Is_Root (Position));
3191 return Subtree_Node_Count (Position.Container.all, Position.Node);
3192 end Subtree_Node_Count;
3194 function Subtree_Node_Count
3196 Subtree : Count_Type) return Count_Type
3198 Result : Count_Type;
3199 Node : Count_Type'Base;
3203 Node := Container.Nodes (Subtree).Children.First;
3205 Result := Result + Subtree_Node_Count (Container, Node);
3206 Node := Container.Nodes (Node).Next;
3209 end Subtree_Node_Count;
3216 (Container : in out Tree;
3220 TE_Check (Container.TC);
3222 if Checks and then I = No_Element then
3223 raise Constraint_Error with "I cursor has no element";
3226 if Checks and then I.Container /= Container'Unrestricted_Access then
3227 raise Program_Error with "I cursor not in container";
3230 if Checks and then Is_Root (I) then
3231 raise Program_Error with "I cursor designates root";
3234 if I = J then -- make this test sooner???
3238 if Checks and then J = No_Element then
3239 raise Constraint_Error with "J cursor has no element";
3242 if Checks and then J.Container /= Container'Unrestricted_Access then
3243 raise Program_Error with "J cursor not in container";
3246 if Checks and then Is_Root (J) then
3247 raise Program_Error with "J cursor designates root";
3251 EE : Element_Array renames Container.Elements;
3252 EI : constant Element_Type := EE (I.Node);
3255 EE (I.Node) := EE (J.Node);
3260 --------------------
3261 -- Update_Element --
3262 --------------------
3264 procedure Update_Element
3265 (Container : in out Tree;
3267 Process : not null access procedure (Element : in out Element_Type))
3270 if Checks and then Position = No_Element then
3271 raise Constraint_Error with "Position cursor has no element";
3274 if Checks and then Position.Container /= Container'Unrestricted_Access
3276 raise Program_Error with "Position cursor not in container";
3279 if Checks and then Is_Root (Position) then
3280 raise Program_Error with "Position cursor designates root";
3284 T : Tree renames Position.Container.all'Unrestricted_Access.all;
3285 Lock : With_Lock (T.TC'Unrestricted_Access);
3287 Process (Element => T.Elements (Position.Node));
3296 (Stream : not null access Root_Stream_Type'Class;
3299 procedure Write_Children (Subtree : Count_Type);
3300 procedure Write_Subtree (Subtree : Count_Type);
3302 --------------------
3303 -- Write_Children --
3304 --------------------
3306 procedure Write_Children (Subtree : Count_Type) is
3307 CC : Children_Type renames Container.Nodes (Subtree).Children;
3308 C : Count_Type'Base;
3311 Count_Type'Write (Stream, Child_Count (Container, Subtree));
3316 C := Container.Nodes (C).Next;
3324 procedure Write_Subtree (Subtree : Count_Type) is
3326 Element_Type'Write (Stream, Container.Elements (Subtree));
3327 Write_Children (Subtree);
3330 -- Start of processing for Write
3333 Count_Type'Write (Stream, Container.Count);
3335 if Container.Count = 0 then
3339 Write_Children (Root_Node (Container));
3343 (Stream : not null access Root_Stream_Type'Class;
3347 raise Program_Error with "attempt to write tree cursor to stream";
3351 (Stream : not null access Root_Stream_Type'Class;
3352 Item : Reference_Type)
3355 raise Program_Error with "attempt to stream reference";
3359 (Stream : not null access Root_Stream_Type'Class;
3360 Item : Constant_Reference_Type)
3363 raise Program_Error with "attempt to stream reference";
3366 end Ada.Containers.Bounded_Multiway_Trees;