

--
-- Copyright (C) 2021  <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 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.
--    Equal priorities are inserted AFTER others using AddNode2.
--
-- 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
--
--*******************************************************************





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.

	-- This version of splaypq has a single priority measure
	-- in range 0..500.


package splaypq0 is -- clients are: bfs7.adb, bfs26.adb


subtype p1range is integer range 0..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;
							 pri    : in p1range;
                      List   : in out ListType;
                      Status :    out StatusType);




	--20dec20 addendum
	-- delete node @ specified key
	procedure rmKey(
		List   : in out ListType;
		Id   : IdType;
		Status :    out StatusType);


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








	--get/remove head of FIFO queue:
   procedure popNode( List   : in out ListType;
                   Id     : out IdType;
                   Data   : out DataType;
						 pri : out integer;
                   Status :    out StatusType);






	--get/remove head of FIFO queue:
   procedure peekNode( List   : in out ListType;
                   Id     : out IdType;
                   Data   : out DataType;
						 pri : out integer;
                   Status :    out StatusType);





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




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




   ------------------------------------------
   -- modifies the nodal data at specified Id; priority unchanged.
   ------------------------------------------
   procedure ModifyNode( Id     : in     IdType;
                         Data   : in     DataType;
                         List   : in out ListType;
                         Status :    out StatusType);




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





private

   type splayrec;
   type splayptr is access splayrec;

	type hashnode;
	type hashptr is access hashnode;
	type hashnode is
		record
			down: splayptr := null;
			hnext,hprev: hashptr := null;
		end record;
	type hasharray is array(p1range) of hashptr;

   type splayrec is
      record
         Id : IdType;
         Data: DataType;
			priority : p1range; -- 0..500
         parent,
         left_child,
         right_child
            : splayptr := null;
			hptr: hashptr := null;
      end record;

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

   type listptr is access listheader;

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

end splaypq0;
