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-2010, 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;
  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 Pure;
  65
  66    function Min (Tree : Tree_Type'Class; Node : Count_Type) return Count_Type;
  67    --  Returns the smallest-valued node of the subtree rooted at Node
  68
  69    function Max (Tree : Tree_Type'Class; Node : Count_Type) return Count_Type;
  70    --  Returns the largest-valued node of the subtree rooted at Node
  71
  72    function Vet (Tree : Tree_Type'Class; Index : Count_Type) return Boolean;
  73    --  Inspects Node to determine (to the extent possible) whether
  74    --  the node is valid; used to detect if the node is dangling.
  75
  76    function Next
  77      (Tree : Tree_Type'Class;
  78       Node : Count_Type) return Count_Type;
  79    --  Returns the smallest node greater than Node
  80
  81    function Previous
  82      (Tree : Tree_Type'Class;
  83       Node : Count_Type) return Count_Type;
  84    --  Returns the largest node less than Node
  85
  86    generic
  87       with function Is_Equal (L, R : Node_Type) return Boolean;
  88    function Generic_Equal (Left, Right : Tree_Type'Class) return Boolean;
  89    --  Uses Is_Equal to perform a node-by-node comparison of the
  90    --  Left and Right trees; processing stops as soon as the first
  91    --  non-equal node is found.
  92
  93    procedure Delete_Node_Sans_Free
  94      (Tree : in out Tree_Type'Class; Node : Count_Type);
  95    --  Removes Node from Tree without deallocating the node. If Tree
  96    --  is busy then Program_Error is raised.
  97
  98    procedure Clear_Tree (Tree : in out Tree_Type'Class);
  99    --  Clears Tree by deallocating all of its nodes. If Tree is busy then
 100    --  Program_Error is raised.
 101
 102    generic
 103       with procedure Process (Node : Count_Type) is <>;
 104    procedure Generic_Iteration (Tree : Tree_Type'Class);
 105    --  Calls Process for each node in Tree, in order from smallest-valued
 106    --  node to largest-valued node.
 107
 108    generic
 109       with procedure Process (Node : Count_Type) is <>;
 110    procedure Generic_Reverse_Iteration (Tree : Tree_Type'Class);
 111    --  Calls Process for each node in Tree, in order from largest-valued
 112    --  node to smallest-valued node.
 113
 114    generic
 115       with procedure Write_Node
 116         (Stream : not null access Root_Stream_Type'Class;
 117          Node   : Node_Type);
 118    procedure Generic_Write
 119      (Stream : not null access Root_Stream_Type'Class;
 120       Tree   : Tree_Type'Class);
 121    --  Used to implement stream attribute T'Write. Generic_Write
 122    --  first writes the number of nodes into Stream, then calls
 123    --  Write_Node for each node in Tree.
 124
 125    generic
 126       with procedure Allocate
 127         (Tree : in out Tree_Type'Class;
 128          Node : out Count_Type);
 129    procedure Generic_Read
 130      (Stream : not null access Root_Stream_Type'Class;
 131       Tree   : in out Tree_Type'Class);
 132    --  Used to implement stream attribute T'Read. Generic_Read
 133    --  first clears Tree. It then reads the number of nodes out of
 134    --  Stream, and calls Read_Node for each node in Stream.
 135
 136    procedure Rebalance_For_Insert
 137      (Tree : in out Tree_Type'Class;
 138       Node : Count_Type);
 139    --  This rebalances Tree to complete the insertion of Node (which
 140    --  must already be linked in at its proper insertion position).
 141
 142    generic
 143       with procedure Set_Element (Node : in out Node_Type);
 144    procedure Generic_Allocate
 145      (Tree : in out Tree_Type'Class;
 146       Node : out Count_Type);
 147    --  Claim a node from the free store. Generic_Allocate first
 148    --  calls Set_Element on the potential node, and then returns
 149    --  the node's index as the value of the Node parameter.
 150
 151    procedure Free (Tree : in out Tree_Type'Class; X : Count_Type);
 152    --  Return a node back to the free store, from where it had
 153    --  been previously claimed via Generic_Allocate.
 154
 155 end Ada.Containers.Red_Black_Trees.Generic_Bounded_Operations;