/*
  Copyright (c) 2023 Alex Diener
  
  This software is provided 'as-is', without any express or implied
  warranty. In no event will the authors be held liable for any damages
  arising from the use of this software.
  
  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:
  
  1. The origin of this software must not be misrepresented; you must not
     claim that you wrote the original software. If you use this software
     in a product, an acknowledgment in the product documentation would be
     appreciated but is not required.
  2. Altered source versions must be plainly marked as such, and must not be
     misrepresented as being the original software.
  3. This notice may not be removed or altered from any source distribution.
  
  Alex Diener alex@ludobloom.com
*/

#include "utilities/UndoUtilities.h"
#include <stdio.h>
#include <string.h>

void enumerateChangesBetweenOldAndNewLists(void * oldItems,
                                           unsigned int oldCount,
                                           void * newItems,
                                           unsigned int newCount,
                                           size_t stride,
                                           unsigned int (* compare)(void * oldItem, void * newItem, void * context),
                                           void (* itemAdded)(unsigned int index, void * newItem, void * context),
                                           void (* itemRemoved)(unsigned int index, void * oldItem, void * context),
                                           void (* itemModified)(unsigned int index, void * oldItem, void * newItem, unsigned int compareResult, void * context),
                                           void * context) {
	unsigned int startMatchCount = 0, endMatchCount = 0;
	unsigned int startCompareResult = 0, endCompareResult = 0;
	while (startMatchCount < oldCount && startMatchCount < newCount) {
		startCompareResult = compare(oldItems + startMatchCount * stride, newItems + startMatchCount * stride, context);
		if (startCompareResult != 0) {
			break;
		}
		startMatchCount++;
	}
	
	if (startMatchCount == oldCount && oldCount == newCount) {
		// Lists are identical; no changes
		return;
	}
	
	while (endMatchCount < oldCount - startMatchCount && endMatchCount < newCount - startMatchCount) {
		endCompareResult = compare(oldItems + (oldCount - 1 - endMatchCount) * stride, newItems + (newCount - 1 - endMatchCount) * stride, context);
		if (endCompareResult != 0) {
			break;
		}
		endMatchCount++;
	}
	
	if (startMatchCount + endMatchCount == oldCount) {
		// A run of items was added, and nothing else was changed
		for (unsigned int itemIndex = startMatchCount; itemIndex < newCount - endMatchCount; itemIndex++) {
			itemAdded(itemIndex, newItems + itemIndex * stride, context);
		}
		return;
	}
	
	if (startMatchCount + endMatchCount == newCount) {
		// A run of items was removed, and nothing else was changed
		for (unsigned int itemIndex = startMatchCount; itemIndex < oldCount - endMatchCount; itemIndex++) {
			itemRemoved(startMatchCount, oldItems + itemIndex * stride, context);
		}
		return;
	}
	
	if (oldCount == newCount) {
		// A run of items was modified without any additions or removals. The item after the first match (and before the last match, if non-overlapping) is known to have changed, so first and last compare can be skipped.
		itemModified(startMatchCount, oldItems + startMatchCount * stride, newItems + startMatchCount * stride, startCompareResult, context);
		for (unsigned int itemIndex = startMatchCount + 1; itemIndex < oldCount - endMatchCount - 1; itemIndex++) {
			unsigned int compareResult = compare(oldItems + itemIndex * stride, newItems + itemIndex * stride, context);
			if (compareResult != 0) {
				itemModified(itemIndex, oldItems + itemIndex * stride, newItems + itemIndex * stride, compareResult, context);
			}
		}
		if (oldCount - endMatchCount - 1 > startMatchCount) {
			itemModified(oldCount - endMatchCount - 1, oldItems + (oldCount - endMatchCount - 1) * stride, newItems + (oldCount - endMatchCount - 1) * stride, endCompareResult, context);
		}
		return;
	}
	
	// More than one type of change has taken place, and/or insertions/deletions are noncontiguous. Fall back to deleting and re-adding the entire nonmatching run.
	// TODO: This could be further improved by subdividing the nonmatching space after the first nonmatch and before the last nonmatch, and checking for matching runs within
	for (unsigned int itemIndex = startMatchCount; itemIndex < oldCount - endMatchCount; itemIndex++) {
		itemRemoved(startMatchCount, oldItems + itemIndex * stride, context);
	}
	for (unsigned int itemIndex = startMatchCount; itemIndex < newCount - endMatchCount; itemIndex++) {
		itemAdded(itemIndex, newItems + itemIndex * stride, context);
	}
}

void enumerateIdentifiableObjectChanges(void * oldItems,
                                        unsigned int oldCount,
                                        void * newItems,
                                        unsigned int newCount,
                                        size_t stride,
                                        bool (* compare)(void * oldItem, void * newItem, unsigned int * outCompareResult, void * context),
                                        void (* itemAdded)(unsigned int index, void * newItem, void * context),
                                        void (* itemRemoved)(unsigned int index, void * oldItem, void * context),
                                        void (* itemModified)(unsigned int index, void * oldItem, void * newItem, unsigned int compareResult, void * context),
                                        void * context) {
	unsigned int startExactMatchCount = 0, endExactMatchCount = 0;
	unsigned int startCompareResult = 0, endCompareResult = 0;
	bool startIsSameObject = false, endIsSameObject = false;
	unsigned int insertionCount = 0, deletionCount = 0;
	
	for (;;) {
		while (startExactMatchCount + deletionCount < oldCount - endExactMatchCount && startExactMatchCount + insertionCount < newCount - endExactMatchCount) {
			startIsSameObject = compare(oldItems + (startExactMatchCount + deletionCount) * stride, newItems + (startExactMatchCount + insertionCount) * stride, &startCompareResult, context);
			if (!startIsSameObject || startCompareResult != 0) {
				break;
			}
			startExactMatchCount++;
		}
		
		if (startExactMatchCount == oldCount && oldCount == newCount) {
			// Lists are identical; no changes
			return;
		}
		
		while (endExactMatchCount < oldCount - startExactMatchCount && endExactMatchCount < newCount - startExactMatchCount) {
			endIsSameObject = compare(oldItems + (oldCount - endExactMatchCount - 1) * stride, newItems + (newCount - endExactMatchCount - 1) * stride, &endCompareResult, context);
			if (!endIsSameObject || endCompareResult != 0) {
				break;
			}
			endExactMatchCount++;
		}
		
		if (startIsSameObject && startExactMatchCount + deletionCount < oldCount - endExactMatchCount && startExactMatchCount + insertionCount < newCount - endExactMatchCount) {
			// Narrow start range to objects that have different identities, invoking itemModified for changes
			itemModified(startExactMatchCount + insertionCount, oldItems + (startExactMatchCount + deletionCount) * stride, newItems + (startExactMatchCount + insertionCount) * stride, startCompareResult, context);
			startExactMatchCount++;
			while (startExactMatchCount + deletionCount < oldCount - endExactMatchCount - deletionCount && startExactMatchCount + insertionCount < newCount - endExactMatchCount - insertionCount) {
				startIsSameObject = compare(oldItems + (startExactMatchCount + deletionCount) * stride, newItems + (startExactMatchCount + insertionCount) * stride, &startCompareResult, context);
				if (!startIsSameObject) {
					break;
				}
				if (startCompareResult != 0) {
					itemModified(startExactMatchCount + insertionCount, oldItems + (startExactMatchCount + deletionCount) * stride, newItems + (startExactMatchCount + insertionCount) * stride, startCompareResult, context);
				}
				startExactMatchCount++;
			}
		}
		if (startExactMatchCount == oldCount - endExactMatchCount && oldCount == newCount) {
			// Start has met end, and all changes have been processed
			return;
		}
		if (endIsSameObject && endCompareResult != 0 && oldCount - endExactMatchCount > startExactMatchCount) {
			// If start hasn't met end, narrow end range in the same way
			itemModified(oldCount - endExactMatchCount - 1, oldItems + (oldCount - endExactMatchCount - 1) * stride, newItems + (newCount - endExactMatchCount - 1) * stride, endCompareResult, context);
			endExactMatchCount++;
			while (endExactMatchCount < oldCount - startExactMatchCount && endExactMatchCount < newCount - startExactMatchCount) {
				endIsSameObject = compare(oldItems + (oldCount - endExactMatchCount - 1) * stride, newItems + (newCount - endExactMatchCount - 1) * stride, &endCompareResult, context);
				if (!endIsSameObject) {
					break;
				}
				if (endCompareResult != 0) {
					itemModified(oldCount - endExactMatchCount - 1 + insertionCount - deletionCount, oldItems + (oldCount - endExactMatchCount - 1) * stride, newItems + (newCount - endExactMatchCount - 1) * stride, endCompareResult, context);
				}
				endExactMatchCount++;
			}
		}
		
		if (startExactMatchCount + endExactMatchCount == oldCount) {
			// A run of items was added, and nothing else was changed other than modifications already encoded
			for (unsigned int itemIndex = startExactMatchCount + insertionCount - deletionCount; itemIndex < newCount - endExactMatchCount; itemIndex++) {
				itemAdded(itemIndex, newItems + itemIndex * stride, context);
			}
			return;
		}
		
		if (startExactMatchCount + endExactMatchCount == newCount) {
			// A run of items was removed, and nothing else was changed other than modifications already encoded
			for (unsigned int itemIndex = startExactMatchCount + deletionCount; itemIndex < oldCount - endExactMatchCount; itemIndex++) {
				itemRemoved(startExactMatchCount, oldItems + itemIndex * stride, context);
			}
			return;
		}
		
		if (startExactMatchCount + deletionCount < oldCount) {
			// There's at least one nonmatching object to handle; process insertion and/or deletion
			startIsSameObject = false;
			for (unsigned int searchIndexNew = startExactMatchCount; searchIndexNew < newCount - endExactMatchCount - insertionCount; searchIndexNew++) {
				startIsSameObject = compare(oldItems + (startExactMatchCount + deletionCount) * stride, newItems + (searchIndexNew + insertionCount) * stride, &startCompareResult, context);
				if (startIsSameObject) {
					// Assuming no reordering, one or more insertions has taken place at this object's prior index
					for (unsigned int insertedItemIndex = startExactMatchCount; insertedItemIndex < searchIndexNew; insertedItemIndex++) {
						itemAdded(startExactMatchCount + insertionCount, newItems + (startExactMatchCount + insertionCount) * stride, context);
						insertionCount++;
					}
					break;
				}
			}
			if (!startIsSameObject) {
				// No match for this object anywhere; has been deleted
				itemRemoved(startExactMatchCount + insertionCount, oldItems + (startExactMatchCount + deletionCount) * stride, context);
				deletionCount++;
			}
		}
		if (startExactMatchCount + deletionCount >= oldCount - endExactMatchCount) {
			// No more old nonmatches, so changes ended with a deletion and one or more insertions; complete insertions and terminate
			for (unsigned int insertedItemIndex = startExactMatchCount + insertionCount; insertedItemIndex < newCount - endExactMatchCount; insertedItemIndex++) {
				itemAdded(insertedItemIndex, newItems + insertedItemIndex * stride, context);
				insertionCount++;
			}
			return;
		}
		// Start over and continue narrowing until all changes are resolved
	}
}

void listReorderSwaps(void * oldItems,
                      void * newItems,
                      unsigned int count,
                      size_t stride,
                      bool (* compare)(void * oldItem, void * newItem, void * context),
                      void (* swap)(unsigned int oldIndex, unsigned int newIndex, void * context),
                      void * context) {
	bool visited[count];
	memset(visited, 0, sizeof(visited));
	for (unsigned int itemIndex = 0; itemIndex < count; itemIndex++) {
		if (!visited[itemIndex]) {
			unsigned int adjustedIndex = itemIndex;
			while (!compare(oldItems + adjustedIndex * stride, newItems + itemIndex * stride, context)) {
				bool found = false;
				for (unsigned int itemIndex2 = itemIndex + 1; itemIndex2 < count; itemIndex2++) {
					if (!visited[itemIndex2] && itemIndex2 != adjustedIndex && compare(oldItems + adjustedIndex * stride, newItems + itemIndex2 * stride, context)) {
						swap(itemIndex, itemIndex2, context);
						visited[itemIndex2] = true;
						adjustedIndex = itemIndex2;
						found = true;
						break;
					}
				}
				if (!found) {
#ifdef DEBUG
					fprintf(stderr, "Warning: listReorderSwaps couldn't find a match for item %u; skipping\n", adjustedIndex);
#endif
					break;
				}
			}
		}
	}
}