Модуль:DynamicQueue

Queue: 1, 2, 3, 4 -- removed, 6

---

--[[
	A dynamic queue, i.e. a queue that can add, remove or move its elements while iterating.
	
	Dependencies:
		Module:Class
		Module:Set
--]]
local Class	= require 'Module:Class'.create
local Set	= require 'Module:Set'

local DynamicQueue = Class {
  	no			= 0
  , limit		= 100
  , items		= {}
  , positions	= {}
}

function DynamicQueue:put (item)
	self:pop (item)
	for pos = #self.items, 0, -1 do
		if not self.items [pos] or self.items [pos] < item then
			table.insert (self.items, pos + 1, item)
			self.positions [item] = pos + 1
			self.no = self.no + 1
			break
		end
	end
	return item
end		-- function DynamicQueue:put (item)

function DynamicQueue:pop (item)
	local pos = self.positions [item]
	if pos then
		self.no = self.no - 1
		return table.remove (self.items, pos)
	else
		return nil
	end
end		-- function DynamicQueue:pop (item)

function DynamicQueue:pos (item)
	return self.positions [item]
end		-- function DynamicQueue:pos (item)

-- An iterator:
-- Visits even newly added items, even at queue's head.
function DynamicQueue:_call ()
	local coroutine = coroutine	
	return coroutine.wrap (function ()
		local pos = 1
		local unchanged = 0
		while self.no > 0 and pos <= #self.items and unchanged < self.no and self.no <= self.limit do
			old_no = self.no
			coroutine.yield (pos, self.items [pos])
			-- To prevent endless moving to the end:
			if self.no == old_no then
				unchanged = unchanged + 1
			else
				unchanged = 0
			end
			pos = pos + 1
		end	-- while self.no > 0 and pos <= #self.items and unchanged < self.no and self.no <= self.limit
	end)	-- return coroutine.wrap (function () ...
end		-- function DynamicQueue:_call ()

function DynamicQueue:test (frame)
	local ret = {}
	local q = DynamicQueue ()
	q:put (1)
	q:put (2)
	q:put (5)
	q:put (3)
	q:put (4)
	--return require 'Module:Test'.serialise (q ())
	for pos, item in q () do
		ret [#ret + 1] = tostring (item)
		if item == 2 then
			item = 6
			q:put (item)
		elseif item == 4 then
			if not q:pop (item) then
				ret [#ret] = ret [#ret] .. ' -- not removed'
			else
				ret [#ret] = ret [#ret] .. ' -- removed'
			end
		end
		
	end
	return 'Queue: ' .. table.concat (ret, ', ')
end		-- function DynamicQueue:test (frame)

-- end of class DynamicQueue

return DynamicQueue