struct history_info {
    uint16 ActionCount_Total;
    uint16 ActionCount_EndOfPlayhead;
    uint16 ActionCount_Current;

    uint64 ActionOffset_Total;
    uint64 ActionOffset_EndOfPlayhead;
    uint64 ActionOffset_Current;

    uint64 EntrySize_Current;
};

static uint64
History_GetActionSize(history_entry_list *History, int i, uint16 ActionCount_EndOfPlayhead)
{
    history_action *Action = &History->Action[i];
    if (Action->Type == action_type_swap)
        return Action->Size;
    return 0;
}

// Returns information on the undo tree based on three points of data: the
// total amount of entries, the location of the playhead, and whatever location
// SampleIndex is set to, which should be either one minus playhead or the playhead.

// I wrote this with the intent of precomputing things like the tree's total
// size and the size of the current action, because calculating them in the
// Action_Redo/Undo calls got extremely confusing.

static history_info
History_GetTreeInfo(history_entry_list *History, uint16 SampleIndex)
{
    history_info Info = {};

    for (int i = 0; i < History->NumberOfEntries; i++)
    {
        history_entry *Entry = &History->Entry[i];
        Info.ActionCount_Total += Entry->NumberOfActions;
        if (i < History->EntryPlayhead)
            Info.ActionCount_EndOfPlayhead += Entry->NumberOfActions;
        if (i < SampleIndex)
            Info.ActionCount_Current += Entry->NumberOfActions;
    }

    for (int i = 0; i < Info.ActionCount_Total; i++)
    {
        uint64 Size = History_GetActionSize(History, i, Info.ActionCount_EndOfPlayhead);
        Info.ActionOffset_Total += Size;
        if (i < Info.ActionCount_EndOfPlayhead)
            Info.ActionOffset_EndOfPlayhead += Size;

        if (i < Info.ActionCount_Current)
            Info.ActionOffset_Current += Size;
        else if (i < Info.ActionCount_EndOfPlayhead)  // Only increment the current size if i is between
            Info.EntrySize_Current += Size;           // the current count and playhead count!
    }

    return Info;
}

void History_Action_Undo(memory *Memory, history_info Info, history_action *ActionPointer, uint64 Action_Offset)
{
    history_entry_list *History = &Memory->History;

    // Only swap_bitmap should touch the data!
    history_action Action = *ActionPointer;

    uint8 *Address_HistoryTree_Start = (uint8 *)Memory_AddressAtOffset(Memory, P_UndoBuffer, Action_Offset);
    uint8 *Address_HistoryTree_End = (uint8 *)Memory_AddressAtOffset(Memory, P_UndoBuffer, Info.ActionOffset_Total);
    uint8 *Address_Data = (uint8 *)Memory_AddressAtOffset(Memory, Action.TableName, Action.ByteOffset);

    if (Action.Type == action_type_swap) {
        Arbitrary_SwapData(Memory, Address_HistoryTree_Start, Address_Data, Action.Size);
    } else if (Action.Type == action_type_shift) {
        // In order to shift back we have to start the address at where the
        // shifted chunk is _now_, not when we called the function.
        uint64 NewByteOffset = (Action.Direction > 0) ? Action.ByteOffset + Action.ShiftAmount : Action.ByteOffset - Action.ShiftAmount;
        void *Address_Start = Memory_AddressAtOffset(Memory, Action.TableName, NewByteOffset);
        uint8 *Address_End = (uint8 *)Address_Start + Action.Size;
        // Direction also needs to be reversed.
        int16 Direction = Action.Direction * -1;
        Arbitrary_ShiftData((uint8 *)Address_Start, Address_End, Action.ShiftAmount, Direction);
    } else {
        Assert(0);
    }
}

void History_Action_Redo(memory *Memory, history_info Info, history_action *ActionPointer, uint64 Action_Offset) {

    history_entry_list *History = &Memory->History;

    history_action Action = *ActionPointer;

    uint8 *Address_HistoryTree_Start = (uint8 *)Memory_AddressAtOffset(Memory, P_UndoBuffer, Action_Offset);
    uint8 *Address_HistoryTree_End = (uint8 *)Memory_AddressAtOffset(Memory, P_UndoBuffer, Info.ActionOffset_Total);
    uint8 *Address_Data = (uint8 *)Memory_AddressAtOffset(Memory, Action.TableName, Action.ByteOffset);

    if (Action.Type == action_type_swap) {
        Arbitrary_SwapData(Memory, Address_HistoryTree_Start, Address_Data, Action.Size);
    } else if (Action.Type == action_type_shift) {
        void *Address_Start = Memory_AddressAtOffset(Memory, Action.TableName, Action.ByteOffset);
        uint8 *Address_End = (uint8 *)Address_Start + Action.Size;
        int16 Direction = Action.Direction;
        Arbitrary_ShiftData((uint8 *)Address_Start, Address_End, Action.ShiftAmount, Direction);
    } else {
        Assert(0);
    }
}

void History_Undo(memory *Memory) {
    history_entry_list *History = &Memory->History;
    if (History->EntryPlayhead == 0) return;

    // We want Current to represent the beginning of the current entry, so we
    // subtract one from the playhead.
    history_info Info = History_GetTreeInfo(History, History->EntryPlayhead - 1);
    history_entry *Entry = &History->Entry[History->EntryPlayhead - 1];

    // This puts us at the end of the current entry's offset.
    uint64 ActionOffset_Stepback = Info.ActionOffset_Current + Info.EntrySize_Current;

    for (int i = Entry->NumberOfActions - 1; i >= 0; i--) {
        history_action *Action = &History->Action[Info.ActionCount_Current + i];

        // We step backwards only if the action is currently storing data.
        if (Action->Type != action_type_shift)
            ActionOffset_Stepback -= Action->Size;

        History_Action_Undo(Memory, Info, Action, ActionOffset_Stepback);
    }

    History->EntryPlayhead--;

}

void History_Redo(memory *Memory) {
    history_entry_list *History = &Memory->History;
    if (History->EntryPlayhead == History->NumberOfEntries) return;

    // NOTE(fox): The third part of this function for recording the "current"
    // action's size is only necessary for the undo call, so it's not correct on the redo.
    history_info Info = History_GetTreeInfo(History, History->EntryPlayhead);
    history_entry *Entry = &History->Entry[History->EntryPlayhead];

    History->EntryPlayhead++;

    uint64 ActionOffset_Stepforward = Info.ActionOffset_Current;

    for (int i = 0; i < Entry->NumberOfActions; i++) {
        history_action *Action = &History->Action[Info.ActionCount_Current + i];

        History_Action_Redo(Memory, Info, Action, ActionOffset_Stepforward);

        // We step forwards only if the action is currently storing data.
        if (Action->Type != action_type_shift)
            ActionOffset_Stepforward += Action->Size;

    }

}

// This is only called when we're certain the action is going to be taken.
void History_Entry_Commit(memory *Memory, char *Name)
{
    history_entry_list *History = &Memory->History;
    history_entry *Entry = &History->Entry[History->EntryPlayhead];
    Entry->Name = Name;
    Entry->NumberOfActions = 0;
    // Effectively deletes entries in front if we're beginning out of an undo.
    if (History->NumberOfEntries != History->EntryPlayhead)
        History->NumberOfEntries = History->EntryPlayhead;
    History->NumberOfEntries++;
    History->EntryPlayhead++;
    Memory->IsFileSaved = false;
#if DEBUG
    Assert(Debug.UndoState != 1);
    Debug.UndoState = 1;
#endif
}

void History_Entry_End(memory *Memory)
{
    history_entry_list *History = &Memory->History;
#if DEBUG
    Debug.UndoState = 0;
#endif
}

// NOTE(fox): Shift is the only action that additionally changes the data after
// the info is put on the tree, since it's always the same function used.

static void History_Action_Add(memory *Memory, history_action ActionData, void *ReferenceData = NULL)
{
    history_entry_list *History = &Memory->History;
    history_entry *Entry = &History->Entry[History->EntryPlayhead - 1];

    history_info Info = History_GetTreeInfo(History, History->EntryPlayhead - 1);

    history_action *Action = &History->Action[Info.ActionCount_Total];
    *Action = ActionData;

    if (Action->Type == action_type_swap)
    {
        void *Address_HistoryTree = Memory_AddressAtOffset(Memory, P_UndoBuffer, Info.ActionOffset_Total);
        void *Address_Data = Memory_AddressAtOffset(Memory, Action->TableName, Action->ByteOffset);
        Memory_Copy((uint8 *)Address_HistoryTree, (uint8 *)Address_Data, Action->Size);
    } else if (Action->Type == action_type_shift)
    {
        void *Address_Start = Memory_AddressAtOffset(Memory, Action->TableName, Action->ByteOffset);
        uint8 *Address_End = (uint8 *)Address_Start + Action->Size;
        Arbitrary_ShiftData((uint8 *)Address_Start, Address_End, Action->ShiftAmount, Action->Direction);
    }

    Entry->NumberOfActions++;
}

// Helper functions for different tables.


static void History_Action_Shift(memory *Memory, memory_table_list TableName,
                                 void *Address0, void *Address1, uint64 Amount, int16 Direction)
{
    void *Address_Start = Memory->Slot[TableName].Address;
    uint64 ByteOffset = (ptrsize)Address0 - (ptrsize)Address_Start;
    uint64 Size = (ptrsize)Address1 - (ptrsize)Address0;

    history_action Action = { TableName, action_type_shift, Size, ByteOffset, Amount, Direction };

    History_Action_Add(Memory, Action);
}

static void History_Action_Block_Swap(memory *Memory, memory_table_list TableName, void *Address_Data)
{
    void *Address_Start = Memory->Slot[TableName].Address;
    uint64 Size = Memory->Slot[TableName].Block_ElementSize;
    uint64 ByteOffset = (ptrsize)Address_Data - (ptrsize)Address_Start;
    history_action Action = { TableName, action_type_swap, Size, ByteOffset, 0 };
    History_Action_Add(Memory, Action);
}

// Remember to dereference pointers if taking the sizeof() a variable, or else Size will be 8!

static void History_Action_Swap(memory *Memory, memory_table_list TableName, uint64 Size, void *Address_Data)
{
    void *Address_Start = Memory->Slot[TableName].Address;
    uint64 ByteOffset = (ptrsize)Address_Data - (ptrsize)Address_Start;
    history_action Action = { TableName, action_type_swap, Size, ByteOffset, 0 };
    History_Action_Add(Memory, Action);
}