Lua Ropes

lua-users home
wiki

Lua Ropes

Because strings are immutable objects in Lua, it is important to avoid creating them unnecessarily. Very often programs manipulate strings in order to create some textual output. One strategy is to avoid creating intermediate strings, and to output all the pieces of the final text in the right order. The appropriate datatype for this is the rope[1], where

 rope ::= string | list of rope 
In other words, a rope is a tree whose leaves are strings. The important operation on trees is the tree-walk, applying a procedure to each leaf.

do
  local function walk(x,f)
    local typ, ok, bad = type(x),true
    local errmsg = "bad type (%s), %s"
    if typ == "string" then return pcall(f,x)
    elseif typ == "table" then
      local i,n = 1,#x
      while ok and i <= n do
        ok,bad = walk(x[i],f)
        i = i+1
      end -- while
      return ok,bad
    else
      bad = errmsg:format(typ,typ and "" or "something undefined?")
      return nil,bad
    end -- if
  end -- function

  local mt = {
    push = function (self,x)
      local function f(y)
        if y and type(y) ~= "function" then
          self[#self + 1] =y
          return f
        elseif y then
          return function (z)
            return f(y(z))
          end -- function
        end -- if
      end -- function y
      return f(x)
    end; -- function push
    walk = walk;
    flatten = function(self)
      local o = {}
      local f = function (x) o[#o + 1] = x end -- function
      self:walk(f)
      return table.concat(o)
    end; -- function
  }

  function rope()
    return setmetatable({}, {__index = mt})
  end -- function
end -- do

t,x = rope(),rope()
t:push (string.upper) "m" "r" (string.char) (32) "Smith" ;
x:push [[ Good ]] [[morning]];
t:push (x)
t:walk(io.write) --> Mr Smith Good morning
print(t:flatten()) --> Mr Smith Good morning

RecentChanges · preferences
edit · history
Last edited June 4, 2007 6:43 pm GMT (diff)