blunty666

pQueue

Jul 1st, 2014
444
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. local function sift_up(queue, index)
  2.     local current, parent = index, (index - (index % 2))/2
  3.     while current > 1 and queue.cmp(queue[current][2], queue[parent][2]) do
  4.         queue[current], queue[parent] = queue[parent], queue[current]
  5.         current, parent = parent, (parent - (parent % 2))/2
  6.     end
  7.     return current
  8. end
  9.  
  10. local function sift_down(queue, index)
  11.     local current, child, size = index, 2*index, #queue
  12.     while child <= size do
  13.         if child < size and queue.cmp(queue[child + 1][2], queue[child][2]) then
  14.             child = child + 1
  15.         end
  16.         if queue.cmp(queue[child][2], queue[current][2]) then
  17.             queue[current], queue[child] = queue[child], queue[current]
  18.             current, child = child, 2*child
  19.         else
  20.             break
  21.         end
  22.     end
  23.     return current
  24. end
  25.  
  26. local methods = {
  27.  
  28.     insert = function(self, element, value)
  29.         table.insert(self, {element, value})
  30.         return sift_up(self, #self)
  31.     end,
  32.  
  33.     remove = function(self, element, compFunc)
  34.         local index = self:contains(element, compFunc)
  35.         if index then
  36.             local size = #self
  37.             self[index], self[size] = self[size], self[index]
  38.             local ret = table.remove(self)
  39.             if size > 1 and index < size then
  40.                 sift_down(self, index)
  41.                 if index > 1 then
  42.                     sift_up(self, index)
  43.                 end
  44.             end
  45.             return unpack(ret)
  46.         end
  47.     end,
  48.  
  49.     pop = function(self)
  50.         if self[1] then
  51.             local size = #self
  52.             self[1], self[size] = self[size], self[1]
  53.             local ret = table.remove(self)
  54.             if size > 1 then
  55.                 sift_down(self, 1)
  56.             end
  57.             return unpack(ret)
  58.         end
  59.     end,
  60.  
  61.     peek = function(self)
  62.         if self[1] then
  63.             return self[1][1], self[1][2]
  64.         end
  65.     end,
  66.  
  67.     contains = function(self, element, compFunc)
  68.         for index, entry in ipairs(self) do
  69.             if (compFunc and compFunc(entry[1], element)) or entry[1] == element then
  70.                 return index
  71.             end
  72.         end
  73.         return false
  74.     end,
  75.  
  76.     isEmpty = function(self)
  77.         return #self == 0
  78.     end,
  79.  
  80.     size = function(self)
  81.         return #self
  82.     end,
  83.  
  84.     getValue = function(self, element, compFunc)
  85.         local index = self:contains(element, compFunc)
  86.         return (index and self[index][2]) or false
  87.     end,
  88.  
  89.     setValue = function(self, element, value, compFunc)
  90.         local index = self:contains(element, compFunc)
  91.         if index then
  92.             self[index][2] = value
  93.             sift_up(self, index)
  94.             sift_down(self, index)
  95.             return true
  96.         else
  97.             return false
  98.         end
  99.     end,
  100.  
  101. }
  102.  
  103. function new(compareFunc)
  104.     local queue = {}
  105.     queue.cmp = type(compareFunc) == "function" and compareFunc or function(a, b) return a < b end
  106.     setmetatable(queue, {__index = methods})
  107.     return queue
  108. end
RAW Paste Data