--[[----------------------------------------------------------------------------

WFQueueing.lua

--------------------------------------------------------------------------------

ADOBE CONFIDENTIAL
------------------
Copyright 2013 Adobe Systems Incorporated
All Rights Reserved.

NOTICE: All information contained herein is, and remain the property of
Adobe Systems Incorporated and its suppliers, if any. The intellectual and
technical concepts contained herein are proprietary to Adobe Systems
Incorporated and its suppliers and may be covered by U.S. and Foreign
Patents, patents in process, and are protected by trade secret or copyright
law.  Dissemination of this information or reproduction of this material is
strictly forbidden unless prior written permission is obtained from
Adobe Systems Incorporated.

------------------------------------------------------------------------------]]

	-- core.os
local WFQueueingImp = require 'WFQueueingImp'

--============================================================================--

-- @mark WFQueueing namespace

--[[!

\class WFQueueing

\brief This namespace provides queueing utilities. The function calls
	return sets of functions that provide access to stacks and queues
	of various kinds.

]]--


local WFQueueing = {}

--------------------------------------------------------------------------------
--[[!
	Creates a stack. Returns four stack-management functions.

	\return (function) A function to push a value on the stack.
	\return (function) A function to pop a value from the stack.  If the stack is empty, it returns nothing.
	\return (function) A function to test whether the stack is empty.  Returns true if the stack is empty.
	\return (function) A function to peek at the next value on the stack.  If the stack is empty it returns nothing.
]]--

function WFQueueing.makeStack( )
	-- WFArguments.check( )
	-- This wrapper exists only for documentation purposes; real implementation
	-- comes from native code (see "Real implementation" below).
end

--------------------------------------------------------------------------------
--[[!
	Creates a queue. Returns five queue-management functions.

	\return (function) A function to enqueue a value.
	\return (function) A function to dequeue a value.  If the queue is empty, it returns nothing.
	\return (function) A function to test whether the stack is empty.  Returns true if the stack is empty.
	\return (function) A function to peek at the oldest value in the queue.  If the stack is empty it returns nothing.
	\return (function) A function to peek at the most recent value enqueued.  If the stack is empty it returns nothing.
]]--

function WFQueueing.makeQueue( )
	-- WFArguments.check( )
	-- This wrapper exists only for documentation purposes; real implementation
	-- comes from native code (see "Real implementation" below).
end

--------------------------------------------------------------------------------
--[[!
	Creates a prioritized queue. Returns five queue-management functions.

	SPAM [jandrew 2016-11-21]: THIS IMPLEMENTATION DOES NOT GUARANTEE FIFO ORDERING
	FOR ENTRIES WITH THE SAME PRIORITY.
	
	\return (function) A function to enqueue a value.  The first argument is a numeric priority, the second is the value.
	\return (function) A function to dequeue a value.  If the queue is empty, it returns nothing.
	\return (function) A function to test whether the stack is empty.  Returns true if the stack is empty.
	\return (function) A function to peek at the highest priority in the queue.  If the stack is empty it returns nothing.
	\return (function) A function to peek at the lowest priority value in the queue.  If the stack is empty it returns nothing.

	\return (WFQueueing) The enumerator.
]]--

function WFQueueing.makePriorityQueue( )
	-- WFArguments.check( )
	-- This wrapper exists only for documentation purposes; real implementation
	-- comes from native code (see "Real implementation" below).
end

--==============================================================================
-- @mark The Real implementation
--==============================================================================

WFQueueing = WFQueueingImp

--------------------------------------------------------------------------------
--[[!
	A second implementation of makePriorityQueue that relies on multiple queues
	under the hood. This implementation guarantees FIFO order when priorities are
	the same.
	
	\return (function) A function to enqueue a value.  The first argument is a numeric priority, the second is the value.
	\return (function) A function to dequeue a value.  If the queue is empty, it returns nothing.
	\return (function) A function to test whether the stack is empty.  Returns true if the stack is empty.
	\return (function) A function to peek at the highest priority in the queue.  If the stack is empty it returns nothing.
]]--

function WFQueueing.makePriorityQueueNew()

	local queues = {}
		-- key: priority
		-- value: a table of queue methods
		
	local priorities = {}
		-- A sorted array of the created queue priorities.
		
	----------------------------------------------------------------------------
	
	local enqueue = function( priority, value )
	
		local queueMethods = queues[ priority ] or {}
		
		if not next( queueMethods ) then
		
			local enqueueMethod, dequeueMethod, emptyMethod, peekHead = WFQueueing.makeQueue()
			queueMethods.enqueue = enqueueMethod
			queueMethods.dequeue = dequeueMethod
			queueMethods.isEmpty = emptyMethod
			queueMethods.peekHead = peekHead
			queues[ priority ] = queueMethods
			
			table.insert( priorities, priority )
			table.sort( priorities, function( a, b ) return a > b end)
			
		end
		
		queueMethods.enqueue( value )
	
	end

	----------------------------------------------------------------------------

	local dequeue = function()
	
		for _, priority in ipairs( priorities ) do
			
			local queueMethods = queues[ priority ]
			
			local value = queueMethods and queueMethods.dequeue()
			
			if value then
				return priority, value
			end
			
		end
	
	end

	----------------------------------------------------------------------------

	local isEmpty = function()
	
		for _, priority in ipairs( priorities ) do
		
			local queueMethods = queues[ priority ]
		
			if queueMethods and not queueMethods.isEmpty() then
				return false
			end
			
		end
	
		return true
	
	end

	----------------------------------------------------------------------------

	local peekHead = function()
	
		for _, priority in ipairs( priorities ) do
			
			local queueMethods = queues[ priority ]
			
			local value = queueMethods and queueMethods.peekHead()
			
			if value then
				return priority, value
			end
		
		end
	
	end

	----------------------------------------------------------------------------

	return enqueue, dequeue, isEmpty, peekHead
	
end

--==============================================================================

return WFQueueing
