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

WFAlbumOrdering.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.

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

local WFSortOrderStrings = require 'WFSortOrderStrings'

local function orderGenerator( initialValue, valueBefore, valueAfter, valueBetween )
	return function( v1, v2 )
		if not v1 and not v2 then
			return initialValue
		elseif not v1 then
			return valueBefore( v2 )
		elseif not v2 then
			return valueAfter( v1 )
		else
			return valueBetween( v1, v2 )
		end
	end
end

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

local function insertBefore_lex64( v )
	return WFSortOrderStrings.insertBefore_lex64( v, 'high' )
end

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

local function insertAfter_lex64( v )
	return WFSortOrderStrings.insertAfter_lex64( v, 'low' )
end

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

local orderGeneratorLex64 = orderGenerator(
	WFSortOrderStrings.insertAfter_lex64( '' ),
	insertBefore_lex64,
	insertAfter_lex64,
	WFSortOrderStrings.insertBetween_lex64
)

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

--
-- Scan an array of items from a given starting point and look for an anchor
-- item with valid order information to use for updating surrounding items.
--

local function findAnchor( items, startIndex, maxValue )
	for i = startIndex, #items do
		local asset = items[ i ]
		if not asset.touched and asset.order then
			if not maxValue or asset.order > maxValue then
				return i, asset.order
			end
		end
	end
end

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

--
-- Scan an array of items from a given starting point and look for items that
-- are out of order and suggest a starting index and maxValue to use to correct
-- that order. Where possible, prefer advising correction to start with a touched
-- element than an untouched one.
--

local function findProblem( items, startIndex, maxValue )
	local firstTouched
	local previousUntouched
	local previous = maxValue
	
	for i = startIndex, #items do
		local order = items[ i ].order
		local touched = items[ i ].touched
		if not order or ( previous and order <= previous ) then
			return firstTouched or i, previousUntouched or maxValue
		end
		
		previous = order
		
		if touched and not firstTouched then
			firstTouched = i
		elseif not touched then
			firstTouched = nil
		end
		
		if not touched then
			previousUntouched = order
		end
	end
end

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

local function updateItem( i, items, altered, order )

	items[ i ].order = order
	altered[ i ] = order
	
	return order
	
end

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

local function adjustOrderFields( items, orderValue )
	orderValue = orderValue or orderGeneratorLex64

	--[[
	algorithm:
		scan to find first index with untouched order value
		if not found then
			assign first
			use insertAfter to fill array
			doneIndex = last
		else
			walk backward from found index w/ insertBefore
			
			doneIndex = foundIndex
		end
	
		find next index with untouched order value
		walk from doneIndex + 1 to foundIndex using insertBewtween to fill entries
		doneIndex = foundIndex
		repeat while doneIndex < #items
	]]
	local from = 1
	local maxValue
	local altered = { }

	while true do
		from, maxValue = findProblem( items, from, maxValue )
	
		if not from then
			break
		end
	
		-- locate a suitable basis value
		local foundIndex, anchorOrder = findAnchor( items, from, maxValue )

		if not foundIndex then
			-- fill out the remaining values after each other
			local previous = maxValue
			for i = from, #items do
				local nextValue = orderValue( previous, nil )
				previous = updateItem( i, items, altered, nextValue )
			end
			
			from = #items + 1
			maxValue = previous
		else
			-- walk backward to current point from anchor
			local previous = anchorOrder
			local oldMax = maxValue
			
			for i = foundIndex - 1, from, -1 do
				local nextValue = orderValue( oldMax, previous )
				previous = updateItem( i, items, altered, nextValue )
			end
			
			from = foundIndex + 1
			maxValue = anchorOrder
		end
	end
	
	return altered
end

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

return {

	findProblem = findProblem,
	orderGenerator = orderGenerator,
	adjustOrderFields = adjustOrderFields
	
}
