1--  GHDL Run Time (GRT) - binary balanced tree.
2--  Copyright (C) 2002 - 2014 Tristan Gingold
3--
4--  This program is free software: you can redistribute it and/or modify
5--  it under the terms of the GNU General Public License as published by
6--  the Free Software Foundation, either version 2 of the License, or
7--  (at your option) any later version.
8--
9--  This program is distributed in the hope that it will be useful,
10--  but WITHOUT ANY WARRANTY; without even the implied warranty of
11--  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12--  GNU General Public License for more details.
13--
14--  You should have received a copy of the GNU General Public License
15--  along with this program.  If not, see <gnu.org/licenses>.
16--
17--  As a special exception, if other files instantiate generics from this
18--  unit, or you link this unit with other files to produce an executable,
19--  this unit does not by itself cause the resulting executable to be
20--  covered by the GNU General Public License. This exception does not
21--  however invalidate any other reasons why the executable file might be
22--  covered by the GNU Public License.
23with Grt.Types; use Grt.Types;
24
25package Grt.Avls is
26   --  Implementation of a binary balanced tree.
27   --  This package is very generic, and provides only the algorithm.
28   --  The user must provide the storage of the tree.
29   --  The basic types of this implementation ares:
30   --  * AVL_Value: the value stored in the tree.  This is an integer on 32
31   --    bits.  However, they may either really represent integers or an index
32   --    into another table.  To compare two values, a user function is always
33   --    provided.
34   --  * AVL_Nid: a node id or an index into the tree.
35   --  * AVL_Node: a node, indexed by AVL_Nid.
36   --  * AVL_Tree: an array of AVL_Node, indexed by AVL_Nid.  This represents
37   --    the tree.  The root of the tree is always AVL_Root, which is the
38   --    first element of the array.
39   --
40   --  As a choice, this package never allocate nodes.  So, to insert a value
41   --  in the tree, the user must allocate an (empty) node, set the value of
42   --  the node and try to insert this node into the tree.  If the value is
43   --  already in the tree, Get_Node will returns the node id which contains
44   --  the value.  Otherwise, Get_Node returns the node just created by the
45   --  user.
46
47   --  The value in an AVL tree.
48   --  This is fixed.
49   type AVL_Value is new Ghdl_I32;
50
51   --  An AVL node id.
52   type AVL_Nid is new Ghdl_I32;
53   AVL_Nil : constant AVL_Nid := 0;
54   AVL_Root : constant AVL_Nid := 1;
55
56   type AVL_Node is record
57      Val : AVL_Value;
58      Left : AVL_Nid;
59      Right : AVL_Nid;
60      Height : Ghdl_I32;
61   end record;
62
63   type AVL_Tree is array (AVL_Nid range <>) of AVL_Node;
64
65   --  Compare two values.
66   --  Returns < 0 if L < R, 0 if L = R, > 0 if L > R.
67   type AVL_Compare_Func is access function (L, R : AVL_Value) return Integer;
68
69   --  Try to insert node N into TREE.
70   --  Returns either N or the node id of a node containing already the value.
71   procedure Get_Node (Tree : in out AVL_Tree;
72                       Cmp : AVL_Compare_Func;
73                       N : AVL_Nid;
74                       Res : out AVL_Nid);
75
76   function Find_Node (Tree : AVL_Tree;
77                       Cmp : AVL_Compare_Func;
78                       Val : AVL_Value) return AVL_Nid;
79
80end Grt.Avls;
81
82
83