local NewHeap = pd.Class:new():register("newheap") function NewHeap:initialize(sel, atoms) self.inlets = 1 self.outlets = 2 self.comp = function(a, b) return a[1] < b[1] end self.storage = {} pd.post("Table size = " .. #self.storage) -- remove later! table.insert(self.storage, {100000000100, "dummy"}) return true end function NewHeap:in_1(sel, atoms) if sel == "top" then self:outlet(2, "float", {NewHeap:top()}) elseif sel == "pop" then self:outlet(1, "list", NewHeap:pop()) elseif sel == "insert" then NewHeap:insert(atoms) elseif sel == "clear" then NewHeap:clear() end end -- internal function NewHeap:top() if #self.storage > 1 then return self.storage[1][1] else return "bang" end end function NewHeap:pop() local val = self.storage[1] if self.storage[2] then self[1] = table.remove(self.storage) -- move last up to top NewHeap:down(self, 1) else self[1] = nil end return val end function NewHeap:insert(insertValue) pd.post("Table size = " .. #self.storage) -- remove later! table.insert(self.storage, insertValue) NewHeap:up(self.storage, #self.storage) end function NewHeap:clear() for i=1, #self.storage do self.storage[i] = nil end end function NewHeap:up(k) local half = math.floor(k/2) local val = self.storage[k] while (half > 0 and self.comp(self.storage[half], val)) do self[k] = self[half] k = half half = math.floor(k/2) end self[k] = val return k end function NewHeap:down(k) local val = self[k] local j while(k <= math.floor(#self.storage/2)) do j = k+k if(j < #self.storage and self.comp(self.storage[j], self.storage[j + 1])) then j = j + 1 end if(self.comp(self[j], val)) then break end self[k], k = self[j], j end self[k] = val return k end