forked from rjpcomputing/luaforwindows
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathOrderedSet.lua
More file actions
executable file
·164 lines (141 loc) · 4.62 KB
/
OrderedSet.lua
File metadata and controls
executable file
·164 lines (141 loc) · 4.62 KB
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
--------------------------------------------------------------------------------
---------------------- ## ##### ##### ###### -----------------------
---------------------- ## ## ## ## ## ## ## -----------------------
---------------------- ## ## ## ## ## ###### -----------------------
---------------------- ## ## ## ## ## ## -----------------------
---------------------- ###### ##### ##### ## -----------------------
---------------------- -----------------------
----------------------- Lua Object-Oriented Programming ------------------------
--------------------------------------------------------------------------------
-- Project: LOOP Class Library --
-- Release: 2.3 beta --
-- Title : Ordered Set Optimized for Insertions and Removals --
-- Author : Renato Maia <[email protected]> --
--------------------------------------------------------------------------------
-- Notes: --
-- Storage of strings equal to the name of one method prevents its usage. --
--------------------------------------------------------------------------------
local oo = require "loop.base"
--------------------------------------------------------------------------------
-- key constants ---------------------------------------------------------------
--------------------------------------------------------------------------------
local FIRST = newproxy()
local LAST = newproxy()
module("loop.collection.OrderedSet", oo.class)
--------------------------------------------------------------------------------
-- basic functionality ---------------------------------------------------------
--------------------------------------------------------------------------------
local function iterator(self, previous)
return self[previous], previous
end
function sequence(self)
return iterator, self, FIRST
end
function contains(self, element)
return element ~= nil and (self[element] ~= nil or element == self[LAST])
end
function first(self)
return self[FIRST]
end
function last(self)
return self[LAST]
end
function empty(self)
return self[FIRST] == nil
end
function insert(self, element, previous)
if element ~= nil and not contains(self, element) then
if previous == nil then
previous = self[LAST]
if previous == nil then
previous = FIRST
end
elseif not contains(self, previous) and previous ~= FIRST then
return
end
if self[previous] == nil
then self[LAST] = element
else self[element] = self[previous]
end
self[previous] = element
return element
end
end
function previous(self, element, start)
if contains(self, element) then
local previous = (start == nil and FIRST or start)
repeat
if self[previous] == element then
return previous
end
previous = self[previous]
until previous == nil
end
end
function remove(self, element, start)
local prev = previous(self, element, start)
if prev ~= nil then
self[prev] = self[element]
if self[LAST] == element
then self[LAST] = prev
else self[element] = nil
end
return element, prev
end
end
function replace(self, old, new, start)
local prev = previous(self, old, start)
if prev ~= nil and new ~= nil and not contains(self, new) then
self[prev] = new
self[new] = self[old]
if old == self[LAST]
then self[LAST] = new
else self[old] = nil
end
return old, prev
end
end
function pushfront(self, element)
if element ~= nil and not contains(self, element) then
if self[FIRST] ~= nil
then self[element] = self[FIRST]
else self[LAST] = element
end
self[FIRST] = element
return element
end
end
function popfront(self)
local element = self[FIRST]
self[FIRST] = self[element]
if self[FIRST] ~= nil
then self[element] = nil
else self[LAST] = nil
end
return element
end
function pushback(self, element)
if element ~= nil and not contains(self, element) then
if self[LAST] ~= nil
then self[ self[LAST] ] = element
else self[FIRST] = element
end
self[LAST] = element
return element
end
end
--------------------------------------------------------------------------------
-- function aliases ------------------------------------------------------------
--------------------------------------------------------------------------------
-- set operations
add = pushback
-- stack operations
push = pushfront
pop = popfront
top = first
-- queue operations
enqueue = pushback
dequeue = popfront
head = first
tail = last
firstkey = FIRST