data_structures.lua

   1 --[[--------------------------------------------------------------------
   2
   3   data_structures.lua
   4
   5   Implementations of useful data structures that we use often.
   6   Most of these are just useful interfaces around Lua's tables.
   7
   8   Copyright (c) 2007 Joshua Haberman.  See LICENSE for details.
   9
  10 --------------------------------------------------------------------]]--
  11
  12 require "misc"
  13
  14 -- Queue
  15 Queue = {name="Queue"}
  16   function Queue:new(init)
  17     local obj = newobject(self)
  18     obj.first = 0
  19     obj.last  = -1
  20     if init then obj:enqueue(init) end
  21     return obj
  22   end
  23
  24   function Queue:enqueue(val)
  25     self.last = self.last + 1
  26     self[self.last] = val
  27   end
  28
  29   function Queue:dequeue()
  30     if self:isempty() then error("Tried to dequeue an empty queue") end
  31     local val = self[self.first]
  32     self[self.first] = nil
  33     self.first = self.first + 1
  34     return val
  35   end
  36
  37   function Queue:isempty()
  38     return self.first > self.last
  39   end
  40 -- class Queue
  41
  42
  43 -- Stack
  44 Stack = {name="Stack"}
  45   function Stack:new(init)
  46     local obj = newobject(self)
  47     obj.stack = {}
  48     return obj
  49   end
  50
  51   function Stack:push(val)
  52     table.insert(self.stack, val)
  53   end
  54
  55   function Stack:pop()
  56     return table.remove(self.stack)
  57   end
  58
  59   function Stack:top()
  60     return self.stack[#self.stack]
  61   end
  62
  63   function Stack:contains(elem)
  64     for e in each(self.stack) do
  65       if elem == e then
  66         return true
  67       end
  68     end
  69     return false
  70   end
  71
  72   function Stack:to_array()
  73     local arr = {}
  74     for i, val in ipairs(self.stack) do
  75       table.insert(arr, val)
  76     end
  77     return arr
  78   end
  79 -- class Stack
  80
  81
  82 -- Set
  83 Set = {name="Set"}
  84   function Set:new(init)
  85     local obj = newobject(self)
  86     obj.elements = {}
  87     if init then
  88       obj:add_collection(init)
  89     end
  90     return obj
  91   end
  92
  93   function Set:contains(x)
  94     return self.elements[x] ~= nil
  95   end
  96
  97   function Set:add(x)
  98     self.elements[x] = true
  99   end
 100
 101   function Set:remove(x)
 102     self.elements[x] = nil
 103   end
 104
 105   function Set:add_collection(arr)
 106     for elem in each(arr) do
 107       self:add(elem)
 108     end
 109   end
 110
 111   function Set:each()
 112     return pairs(self.elements)
 113   end
 114
 115   function Set:to_array()
 116     local arr = {}
 117     for elem in self:each() do
 118       table.insert(arr, elem)
 119     end
 120     return arr
 121   end
 122
 123   function Set:isempty()
 124     return self:count() == 0
 125   end
 126
 127   function Set:count()
 128     local i = 0
 129     for elem in self:each() do
 130       i = i + 1
 131     end
 132     return i
 133   end
 134
 135   function Set:hash_key()
 136     local arr = self:to_array()
 137     for i=1,#arr do
 138       arr[i] = tostring(arr[i])
 139     end
 140
 141     table.sort(arr)
 142
 143     str = "" for elem in each(arr) do str = str .. elem end
 144     return str
 145   end
 146 -- class Set
 147
 148 -- Range
 149 -- The Range is *inclusive* at both ends.
 150 Range = {name="Range"}
 151   function Range:new(low, high)
 152     assert(low <= high)
 153
 154     local obj = newobject(self)
 155     obj.low = low
 156     obj.high = high
 157     return obj
 158   end
 159
 160   function Range.union(a, b)
 161     if math.max(a.low, b.low) <= (math.min(a.high, b.high)+1) then
 162       return Range:new(math.min(a.low, b.low), math.max(a.high, b.high))
 163     else
 164       return nil
 165     end
 166   end
 167
 168   function Range:contains(int)
 169     return (self.low <= int) and (self.high >= int)
 170   end
 171
 172   function Range:tostring(display_val_func)
 173     if self.low == self.high then
 174       return display_val_func(self.low)
 175     else
 176       return display_val_func(self.low) .. "-" .. display_val_func(self.high)
 177     end
 178   end
 179 -- class Range
 180
 181
 182 -- IntSet
 183 -- None of the ranges may overlap.
 184 IntSet = {name="IntSet"}
 185   function IntSet:new()
 186     local obj = newobject(self)
 187     obj.list = {}
 188     obj.negated = false
 189     return obj
 190   end
 191
 192   function IntSet:add(new_range)
 193     local newlist = {}
 194     for range in each(self.list) do
 195       local union = new_range:union(range)
 196       if union then
 197         new_range = union
 198       else
 199         table.insert(newlist, range)
 200       end
 201     end
 202
 203     table.insert(newlist, new_range)
 204     self.list = newlist
 205   end
 206
 207   function IntSet:get_non_negated()
 208     if self.negated then
 209       return self:invert()
 210     else
 211       return self
 212     end
 213   end
 214
 215   -- This is O(n^2) right now, and can probably
 216   -- be made O(n lg n) with a little thought, but n's
 217   -- are so small right now that I won't worry.
 218   function IntSet:add_intset(intset)
 219     for range in each(intset.list) do
 220       self:add(range)
 221     end
 222   end
 223
 224   function IntSet:contains(int)
 225     local obj = self:get_non_negated()
 226     for range in each(obj.list) do
 227       if range:contains(int) then return true end
 228     end
 229     return false
 230   end
 231
 232   function IntSet:sampleint()
 233     local obj = self:get_non_negated()
 234
 235     if #obj.list == 0 then
 236       return nil
 237     else
 238       return obj.list[1].low
 239     end
 240   end
 241
 242   function IntSet:invert()
 243     local new_intset = IntSet:new()
 244     new_intset.negated = not self.negated
 245
 246     table.sort(self.list, function (a, b) return a.low < b.low end)
 247     local offset = 0
 248
 249     for range in each(self.list) do
 250       if offset <= range.low-1 then
 251         new_intset:add(Range:new(offset, range.low-1))
 252       end
 253       offset = range.high+1
 254     end
 255
 256     if offset ~= math.huge then
 257       new_intset:add(Range:new(offset, math.huge))
 258     end
 259
 260     return new_intset
 261   end
 262
 263   function IntSet:each_range()
 264     return each(self:get_non_negated().list)
 265   end
 266
 267   function IntSet:isunbounded()
 268     for range in each(self.list) do
 269       if range.high == math.huge then
 270         return true
 271       end
 272     end
 273     return false
 274   end
 275
 276   function IntSet:tostring(display_val_func)
 277     local str = ""
 278     if self.negated then str = "^" end
 279
 280     table.sort(self.list, function (a, b) return a.low < b.low end)
 281     local first = true
 282     for range in each(self.list) do
 283       if first then
 284         first = false
 285       else
 286         str = str .. ","
 287       end
 288
 289       str = str .. range:tostring(display_val_func)
 290     end
 291
 292     return str
 293   end
 294
 295   function IntSet:toasciistring()
 296     local convert_func = function (x)
 297       if x == math.huge then
 298         return "del"
 299       elseif x < 33 then
 300         return string.format("\\%03o", x)
 301       else
 302         return string.char(x)
 303       end
 304     end
 305     return self:tostring(convert_func)
 306   end
 307
 308   function IntSet:tointstring()
 309     return self:tostring(function (x) return tostring(x) end)
 310   end
 311 -- class IntSet
 312
 313 ShallowTable = {name="ShallowTable"}
 314 function ShallowTable:new(val)
 315   if val == nil then return nil end
 316
 317   if not self.cache then
 318     self.cache = {}
 319     --setmetatable(self.cache, {__mode = "v"})  -- make values weak
 320   end
 321
 322   local str = ""
 323   local keys = {}
 324   for key in pairs(val) do table.insert(keys, key) end
 325   table.sort(keys)
 326   for key in each(keys) do
 327     if type(val[key]) == "table" and val[key].class == fa.NonTerm then
 328       str = str .. "|" .. key .. ":NONTERM" .. tostring(val[key].name)
 329     else
 330       str = str .. "|" .. key .. ":" .. tostring(val[key])
 331     end
 332   end
 333
 334   if not self.cache[str] then
 335     self.cache[str] = newobject(self)
 336     for k,v in pairs(val) do
 337       self.cache[str][k] = v
 338     end
 339   end
 340
 341   return self.cache[str]
 342 end
 343