1------------------------------------------------------------------------------ 2-- -- 3-- GNAT LIBRARY COMPONENTS -- 4-- -- 5-- ADA.CONTAINERS.RED_BLACK_TREES.GENERIC_KEYS -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 2004-2018, 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-- 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. -- 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 ordered containers. This package declares 31-- the tree operations that depend on keys. 32 33with Ada.Containers.Red_Black_Trees.Generic_Operations; 34 35generic 36 with package Tree_Operations is new Generic_Operations (<>); 37 38 use Tree_Operations.Tree_Types, Tree_Operations.Tree_Types.Implementation; 39 40 type Key_Type (<>) is limited private; 41 42 with function Is_Less_Key_Node 43 (L : Key_Type; 44 R : Node_Access) return Boolean; 45 46 with function Is_Greater_Key_Node 47 (L : Key_Type; 48 R : Node_Access) return Boolean; 49 50package Ada.Containers.Red_Black_Trees.Generic_Keys is 51 pragma Pure; 52 53 generic 54 with function New_Node return Node_Access; 55 procedure Generic_Insert_Post 56 (Tree : in out Tree_Type; 57 Y : Node_Access; 58 Before : Boolean; 59 Z : out Node_Access); 60 -- Completes an insertion after the insertion position has been 61 -- determined. On output Z contains a pointer to the newly inserted 62 -- node, allocated using New_Node. If Tree is busy then 63 -- Program_Error is raised. If Y is null, then Tree must be empty. 64 -- Otherwise Y denotes the insertion position, and Before specifies 65 -- whether the new node is Y's left (True) or right (False) child. 66 67 generic 68 with procedure Insert_Post 69 (T : in out Tree_Type; 70 Y : Node_Access; 71 B : Boolean; 72 Z : out Node_Access); 73 74 procedure Generic_Conditional_Insert 75 (Tree : in out Tree_Type; 76 Key : Key_Type; 77 Node : out Node_Access; 78 Inserted : out Boolean); 79 -- Inserts a new node in Tree, but only if the tree does not already 80 -- contain Key. Generic_Conditional_Insert first searches for a key 81 -- equivalent to Key in Tree. If an equivalent key is found, then on 82 -- output Node designates the node with that key and Inserted is 83 -- False; there is no allocation and Tree is not modified. Otherwise 84 -- Node designates a new node allocated using Insert_Post, and 85 -- Inserted is True. 86 87 generic 88 with procedure Insert_Post 89 (T : in out Tree_Type; 90 Y : Node_Access; 91 B : Boolean; 92 Z : out Node_Access); 93 94 procedure Generic_Unconditional_Insert 95 (Tree : in out Tree_Type; 96 Key : Key_Type; 97 Node : out Node_Access); 98 -- Inserts a new node in Tree. On output Node designates the new 99 -- node, which is allocated using Insert_Post. The node is inserted 100 -- immediately after already-existing equivalent keys. 101 102 generic 103 with procedure Insert_Post 104 (T : in out Tree_Type; 105 Y : Node_Access; 106 B : Boolean; 107 Z : out Node_Access); 108 109 with procedure Unconditional_Insert_Sans_Hint 110 (Tree : in out Tree_Type; 111 Key : Key_Type; 112 Node : out Node_Access); 113 114 procedure Generic_Unconditional_Insert_With_Hint 115 (Tree : in out Tree_Type; 116 Hint : Node_Access; 117 Key : Key_Type; 118 Node : out Node_Access); 119 -- Inserts a new node in Tree near position Hint, to avoid having to 120 -- search from the root for the insertion position. If Hint is null 121 -- then Generic_Unconditional_Insert_With_Hint attempts to insert 122 -- the new node after Tree.Last. If Hint is non-null then if Key is 123 -- less than Hint, it attempts to insert the new node immediately 124 -- prior to Hint. Otherwise it attempts to insert the node 125 -- immediately following Hint. We say "attempts" above to emphasize 126 -- that insertions always preserve invariants with respect to key 127 -- order, even when there's a hint. So if Key can't be inserted 128 -- immediately near Hint, then the new node is inserted in the 129 -- normal way, by searching for the correct position starting from 130 -- the root. 131 132 generic 133 with procedure Insert_Post 134 (T : in out Tree_Type; 135 Y : Node_Access; 136 B : Boolean; 137 Z : out Node_Access); 138 139 with procedure Conditional_Insert_Sans_Hint 140 (Tree : in out Tree_Type; 141 Key : Key_Type; 142 Node : out Node_Access; 143 Inserted : out Boolean); 144 145 procedure Generic_Conditional_Insert_With_Hint 146 (Tree : in out Tree_Type; 147 Position : Node_Access; -- the hint 148 Key : Key_Type; 149 Node : out Node_Access; 150 Inserted : out Boolean); 151 -- Inserts a new node in Tree if the tree does not already contain 152 -- Key, using Position as a hint about where to insert the new node. 153 -- See Generic_Unconditional_Insert_With_Hint for more details about 154 -- hint semantics. 155 156 function Find 157 (Tree : Tree_Type; 158 Key : Key_Type) return Node_Access; 159 -- Searches Tree for the smallest node equivalent to Key 160 161 function Ceiling 162 (Tree : Tree_Type; 163 Key : Key_Type) return Node_Access; 164 -- Searches Tree for the smallest node equal to or greater than Key 165 166 function Floor 167 (Tree : Tree_Type; 168 Key : Key_Type) return Node_Access; 169 -- Searches Tree for the largest node less than or equal to Key 170 171 function Upper_Bound 172 (Tree : Tree_Type; 173 Key : Key_Type) return Node_Access; 174 -- Searches Tree for the smallest node greater than Key 175 176 generic 177 with procedure Process (Node : Node_Access); 178 procedure Generic_Iteration 179 (Tree : Tree_Type; 180 Key : Key_Type); 181 -- Calls Process for each node in Tree equivalent to Key, in order 182 -- from earliest in range to latest. 183 184 generic 185 with procedure Process (Node : Node_Access); 186 procedure Generic_Reverse_Iteration 187 (Tree : Tree_Type; 188 Key : Key_Type); 189 -- Calls Process for each node in Tree equivalent to Key, but in 190 -- order from largest in range to earliest. 191 192end Ada.Containers.Red_Black_Trees.Generic_Keys; 193