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



-- This package provides an interface to the munkres
-- Hungarian algorithm for usage as the heuristic
-- measure in an A* algorithm to solve sokoban puzzles.

-- Herein, the integer type "ushort", defined as 
-- mod 2**16 = 0..65535, is used to fill a cost matrix 
-- that defines the estimated number of moves to slide a 
-- particular box onto a particular goal.  The value 
-- usmx=65535 is used as "infinity" to indicate an 
-- impossible association between a particular box with 
-- a particular goal position,




with text_io;
with emutils;
with munkres;

package emhungarian is

	use emutils;

	nubvalid,
	hviano,hviaso,hviaea,hviawe: booltype;
	hbestcost: vustype;


	hboxrow, hgoalrow : array(boxrng) of rowrng;
	hboxcol, hgoalcol : array(boxrng) of colrng;
	hvf, hff, hfff: vftype;

	nrows, ncols: ushort;




	--NOTE #boxes is limited to 24 or less.
	ubmx: constant ushort := emutils.maxbx; --ushort(nbmx);
	nbmx: constant integer := integer(ubmx); --24;


	type boxcostype is array(rowrng,colrng) of ushort;

	type hunmatrixtype is array(rowrng,colrng) of boxcostype;

	infinitecost : constant boxcostype := (others=>(others=>usmx));

	hunmatrix: hunmatrixtype := (others=>(others=>infinitecost));


	package myintio is new text_io.modular_io(ushort);
	use myintio;



	-- for each box, this gives best goal index:
	gassn: munkres.iatype(1..nbmx);

	-- linearized 2D array that holds an estimate
	-- of the cost of moving box(bx) to goal(gx)
	-- in element cost( (bx-1)*ub+gx )
	gcost: munkres.iatype(1..nbmx*nbmx);



	nb: integer; --dynamically-defined #boxes
	ub: ushort; --dynamically-defined #boxes


procedure inithun(
	ivf,iff: vftype; 
	--ee:vustype;
	--pvalid: in  booltype;
	bvalid: in out booltype;
	numrows,numcols: ushort
	); --sets nb, ub, hff
--define [once] goalrow,goalcol (after read) & hunmatrix

procedure setboxes(ivf:vftype); -- preps (boxrow,boxcol) from current VF

-- ?dont call directly?
procedure getboxcost( r0: rowrng; c0: colrng );
-- define single hunmatrix entry at (r0,c0) using flood-fill
-- this represents the cost of moving a particular box
-- to any reachable position.


function evalpairings(
	ontgt: out integer; 
	ok: out boolean
	) return ushort; 
-- 1) define match arrays
-- 2) return minimum cost

--estimated cost of moving box bx to goal gx:
function getcost( bx, gx : boxrng ) return ushort;

--estimated cost of moving a box from (r0,c0) to (r1,c1):
function getcost(  
	r0: rowrng; c0: colrng;
	r1: rowrng; c1: colrng
) return ushort;

--find goal# to which box# bx is matched:
function getmatch(bx: boxrng) return boxrng;

procedure getBoxRc (bx: boxrng; r: out rowrng; c: out colrng);
procedure getGoalRc(gx: boxrng; r: out rowrng; c: out colrng);

function getBoxNum(br: rowrng; bc: colrng) return integer;


end emhungarian; --package
