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

WFQueueingTest.lua

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

ADOBE CONFIDENTIAL
------------------
Copyright 2012 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.

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

local WFQueueingTest = {}

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

local assert = assert

-- local KSTestUtils = require 'KSTestUtils'

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

function WFQueueingTest.testNamespace()

	local WFQueueing = require 'WFQueueing'
	
	assert( WFQueueing.makeStack, "No makeStack routine" )
	assert( WFQueueing.makeQueue, "No makeQueue routine" )
	assert( WFQueueing.makePriorityQueue, "No makePriorityQueue routine" )

end

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

function WFQueueingTest.testStacks()

	local WFQueueing = require 'WFQueueing'
	
	local push, pop, isEmpty, peek = WFQueueing.makeStack()
	
	assert( select( '#', pop() ) == 0, "Pop should return nothing at first." )
	assert( select( '#', peek() ) == 0, "Peek should return nothing at first." )
	assert( isEmpty(), "Stack should report as empty" );
	
	push( 1 )
	push( 2 )
	push( 3 )
	
	assert( peek() == 3, "Peek should reveal the top of the stack (3)." )
	assert( peek() == 3, "Peek should still reveal the top of the stack (3)." )
	assert( not isEmpty(), "Stack should report as non-empty" )
	
	assert( pop() == 3, "Pop should yield 3" )
	assert( pop() == 2, "Pop should yield 2" )
	
	assert( peek() == 1, "Peek should now yield 1." )

	push( 4 )
	push( 5 )

	assert( pop() == 5, "Pop should yield 5" )
	assert( pop() == 4, "Pop should yield 4" )
	assert( pop() == 1, "Pop should yield 1" )

	assert( select( '#', pop() ) == 0, "Pop should return nothing at the end." )
	assert( isEmpty(), "Stack should report as empty" );

end

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

local function testClearsProperly( push, pop )

	local items = setmetatable( {}, { __mode = 'kv' } )
	
	local function countItems()
	
		collectgarbage()
		collectgarbage()
		collectgarbage()
		
		local count = 0
		
		for _ in pairs( items ) do
			count = count + 1
		end
		
		return count
		
	end
	
	local function makeItem()
		local x = { }
		items[ x ] = x
		return x
	end
	
	push( makeItem() )
	push( makeItem() )
	push( makeItem() )
	
	assert( countItems() == 3, "There should be three items" )
	
	pop()
	pop()
	
	assert( countItems() == 1, "There should be one item" )
	
	pop()
	
	assert( countItems() == 0, "There should be no items left" )

end

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

function WFQueueingTest.testStacksClearProperly()

	local WFQueueing = require 'WFQueueing'
	
	local push, pop = WFQueueing.makeStack()
	
	testClearsProperly( push, pop )

end

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

function WFQueueingTest.testQueues()

	local WFQueueing = require 'WFQueueing'
	
	local enqueue, dequeue, isEmpty, peekHead, peekTail = WFQueueing.makeQueue()
	
	assert( select( '#', dequeue() ) == 0, "Dequeue should return nothing at first." )
	assert( select( '#', peekHead() ) == 0, "Peek (head) should return nothing at first." )
	assert( select( '#', peekTail() ) == 0, "Peek (tail) should return nothing at first." )
	assert( isEmpty(), "Queue should report as empty" )
	
	enqueue( 1 )
	enqueue( 2 )
	enqueue( 3 )
	enqueue( 4 )
	
	assert( peekTail() == 4, "Peek (tail) should yield 4." )
	assert( peekHead() == 1, "Peek (head) should yield 1." )

	assert( not isEmpty(), "Queue should report as non-empty" )

	assert( dequeue() == 1, "Dequeue should yield 1" )
	assert( dequeue() == 2, "Pop should yield 2" )

	assert( peekHead() == 3, "Peek (head) should now yield 3." )
	assert( peekTail() == 4, "Peek (tail) should still yield 4." )

	assert( not isEmpty(), "Queue should report as non-empty" )

	enqueue( 5 )
	enqueue( 6 )

	assert( dequeue() == 3, "Dequeue should yield 3" )
	assert( dequeue() == 4, "Dequeue should yield 4" )
	assert( dequeue() == 5, "Dequeue should yield 5" )
	assert( dequeue() == 6, "Dequeue should yield 6" )

	assert( select( '#', peekHead() ) == 0, "Peek (head) should return nothing at the end." )
	assert( select( '#', peekTail() ) == 0, "Peek (tail) should return nothing at the end." )
	assert( select( '#', dequeue() ) == 0, "Dequeue should return nothing at the end." )
	assert( isEmpty(), "Queue should report as empty" )

end

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

function WFQueueingTest.testQueuesClearProperly()

	local WFQueueing = require 'WFQueueing'
	
	local enqueue, dequeue = WFQueueing.makeQueue()
	
	testClearsProperly( enqueue, dequeue )

end

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

local function runPQTest( enqueue, testDequeue )

	enqueue( 1 )
	enqueue( 2 )
	enqueue( 3 )
	enqueue( - 1 )
	enqueue( 4 )
	enqueue( 2 )
	
	testDequeue( 4 )
	testDequeue( 3 )
	testDequeue( 2 )
	testDequeue( 2 )
	testDequeue( 1 )
	testDequeue( -1 )
	
	enqueue( 4 )
	enqueue( 5 )

	testDequeue( 5 )

	enqueue( 6 )

	testDequeue( 6 )
	testDequeue( 4 )
	
	testDequeue()
	
	enqueue( 7 )
	enqueue( 8 )
	
	enqueue( 11 )
	enqueue( 9 )
	enqueue( 10 )

	testDequeue( 11 )
	
	testDequeue( 10 )
	
	testDequeue( 9 )
	testDequeue( 8 )
	
	enqueue( 4 )
	enqueue( 2 )
	enqueue( 3 )
	
	testDequeue( 7 )
	testDequeue( 4 )
	testDequeue( 3 )
	testDequeue( 2 )

	testDequeue()

end

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

local function doPQTest( enqueue, dequeue, _, peekHead )

	local function testEnqueue( x )
		enqueue( x, { x } )
	end
	
	local function assert2results( fname, ... )
		assert( select( '#', ... ) == 2, "There should have been two results to " .. fname )
		return ...
	end
	
	local function testDequeue( ... )
		
		local n = select( '#', ... )
		
		if n == 0 then
			assert( select( '#', peekHead() ) == 0, "peekHead should have returned no results" )
			assert( select( '#', dequeue() ) == 0, "dequeue should have returned no results" )
		else
			local x = ( ... )
			local peekPriority, peekValue = assert2results( 'peekHead', peekHead() )
			assert( peekValue[ 1 ] == x, "The peeked value should have had the form { " .. tostring( x ) .. " }" )
			assert( peekPriority == x, "The peeked priority should have been " .. tostring( x ) )
			local priority, value = assert2results( 'dequeue', dequeue() )
			assert( value[ 1 ] == x, "The value should have had the form { " .. tostring( x ) .. " }" )
			assert( priority == x, "The priority should have been " .. tostring( x ) )
		end
	
	end
	
	runPQTest( testEnqueue, testDequeue )

end

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

function WFQueueingTest.testPriorityQueue()

	local WFQueueing = require 'WFQueueing'
	doPQTest( WFQueueing.makePriorityQueue() )

end

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

local function runSPQTest( enqueue, testDequeue )

	enqueue( 2 )
	enqueue( 2 )
	enqueue( 2 )
	enqueue( 2 )
	enqueue( 2 )
	enqueue( 2 )
	enqueue( 2 )
	enqueue( 2 )
	enqueue( 2 )
	enqueue( 2 )
	
	testDequeue( 2, 1 )
	testDequeue( 2, 2 )
	testDequeue( 2, 3 )
	testDequeue( 2, 4 )
	testDequeue( 2, 5 )
	testDequeue( 2, 6 )
	testDequeue( 2, 7 )
	testDequeue( 2, 8 )
	testDequeue( 2, 9 )
	testDequeue( 2, 10 )
	
	testDequeue()

end

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

function WFQueueingTest.testPriorityQueueImpTwo()

	local WFQueueing = require 'WFQueueing'
	doPQTest( WFQueueing.makePriorityQueueNew() )

end

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

function WFQueueingTest.testPriorityQueueSamePriority()

	local WFQueueing = require 'WFQueueing'
	
	local enqueue, dequeue, _, peekHead = WFQueueing.makePriorityQueueNew()
	
	local enqueueId = 0
	
	local function testEnqueue( x )
		enqueueId = enqueueId + 1
		enqueue( x, { x, enqueueId } )
	end
	
	local function assert2results( fname, ... )
		assert( select( '#', ... ) == 2, "There should have been two results to " .. fname )
		return ...
	end
	
	local function testDequeue( ... )
		
		local n = select( '#', ... )
		
		if n == 0 then
			assert( select( '#', peekHead() ) == 0, "peekHead should have returned no results" )
			assert( select( '#', dequeue() ) == 0, "dequeue should have returned no results" )
		else
			local x, expectedId = ...
			local peekPriority, peekValue = assert2results( 'peekHead', peekHead() )
			local enqueuedValue = peekValue[ 1 ]
			local enqueuedId = peekValue[ 2 ]
			assert( enqueuedValue == x, "The peeked value should have had the form { " .. tostring( x ) .. " }" )
			assert( enqueuedId == expectedId, "Expected ID: " .. tostring( expectedId ) .. ", received ID: " .. tostring( enqueuedId ) )
			assert( peekPriority == x, "The peeked priority should have been " .. tostring( x ) )
			local priority, value = assert2results( 'dequeue', dequeue() )
			assert( value[ 1 ] == x, "The value should have had the form { " .. tostring( x ) .. " }" )
			assert( priority == x, "The priority should have been " .. tostring( x ) )
		end
	
	end
	
	runSPQTest( testEnqueue, testDequeue )

end

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

return WFQueueingTest
