Modul:queue

Dokumentation för denna modul finns på /dok ^{(redigera), /test}

---

Syfte

Den här modulen innehåller en generell implementering av en Single Queue-datastruktur för moduler som har nytta av det.

Användning

local Queue = require("Modul:queue") --importerar Queue-datastrukturen
local q = Queue()                    --skapar en ny "instans" q
Queue.enqueue(q, "abc")              --lägger till elementet "abc" i kön q

Specifikation

Publika funktioner:

• enqueue("abc") Lägger till elemenet "abc" i kön.
• dequeue() Tar bort det första elementet från kön och returnerar det, det vill säga "Först in, först ut". Om kön är tom returneras nil.
• peek(index) Returnerar elementet som befinner sig på position index i kön. 1 är det första elementet. Om värdet på index är negativt returneras elementet som befinner sig på position index i kön räknat bakifrån. -1 är det sista elementet. Värdet på index kan inte vara 0 eller utanför köns omfång. Då returneras nil.
• peekFirst() Samma som peek(1).
• peekSecond() Samma som peek(2).
• peekLast() Samma som peek(-1).
• isEmpty() Returnerar true om kön är tom, annars false.
• length() Returnerar köns längd, dvs köns totala antal element.

Tester

All tests passed. (refresh)

test01_enqueue:

	Text	Expected	Actual
	mut.enqueue(q)	(nil)	(nil)

test02_empty_queue:

	Text	Expected	Actual
	mut.isEmpty(q)	true	true
	mut.length(q)	0	0
	mut.peekFirst(q)	(nil)	(nil)
	mut.peekSecond(q)	(nil)	(nil)
	mut.peekLast(q)	(nil)	(nil)
	mut.peek(q, 1)	(nil)	(nil)
	mut.peek(q, 0)	(nil)	(nil)
	mut.peek(q, -1)	(nil)	(nil)
	mut.dequeue(q)	(nil)	(nil)

test03_one_element_added:

	Text	Expected	Actual
	mut.isEmpty(q)	false	false
	mut.length(q)	1	1
	mut.peekFirst(q)	one	one
	mut.peekSecond(q)	(nil)	(nil)
	mut.peekLast(q)	one	one
	mut.peek(q, 1)	one	one
	mut.peek(q, -1)	one	one
	mut.dequeue(q)	one	one

test04_two_elements_added:

	Text	Expected	Actual
	mut.isEmpty(q)	false	false
	mut.length(q)	2	2
	mut.peekFirst(q)	one	one
	mut.peekSecond(q)	two	two
	mut.peekLast(q)	two	two
	mut.peek(q, 1)	one	one
	mut.peek(q, 2)	two	two
	mut.peek(q, -1)	two	two
	mut.peek(q, -2)	one	one

test05_four_elements_added:

	Text	Expected	Actual
	mut.length(q)	false	false
	mut.length(q)	4	4
	mut.peekFirst(q)	one	one
	mut.peekSecond(q)	two	two
	mut.peekLast(q)	four	four
	mut.peek(q, 1)	one	one
	mut.peek(q, 4)	four	four
	mut.peek(q, 5)	(nil)	(nil)
	mut.peek(q, 0)	(nil)	(nil)
	mut.peek(q, -1)	four	four
	mut.peek(q, -4)	one	one
	mut.peek(q, -5)	(nil)	(nil)

test06_multiple:

	Text	Expected	Actual
	mut.dequeue(q)	(nil)	(nil)
	mut.length(q)	true	true
	mut.length(q)	0	0
	mut.enqueue(q, "one")	(nil)	(nil)
	mut.enqueue(q, "two")	(nil)	(nil)
	mut.length(q)	2	2
	mut.dequeue(q)	one	one
	mut.length(q)	1	1
	mut.enqueue(q, "three")	(nil)	(nil)
	mut.enqueue(q, "four")	(nil)	(nil)
	mut.length(q)	3	3
	mut.dequeue(q)	two	two
	mut.peekFirst(q)	three	three
	mut.peekSecond(q)	four	four
	mut.peekLast(q)	four	four
	mut.length(q)	2	2
	mut.dequeue(q)	three	three
	mut.dequeue(q)	four	four
	mut.length(q)	true	true
	mut.dequeue(q)	(nil)	(nil)
	mut.length(q)	0	0

local export = {}

export.prototype = {
    firstIndex = 0,
    lastIndex = -1
}

setmetatable(export, {__call = 
	function()
		local t = {}
	    setmetatable(t, {
	    	__index = export.prototype
	    })
	    return t
    end
})

function export:isEmpty()
	return (self.firstIndex > self.lastIndex)
end

function export:length()
	return (self.lastIndex - self.firstIndex + 1)
end
	
function export:enqueue(item)
	local lastIndex = self.lastIndex + 1
	self.lastIndex = lastIndex
	self[lastIndex] = item
end

function export:dequeue()
	local item

	local firstIndex = self.firstIndex
	if (export.isEmpty(self)) then 
		item = nil
	else
		item = self[firstIndex]
		self[firstIndex] = nil
		self.firstIndex = firstIndex + 1
	end
	
	return item
end

function export:peek(index)
	local item
	
	if (index > 0) then
		item = self[self.firstIndex - 1 + index]
	elseif (index < 0) then
		item = self[self.lastIndex + 1 + index]
	end
	
	return item
end

function export:peekFirst()
	return export.peek(self, 1)
end

function export:peekSecond()
	return export.peek(self, 2)
end

function export:peekLast()
	return export.peek(self, -1)
end

return export