-- $Id$
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--
--  Copyright (C) 2008.
--  Licensed under the terms of the GNU GPL, v2 or later.
--
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

function widget:GetInfo()
  return {
    name      = "CustomFormations2",
    desc      = "Allows you to draw your own formation line.",
    author    = "jK (Hungarian code written by gunblob) (Line attack/unload written by Niobium)",
    version   = "1.0",
    date      = "Jan 7th, 2009",
    license   = "GNU GPL, v2 or later",
    layer     = 10000,
    enabled   = true,
    handler   = true,
  }
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

--// user configurable
local maxHungarianUnits         = 19
local maxOptimizationUnits      = 75  --// above it will use the random algo
local maxOptimizationIterations = 600 --// break the optimization after a limited iterations and distribute the remaining units on free nodes

local desiredSFP = 1/20 --// the optimization shouldn't take longer than 1/20 seconds (else decrease the maxUnits for that algo)

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

local gl      = gl
local Spring  = Spring
local GiveOrderToUnit   = Spring.GiveOrderToUnit
local spGetUnitPosition = Spring.GetUnitPosition
local spGetCommandQueue = Spring.GetCommandQueue
local spGetMiniMapGeometry = Spring.GetMiniMapGeometry
local tinsert = table.insert
local tremove = table.remove
local rand    = math.random
local sqrt    = math.sqrt
local abs     = math.abs
local min     = math.min
local floor   = math.floor
local ceil    = math.ceil

local formationNodes = {}
local totaldxy = 0  --// moved mouse distance 

local dimmNodes = {}
local alphaDimm = 1

local inMinimap = false

local endShift = false
local activeCmdIndex = -1
local cmdTag = CMD.MOVE
local inButtonEvent = false  --//if you click the command menu the move/fight command is handled with left click instead of right one

local invertQueueKey = (Spring.GetConfigInt("InvertQueueKey", 0) == 1)

local CMD_JUMP = 38521

local spGetUnitIsTransporting = Spring.GetUnitIsTransporting

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-- Minimap functions

local function InMinimap(x,y)
  local posx,posy,sizex,sizey,minimized,maximized = spGetMiniMapGeometry()
  local rx,ry = (x-posx)/sizex,(y-posy)/sizey
  return (not (minimized or maximized)) and
         (rx>=0)and(rx<=1)and
         (ry>=0)and(ry<=1),rx,ry
end

local function MinimapToWorld(rx,ry)
  if (rx>=0)and(rx<=1)and
     (ry>=0)and(ry<=1)
  then
    local mapx,mapz = Game.mapSizeX*rx,Game.mapSizeZ-Game.mapSizeZ*ry
    local mapy = Spring.GetGroundHeight(mapx,mapz)
    return {mapx,mapy,mapz}
  else
    return {-1,-1,-1}
  end
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

local moveCmds = {
  [CMD.MOVE]=true,  [CMD.ATTACK]=true, [CMD.RECLAIM]=true,[CMD.RESTORE]=true,[CMD.RESURRECT]=true,
  [CMD.PATROL]=true,[CMD.CAPTURE]=true,[CMD.FIGHT]=true,  [CMD.DGUN]=true, [CMD_JUMP]=true, [CMD.UNLOAD_UNITS]=true,
}

function GetUnitPosition(unitID)
  local x,y,z = spGetUnitPosition(unitID)

  local cmds = spGetCommandQueue(unitID)
  if (cmds)and(cmds[1]) then
    for i=1,#cmds do
      local cmd = cmds[i]
      if (moveCmds[cmd.id])and(cmd.params[3]) then
        local params = cmd.params
        x,y,z = params[1],params[2],params[3]
      end
    end
  end

  return x,y,z
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

function widget:MousePress(x, y, button)
  local activeid
  endShift = false
  activeCmdIndex,activeid = Spring.GetActiveCommand()

  local _, _, meta = Spring.GetModKeyState() -- This is used only for the next line (Jason)
  inButtonEvent = (activeid) and ((meta and ((activeid==CMD.UNLOAD_UNITS) or (activeid==CMD.ATTACK))) or (activeid==CMD.PATROL) or (activeid==CMD.FIGHT) or (activeid==CMD.MOVE) or (activeid==CMD_JUMP)) and (button==1)

  if (inButtonEvent) or ((activeid==nil)and(button==3)) then

    local selcnt = Spring.GetSelectedUnitsCount()
    if ((selcnt>1) or (activeid==CMD.UNLOAD_UNITS)) then

      local _,defid    = Spring.GetDefaultCommand()
      cmdTag = activeid or defid   --// CMD.MOVE or CMD.FIGHT

      if (defid==CMD.MOVE) or (inButtonEvent) then
        local units = Spring.GetSelectedUnits()
        units.n = nil

        --// check if there are moveable units selected
        local moveableUnits = false
        for _,unitID in pairs(units) do
          local unitDefID = Spring.GetUnitDefID(unitID)
          if (((UnitDefs[unitDefID].canMove) and ((cmdTag==CMD.MOVE) or (cmdTag==CMD.FIGHT))) or
              ((UnitDefs[unitDefID].weapons.n~=0) and (cmdTag==CMD.ATTACK)) or
	      (cmdTag==CMD.UNLOAD_UNITS)) then moveableUnits = true; break; end
        end

        if (moveableUnits) then
          local rx,ry, pos
          inMinimap,rx,ry = InMinimap(x,y)
          if inMinimap then
            pos = MinimapToWorld(rx,ry)
          else
            _,pos = Spring.TraceScreenRay(x,y,true)
          end

          if (pos) then
            widgetHandler:UpdateWidgetCallIn("DrawInMiniMap", self)
            widgetHandler:UpdateWidgetCallIn("DrawWorld", self)
            table.insert(formationNodes,pos)
            totaldxy = 0
            return true
          end
        end
      end
    end
  end

  return false
end


function widget:MouseMove(x, y, dx, dy, button)
  if ((inButtonEvent)and(button==3)) or
     ((not inButtonEvent)and(button~=3))
  then
    return false
  end

  if (#formationNodes>0) then
    if (totaldxy>40) then
      if (inMinimap) then
        local inMinimap,rx,ry = InMinimap(x,y)
        if inMinimap then
          table.insert(formationNodes,MinimapToWorld(rx,ry))
          totaldxy = 0
        end
      else
        local _,pos = Spring.TraceScreenRay(x,y,true)
        if (pos) then
          table.insert(formationNodes,pos)
          totaldxy = 0
        end
      end
    end

    if (inMinimap) then
      local _,_,sizex,sizey = spGetMiniMapGeometry()
      totaldxy = totaldxy + (dx*dx)*1024/sizex + (dy*dy)*1024/sizey
    else
      totaldxy = totaldxy + (dx*dx) + (dy*dy)
    end
  end

  return false
end


function widget:MouseRelease(x, y, button)
  --// create modkeystate list
  --// (keyState is for GiveOrder and keyState2 is for CommandNotify)
  local alt, ctrl, meta, shift = Spring.GetModKeyState()
  if (Spring.GetInvertQueueKey()) then
    shift = not shift
    -- check for immediate mode mouse 'rocker' gestures
    local x, y, b1, b2, b3 = Spring.GetMouseState()
    if (((button == 1) and b3) or
        ((button == 3) and b1)) then
      shift = false
    end
  end
  local keyState,keyState2 = {},{coded=0,alt=false,ctrl=false,shift=false,right=false}    
  if alt   then table.insert(keyState,"alt");   keyState2.alt =true;  end
  if ctrl  then table.insert(keyState,"ctrl");  keyState2.ctrl=true;  end
  if meta  then table.insert(keyState,"meta")                         end
  if shift then table.insert(keyState,"shift"); keyState2.shift=true  end
  if (not inButtonEvent) then                   keyState2.right=true; end

  --// calc the "coded" number of keyState2
  if keyState2.alt   then keyState2.coded = keyState2.coded + CMD.OPT_ALT   end
  if keyState2.ctrl  then keyState2.coded = keyState2.coded + CMD.OPT_CTRL  end
  if keyState2.shift then keyState2.coded = keyState2.coded + CMD.OPT_SHIFT end
  if keyState2.right then keyState2.coded = keyState2.coded + CMD.OPT_RIGHT end

  --// end button event (user clicked command menu)
  if (inButtonEvent) then
    Spring.SetActiveCommand(-1)
  end

  --// single click? (no line drawn)
  if (#formationNodes==1) then

    --// check if some widgets want to stop the command
    local retval = widgetHandler:CommandNotify(cmdTag, formationNodes[1], keyState2) or false
    if (retval) then
      formationNodes = {}
      return -1
    end

    Spring.GiveOrder(cmdTag, formationNodes[1], keyState)
    formationNodes = {}
    if (keyState2.shift)and(activeCmdIndex>-1) then
      endShift = true
      return activeCmdIndex
    end
    return -1
  end

  --// spread units out
  if (#formationNodes>0) then
    if inMinimap then
      local inMinimap,rx,ry = InMinimap(x,y)
      if inMinimap then
        table.insert(formationNodes,MinimapToWorld(rx,ry))
      end
    else
      local _,pos = Spring.TraceScreenRay(x,y,true)
      if (pos) then
        table.insert(formationNodes,pos)
        totaldxy = 0
      end
    end

    if (cmdTag==CMD.UNLOAD_UNITS) then

      local selunits = Spring.GetSelectedUnits()
	local transports = {}
	local intrans = {}
	local totalunits = 0
	
	for _,unitID in ipairs(selunits) do
	  intrans = spGetUnitIsTransporting(unitID)
	  
        if (intrans.n~=0) then
		tinsert(transports, unitID)
	      totalunits = totalunits + #intrans
	  end
      end

	--Spring.Echo("Total units: " .. totalunits .. " in " .. #transports .. " transports")
      
      if (totalunits~=0) then

	  local unloadpoints = GetInterpolatedNodes(formationNodes,totalunits)
	  local currpoint = 1

        for _,transID in ipairs(transports) do
	    intrans = spGetUnitIsTransporting(transID) -- this should be removed, we shouldve had another column in table with results from last time
          
          GiveOrderToUnit(transID, CMD.UNLOAD_UNIT, unloadpoints[currpoint], keyState)
	    currpoint = currpoint + 1

	    if (keyState2.shift==false) then
	      tinsert(keyState, "shift")
          end

	    if (#intrans>1) then
	      for unit=2,#intrans do
              GiveOrderToUnit(transID, CMD.UNLOAD_UNIT, unloadpoints[currpoint], keyState)
	        currpoint = currpoint + 1
	      end
	    end

	    if (keyState2.shift==false) then
	      tremove(keyState, keyState.n)
          end
	  end
      end
      
    else -- CMD.ATTACK / CMD.FIGHT / CMD.MOVE -- All similar.

      local units  = Spring.GetSelectedUnitsSorted()
      units.n = nil

      --// count moveable units
      local selectedMobileUnits = {}
      local movunits = 0
      for unitDefID,unitIDs in pairs(units) do
        if (((UnitDefs[unitDefID].canMove) and ((cmdTag==CMD.MOVE) or (cmdTag==CMD.FIGHT))) or
            ((UnitDefs[unitDefID].weapons.n~=0) and (cmdTag==CMD.ATTACK))) then

          movunits = movunits + #unitIDs
          for i=1,#unitIDs do
            tinsert(selectedMobileUnits,unitIDs[i])
          end
       end
      end

      if (movunits>0) then
        local interNodes = GetInterpolatedNodes(formationNodes,movunits)

        if (not keyState2.alt)and(#selectedMobileUnits<maxOptimizationUnits) then
          if (#selectedMobileUnits<maxHungarianUnits) then
            SendOrdersHungarian(interNodes,selectedMobileUnits,keyState)
          else
            SendOrdersOptimized(interNodes,selectedMobileUnits,keyState)
          end
        else
          SendOrdersRandom(interNodes,selectedMobileUnits,keyState)
        end
      end
    end

    dimmNodes = formationNodes
    alphaDimm = 1
    formationNodes = {}

    if (keyState2.shift)and(activeCmdIndex>-1) then
      endShift = true
      return activeCmdIndex
    end
  end
  
  return -1
end


function widget:KeyRelease(key)
  if (key==304)and(endShift) then
    endShift = false
    Spring.SetActiveCommand(-1)
    return true
  end
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

local glVertex = gl.Vertex
local glLineStipple = gl.LineStipple
local glLineWidth   = gl.LineWidth
local glColor       = gl.Color
local glBeginEnd    = gl.BeginEnd
local GL_LINE_STRIP = GL.LINE_STRIP

local DrawFormationLine = function(dimmNodes)
  for _,v in pairs(dimmNodes) do
    glVertex(v[1],v[2],v[3])
  end
end

local DrawMinimapFormationLine = function(dimmNodes)
  for _,v in pairs(dimmNodes) do
    glVertex(v[1],v[3],1)
  end
end

local CommandColor = function(alpha)

  if (cmdTag==CMD.MOVE) then
    glColor(0.5,1,0.5,alpha)
  else
    if (cmdTag==CMD.UNLOAD_UNITS) then
      glColor(1,1,0.5,alpha)
    else
      if (cmdTag==CMD.ATTACK) then
        glColor(1,0.5,0.5,alpha) -- pink
      else
        glColor(0.5,0.5,1,alpha)
      end
    end
  end
end

function widget:DrawWorld()
  if (#formationNodes<1)and(#dimmNodes<1) then
    widgetHandler:RemoveWidgetCallIn("DrawWorld", self)
    return
  end

  --// draw the lines
  glLineStipple(2, 4095)
  glLineWidth(2.0)

  CommandColor(1)

  glBeginEnd(GL_LINE_STRIP, DrawFormationLine, formationNodes)

  if (#dimmNodes>1) then

    CommandColor(alphaDimm)

    glBeginEnd(GL_LINE_STRIP, DrawFormationLine, dimmNodes)
    alphaDimm = alphaDimm - 0.03
    if (alphaDimm<=0) then dimmNodes = {} end
  end

  glColor(1,1,1,1)
  glLineWidth(1.0)
  glLineStipple(false)
end


function widget:DrawInMiniMap()
  if (#formationNodes<1)and(#dimmNodes<1) then
    widgetHandler:RemoveWidgetCallIn("DrawInMiniMap", self)
    return
  end

  --// draw the lines
  glLineStipple(1, 4095)
  glLineWidth(2.0)

  CommandColor(1)

  gl.PushMatrix()
  gl.LoadIdentity()
  gl.Translate(0,1,0)
  gl.Scale(1/Game.mapSizeX,-1/Game.mapSizeZ,1)

  glBeginEnd(GL_LINE_STRIP, DrawMinimapFormationLine, formationNodes)

  if (#dimmNodes>1) then
    CommandColor(alphaDimm)

    glBeginEnd(GL_LINE_STRIP, DrawMinimapFormationLine, dimmNodes)
    alphaDimm = alphaDimm - 0.03
    if (alphaDimm<=0) then dimmNodes = {} end
  end

  gl.PopMatrix()

  glColor(1,1,1,1)
  glLineWidth(1.0)
  glLineStipple(false)
end




---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
----   «Interpolate drawn line nodes»                                                                ----
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------

function GetInterpolatedNodes(nodes,totalUnits)
  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- detect formation line length

  local length = 0
  for i=2,#nodes do
    local lv = nodes[i-1]
    local v  = nodes[i]
    local dlx,dlz = lv[1]-v[1],lv[3]-v[3]
    length = length + sqrt( dlx*dlx + dlz*dlz )
  end

  local unitdist = length / (totalUnits-1)   --// movunits == 1 -> x/0 -> math.huge  , no segm ;)
  local idx,idxLength = 1,0
  local interpolatedNodes = {nodes[1]}

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- determine unit positions on the line

  repeat
    for i=idx+1,#nodes+1 do
      if (i>#nodes) then
        idx = #nodes
        if (#interpolatedNodes<totalUnits) then
          tinsert(interpolatedNodes,nodes[idx])
        end
        break
      end
      local lv = nodes[i-1]
      local v  = nodes[i]
      local dlx,dly,dlz = lv[1]-v[1], lv[2]-v[2], lv[3]-v[3]
      local dl = sqrt( dlx*dlx + dlz*dlz )
      local bfr_idxLength = idxLength + dl

      local rel_dist = unitdist-bfr_idxLength

      if (rel_dist==0) then
        idxLength = 0
        idx = i
        tinsert(interpolatedNodes,nodes[i])
        break
      end
      if (rel_dist<0) then
        local fracLength = unitdist - idxLength
        local frac = fracLength/dl

        --// add an in-between node
        local inBetween = {lv[1]-frac*dlx, lv[2]-frac*dly, lv[3]-frac*dlz}
        tinsert(nodes,i,inBetween)

        idxLength = 0
        idx = i
        tinsert(interpolatedNodes,inBetween)
        break
      end

      idxLength = bfr_idxLength
    end
  until (idx >= #nodes)

  return interpolatedNodes
end --// end function GetInterpolatedNodes()






---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
----   «Different Linear Optimization Algorithms»                                                    ----
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
-- following algos:
--
--  SendOrdersRandom()
--  SendOrdersOptimized()
--  SendOrdersHungarian()
--

function SendOrdersRandom(nodes,units,keyState)
  ----------------------------------------------------------------------
  ----------------------------------------------------------------------
  -- the next code doesn't do any optimization at all,
  -- it simply gives each unit a random waypoint
  ----------------------------------------------------------------------
  ----------------------------------------------------------------------

  --// send orders
  for n=1,#nodes do
    local m = rand(1,#units)
    local unitID = units[m]
    local pos  = nodes[n]
    GiveOrderToUnit(unitID, cmdTag, pos, keyState)
    tremove(units,m)
  end
end --// end function SendOrdersRandom()



function SendOrdersOptimized(nodes,units,keyState)
  -------------------------------------------------------------------------------------
  -------------------------------------------------------------------------------------
  -- the next code tries to optimize the total movement length (not optimal, but fast)
  -------------------------------------------------------------------------------------
  -------------------------------------------------------------------------------------

  --// (tip: from now on "i" should index an unit var and "n" a formation node var)

  local t = os.clock()

  --// cache unit positions
  for i=1,#units do
    local unitID = units[i]
    units[i]={id=unitID, pos={GetUnitPosition(unitID)}}
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- 1. make array with all desired unit positions and
  --    add each unit to its nearest node

  local formationsNodesN = #nodes
  local sortFormation = {}
  for n=1,#nodes do sortFormation[n] = {} end

  for i=1,#units do
    local unit  = units[i]
    local ux,uz = unit.pos[1],unit.pos[3]
    local dist  = math.huge
    local nearest_n = -1
    unit.dists = {}
    for n=1,#nodes do
      local nn      = n*0.5
      if (n%2<1) then nn=ceil(nn) else nn=formationsNodesN-floor(nn) end --// this is faster!!!
      local pos     = nodes[nn]
      local px,pz   = pos[1],pos[3]
      local dlx,dlz = px-ux,pz-uz
      local dl      = sqrt(dlx*dlx + dlz*dlz)
      for m=1,min(#(unit.dists)+1,30) do --// save the 30 best nodes for this unit
        if (not unit.dists[m])or(unit.dists[m].dist>dl) then
          tinsert( unit.dists , m, {n=nn,dist=dl})
          break
        end
      end
    end
    for m=31,#(unit.dists) do
      tremove( unit.dists , m)
    end
    unit.n = 1
    tinsert( sortFormation[unit.dists[1].n] , unit)
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- some desired unit positions are now double (or more) used, so ..
  -- 2. try to optimize the formation (try to reduce the overall walk distances)

  local SearchNewNextNodes = function(unit)
    --// unit = { pos={vec3}, n=used_dists_n, dists={[1]={n=int,dist=float} }
    local currentDist,distsN = unit.dists[unit.n].dist,#(unit.dists)
    local maxNodes = distsN+30
    local ux,uz = unit.pos[1],unit.pos[3]
    for n=1,#nodes do
      local nn      = n*0.5; if (n%2<1) then nn=ceil(nn) else nn=formationsNodesN-floor(nn) end --// this is faster!!!
      local pos     = nodes[nn]; local px,pz = pos[1],pos[3]; local dlx,dlz = px-ux,pz-uz; local dl = sqrt(dlx*dlx + dlz*dlz)
      for m=1,min(#(unit.dists)+1,maxNodes) do --// save the 30 best nodes for this unit
        if ((not unit.dists[m])or(unit.dists[m].dist>dl))and(dl>currentDist) then
          tinsert( unit.dists , m, {n=nn,dist=dl}); break
        end
      end
    end
    for m=maxNodes+1,#(unit.dists) do
      tremove( unit.dists , m)
    end
  end

  local max_repeat,idx = maxOptimizationIterations
  repeat
    idx=0
    --// find next multi used node
    for n=1,#sortFormation do 
      local nn = 0
      if (max_repeat%2<1) then nn=math.ceil(n*0.5) else nn=#sortFormation-math.floor(n*0.5) end
      if (#(sortFormation[n])>1) then
        idx=n
        break
      end
    end
    --// try to solve the multi usage
    if (idx>0) then
      local v = sortFormation[idx]

      --// determine which unit would suffer at least, if it takes another node
      local worst_dist = 0
      local ignore = 1 --// this is the unit, which should stay on that node
      for i=1,#v do
        local unit      = v[i]
        local next_node = unit.dists[unit.n+1]
        if (not next_node) then
          SearchNewNextNodes(unit)
          next_node = unit.dists[unit.n+1]
        end
        if (next_node)and(next_node.dist>worst_dist) then
          worst_dist = next_node.dist
          ignore     = i
        end
      end

      --// move all units to their >next< best node, except one
      for i=1,#v do
        if (i~=ignore) then
          local unit      = v[i]
          unit.n          = unit.n+1
          local next_node = unit.dists[unit.n]
          tinsert(sortFormation[next_node.n],unit)
        end
      end

      --// clean node unit list, so only 1 units stays there
      sortFormation[idx] = {v[ignore]}
    end
    max_repeat = max_repeat - 1
  until (idx==0)or(max_repeat<0)

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- 'cus we cut the optimize loop after some passes (->max_repeat),
  --  we can't be 100% that there aren't any multi usages left.
  --  so we solve the rest with a not optimized algo

  local freeNodes = {}
  for n=1,#sortFormation do
    if (#sortFormation[n]==0) then
      tinsert(freeNodes,n)
    end
  end
  local freeNodesN = #freeNodes
  for n=1,#sortFormation do 
    if (#sortFormation[n]>1) then
      local beforeN = #sortFormation[n]
      for m=#sortFormation[n],2,-1 do
        tinsert(sortFormation[ freeNodes[freeNodesN] ],sortFormation[n][m])
        tremove(sortFormation[n],m)
        freeNodesN = freeNodesN -1
      end
    end
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- send orders

  for n=1,#sortFormation do
    local unit = sortFormation[n][1]
    local pos  = nodes[n]
    GiveOrderToUnit(unit.id, cmdTag, pos, keyState)
  end


  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- determine needed time and optimize the maxUnits limit

  if (rand(0,2)==2) then
    local delay = os.clock()-t
    if (delay>desiredSFP) then
      maxOptimizationUnits=maxOptimizationUnits-1
    elseif (delay<(desiredSFP*0.8))and(#units>maxOptimizationUnits*0.95) then
      maxOptimizationUnits=maxOptimizationUnits+1
    end
  end
end --// end function SendOrdersOptimized()




function SendOrdersHungarian(nodes,units,keyState)
  -------------------------------------------------------------------------------------
  -------------------------------------------------------------------------------------
  -- (the following code is written by gunblob)
  --   this code finds the optimal solution (slow, but effective!)
  --   it uses the hungarian algorithm from http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html
  --   if this violates gpl license please let gunblob and me know
  -------------------------------------------------------------------------------------
  -------------------------------------------------------------------------------------
  local t = os.clock()

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- cache node<->unit distances

  local distances = {}
  for n=1,#nodes do distances[n]={} end

  for i=1,#units do
    local unitID = units[i]
    local thisDistances = {}
    local ux, _, uz = GetUnitPosition(unitID)
    for n=1,#nodes do
      local nodePos   = nodes[n]
      local dx,dz     = (nodePos[1]-ux),(nodePos[3]-uz)
      distances[n][i] = dx*dx+dz*dz
    end
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- find optimal solution and send orders

  local result = findHungarian(distances)
  for j=1,#result do
    local pair = result[j]
    GiveOrderToUnit(units[pair[2]], cmdTag, nodes[pair[1]], keyState)
  end

  --------------------------------------------------------------------------------------------
  --------------------------------------------------------------------------------------------
  -- determine needed time and optimize the maxUnits limit

  if (rand(0,2)==2) then
    local delay = os.clock()-t
    if (delay>desiredSFP) then
      maxHungarianUnits=maxHungarianUnits-1
    elseif (delay<(desiredSFP*0.8))and(#units>maxHungarianUnits*0.95) then
      maxHungarianUnits=maxHungarianUnits+1
    end
  end
end --// end function SendOrdersHungarian()


function findHungarian(array)
  local starmask = {}
  local colcover = {}
  local rowcover = {}

  for i=1,#array do
    starmask[i] = {}
    rowcover[i] = false
    for j=1,#(array[i]) do
      starmask[i][j] = 0
      colcover[j]    = false
    end
  end

  subMinimumFromRows(array)
  starZeroes(array, starmask)
  return stepCoverStarCol(array, starmask, colcover, rowcover)
end


function subMinimumFromRows(array)
  for i,list in ipairs(array) do
    local min = math.huge
    for j,val in ipairs(list) do
      if val < min then
        min = val
      end
    end
    for j,_ in ipairs(list) do
      list[j] = list[j] - min
    end
  end
end

function starZeroes(array, starmask)
  for i,list in ipairs(array) do
    for j, val in ipairs(list) do
      if val == 0 then
        maybeStar(starmask, i, j)
      end
    end
  end
end

function maybeStar(starmask, row, col)
  for i,_ in ipairs(starmask) do
    if starmask[i][col] == 1 then
      return
    end
  end
  for j,val in ipairs(starmask[row]) do
    if val == 1 then
      return
    end
  end
  starmask[row][col] = 1
end

function stepCoverStarCol(array, starmask, colcover, rowcover)
  coverStarCol(starmask, colcover)
  if allCovered(colcover) then
    return returnStarPositions(starmask)
  else
    return stepPrimeZeroes(array, starmask, colcover, rowcover)
  end
end

function coverStarCol(starmask, colcover)
  for i,list in ipairs(starmask) do
    for j,val in ipairs(list) do
      if starmask[i][j] == 1 then
        colcover[j] = true
      end
    end
  end
end

function allCovered(colcover)
  for _,val in ipairs(colcover) do
    if not val then
      return false
    end
  end
  return true
end

function returnStarPositions(starmask)
  local positions = {}
  for i,list in ipairs(starmask) do
    for j,val in ipairs(list) do
      if val == 1 then
        tinsert(positions, {i, j})
      end
    end
  end
  return positions
end

function stepPrimeZeroes(array, starmask, colcover, rowcover)
  for i,list in ipairs(array) do
    for j,val in ipairs(list) do
      if not colcover[j] and not rowcover[i] and val == 0 then
        starmask[i][j] = 2
        local starpos = findStarInRow(starmask, i)
        if starpos then
          rowcover[i] = true
          colcover[starpos] = false
        else
          return stepFiveStar(array,starmask,colcover,rowcover, {}, {{i,j}}, i,j)
        end
      end
    end
  end

  adjustValue(array,colcover,rowcover)
  return stepPrimeZeroes(array,starmask,colcover,rowcover)
end

function findStarInRow(starmask, row)
  for j,val in ipairs(starmask[row]) do
    if val == 1 then
      return j
    end
  end
  return nil
end

function adjustValue(array, colcover, rowcover)
  local min = math.huge
  for i,list in ipairs(array) do
    for j,val in ipairs(list) do
      if not colcover[j] and not rowcover[i] then
        if val < min then
          min = val
        end
      end
    end
  end
  for i,list in ipairs(array) do
    if rowcover[i] then
      for j,_ in ipairs(list) do
        list[j] = list[j] + min
      end
    end
  end
  for j,_ in ipairs(array[1]) do
    if not colcover[j] then
      for i,list in ipairs(array) do
        list[j] = list[j] - min
      end
    end
  end
end

function stepFiveStar(array,starmask,colcover,rowcover,stars,primes,row,col)
  local starrow = nil
  for i,list in ipairs(starmask) do
    if list[col] == 1 then
      starrow = i
      break
    end
  end
  if starrow then
    tinsert(stars, {starrow, col})
    return stepFivePrime(array,starmask,colcover,rowcover,stars,primes,starrow,col)
  else
    return stepFiveLast(array,starmask,colcover,rowcover,stars,primes)
  end
end

function stepFivePrime(array,starmask,colcover,rowcover,stars,primes,row,col)
  local primecol = nil
  for j,_ in ipairs(starmask) do
    if starmask[row][j] == 2 then
      primecol = j
      break
    end
  end
  if primecol then
    tinsert(primes, {row, primecol})
    return stepFiveStar(array,starmask,colcover,rowcover,stars,primes,row,primecol)
  else
    return stepFiveLast(array,starmask,colcover,rowcover,stars,primes)
  end
end

function stepFiveLast(array,starmask,colcover,rowcover,stars,primes)
  for _,pos in ipairs(stars) do
    starmask[pos[1]][pos[2]] = 0
  end
  for _,pos in ipairs(primes) do
    starmask[pos[1]][pos[2]] = 1
  end
  for i,list in ipairs(starmask) do
    for j,val in ipairs(list) do
      if val == 2 then
        list[j] = 0
      end
    end
  end
  for j,_ in ipairs(colcover) do
    colcover[j] = false
  end
  for i,_ in ipairs(rowcover) do
    rowcover[i] = false
  end
  return stepCoverStarCol(array, starmask,colcover,rowcover)
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------