-- $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)