gcc/ada/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 -- 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_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;