------------------------------------------------------------------------------ -- -- -- GNAT LIBRARY COMPONENTS -- -- -- -- ADA.CONTAINERS.RED_BLACK_TREES.GENERIC_KEYS -- -- -- -- S p e c -- -- -- -- Copyright (C) 2004-2009, Free Software Foundation, Inc. -- -- -- -- GNAT is free software; you can redistribute it and/or modify it under -- -- terms of the GNU General Public License as published by the Free Soft- -- -- ware Foundation; either version 3, or (at your option) any later ver- -- -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- -- or FITNESS FOR A PARTICULAR PURPOSE. -- -- -- -- As a special exception under Section 7 of GPL version 3, you are granted -- -- additional permissions described in the GCC Runtime Library Exception, -- -- version 3.1, as published by the Free Software Foundation. -- -- -- -- You should have received a copy of the GNU General Public License and -- -- a copy of the GCC Runtime Library Exception along with this program; -- -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- -- . -- -- -- -- This unit was originally developed by Matthew J Heaney. -- ------------------------------------------------------------------------------ -- Tree_Type is used to implement ordered containers. This package declares -- the tree operations that depend on keys. with Ada.Containers.Red_Black_Trees.Generic_Operations; generic with package Tree_Operations is new Generic_Operations (<>); use Tree_Operations.Tree_Types; type Key_Type (<>) is limited private; with function Is_Less_Key_Node (L : Key_Type; R : Node_Access) return Boolean; with function Is_Greater_Key_Node (L : Key_Type; R : Node_Access) return Boolean; package Ada.Containers.Red_Black_Trees.Generic_Keys is pragma Pure; generic with function New_Node return Node_Access; procedure Generic_Insert_Post (Tree : in out Tree_Type; Y : Node_Access; Before : Boolean; Z : out Node_Access); -- Completes an insertion after the insertion position has been -- determined. On output Z contains a pointer to the newly inserted -- node, allocated using New_Node. If Tree is busy then -- Program_Error is raised. If Y is null, then Tree must be empty. -- Otherwise Y denotes the insertion position, and Before specifies -- whether the new node is Y's left (True) or right (False) child. generic with procedure Insert_Post (T : in out Tree_Type; Y : Node_Access; B : Boolean; Z : out Node_Access); procedure Generic_Conditional_Insert (Tree : in out Tree_Type; Key : Key_Type; Node : out Node_Access; Inserted : out Boolean); -- Inserts a new node in Tree, but only if the tree does not already -- contain Key. Generic_Conditional_Insert first searches for a key -- equivalent to Key in Tree. If an equivalent key is found, then on -- output Node designates the node with that key and Inserted is -- False; there is no allocation and Tree is not modified. Otherwise -- Node designates a new node allocated using Insert_Post, and -- Inserted is True. generic with procedure Insert_Post (T : in out Tree_Type; Y : Node_Access; B : Boolean; Z : out Node_Access); procedure Generic_Unconditional_Insert (Tree : in out Tree_Type; Key : Key_Type; Node : out Node_Access); -- Inserts a new node in Tree. On output Node designates the new -- node, which is allocated using Insert_Post. The node is inserted -- immediately after already-existing equivalent keys. generic with procedure Insert_Post (T : in out Tree_Type; Y : Node_Access; B : Boolean; Z : out Node_Access); with procedure Unconditional_Insert_Sans_Hint (Tree : in out Tree_Type; Key : Key_Type; Node : out Node_Access); procedure Generic_Unconditional_Insert_With_Hint (Tree : in out Tree_Type; Hint : Node_Access; Key : Key_Type; Node : out Node_Access); -- Inserts a new node in Tree near position Hint, to avoid having to -- search from the root for the insertion position. If Hint is null -- then Generic_Unconditional_Insert_With_Hint attempts to insert -- the new node after Tree.Last. If Hint is non-null then if Key is -- less than Hint, it attempts to insert the new node immediately -- prior to Hint. Otherwise it attempts to insert the node -- immediately following Hint. We say "attempts" above to emphasize -- that insertions always preserve invariants with respect to key -- order, even when there's a hint. So if Key can't be inserted -- immediately near Hint, then the new node is inserted in the -- normal way, by searching for the correct position starting from -- the root. generic with procedure Insert_Post (T : in out Tree_Type; Y : Node_Access; B : Boolean; Z : out Node_Access); with procedure Conditional_Insert_Sans_Hint (Tree : in out Tree_Type; Key : Key_Type; Node : out Node_Access; Inserted : out Boolean); procedure Generic_Conditional_Insert_With_Hint (Tree : in out Tree_Type; Position : Node_Access; -- the hint Key : Key_Type; Node : out Node_Access; Inserted : out Boolean); -- Inserts a new node in Tree if the tree does not already contain -- Key, using Position as a hint about where to insert the new node. -- See Generic_Unconditional_Insert_With_Hint for more details about -- hint semantics. function Find (Tree : Tree_Type; Key : Key_Type) return Node_Access; -- Searches Tree for the smallest node equivalent to Key function Ceiling (Tree : Tree_Type; Key : Key_Type) return Node_Access; -- Searches Tree for the smallest node equal to or greater than Key function Floor (Tree : Tree_Type; Key : Key_Type) return Node_Access; -- Searches Tree for the largest node less than or equal to Key function Upper_Bound (Tree : Tree_Type; Key : Key_Type) return Node_Access; -- Searches Tree for the smallest node greater than Key generic with procedure Process (Node : Node_Access); procedure Generic_Iteration (Tree : Tree_Type; Key : Key_Type); -- Calls Process for each node in Tree equivalent to Key, in order -- from earliest in range to latest. generic with procedure Process (Node : Node_Access); procedure Generic_Reverse_Iteration (Tree : Tree_Type; Key : Key_Type); -- Calls Process for each node in Tree equivalent to Key, but in -- order from largest in range to earliest. end Ada.Containers.Red_Black_Trees.Generic_Keys;