File : a-rbtgbo.ads
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT LIBRARY COMPONENTS --
4 -- --
5 -- ADA.CONTAINERS.RED_BLACK_TREES.GENERIC_BOUNDED_OPERATIONS --
6 -- --
7 -- S p e c --
8 -- --
9 -- Copyright (C) 2004-2015, Free Software Foundation, Inc. --
10 -- --
11 -- GNAT is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
17 -- --
18 -- --
19 -- --
20 -- --
21 -- --
22 -- You should have received a copy of the GNU General Public License and --
23 -- a copy of the GCC Runtime Library Exception along with this program; --
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
25 -- <http://www.gnu.org/licenses/>. --
26 -- --
27 -- This unit was originally developed by Matthew J Heaney. --
28 ------------------------------------------------------------------------------
29
30 -- Tree_Type is used to implement the ordered containers. This package
31 -- declares the tree operations that do not depend on keys.
32
33 with Ada.Streams; use Ada.Streams;
34
35 generic
36 with package Tree_Types is new Generic_Bounded_Tree_Types (<>);
37 use Tree_Types, Tree_Types.Implementation;
38
39 with function Parent (Node : Node_Type) return Count_Type is <>;
40
41 with procedure Set_Parent
42 (Node : in out Node_Type;
43 Parent : Count_Type) is <>;
44
45 with function Left (Node : Node_Type) return Count_Type is <>;
46
47 with procedure Set_Left
48 (Node : in out Node_Type;
49 Left : Count_Type) is <>;
50
51 with function Right (Node : Node_Type) return Count_Type is <>;
52
53 with procedure Set_Right
54 (Node : in out Node_Type;
55 Right : Count_Type) is <>;
56
57 with function Color (Node : Node_Type) return Color_Type is <>;
58
59 with procedure Set_Color
60 (Node : in out Node_Type;
61 Color : Color_Type) is <>;
62
63 package Ada.Containers.Red_Black_Trees.Generic_Bounded_Operations is
64 pragma Annotate (CodePeer, Skip_Analysis);
65 pragma Pure;
66
67 function Min (Tree : Tree_Type'Class; Node : Count_Type) return Count_Type;
68 -- Returns the smallest-valued node of the subtree rooted at Node
69
70 function Max (Tree : Tree_Type'Class; Node : Count_Type) return Count_Type;
71 -- Returns the largest-valued node of the subtree rooted at Node
72
73 function Vet (Tree : Tree_Type'Class; Index : Count_Type) return Boolean;
74 -- Inspects Node to determine (to the extent possible) whether
75 -- the node is valid; used to detect if the node is dangling.
76
77 function Next
78 (Tree : Tree_Type'Class;
79 Node : Count_Type) return Count_Type;
80 -- Returns the smallest node greater than Node
81
82 function Previous
83 (Tree : Tree_Type'Class;
84 Node : Count_Type) return Count_Type;
85 -- Returns the largest node less than Node
86
87 generic
88 with function Is_Equal (L, R : Node_Type) return Boolean;
89 function Generic_Equal (Left, Right : Tree_Type'Class) return Boolean;
90 -- Uses Is_Equal to perform a node-by-node comparison of the
91 -- Left and Right trees; processing stops as soon as the first
92 -- non-equal node is found.
93
94 procedure Delete_Node_Sans_Free
95 (Tree : in out Tree_Type'Class; Node : Count_Type);
96 -- Removes Node from Tree without deallocating the node. If Tree
97 -- is busy then Program_Error is raised.
98
99 procedure Clear_Tree (Tree : in out Tree_Type'Class);
100 -- Clears Tree by deallocating all of its nodes. If Tree is busy then
101 -- Program_Error is raised.
102
103 generic
104 with procedure Process (Node : Count_Type) is <>;
105 procedure Generic_Iteration (Tree : Tree_Type'Class);
106 -- Calls Process for each node in Tree, in order from smallest-valued
107 -- node to largest-valued node.
108
109 generic
110 with procedure Process (Node : Count_Type) is <>;
111 procedure Generic_Reverse_Iteration (Tree : Tree_Type'Class);
112 -- Calls Process for each node in Tree, in order from largest-valued
113 -- node to smallest-valued node.
114
115 generic
116 with procedure Write_Node
117 (Stream : not null access Root_Stream_Type'Class;
118 Node : Node_Type);
119 procedure Generic_Write
120 (Stream : not null access Root_Stream_Type'Class;
121 Tree : Tree_Type'Class);
122 -- Used to implement stream attribute T'Write. Generic_Write
123 -- first writes the number of nodes into Stream, then calls
124 -- Write_Node for each node in Tree.
125
126 generic
127 with procedure Allocate
128 (Tree : in out Tree_Type'Class;
129 Node : out Count_Type);
130 procedure Generic_Read
131 (Stream : not null access Root_Stream_Type'Class;
132 Tree : in out Tree_Type'Class);
133 -- Used to implement stream attribute T'Read. Generic_Read
134 -- first clears Tree. It then reads the number of nodes out of
135 -- Stream, and calls Read_Node for each node in Stream.
136
137 procedure Rebalance_For_Insert
138 (Tree : in out Tree_Type'Class;
139 Node : Count_Type);
140 -- This rebalances Tree to complete the insertion of Node (which
141 -- must already be linked in at its proper insertion position).
142
143 generic
144 with procedure Set_Element (Node : in out Node_Type);
145 procedure Generic_Allocate
146 (Tree : in out Tree_Type'Class;
147 Node : out Count_Type);
148 -- Claim a node from the free store. Generic_Allocate first
149 -- calls Set_Element on the potential node, and then returns
150 -- the node's index as the value of the Node parameter.
151
152 procedure Free (Tree : in out Tree_Type'Class; X : Count_Type);
153 -- Return a node back to the free store, from where it had
154 -- been previously claimed via Generic_Allocate.
155
156 end Ada.Containers.Red_Black_Trees.Generic_Bounded_Operations;