gcc/ada/libgnat/a-crbtgo.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT LIBRARY COMPONENTS                          --
   4 --                                                                          --
   5 --             ADA.CONTAINERS.RED_BLACK_TREES.GENERIC_OPERATIONS            --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --          Copyright (C) 2004-2023, 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 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_Tree_Types (<>);
  37    use Tree_Types, Tree_Types.Implementation;
  38
  39    with function  Parent (Node : Node_Access) return Node_Access is <>;
  40    with procedure Set_Parent (Node : Node_Access; Parent : Node_Access) is <>;
  41    with function  Left (Node : Node_Access) return Node_Access is <>;
  42    with procedure Set_Left (Node : Node_Access; Left : Node_Access) is <>;
  43    with function  Right (Node : Node_Access) return Node_Access is <>;
  44    with procedure Set_Right (Node : Node_Access; Right : Node_Access) is <>;
  45    with function  Color (Node : Node_Access) return Color_Type is <>;
  46    with procedure Set_Color (Node : Node_Access; Color : Color_Type) is <>;
  47
  48 package Ada.Containers.Red_Black_Trees.Generic_Operations is
  49    pragma Pure;
  50
  51    function Min (Node : Node_Access) return Node_Access;
  52    --  Returns the smallest-valued node of the subtree rooted at Node
  53
  54    function Max (Node : Node_Access) return Node_Access;
  55    --  Returns the largest-valued node of the subtree rooted at Node
  56
  57    --  NOTE: The Check_Invariant operation was used during early
  58    --  development of the red-black tree. Now that the tree type
  59    --  implementation has matured, we don't really need Check_Invariant
  60    --  anymore.
  61
  62    --  procedure Check_Invariant (Tree : Tree_Type);
  63
  64    function Vet (Tree : Tree_Type; Node : Node_Access) return Boolean
  65      with Inline;
  66    --  Inspects Node to determine (to the extent possible) whether
  67    --  the node is valid; used to detect if the node is dangling.
  68
  69    function Next (Node : Node_Access) return Node_Access;
  70    --  Returns the smallest node greater than Node
  71
  72    function Previous (Node : Node_Access) return Node_Access;
  73    --  Returns the largest node less than Node
  74
  75    generic
  76       with function Is_Equal (L, R : Node_Access) return Boolean;
  77    function Generic_Equal (Left, Right : Tree_Type) return Boolean;
  78    --  Uses Is_Equal to perform a node-by-node comparison of the
  79    --  Left and Right trees; processing stops as soon as the first
  80    --  non-equal node is found.
  81
  82    procedure Delete_Node_Sans_Free
  83      (Tree : in out Tree_Type;
  84       Node : Node_Access);
  85    --  Removes Node from Tree without deallocating the node. If Tree
  86    --  is busy then Program_Error is raised.
  87
  88    generic
  89       with procedure Free (X : in out Node_Access);
  90    procedure Generic_Delete_Tree (X : in out Node_Access);
  91    --  Deallocates the tree rooted at X, calling Free on each node
  92
  93    generic
  94       with function Copy_Node (Source : Node_Access) return Node_Access;
  95       with procedure Delete_Tree (X : in out Node_Access);
  96    function Generic_Copy_Tree (Source_Root : Node_Access) return Node_Access;
  97    --  Copies the tree rooted at Source_Root, using Copy_Node to copy each
  98    --  node of the source tree. If Copy_Node propagates an exception
  99    --  (e.g. Storage_Error), then Delete_Tree is first used to deallocate
 100    --  the target tree, and then the exception is propagated.
 101
 102    generic
 103       with function Copy_Tree (Root : Node_Access) return Node_Access;
 104    procedure Generic_Adjust (Tree : in out Tree_Type);
 105    --  Used to implement controlled Adjust. On input to Generic_Adjust, Tree
 106    --  holds a bitwise (shallow) copy of the source tree (as would be the case
 107    --  when controlled Adjust is called). On output, Tree holds its own (deep)
 108    --  copy of the source tree, which is constructed by calling Copy_Tree.
 109
 110    generic
 111       with procedure Delete_Tree (X : in out Node_Access);
 112    procedure Generic_Clear (Tree : in out Tree_Type);
 113    --  Clears Tree by deallocating all of its nodes. If Tree is busy then
 114    --  Program_Error is raised.
 115
 116    generic
 117       with procedure Clear (Tree : in out Tree_Type);
 118    procedure Generic_Move (Target, Source : in out Tree_Type);
 119    --  Moves the tree belonging to Source onto Target. If Source is busy then
 120    --  Program_Error is raised. Otherwise Target is first cleared (by calling
 121    --  Clear, to deallocate its existing tree), then given the Source tree, and
 122    --  then finally Source is cleared (by setting its pointers to null).
 123
 124    generic
 125       with procedure Process (Node : Node_Access) is <>;
 126    procedure Generic_Iteration (Tree : Tree_Type);
 127    --  Calls Process for each node in Tree, in order from smallest-valued
 128    --  node to largest-valued node.
 129
 130    generic
 131       with procedure Process (Node : Node_Access) is <>;
 132    procedure Generic_Reverse_Iteration (Tree : Tree_Type);
 133    --  Calls Process for each node in Tree, in order from largest-valued
 134    --  node to smallest-valued node.
 135
 136    generic
 137       with procedure Write_Node
 138         (Stream : not null access Root_Stream_Type'Class;
 139          Node   : Node_Access);
 140    procedure Generic_Write
 141      (Stream : not null access Root_Stream_Type'Class;
 142       Tree   : Tree_Type);
 143    --  Used to implement stream attribute T'Write. Generic_Write
 144    --  first writes the number of nodes into Stream, then calls
 145    --  Write_Node for each node in Tree.
 146
 147    generic
 148       with procedure Clear (Tree : in out Tree_Type);
 149       with function Read_Node
 150         (Stream : not null access Root_Stream_Type'Class) return Node_Access;
 151    procedure Generic_Read
 152      (Stream : not null access Root_Stream_Type'Class;
 153       Tree   : in out Tree_Type);
 154    --  Used to implement stream attribute T'Read. Generic_Read
 155    --  first clears Tree. It then reads the number of nodes out of
 156    --  Stream, and calls Read_Node for each node in Stream.
 157
 158    procedure Rebalance_For_Insert
 159      (Tree : in out Tree_Type;
 160       Node : Node_Access);
 161    --  This rebalances Tree to complete the insertion of Node (which
 162    --  must already be linked in at its proper insertion position).
 163
 164 end Ada.Containers.Red_Black_Trees.Generic_Operations;