--
-- $Header: /Users/dap/lua/RCS/HanoiPageIO_async.lua,v 1.1 2007/02/11 11:10:12 dap Exp $
--
-- Hanoi - Towers of Hanoi diversion
--
-- Author (a) 2007, Damon A Permezel.  All bugs revered.
--
-- a) See if we can subclass HanoiPageIO in a manner that allows
-- b) async scheduling of the moveRings
--

module(..., package.seeall)

local Hanoi = require"HanoiPageIO":subclass {}
local Worker = OO.class {}
local Lock   = OO.class {}
local hanoi     -- file scope copy of the current instance
local idle = {}
local runq = {}

function Lock:init()
   self.owner = nil
   self.waitq = {}
   self.name  = self.name or '**gok'
end

local flyLock = Lock:new { name = 'flyLock' }

-- FIFO queueing discipline

local function enq(q, elem) table.insert(q, 1, elem) end
local function deq(q) return table.remove(q) end

function Worker:init()
   self.coro = coroutine.create(function ()
				   local my = self
				   my:work()
				end)
   self:resume()
end

function Worker:idle()
   enq(idle, self)
   coroutine.yield()
end

function Worker:work()
   while not self.dead do
      self:idle()
      while self.task do
	 local t = self.task
	 self.task = nil
	 t:perform(self)
      end
   end
end

-- assign: called by main thread to allocate a worker for a task

function Worker.assign(task)
   local sucker = deq(idle)

   while not sucker do
      -- call scheduler to run some tasks
      Worker.sched()
      sucker = deq(idle)
   end
   sucker.task = task -- some object with a perform() method
   return sucker
end

function Worker:sched()
   if self then
      -- called by a Worker instance, not necessarily running
      enq(runq, self)

      if (coroutine.running()) then
	 coroutine.yield()
      end
   else
      local grunt = deq(runq)
      grunt:resume()
   end
end

function Worker:resume()
   local res, errs = coroutine.resume(self.coro)

   if res == false then
      p = require'ScratchIO':new{}
      p:out('sched: resume returns false')
      p:out('%s', errs)

      assert(res)
   end
end

function Worker:lock(lck)
   --
   -- we can call this on the main path.  This, according to a bad design,
   -- is not a coroutine, and thus cannot yield.  We cannot get everything off
   -- the main thread, so we have to kluge things.  If we are calling wrk:lock()
   -- on the main thread, all we  we cannot make progress until we can
   -- record the lock for the wrk, as we are arranging for the worker
   -- to be run with the lock owned.
   -- 
   -- If we wish to preserve the to:push(from:pop()) paradigm from the
   -- super-class, we need to get this right.  from:pop() returns a Ring
   -- with a Worker allocated and with the from.lock held.
   --

   if not coroutine.running() then
      while lck.owner do
	 Worker.sched()
      end
   else
      while lck.owner do
	 enq(lck.waitq, self)

	 coroutine.yield()
      end
   end

   lck.owner = self
end

function Worker:unlock(lck, yield)
   assert(coroutine.running() or false)
   assert(lck.owner == self)

   lck.owner = nil

   grunt = deq(lck.waitq)

   if grunt then enq(runq, grunt) end
   if yield then self:sched() end
end

-- init - initialise a Hanoi object instance
function Hanoi:init()
   hanoi = self -- XXX

   Hanoi:super().init(self)
end

--
-- run - perform the Towers of Hanoi algorithm
-- need to override this so we can sched workers.  otherwise, no work
-- gets done!
--
function Hanoi:run()
   Hanoi:super().run(self)

   while runq[1] do Worker.sched() end
end

--
-- resetPoles - need newimplementation of Poles and Rings
--
function Hanoi:resetPoles()
   local n = self.nRings
   local off = 1		-- border width
   local delta = 1 + n + 1 + n	-- base separation

   -- establish the work pool: really only need 2, I think
   for i = 1, n do
      Worker:new {
	 ident = i,
	 hanoi = self,
      }
   end

   local Pole = OO.class {
      floor  = self.baseRow,
      flyRow = self.flyRow,
   }

   function Pole:init()
      self.rows  = {}
      self.depth = 0
      self.lock = Lock:new{ name = self.name or '**gok' }
   end

   --
   -- pop - arrange to remove the ring from the pole
   --
   -- This is called by the main thread.  We can be blocked here
   -- waiting for resources.
   --
   function Pole:pop()
      local wrk = Worker.assign(self)

      wrk:lock(self.lock)

      ring = table.remove(self.rows)

      ring.fromPole = self
      ring.toPole   = nil

      wrk.ring = ring
      ring.wrk = wrk

      return ring
   end

   --
   -- After we have allocated a worker for the ring, we are called
   -- here to record the target pole
   --
   function Pole:push(ring)
      ring.wrk:lock(self.lock)
      ring.toPole = self
      ring.wrk:sched()
   end

   function Pole:perform(wrk)
      self:dance(wrk)
   end

   -- couldn't resist.
   function Pole:dance(grunt)
      --
      -- the grunt is a worker thread.
      -- items of interest to us are:
      --    fromPole - must match
      --      toPole - should not be nil
      --        ring - the ring to use
      --
      -- The grunt must hold the pole locks
      --
      local ring = grunt.ring

      assert(self.lock.owner == grunt)
      assert(ring.fromPole == self)
      assert(ring.toPole)
      assert(ring.toPole.lock.owner == grunt)

      -- float up off the pole
      ring:toRow(self.flyRow+1)

      ring.onPole = nil
      self.floor  = self.floor + 1
      self.depth  = self.depth - 1

      -- need the fly lock to move to the fly row
      -- need both the fly lock and the target pole lock
      -- cannot release source pole lock until we move to the fly row.

      grunt:lock(flyLock)
      ring:toRow(self.flyRow)
      grunt:unlock(self.lock, true)

      --
      -- WARNING!!! I really am being intentionally schizoid here
      --

      self = ring.toPole	-- sic!  not sick!

      -- holding the locks, we can fly over to the toPole
      ring:toCol(self.col)

      -- get rid of flyLock as soon as possible
      ring:toRow(self.flyRow+1)
      grunt:unlock(flyLock, true)

      table.insert(self.rows, ring)
      ring.pole  = self
      self.depth = self.depth + 1

      ring:toRow(self.floor)

      self.floor = self.floor - 1
      ring.last  = nil
      ring.wrk   = nil
      grunt.ring = nil

      grunt:unlock(self.lock)
   end

   --
   -- we can no longer just push nascent rings onto the pole
   --
   function Pole:populate(ring)
      local Staff = Pole:subclass {
	 name = 'staff',
	 pole = self
      }

      function Staff:perform(wrk)
	 local ring = wrk.ring

	 self = self.pole -- OK, we are getting schizoid again

	 ring:toCol(self.col)
	 table.insert(self.rows, ring)
	 ring.pole  = self
	 self.depth = self.depth + 1

	 ring:toRow(self.floor)

	 self.floor = self.floor - 1
	 ring.last  = nil

	 wrk:unlock(self.lock)
      end
	 
      ring.toPole = self
      local wrk = Worker.assign(Staff:new())

      wrk:lock(self.lock)
      wrk.ring = ring
      wrk:sched()
   end

   self.poles = {
      A = Pole:new{
	 name='A',
	 col = off + 0 * delta + delta / 2
      },
      B = Pole:new{
	 name='B',
	 col = off + 1 * delta + delta / 2
      },
      C = Pole:new{
	 name='C',
	 col = off + 2 * delta + delta / 2
      },
   }

   if self.optim then
      self.poles.A.next = self.poles.B
      self.poles.B.next = self.poles.C

      self.poles.C.prev = self.poles.B
      self.poles.B.prev = self.poles.A
   end

   local Ring = self:resetRings():subclass{}

   function Ring:draw()
      Ring:super().draw(self)
      if self.wrk then self.wrk:sched() end
   end


   for i = n, 1, -1 do
      local ring = Ring:new{ n=i, row=0, col=1+i }

      if math.random(0, 1) == 1 then
	 ring.col = self.winWidth - i - 4
      end

      ring:draw()
      self.poles.A:populate(ring)
   end

   --
   -- need to allow things to settle out here first
   --
   while runq[1] do Worker.sched() end
end

return Hanoi