--[[ nef_20230307  djikstra path finder
      
As coded the primary function is called as a coroutine with the function as follows:

  game.min_path;   but could be changed to anything suitable.
  
The initial resume requires TWO ARGUMENTS to start the search.  These are:

context     - a table of named parameters
    edger       - user supplied method defining the 'edge' length from one
                  tile to the next. Supplied  with arguments :
                  
                  (self, distance, current_tile, neighbour_tile). 
                  
                  Distance is the distance the current_tile is from the
                  origin. Return value is the length of the edge.
                  nil/false indicates no connection.  Being a method the
                  function can use the context table for reference material.
                  Generally, the edger should NOT alter any state vector.
                  (The combination of current_tile and neighbour_tile will
                  be unique but individually they are not.)
                       Mandatory.
    terminator  - user supplied method defining termination events. 
                  Supplied  with arguments: 
                  
                  (self, distance, current_tile). 
                  
                  The return value will become the return value of min_path 
                  (usually the total distance). nil or false means the search
                  will continue (provided there are still tiles to search: 
                  min_path will return nil if there are no more  tiles to
                  search). Being a method the function can use the context
                  table for reference material. The method MAY alter a state
                  vector (with care) irrespective of return value.
                       Mandatory.
    manhatten   - conditional choosing the walk:
                  false = Chebyshev (Adjacent),
                  true  = Manhatten (Cadjacent).
                       Default = nil (= false).
    lower_bound - conditional defining how to
                  convert edge lengths to integers
                  false = math.ceil
                  true  = math.floor
                       Default = nil (= false).
    start       - if the argument tile is a Tile (i.e. not a table), this value
                  will be used as the 'distance' of that tile.
                       Default = 0.
tile        - the start tile (Tile userdata), OR a (Lua) table with fields
              {key = Tile, value = distance of the Tile from the hypothetical
              origin}.  If a Tile is used then the terminator will NOT be called
              to examine this tile .
               
Return value of min_path is the return value from the call to terminator that
terminates the search. This will typically be the minimun path length from the
start tile(s) to the destination as defined by the arguments and parameters; or
nil/false if there is no path. 

The second return value is an iterate function that will create the three values
used for a 'generic' for loop.  It takes one arguemnt - the tile used to start
the search. If the first value is not nil/false then this argumant will default
to the tile the terminator was called with. The iterator function used in the for
loop will give two return values: 1 - the tile; 2 - the distance of that tile
from the origin.  The order of the tiles returned is 2nd last to first.  The last
tile can be recorded by the terminator (or by intercepting the third return value
of the iterate function (the initial 'index') if the argument was allowed to
default.  Preseving the iterate function (in a variable) - or the second return
value (the 'state') is sufficient to preserve the trace back history even if the
pathfinder is reused for other purposes.

The parameters manhatten, lower_bound are conditionals with default values
the most likely used (and therefore can be simply omitted).

Edge values should be integer (or integer valued floats). If floats are used they
WILL BE CONVERTED TO INTEGERS. If fractions are needed (e.g. with roads) then use
a scaling factor such as move_frags.

The package itself can be renamed so one could have multiple for special purposes
but the options listed should cater to most requirements allowing the declaration
of just the one package even if used for multiple purposes.  In particular, since
a coroutine is used, additional threads can be created and these will be
independent of each other.

If min_path returns a non nil/false value then the coroutine can be resumed. In
this case the search will be resumed until the next termination event. This can
be repeated until nil/false is returned.  This is an alternative to the creative
use of the terminator. (I.e. have the terminator record the details of the interim
results but allow the search to continue until there are no more tiles left.)                 ]]

do
 local rawget, next, assert,      min,      max, yield,           type =
       rawget, next, assert, math.min, math.max, coroutine.yield, tolua.type
 local _ENV, _G =
       _ENV, _G
        
 local select_next, check_nears, queue_tile, tracer, q_MT
 
 select_next = function (distance);  -- the split with check_nears allows alternate
   if not rawget(queue, distance)    -- entry points; tail calls make these 
   then  distance = next(queue)      -- functions sequential (not stacked)
         if   distance 
         then for new in next, queue, distance do distance = min(distance, new) end
         else return nil, function (site) return tracer, _ENV, site end -- no tiles
         end
   end
   
   local tile, prior = next (queue [distance])  -- must be gravid - see metamethods
   trace [tile] = prior; queue (distance, tile) -- 'visit'
   local path = context:terminator (distance, tile)
   if path then yield (path, function(site) return tracer,_ENV,site or tile end) end
   return check_nears(distance, tile)
               end; 
               
 check_nears = function (distance, prior)
   for new_tile in prior:circle_iterate (context.manhatten and 1 or 2) 
   do  local old = tiles [new_tile]
       if not old or old > distance then  
          local step = context:edger (distance, prior, new_tile) 
          if step then 
             step = distance + max (0, mathint(step))
             if not old or old > step 
             then queue_tile(new_tile,step,prior, old)
             end  -- else leave it where it is
          end
       end              
   end; return select_next (distance)
               end;
 queue_tile =  function (tile, distance, prior, old)
   tiles [tile], queue [distance] [tile] = distance, prior
   return old and queue (old, tile)
               end;
 q_MT = {   -- ensure the group is gravid if it exists
   __index = function(t,k) t[k] = {} return t[k] end;
   __call  = function(t,k,v) t[k][v] = nil;if not next(t[k]) then t[k] = nil end end;
        };
 tracer     =  function(_ENV, tile) tile = trace [tile]
       if type(tile) == 'Tile' then return tile, tiles [tile] end
               end;
 game.min_path = function (context, origin,  test)
     assert(type(context) == 'table','Context not a table.')
     _ENV        = {
       context = context; 
       queue   = _G. setmetatable({},q_MT); -- key = distance; value = table (group)
                                      -- (group) key = tile; value = tile (prior)
       trace   = {};                        -- key = tile; value = tile (prior)
       tiles   = {};                        -- key = tile; value = distance
       mathint = _G.math[context.lower_bound and 'floor' or 'ceil'];
       test    = test;
                   }
     
  --[[ the 'prior' value for initial queue_tiles can be anything other
       than a Tile OR nil ]]
     local  path, distance, tile
     if     type (origin) == 'Tile'  
     then   tile     = origin
            distance = context.start or 0
            queue_tile (tile, distance, true)
            trace [tile] = queue [distance][tile]; queue (distance, tile)
            return check_nears(distance, tile)
     elseif type (origin) == "table"
     then   tile, distance = next(origin)
            assert(type(tile)=='Tile','Table starts with a non tile')
            queue_tile(tile, distance, true)
            for tile, new in next, origin, tile
            do  assert(type(tile)=='Tile','Table start includes non tile')
                queue_tile(tile, new, true) 
                distance = min(distance, new)
            end
            return select_next (distance)
     else   assert(nil,'Origin not a tile or table.')
     end
                 end;
end  -- end block