summaryrefslogtreecommitdiff
path: root/Data/BuiltIn/Libraries/containers
diff options
context:
space:
mode:
Diffstat (limited to 'Data/BuiltIn/Libraries/containers')
-rw-r--r--Data/BuiltIn/Libraries/containers/README.md202
-rw-r--r--Data/BuiltIn/Libraries/containers/list.lua199
-rw-r--r--Data/BuiltIn/Libraries/containers/queue.lua111
-rw-r--r--Data/BuiltIn/Libraries/containers/stack.lua67
-rw-r--r--Data/BuiltIn/Libraries/containers/tuple.lua60
-rw-r--r--Data/BuiltIn/Libraries/containers/vector.lua122
6 files changed, 761 insertions, 0 deletions
diff --git a/Data/BuiltIn/Libraries/containers/README.md b/Data/BuiltIn/Libraries/containers/README.md
new file mode 100644
index 0000000..cba8776
--- /dev/null
+++ b/Data/BuiltIn/Libraries/containers/README.md
@@ -0,0 +1,202 @@
+# Lua-ADT(5.1分支和5.2分支)
+封装的lua数据结构, 元组(tuple)、动态数组(vector)、双向链表(list)、队列(queue)、栈(stack)。
+纯lua方法封装，没有使用oop，延续lua的简洁的风格。封装的数据结构能安全使用，在语言层面过滤掉非法操作，使其使用更加简单高效。
+
+所有的类型都支持#获取长度.
+> eg.
+```lua
+ local tuple = require("tuple")
+ local v = tuple.create({2,3,6})
+ print(#v)
+ ---3
+```
+
+### 元组(tuple)
+需要用table的动态数组初始化(不支持hashtable),只对外公开遍历，修改关闭。
+
+遍历：
+```lua
+ local tuple = require("tuple")
+ local v = tuple.create({2,3,6})
+
+ for i,v in ipairs(v) do --只支持ipairs遍历,抛弃了pairs(因为原则上我们是数组，不存在key)
+ print(i,v)
+ end
+ ---1 2
+ ---2 3
+ ---3 6
+
+ print(v) --重写了__tostring,方便快速浏览数据
+ ---2,3,6
+
+ v[2] = 9 --因为对修改关闭了所以这地方修改会抛出错误
+ ---lua: .\tuple.lua:33: >> Dee: Limited access
+ ---stack traceback:
+ ---[C]: in function 'error'
+```
+
+### 动态数组(vector)
+实现高效的遍历和修改，但是新增和删除都不是线性时间复杂度。基本上就是lua table的数组，但是lua的table我们会一不小心就搞成不连续的。比如:
+```lua
+ local t = {2,4}
+ t[4] = 9
+
+ print(#t) -- 2
+```
+#### 方法：
+ * add --尾添加(高效的操作)
+ * insert --插入(会有内存整理)
+ * addRange --尾添加一个表,
+ * removeAt
+ * remove
+ * contains
+ * indexOf
+ * sort
+ * find
+
+#### eg.
+```lua
+ local vector = require("vector")
+ local v = vector.create()
+
+ v:add(4)
+ v:add(5)
+ v:add(6)
+ v:add(7)
+
+ for i,v in ipairs(v) do
+ print(i,v)
+ end
+ ---1 4
+ ---2 5
+ ---3 6
+ ---4 7
+
+ print(v)
+ ---4,5,6,7
+
+ v[4] = 9 --修改值
+
+ print(v)
+ ---4,5,6,9
+
+ v[7] = 9
+ ---lua: .\vector.lua:101: outrange of vector
+ ---stack traceback:
+ --- [C]: in function 'assert'
+```
+
+### 双向链表(list)
+弥补动态数组增删的不足，提供增删效率，但是遍历和修改效率比较低
+
+#### 方法：
+ * addFirst --头添加
+ * addLast --尾添加
+ * addBefore --node前添加
+ * addAfter --node后添加
+ * removeNode --删除node
+ * remove --根据值移除
+ * find --查找node
+#### eg.
+```lua
+ local vector = require("list")
+ local v = list.create()
+
+ v.addFirst(1)
+ v.addLast(2)
+ print(v)
+ ---1,2
+
+ local node = v.find(1)
+ node.value = 9
+ print(v)
+ ---9,2
+
+ v.removeNode(node)
+ print(v)
+ ---2
+
+ v.addLast(10)
+ v.addLast(20)
+ v.addLast(30)
+ print(v)
+ ---2,10,20,30
+
+ for _,i,v in ipairs(v) do --第一个参数是node, i: index, v: value
+ print(i,v)
+ end
+ ---1 2
+ ---2 10
+ ---3 20
+ ---4 30
+```
+### 栈(stack)
+FILO先进后出, 对修改关闭，关闭遍历，只能通过方法修改数据
+#### 方法：
+ * push --添加
+ * pop --移除
+ * peek --返回栈顶数据
+ * clear --清空
+#### eg.
+```lua
+ local stack = require("stack")
+ local v = stack.create()
+
+ v.push(1)
+ v.push(2)
+ v.push(5)
+
+ print(v)
+ ---5,2,1
+ print(v.len)
+ ---3
+ v.pop()
+ print(v)
+ ---2,1
+ v.clear()
+ print(v.len)
+ ---0
+```
+### 队列(queue)
+FIFO,先进先出，因为是队首删除所以不能使用table.remove
+#### 方法：
+ * enqueue --添加
+ * dequeue --移除
+ * peek --返回栈顶数据
+ * clear --清空
+ * #queue --获取长度
+#### eg.
+```lua
+local queue = require("queue")
+-- lua table
+local cnt = 10000 * 1
+
+local t = {}
+for i=1,cnt do
+t[i] = i
+end
+
+local time = os.clock()
+while #t > 0 do
+-- table.remove(t)
+ table.remove(t, 1)
+end
+print(os.clock() - time)
+---1.037s
+
+local v = queue.create()
+
+for i=1,cnt do
+ v.enqueue(i)
+end
+
+
+local time1 = os.clock()
+while v.len > 10 do
+ v.dequeue()
+end
+print(os.clock() - time1)
+---0.005s
+```
+1w条数据，lua table直接删除表头的耗时1.037s，queue耗时0.005s,而且queue整理内存的步长可以调整，耗时可以进步一提高.
+
diff --git a/Data/BuiltIn/Libraries/containers/list.lua b/Data/BuiltIn/Libraries/containers/list.lua
new file mode 100644
index 0000000..59233b9
--- /dev/null
+++ b/Data/BuiltIn/Libraries/containers/list.lua
@@ -0,0 +1,199 @@
+---
+--- Generated by EmmyLua(https://github.com/EmmyLua)
+--- Created by Dee.
+--- DateTime: 2019/3/7 14:00
+--- 高效增删有序表，低效遍历
+---
+
+--[[
+遍历:
+ for _,idx, value in ipairs(l) do .. end
+ for _, value in pairs(l) do ... end
+]]
+
+list = list or {}
+
+function list.create()
+ local lenght = 0
+ -- 类似stl的方式，头尾只是作为指针使用
+ local first = {front = nil, next = nil, value = nil}
+ local last = {front = nil, next = nil, value = nil}
+ first.next = last
+ last.front = first
+
+
+ ---查找值
+ ---@param value
+ ---@return node
+ local find = function(value)
+ local ret = nil
+ local nextNode = first
+ while nextNode do
+ nextNode = nextNode.next
+ if nextNode.value == value then
+ ret = nextNode
+ break
+ end
+ end
+
+ return ret
+ end
+
+ ---查找(根据下标查找)
+ ---@param idx 下标
+ ---@return node
+ local findByIdx = function(idx)
+ local i = 0
+ local ret
+ local nextNode = first
+ while nextNode and i < lenght do
+ i = i+1
+ nextNode = nextNode.next
+ if i == idx then
+ ret = nextNode
+ break
+ end
+ end
+
+ return ret
+ end
+
+ ---在node前添加
+ ---@param node
+ ---@param v
+ local addBefore = function(node, v)
+ assert(node)
+
+ local frontNode = node.front
+ local newNode = {}
+ newNode.front = frontNode
+ newNode.next = node
+ newNode.value = v
+ node.front = newNode
+ frontNode.next = newNode
+
+ lenght = lenght+1
+ end
+
+ ---在node后添加
+ ---@param node
+ ---@param v
+ local addAfter = function(node, v)
+ assert(node)
+ local nextNode = node.next
+ local newNode = {}
+ newNode.front = node
+ newNode.next = nextNode
+ newNode.value = v
+ node.next = newNode
+ nextNode.front = newNode
+
+ lenght = lenght+1
+ end
+
+ ---在队首添加
+ ---@param v
+ local addFirst = function(v)
+ addAfter(first, v)
+ end
+
+ ---在队尾添加
+ ---@param v
+ local addLast = function(v)
+ addBefore(last, v)
+ end
+
+ ---删除节点
+ ---@param node
+ local removeNode = function(node)
+ assert(node)
+
+ local frontNode = node.front
+ local nextNode = node.next
+
+ if frontNode == nil then
+ first = nextNode
+ else
+ frontNode.next = nextNode
+ end
+
+ if nextNode ~= nil then
+ nextNode.front = frontNode
+ end
+ lenght = lenght - 1
+ end
+
+ ---删除节点
+ ---@param v
+ local remove = function(v)
+ local node = find(v)
+ if node then
+ removeNode(node)
+ end
+ end
+
+ local t = {
+ addFirst = addFirst,
+ addLast = addLast,
+ addBefore = addBefore,
+ addAfter = addAfter,
+ removeNode = removeNode,
+ remove = remove,
+ find = find,
+ findByIdx = findByIdx
+ }
+
+ local mt = {
+ __index = function(i_t, key)
+ return findByIdx(key)
+ end,
+ __newindex = function(i_t,k,v)
+ local node = findByIdx(k)
+ if not node then
+ error("out range: "..k)
+ else
+ node.value = v
+ end
+ end,
+ __tostring = function()
+ local ret = {}
+ local next = first.next
+ while next and next ~= last do
+ ret[#ret+1] = next.value
+ next = next.next
+ end
+
+ return table.concat(ret, ',')
+ end,
+ __len = function(v)
+ return lenght
+ end,
+ --迭代器返回node-value
+ __ipairs = function(i_t)
+ local idx = 0
+ local function iter(i_t, node)
+ idx = idx + 1
+ if node and node.next ~= last then
+ return node.next, idx, node.next.value
+ end
+ end
+
+ return iter, t, first
+ end,
+ __pairs = function(i_t)
+ local function iter(i_t, node)
+ if node and node.next ~= last then
+ return node.next, node.next.value
+ end
+ end
+
+ return iter, t, first
+ end
+ }
+
+ setmetatable(t, mt)
+
+ return t
+end
+
+return list \ No newline at end of file
diff --git a/Data/BuiltIn/Libraries/containers/queue.lua b/Data/BuiltIn/Libraries/containers/queue.lua
new file mode 100644
index 0000000..126daa8
--- /dev/null
+++ b/Data/BuiltIn/Libraries/containers/queue.lua
@@ -0,0 +1,111 @@
+---
+--- Generated by EmmyLua(https://github.com/EmmyLua)
+--- Created by Dee.
+--- DateTime: 2019/3/7 11:27
+--- FIFO
+---
+
+queue = queue or {}
+
+---@return Queue
+function queue.create()
+ ---数据容器
+ local data = {}
+ ---数据长度
+ local lenght = 0
+ ---队首索引
+ local first = 1
+
+ ---获取队首值
+ local peek = function()
+ return data[first]
+ end
+
+ ---压入数据
+ local enqueue = function(v)
+ assert(v ~= nil, "nil value")
+ first = lenght == 0 and 1 or first
+ lenght = lenght + 1
+ table.insert(data, first+lenght-1, v)
+ end
+
+ ---弹出数据
+ local dequeue = function()
+ assert(lenght > 0, "nill queue")
+
+ local ret = peek()
+ data[first] = nil
+ first = first+1
+ lenght = lenght - 1
+ first = lenght == 0 and 1 or first
+
+ if math.fmod(first, 4) == 0 then
+ local tmp = {}
+ table.move(data, first, first + lenght, 1, tmp)
+
+ first = 1
+ data = nil
+ data = tmp
+ end
+
+ return ret
+ end
+
+ local clear = function()
+ data = {}
+ first = 1
+ lenght = 0
+ end
+
+ local __tostring = function()
+ local tmp = {}
+ for i=1,lenght do
+ tmp[i] = data[i + first - 1]
+ end
+ return table.concat(tmp, ",")
+ end
+
+ local __len = function()
+ return lenght
+ end
+
+ local __index = function(i_t, key)
+ error(">> Dee: Limited access")
+ end
+
+ local __newindex = function(i_t, key, v)
+ error(">> Dee: Limited access")
+ end
+
+ local __ipairs = function(i_t)
+ local idx = 0
+ local function iter(i_t)
+ idx = idx + 1
+ if idx <= lenght then
+ return idx, data[first + idx - 1]
+ end
+ end
+
+ return iter
+ end
+
+ local __pairs = function(i_t)
+ error(">> Dee: Limited access")
+ end
+
+ local mt = {__tostring = __tostring, __index = __index, __newindex = __newindex, __ipairs = __ipairs, __pairs = __pairs, __len = __len}
+
+ ---@class Queue
+ local t = {
+ enqueue = enqueue,
+ dequeue = dequeue,
+ peek = peek,
+ clear = clear
+ }
+
+ setmetatable(t, mt)
+
+ return t
+end
+
+return queue
diff --git a/Data/BuiltIn/Libraries/containers/stack.lua b/Data/BuiltIn/Libraries/containers/stack.lua
new file mode 100644
index 0000000..d828c81
--- /dev/null
+++ b/Data/BuiltIn/Libraries/containers/stack.lua
@@ -0,0 +1,67 @@
+--堆栈实现
+stack = stack or {}
+
+function stack.create()
+ local data = {}
+
+ local function push(v)
+ assert(v)
+ table.insert(data, v)
+ end
+
+ local function pop()
+ assert(#data > 0)
+ table.remove(data)
+ end
+
+ local function peek()
+ return #data > 0 and data[#data] or nil
+ end
+
+ local function clear()
+ for i=1,#data do
+ data[i] = nil
+ end
+ end
+
+
+
+ local __tostring = function()
+ local tmp = {}
+ for i,v in ipairs(data) do
+ tmp[#data+1 - i] = v
+ end
+ return table.concat(tmp, ",")
+ end
+
+ local __index = function(i_t, key)
+ error(">> Dee: Limited access")
+ end
+
+ local __len = function()
+ return #data
+ end
+
+ local __newindex = function(i_t, key, v)
+ error(">> Dee: Limited access")
+ end
+
+ local __ipairs = function()
+ error(">> Dee: Limited access")
+ end
+
+ local mt = {__tostring = __tostring, __index = __index, __newindex = __newindex, __ipairs = __ipairs, __pairs = __ipairs, __len = __len}
+
+ local t = {
+ push = push,
+ pop = pop,
+ peek = peek,
+ clear = clear
+ }
+
+ setmetatable(t, mt)
+
+ return t
+end
+
+return stack \ No newline at end of file
diff --git a/Data/BuiltIn/Libraries/containers/tuple.lua b/Data/BuiltIn/Libraries/containers/tuple.lua
new file mode 100644
index 0000000..0646d5a
--- /dev/null
+++ b/Data/BuiltIn/Libraries/containers/tuple.lua
@@ -0,0 +1,60 @@
+---
+--- Generated by EmmyLua(https://github.com/EmmyLua)
+--- Created by Dee.
+--- DateTime: 2019/3/7 14:00
+--- 元組,對修改關閉
+---
+
+tuple = tuple or {}
+
+function tuple.create(i_data)
+ assert(type(i_data) == "table", ">> Dee: shoudle create with table")
+
+ local data = {}
+ for k,v in pairs(i_data) do
+ data[#data+1] = v
+ end
+
+ local t = {}
+
+ local __tostring = function()
+ return table.concat(data, ",")
+ end
+
+ local __index = function(i_t, key)
+ return data[key]
+ end
+
+ local __newindex = function(i_t, key, v)
+ error(">> Dee: Limited access")
+ end
+
+ local __pairs = function()
+ error(">> Dee: Limited access")
+ end
+
+ local __ipairs = function(i_t)
+ local idx = 0
+ local function iter(i_t)
+ idx = idx + 1
+ if idx <= #data then
+ return idx, data[idx]
+ end
+ end
+
+ return iter
+ end
+
+ local __len = function(v)
+ return #data
+ end
+
+ local mt = {__tostring = __tostring, __index = __index, __newindex = __newindex, __pairs =__pairs, __ipairs = __ipairs, __len = __len}
+
+ setmetatable(t, mt)
+
+ return t
+ end
+
+
+return tuple \ No newline at end of file
diff --git a/Data/BuiltIn/Libraries/containers/vector.lua b/Data/BuiltIn/Libraries/containers/vector.lua
new file mode 100644
index 0000000..0b349ce
--- /dev/null
+++ b/Data/BuiltIn/Libraries/containers/vector.lua
@@ -0,0 +1,122 @@
+---
+--- Generated by EmmyLua(https://github.com/EmmyLua)
+--- Created by Dee.
+--- DateTime: 2019/3/7 14:00
+--- 快速遍历修改,低效的增删
+---
+
+vector = vector or {}
+
+function vector.create()
+ local t = {}
+
+
+ ---尾添加元素(高效)
+ function t:add(v)
+ rawset(self, #self + 1, v)
+ end
+
+ ---插入(低效)
+ ---@param k 位置
+ ---@param v 值
+ function t:insert(k, v)
+ assert(k > 0 and k <= #self, "outrange of vector")
+
+ local cnt = #self
+ for i = cnt, k, -1 do
+ rawset(self, i+1, self[i])
+ end
+
+ rawset(self, k, v)
+ end
+
+ ---值的索引
+ ---@return -1不存在
+ function t:indexOf(i_v)
+ assert(type(self) == 'table')
+
+ local ret = -1
+ local cnt = #self
+ for i = 1, #self do
+ if self[i] == i_v then
+ ret = i
+ end
+ end
+
+ return ret
+ end
+
+ ---是否存在某元素
+ function t:contains(v)
+ assert(type(self) == 'table')
+ return self:indexOf(v) ~= -1
+ end
+
+ ---根据下标索引移除元素(低效)
+ function t:removeAt(idx)
+ assert(idx <= #self)
+ table.remove(self, idx)
+ end
+
+ ---删除值(非贪婪)
+ ---@return 删除位置 -1未删除
+ function t:remove(v)
+ local ret = self:indexOf(v)
+ if ret ~= -1 then
+ self:removeAt(ret)
+ end
+
+ return ret
+ end
+
+ ---删除所有值
+ function t:removeAll(v)
+ assert(type(self) == 'table')
+ error(">>Dee: wait ...")
+ end
+
+ ---排序
+ function t:sort(comparer)
+ assert(type(self) == 'table')
+ table.sort(self, comparer)
+ end
+
+ ---匹配
+ ---@param 匹配函数
+ ---@return idx,value
+ function t:find(matcher)
+ assert(type(self) == 'table')
+
+ local _idx, _value = -1, nil
+ local cnt = #self
+ for i = 1, cnt do
+ if matcher(i, self[i]) then
+ _value = self[i]
+ _idx = i
+ break
+ end
+ end
+
+ return _idx, _value
+ end
+
+ --------------------------------metatable---------------------------------------
+ t.__newindex = function(i_t,k,v)
+ error(">> Dee: [], replace with add()")
+ end
+
+ t.__tostring = function(i_t)
+ return table.concat(i_t, ',')
+ end
+
+ t.__pairs = function(...)
+ error(">> Dee: Limited access")
+ end
+
+ setmetatable(t, t)
+ -----------------------------------------------------------------------
+
+ return t
+end
+
+return vector \ No newline at end of file
generated by cgit v1.1-26-g67d0 at 2025-05-19 00:01:16 +0000