misc.lua

   1 --[[--------------------------------------------------------------------
   2
   3   misc.lua
   4
   5   Miscellaneous algorithms that don't belong anywhere else.
   6
   7 --------------------------------------------------------------------]]--
   8
   9 function newobject(class)
  10   local obj = {}
  11   setmetatable(obj, class)
  12   obj.class = class
  13   class.__index = class
  14   return obj
  15 end
  16
  17 -- each(foo): returns an iterator; if the object supports the each method,
  18 --            call that, otherwise return an iterator for a plain array.
  19 function each(array_or_eachable_obj)
  20   if array_or_eachable_obj.class then
  21     return array_or_eachable_obj:each()
  22   else
  23     local array = array_or_eachable_obj
  24     local i = 0
  25     return function ()
  26       i = i + 1
  27       if array[i] then return array[i] else return nil end
  28     end
  29   end
  30 end
  31
  32 function table_shallow_eql(tbl1, tbl2)
  33   for k,v in pairs(tbl1) do
  34     if tbl1[k] ~= tbl2[k] then return false end
  35   end
  36   for k,v in pairs(tbl2) do
  37     if tbl1[k] ~= tbl2[k] then return false end
  38   end
  39   return true
  40 end
  41
  42 -- traverses a graph of some sort -- caller provides a function that gives
  43 -- children of the current node.
  44 function breadth_first_traversal(obj, children_func)
  45   local seen = Set:new{obj}
  46   local queue = Queue:new(obj)
  47   while not queue:isempty() do
  48     local node = queue:dequeue()
  49     children = children_func(node) or {}
  50     for child_node in each(children) do
  51       if seen:contains(child_node) == false then
  52         seen:add(child_node)
  53         queue:enqueue(child_node)
  54       end
  55     end
  56   end
  57   return seen
  58 end
  59
  60 function depth_first_traversal(obj, children_func)
  61   local seen = Set:new{obj}
  62   local stack = Stack:new()
  63   stack:push(obj)
  64   depth_first_traversal_helper(obj, children_func, stack, seen)
  65 end
  66
  67 function depth_first_traversal_helper(obj, children_func, stack, seen)
  68   children = children_func(obj, stack) or {}
  69   for child in each(children) do
  70     if seen:contains(child) then
  71       error("You gave me a left-recursive grammar you bastard!  Obj: " .. serialize(obj) .. ", Child: " .. serialize(child) .. ", Stack:" .. serialize(stack:to_array()))
  72     elseif seen:contains(child) == false then
  73       seen:add(child)
  74       stack:push(child)
  75       depth_first_traversal_helper(child, children_func, stack, seen)
  76       stack:pop()
  77     end
  78   end
  79 end
  80
  81 -- all ints within each IntSet are assumed to be equivalent.
  82 -- Given this, return a new list of IntSets, where each IntSet
  83 -- returned is considered equivalent across ALL IntSets.
  84 function equivalence_classes(int_sets)
  85   local BEGIN = 0
  86   local END = 1
  87
  88   local events = {}
  89   for int_set in each(int_sets) do
  90     if int_set.negated then int_set = int_set:invert() end
  91     for range in each(int_set.list) do
  92       table.insert(events, {range.low, BEGIN, int_set})
  93       table.insert(events, {range.high+1, END, int_set})
  94     end
  95   end
  96
  97   local cmp_events = function(a, b)
  98     if a[1] == b[1] then
  99       return b[2] < a[2]   -- END events should go before BEGIN events
 100     else
 101       return a[1] < b[1]
 102     end
 103   end
 104
 105   table.sort(events, cmp_events)
 106
 107   local nested_regions = Set:new()
 108   local last_offset = nil
 109   classes = {}
 110   for event in each(events) do
 111     local offset, event_type, int_set = unpack(event)
 112
 113     if last_offset and last_offset < offset and (not nested_regions:isempty()) then
 114       local hk = nested_regions:hash_key()
 115       classes[hk] = classes[hk] or IntSet:new()
 116       classes[hk]:add(Range:new(last_offset, offset-1))
 117     end
 118
 119     if event_type == BEGIN then
 120       nested_regions:add(int_set)
 121     else
 122       nested_regions:remove(int_set)
 123     end
 124     last_offset = offset
 125   end
 126
 127   local ret = {}
 128   for hk, int_set in pairs(classes) do
 129     table.insert(ret, int_set)
 130   end
 131   return ret
 132 end
 133
 134 function str_join(list, separator)
 135   local str = ""
 136   for i, string in ipairs(list) do
 137     str = str .. string
 138     if i < #list then
 139       str = str .. separator
 140     end
 141   end
 142   return str
 143 end
 144