summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/LinkedList.lua
blob: 99a23501858ab5212e1e464e959aeb2d247e1f96 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
local LinkedList = {}

LinkedList.__index = LinkedList

function LinkedList.new()
	local list = {elements = {}}
	setmetatable(list, LinkedList)
	return list
end

function LinkedList:addback(payload)
	if payload == nil then
		error("Need a payload!", 2)
	end
	local element = { payload = payload }
	if self.head then
		local tail = self.head.prev
		self.head.prev = element
		tail.next = element
		element.next = self.head
		element.prev = tail
	else
		self.head = element
		element.next = element
		element.prev = element
	end
	self.elements[element] = true
	return element
end

function LinkedList:addfront(payload)
	self.head = self:addback(payload)
	return self.head
end

function LinkedList:remove(element)
	if self.elements[element] == nil then
		error("Element not in list!", 2)
	end
	if self.head == element then
		if element.next == element then
			self.head = nil
		else
			self.head = element.next
		end
	end
	element.prev.next = element.next
	element.next.prev = element.prev
	self.elements[element] = nil
end

function LinkedList:popfirst()
	if self.head == nil then
		return nil
	end
	local element = self.head
	if element.next == element then
		self.head = nil
	else
		self.head = element.next
		element.next.prev = element.prev
		element.prev.next = element.next
	end
	self.elements[element] = nil
	return element.payload
end

function LinkedList:poplast()
	if self.head == nil then
		return nil
	end
	self.head = self.head.prev
	return self:popfirst()
end

function LinkedList:first()
	return self.head and self.head.payload
end

function LinkedList:last()
	return self.head and self.head.prev.payload
end

function LinkedList:empty()
	return self.head == nil
end

return LinkedList