/*
  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
*/

#ifndef __UndoUtilities_H__
#define __UndoUtilities_H__
#ifdef __cplusplus
extern "C" {
#endif

#include <stdbool.h>
#include <stddef.h>

// Inspects the items in oldItems and newItems, which are of size stride, and makes a series of calls to the provided
// itemAdded, itemRemoved, and itemModified callbacks, in such an order that applying the changes as specified would
// transform oldItems into newItems, and applying the changes in reverse order (swapping the meanings of add and remove)
// would transform newItems into oldItems. The provided compare callback is used to determine whether two items are
// equal to each other, and should return 0 if they are considered equal. The context argument is passed unchanged
// as the final argument to all callbacks.
// 
// Recommended usage: In an UndoStateDelta implementation for an object that tracks a resizable list of data, call
// this function to generate a list of instructions in the itemAdded, itemRemoved, and itemModified callbacks to be
// played back in the UndoStateDelta's apply() and revert() implementations. In revert(), execute the instructions
// backward and swap the meanings of add and remove. If a modification delta is stored in xor format, both apply()
// and revert() can perform the same operation.
// 
// This function makes a basic effort to encode changes efficiently (for example, calling itemModified when possible
// instead of itemRemoved and itemAdded), but does not attempt to be fully optimal. It's best used to compare lists
// where only one of the three types of changes is likely to have been applied at a time, and ideally if added and
// removed items are contiguous. However, it should function as described for any two lists, despite possible
// inefficiencies in delta encoding.
// 
// Note that provided item indexes are relative to the assumed current state of the list in execution order. For
// example, a 4-item list that has the middle 2 items removed would call itemRemoved twice with an index of 1,
// because the first removal would shift all following items downward by one index.
// 
// The return value of the compare function will be passed to itemModified in the compareResult argument, and can be
// used to encode a bitfield of change types between the two compared items if desired. For example, an item might
// consist of a number of primitive struct fields and a large data buffer; by setting a bit in the value returned
// from compare() based on whether the large data buffer has modifications or not, itemModified can use that value
// to determine whether it's necessary to encode buffer changes, or only operate on the simpler, less expensive data
// contained in each modified item.
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);

// Similar behavior to enumerateChangesBetweenOldAndNewLists, but for lists where every item has a unique identity
// that can be matched up between old and new lists, as specified by the value returned by the compare callback.
// itemAdded and itemRemoved will only be used for items that have no match considered to have the same identity,
// and itemModified will only be used for objects with the same identity. This may take more compare operations
// than enumerateChangesBetweenOldAndNewLists, but will have a more precise result with no redundant operations.
// 
// Note that unlike enumerateChangesBetweenOldAndNewLists, the compare callback should return a boolean value
// indicating whether the two objects are considered to have the same identity or not. This value does not indicate
// whether modifications have been made to two objects considered the same; in this case, return true and write a
// value to outCompareResult, which will be passed on to itemModified callbacks as compareResult. Note that if the
// compare function returns false, the value written to outCompareResult is not used, so the implementation can be
// short circuited to return as soon as objects are determined to be different without additional comparisons.
// 
// Note also that this functions assumes items generally are not reordered. Reordering will be handled as calls to
// itemAdded and itemRemoved.
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);

// Calls compare() to determine equality between elements of oldItems and newItems (of size stride, which must
// both have the same count), and calls swap() a minimal number of times to specify a sequence of operations that
// would trandform oldItems into newItems if performed in order, and vice versa if performed in reverse. oldItems
// and newItems must contain the same set of elements, with order being the only difference. compare() should
// return true for two items that are equal, and false for any two items that are not equal. Each item in oldItems
// should match exactly one item in newItems when compared.
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);

#ifdef __cplusplus
}
#endif
#endif