

--
-- Copyright (C) 2022  <fastrgv@gmail.com>
--
-- This program is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You may read the full text of the GNU General Public License
-- at <http://www.gnu.org/licenses/>.
--



--
--*****************************************************************
--
-- Description:
--
-- This package implements an extremely efficient self-adjusting
-- binary search tree called a splay tree with very little overhead
-- to maintain the balance.  The ordering by IdType is maintained
-- to permit fast access by Id and fast checks for duplicates.
--
-- Reference:
-- See the Journal of the A.C.M., July 1985,
-- Vol. 32, No. 3, pg. 652, library call # QA 76 A77
--
--*******************************************************************

--with splaytypes;


generic

   type IdType is private;
   type DataType is private;

   with function "<" ( k1, k2: in IdType ) return boolean is <>;
   with function ">" ( k1, k2: in IdType ) return boolean is <>;

   -- These infix functions (operators) together with the type IdType
   -- are used to define the search tree ordering.  

   -- the following example instantiation is particularly simple
   -- because the idtype (integer) has an intrinsic ordering:
   --
   -- package mytree is new splaytree( idtype   => integer,
   --                             datatype => float,
   --                             "<"      =>  "<",
   --                             ">"      =>  ">" );
   --
	-- If the idtype has an Ada-implicit ordering,
   -- then the instantiations require only the addition
   -- of { "<", ">" } as the last two generic parameters.


package splaytree is


  type StatusType is
       (Ok, Found, Empty, NotFound, Error, DupId, NilPtr);




   type treeType is private;


   --===================================================
   -- temporary routine for debugging purposes only;
   -- allows users to deduce the tree's structure
   --procedure GetParentKey( k: IdType;
   --                        tree: in out treetype;
   --                        kp: out IdType );
   --===================================================



   --------------------------------------
   -- Adds a node;
   --------------------------------------
   procedure AddNode( Id     : in IdType;
                      Data   : in DataType;
                      tree   : in out treeType;
                      Status :    out StatusType);

   ------------------------------------------------
   -- gets the nodal data belonging to specified Id
   ------------------------------------------------
   procedure search( Id     : in     IdType;
                      tree   : in     treeType;
                      Data   :    out DataType;
                      Status :    out StatusType);

   ------------------------------------------
   -- returns the number of nodes in the tree
   ------------------------------------------
   function length( tree : in treeType ) return integer;

   ------------------------------------------
   -- modifies the nodal data at specified Id
   ------------------------------------------
   procedure ModifyNode( Id     : in     IdType;
                         Data   : in     DataType;
                         tree   : in out treeType;
                         Status :    out StatusType);

	procedure make_empty ( tree : in out treeType;
                   Status :    out StatusType);

	function getsize return integer;
	function getalignment return integer;

   ---------------------------------------
   -- deletes the node with specified Id
   ---------------------------------------
   procedure DelNode( Id     : in IdType;
                      tree   : in out treeType;
                      Status :    out StatusType);





private

   type splayrec;
   type splayptr is access splayrec;
   type splayrec is
      record
         Id : IdType;
         Data: DataType;
         parent,
         	left_child,
         		right_child
					: splayptr := null;
      end record;


   type treeheader is
      record
         root : splayptr := null;
         size : integer := 0;
      end record;

   type treeptr is access treeheader;

   type treetype is
      record
         header : treeptr := null;
      end record;


end splaytree;
