

--
-- 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/>.
--



--
--*****************************************************************
--
-- splaypq Package Description:
--
-- New version of splaytree with added priority field that allows:
-- a) random access by unique key value, just as before;
-- b) sequential access by an integer-valued priority field
--    that allows duplicates, with the typical properties
--    of a Priority Queue. Here, equal priorities are inserted 
--    ahead of others (LIFO regimen) using AddNode.
--
-- 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.
-- Linear access and traversal of the tree elements according to
-- insertion order [fifo queue] is also supported using
-- the "head" and "next" accessors.
--
-- Reference:
-- See the Journal of the A.C.M., July 1985,
-- Vol. 32, No. 3, pg. 652, library call # QA 76 A77
--
--*******************************************************************

with utiltypes;


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 mylist is new splaylist( 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 splaypq is

	subtype p4range is integer range 1..4;
	subtype p1range is integer range 0..utiltypes.imaxboxes; --50
	subtype p2range is integer range 0..utiltypes.maxpri0; --500

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




   type ListType is private;


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




	-- list insert AFTER others of equal priority
   procedure AddNode( Id     : in IdType;
                      Data   : in DataType;
							 pri1,pri2,
							 pri3,pri4
							 		: in p1range;
							 pri0   : in p2range;
                      List   : in out ListType;
                      Status :    out StatusType);





	procedure bumpKey(
		List   : in out ListType;
		Id   : IdType;
		data : datatype;
		nupri0 : p2range;
		Status :    out StatusType);







	--get/remove head of FIFO queue:
   procedure popNode( List   : in out ListType;
                   Id     : out IdType;
                   Data   : out DataType;
						 ip: in p4range;
						 pri1,pri2,pri3,pri4,pri0 : out integer;
                   Status :    out StatusType);






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




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





	procedure make_empty(list: in out listtype; status: out statustype);



function getsize return integer;




private

   type splayrec;
   type splayptr is access splayrec;

	type hashnode;
	type hashptr is access hashnode;

	type hash4ptr is array(p4range) of hashptr;

	type hashnode is
		record
			down: splayptr := null;
			hnext, hprev : hash4ptr := (others=>null);
		end record;
	type hasharray is array(p1range,p2range) of hashptr;
	type hash4type is array(p4range) of hasharray;

   type splayrec is
      record
         Id : IdType;
         Data: DataType;
			priority1 : p1range; --primary
			priority2 : p1range; --primary
			priority3 : p1range; --primary
			priority4 : p1range; --primary
			priority0 : p2range; --TotPulz [+hunEst]
         parent,
         left_child,
         right_child
            : splayptr := null;
			hptr: hashptr := null;
      end record; -- 376 bytes

   type listheader is
      record
         root : splayptr := null;
         size : integer := 0;
			hash: hash4type := (others=>(others=>(others=>null)));
      end record;

   type listptr is access listheader;

   type listtype is
      record
         header : listptr := null;
      end record;

end splaypq;
