Lua-ADT(5.1分支和5.2分支)

封装的lua数据结构, 元组(tuple)、动态数组(vector)、双向链表(list)、队列(queue)、栈(stack)。 纯lua方法封装，没有使用oop，延续lua的简洁的风格。封装的数据结构能安全使用，在语言层面过滤掉非法操作，使其使用更加简单高效。

所有的类型都支持#获取长度.

eg.

	local tuple = require("tuple")
	local v = tuple.create({2,3,6})
	print(#v)
	---3

元组(tuple)

需要用table的动态数组初始化(不支持hashtable),只对外公开遍历，修改关闭。

遍历：

  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我们会一不小心就搞成不连续的。比如:

  local t = {2,4}
  t[4] = 9
  
  print(#t) -- 2

方法：

• add --尾添加(高效的操作)
• insert --插入(会有内存整理)
• addRange --尾添加一个表,
• removeAt
• remove
• contains
• indexOf
• sort
• find

eg.

  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.

  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.

  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.

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整理内存的步长可以调整，耗时可以进步一提高.