隊列Queue

1 Queue = Queue or {}
  2 
  3 function Queue.new()
  4     local inst = {}
  5     inst._cname = "lang.Queue"
  6     
  7     local arr = {}
  8     local cursor1 = 1
  9     local len = 0
 10     
 11     function inst:count()
 12         return len
 13     end
 14     
 15     local function getCursor2()
 16         return cursor1 + len - 1
 17     end
 18     
 19     function inst:clear()
 20         for i=cursor1,getCursor2() do
 21             arr[i] = nil
 22         end
 23         cursor1 = 1
 24         len = 0
 25     end
 26     
 27     function inst:contains(v)
 28         for i=cursor1,getCursor2() do
 29             if arr[i] == v then
 30                 return true
 31             end
 32         end
 33         return false
 34     end
 35     
 36     function inst:enqueue(v)
 37         arr[cursor1 + len] = v
 38         len = len + 1
 39     end
 40     
 41     function inst:dequeue()
 42         local cursor2 = getCursor2()
 43         assert(cursor1 <= cursor2, "Queue: dequeue: out of range")
 44         local v = arr[cursor1]
 45         arr[cursor1] = nil
 46         cursor1 = cursor1 + 1
 47         len = len - 1
 48         
 49         if cursor1 >= 8 then --todo: 參考NetBuff
 50             local j = 1
 51             for i=cursor1,cursor2 do
 52                 arr[j] = arr[i]
 53                 j = j + 1
 54             end
 55             for i=j,cursor2 do
 56                 arr[i] = nil
 57             end
 58             cursor1 = 1
 59         end
 60         return v
 61     end
 62     
 63     function inst:peek()
 64         local v = arr[cursor1]
 65         return v
 66     end
 67     
 68     function inst:copyTo(dst)
 69         assert("table" == type(dst), "copyTo: dst not table or Stack")
 70         if "lang.Queue" == dst._cname then
 71             for i=cursor1,getCursor2() do
 72                 dst:enqueue(arr[i])
 73             end
 74         else
 75             for i=cursor1,getCursor2() do
 76                 table.insert(dst, arr[i])
 77             end
 78         end
 79     end
 80     
 81     function inst:__tostring()
 82         if len <= 0 then return "" end
 83         local strTb = {}
 84         for i=cursor1,getCursor2() do
 85             local item = arr[i]
 86             table.insert(strTb, (nil == item) and "nil" or tostring(item))
 87         end
 88         return table.concat(strTb, ",")
 89     end
 90 
 91     function inst:__len()
 92         return len
 93     end
 94     
 95     function inst:__index(k)
 96         error("Queue: invalid member: " .. k)
 97     end
 98     
 99     function inst:__newindex(k, v)
100         error("Queue: add member error: " .. k)
101     end
102     
103     setmetatable(inst, inst)
104     return inst
105 end
106 
107 function Queue.__call()
108     return Queue.new()
109 end
110 setmetatable(Queue, Queue)      

測試代碼：

1 local function Test1()
 2     local q = Queue()
 3     assert(0 == q:count(), "count error")
 4     
 5     q:enqueue("one")
 6     assert(1 == q:count(), "enqueue error")
 7     assert("one" == q:peek(), "peek error")
 8     assert(true == q:contains("one"), "contains error")
 9     assert(false == q:contains("1"), "contains error")
10     
11     q:enqueue("two")
12     assert(2 == q:count(), "enqueue error")
13     assert("one" == q:peek(), "peek error")
14     assert(true == q:contains("one"), "contains error")
15     assert(true == q:contains("two"), "contains error")
16     assert(false == q:contains("1"), "contains error")
17     
18     assert("one" == q:dequeue(), "dequeue error")
19     assert(1 == q:count(), "enqueue error")
20     assert("two" == q:dequeue(), "dequeue error")
21     assert(0 == q:count(), "enqueue error")
22     assert(nil == q:peek(), "dequeue error")
23     --q:dequeue() --error
24     
25     local q2 = Queue()
26     q2:enqueue("1")
27     q:enqueue("a")
28     q:copyTo(q2)
29     assert("1" == q2:dequeue(), "dequeue error")
30     assert(1 == q2:count(), "enqueue error")
31     assert("a" == q2:dequeue(), "dequeue error")
32     assert(0 == q2:count(), "enqueue error")
33     assert(nil == q2:peek(), "dequeue error")
34 end
35 
36 Test1()