lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

> Being able to shrink an array is vital to using it as a stack. If you
> don't need to push nils, you can use "t[#t] = val" for a push
> operation and "t[#t] = nil" for a pop operation. If you have auto-grow
> functionality, then "t[#t] = val" still works, but you'd need
> something like "t.resize(#t-1)" for pop.

Right, and that's in the code but you need to use __call instead of setlength.
BTW, you don't need arrays to have stacks, but arrays make for a slightly
easier implementation. If we allow non-numeric keys in the array,

  __newindex = function (t, k, v)
    if type(k) == "number" and k == floor(k) and k > t.n then
      t.n = k
    return rawset(t, k, v)

as in Roberto's code, we can store the top of the stack and have stacks with
amortized O(1) push/pop operations:

local array = require "array"

function ()
  local s = array() = 0
  return s

function stack.push (s, e)
  if == s.n then -- full?
    s.n = 2 * -- grow
  end = + 1
  s[] = e

function stack.pop (s)
  if == 0 then return nil end -- empty?
  local e = s[] = - 1
  if < s.n / 4 then -- shrink?
    s(math.floor(s.n / 2)) -- or s:setlength(s.n / 2)
  return e

Note the shrinking case when the stack is quarter full in stack.pop: it can
either use __call or setlength to shrink the array.


Computers are useless. They can only give you answers.
                -- Pablo Picasso

Luis Carvalho (Kozure)
lua -e 'print(((""):gsub("(%u+%.)","")))'