lists.lua

-- $Id: lists.lua,v 1.6 2001年01月13日 22:04:18 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- implemented by: Roberto Ierusalimschy
--------------------------------------------------------------
-- List module
-- defines a prototipe for lists
--------------------------------------------------------------
List = {first = 0, last = -1}
function List:new ()
 local n = {}
 for k,v in self do n[k] = v end
 return n
end
function List:length ()
 return self.last - self.first + 1
end
function List:pushleft (value)
 local first = self.first - 1
 self.first = first
 self[first] = value
end
function List:pushright (value)
 local last = self.last + 1
 self.last = last
 self[last] = value
end
function List:popleft ()
 local first = self.first
 if first > self.last then error"list is empty" end
 local value = self[first]
 self[first] = nil -- to allow collection
 self.first = first+1
 return value
end
function List:popright ()
 local last = self.last
 if self.first > last then error"list is empty" end
 local value = self[last]
 self[last] = nil -- to allow collection
 self.last = last-1
 return value
end
function List:reverse ()
 local i, j = self.first, self.last
 while i<j do
 self[i], self[j] = self[j], self[i]
 i = i+1
 j = j-1
 end
end
function List:equal (otherlist)
 if self:length() ~= otherlist:length() then return nil end
 local diff = otherlist.first - self.first
 for i1=self.first,self.last do
 if self[i1] ~= otherlist[i1+diff] then return nil end
 end
 return 1
end
-----------------------------------------------------------
-----------------------------------------------------------
-- Some tests
function test ()
 local SIZE = 10000
 -- create a list with elements 1..SIZE
 local l1 = List:new()
 for i=1,SIZE do
 l1:pushright(i)
 end
 -- creates a copy of l1
 local l2 = l1:new()
 -- remove each individual item from left side of l2 and
 -- append to right side of l3 (preserving order)
 local l3 = List:new()
 while l2:length() > 0 do
 l3:pushright(l2:popleft()) 
 end
 -- remove each individual item from right side of l3 and
 -- append to right side of l2 (reversing list)
 while l3:length() > 0 do
 l2:pushright(l3:popright())
 end
 -- reverse l1 in place
 l1:reverse()
 -- compare Li1 and Li2 for equality
 -- and return length of the list
 if not l1:equal(l2) then return nil
 else return l1:length()
 end
end
N = tonumber((arg and arg[1])) or 1
for i=1, N do
 result = test()
end
print(result)