BinaryMinHeap.lua

--
-- The MIT License (MIT)
--
-- Copyright (c) 2016 iskolbin
--
-- Permission is hereby granted, free of charge, to any person obtaining a copy
-- of this software and associated documentation files (the "Software"), to deal
-- in the Software without restriction, including without limitation the rights
-- to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-- copies of the Software, and to permit persons to whom the Software is
-- furnished to do so, subject to the following conditions:
--
-- The above copyright notice and this permission notice shall be included in all
-- copies or substantial portions of the Software.
--
-- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-- FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-- AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-- LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-- SOFTWARE.
--
-- Generated by gen.lua, don't edit by hand!
-- Direct binary min heap
-- Coded by Ilya Kolbin (iskolbin@gmail.com)

local floor, setmetatable = math.floor, setmetatable

local function siftup( items, priorities, from )
	local index = from
	local parentIndex = floor( 0.5 * index )
	while index > 1 and priorities[parentIndex] > priorities[index] do
		priorities[index], priorities[parentIndex] = priorities[parentIndex], priorities[index]
		items[index], items[parentIndex] = items[parentIndex], items[index]
		
		index = parentIndex
		parentIndex = floor( 0.5 * index )
	end
	return index
end

local function siftdown( items, priorities, size, limit )
	for index = limit, 1, -1 do
		local leftIndex = index + index
		local rightIndex = leftIndex + 1
		while leftIndex <= size do
			local smallerChild = leftIndex
			if rightIndex <= size and priorities[leftIndex] > priorities[rightIndex] then
				smallerChild = rightIndex
			end
				
			if priorities[index] > priorities[smallerChild] then
				items[index], items[smallerChild] = items[smallerChild], items[index]
				priorities[index], priorities[smallerChild] = priorities[smallerChild], priorities[index]
				
			else
				break
			end
				
			index = smallerChild
			leftIndex = index + index
			rightIndex = leftIndex + 1
		end
	end
end

local BinaryMinHeapMt

local BinaryMinHeap = {}

function BinaryMinHeap.new( iparray_ )
	local self = setmetatable( {
		_items = {},
		_priorities = {},
		_size = 0,
	}, BinaryMinHeapMt )
	

	if iparray_ then
		self:batchenq( iparray_ )
	end
	
	return self
end

function BinaryMinHeap:enqueue( item, priority )
	local items, priorities = self._items, self._priorities
	
	local size = self._size + 1
	self._size = size	
	items[size], priorities[size] = item, priority
	siftup( items, priorities, size ) 
	return self
end

local function indexof( items, item )
	for i = 1, #items do
		if items[i] == item then
			return i
		end
	end
end

function BinaryMinHeap:remove( item )
	local index = indexof( self._items, item )
	if index ~= nil then
		local size = self._size
		local items, priorities = self._items, self._priorities
		
		if size == index then
			items[size], priorities[size] = nil, nil
			self._size = size - 1
		else
			local lastitem = items[size]
			items[index], priorities[index] = items[size], priorities[size]
			items[size], priorities[size] = nil, nil
			
			size = size - 1
			self._size = size
			if size > 1 then
				local siftedindex = siftup( items, priorities, index )
				siftdown( items, priorities, size, siftedindex ) 
			end
		end
		return true
	else
		return false
	end
end

function BinaryMinHeap:contains( item )
	return indexof( self._items, item ) ~= nil
end

function BinaryMinHeap:update( item, priority )
	local ok = self:remove( item )
	if ok then
		self:enqueue( item, priority )
		return true
	else
		return false
	end
end

function BinaryMinHeap:dequeue()
	local size = self._size
	
	assert( size > 0, 'Heap is empty' )
	
	local items, priorities = self._items, self._priorities
	local item, priority = items[1], priorities[1]
	

	if size > 1 then
		local newitem = items[size]
		items[1], priorities[1] = newitem, priorities[size]
		items[size], priorities[size] = nil, nil
		
		size = size - 1
		self._size = size
		siftdown( items, priorities, size, 1 )
	else
		items[1], priorities[1] = nil, nil
		self._size = 0
	end

	return item, priority
end

function BinaryMinHeap:peek()
	return self._items[1], self._priorities[1]
end
	
function BinaryMinHeap:len()
	return self._size
end

function BinaryMinHeap:empty()
	return self._size <= 0
end

function BinaryMinHeap:batchenq( iparray )
	local items, priorities = self._items, self._priorities
	local size = self._size
	for i = 1, #iparray, 2 do
		local item, priority = iparray[i], iparray[i+1]
		
		size = size + 1
		items[size], priorities[size] = item, priority
		
	end
	self._size = size
	if size > 1 then
		siftdown( items, priorities, size, floor( 0.5 * size ) )
	end
end

BinaryMinHeapMt = {
	__index = BinaryMinHeap,
	__len = BinaryMinHeap.len,
}
      
return setmetatable( BinaryMinHeap, {
	__call = function( _, ... )
		return BinaryMinHeap.new( ... )
	end
} )