diff options
Diffstat (limited to 'Resources/DefaultContent/Libraries/containers')
6 files changed, 0 insertions, 761 deletions
diff --git a/Resources/DefaultContent/Libraries/containers/README.md b/Resources/DefaultContent/Libraries/containers/README.md deleted file mode 100644 index cba8776..0000000 --- a/Resources/DefaultContent/Libraries/containers/README.md +++ /dev/null @@ -1,202 +0,0 @@ -# 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/Resources/DefaultContent/Libraries/containers/list.lua b/Resources/DefaultContent/Libraries/containers/list.lua deleted file mode 100644 index 59233b9..0000000 --- a/Resources/DefaultContent/Libraries/containers/list.lua +++ /dev/null @@ -1,199 +0,0 @@ ---- ---- 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/Resources/DefaultContent/Libraries/containers/queue.lua b/Resources/DefaultContent/Libraries/containers/queue.lua deleted file mode 100644 index 126daa8..0000000 --- a/Resources/DefaultContent/Libraries/containers/queue.lua +++ /dev/null @@ -1,111 +0,0 @@ ---- ---- 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/Resources/DefaultContent/Libraries/containers/stack.lua b/Resources/DefaultContent/Libraries/containers/stack.lua deleted file mode 100644 index d828c81..0000000 --- a/Resources/DefaultContent/Libraries/containers/stack.lua +++ /dev/null @@ -1,67 +0,0 @@ ---堆栈实现 -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/Resources/DefaultContent/Libraries/containers/tuple.lua b/Resources/DefaultContent/Libraries/containers/tuple.lua deleted file mode 100644 index 0646d5a..0000000 --- a/Resources/DefaultContent/Libraries/containers/tuple.lua +++ /dev/null @@ -1,60 +0,0 @@ ---- ---- 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/Resources/DefaultContent/Libraries/containers/vector.lua b/Resources/DefaultContent/Libraries/containers/vector.lua deleted file mode 100644 index 0b349ce..0000000 --- a/Resources/DefaultContent/Libraries/containers/vector.lua +++ /dev/null @@ -1,122 +0,0 @@ ---- ---- 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 |