/* -*- c++ -*-
FILE: History.cpp
RCS REVISION: $Revision: 1.29 $

COPYRIGHT: (c) 1999 -- 2003 Melinda Green, Don Hatch, and Jay Berkenbilt - Superliminal Software

LICENSE: Free to use and modify for non-commercial purposes as long as the
    following conditions are adhered to:
    1) Obvious credit for the source of this code and the designs it embodies
       are clearly made, and
    2) Ports and derived versions of 4D Magic Cube programs are not distributed
       without the express written permission of the authors.

DESCRIPTION:
    Implementation of the History class
*/

#include "MagicCube.h"
#include "History.h"
#include "Polymgr.h"
#include "Math4d.h"
#include "Preferences.h"
#include <ctype.h>


History::History(Preferences& p, PolygonManager4D *pmgr) :
    preferences(p)
{
    length = p.getLength();
    polymgr = pmgr;
    debug = preferences.getBoolProperty(M4D_HISTORY_DEBUG);
    current = first = last = (struct historynode *)NULL;
}

History::~History()
{
    clear();
}

void History::reset(int new_length)
{
    if (new_length != -1)
    {
        length = new_length;
    }
    clear();
}

int History::isSane()
{
    int found_current = 0;
    int ngrips = NFACES * 3 * 3 * 3;
    struct historynode *node;

    assert((first == 0) == (last == 0));

    if (first)
    {
        for (node = first; node; node = node->next)
        {
            if (node->prev)
            {
                assert(node->prev->next == node);
            }
            else
            {
                assert(first == node);
            }
            if (node->next)
            {
                assert(node->next->prev == node);
            }
            else
            {
                assert(last == node);
            }

            if (node == current)
            {
                assert(node->stickerid >= 0);
                found_current = 1;
            }

            if (node->stickerid >= 0)
            {
                assert(INRANGE(0 <=, node->stickerid, <ngrips));
                assert(node->dir == CCW || node->dir == CW);
            }
        }
    }

    assert(found_current == (current != 0));

    return 1;
}


void History::deleteNode( struct historynode *node)
{
    if (!node)
        return;
    if (current == node)
        current = node->next;

    if (node->prev)
        node->prev->next = node->next;
    else
        first = node->next;
    if (node->next)
        node->next->prev = node->prev;
    else
        last = node->prev;
    delete node;
}

void History::insertNode(
        struct historynode *node_to_insert_before,
        int stickerid, int dir, int slicesmask, int mark)
{
    historynode *temp;

    temp = new historynode;
    temp->stickerid = stickerid;
    temp->dir = dir;
    temp->slicesmask = slicesmask;
    temp->mark = mark;

    temp->prev = (node_to_insert_before ?
                  node_to_insert_before->prev : last);
    temp->next = node_to_insert_before;

    if (temp->next)
        temp->next->prev = temp;
    else
        last = temp;

    if (temp->prev)
        temp->prev->next = temp;
    else
        first = temp;
}

void History::deleteLast()
{
    deleteNode(last);
}

void History::clear()
{
    while (first)
        deleteLast();
}

void History::append(int stickerid, int dir, int slicesmask)
{
    struct historynode *node = getPrevious();
    if(node != NULL // there is a previous twist
        && node->stickerid == stickerid // same axis
        && node->slicesmask == slicesmask // same slices
        && node->dir == -dir) // but in *opposite* direction
    {
        struct stickerspec dummyss;
        int dummyint;
        undo(&dummyss, &dummyint, &dummyint); // just back the move out rather than append an inverse move
    }
    else
        insertNode(NULL, stickerid, dir, slicesmask, 0);
}

void History::mark(int mark)
{
    insertNode(current, -1, 0, 0, mark);
}


/*
 * If there is a "current", delete it and everything after it.
 */
void History::truncate()
{
    while (current)
        deleteLast();
    // Special case: If we are at a macro open mark, eat it.

    // FIX THIS -- see comments in
    // EventHandler::applyMacroCBAfterGotRefStickers about how this
    // makes things awkward at time of application of macro.  The
    // marking of macros is a little problematic implemented this way,
    // but the current kludges seem to work right.  One needs to be
    // able to undo/redo past macros in fast automove mode and to have
    // no stray m[ in the file after doing a move following undoing a
    // macro or after applying a macro after undoing a macro.
    if (atMacroOpen())
    {
        deleteLast();
    }
}

/*
 * Set current to be the beginning of the list.
 */
void History::goToBeginning()
{
    current = first;
}

void History::goToEnd()
{
    current = NULL;
}

/*
 * Put a single move into the history.
 * This clears the history after
 * the current point, so a "redo" is impossible afterwards.
 */
void History::apply(struct stickerspec *sticker, int dir, int slicesmask)
{
    truncate();
    append(sticker->id_within_cube, dir, slicesmask);
}

int History::size()
{
    struct historynode *node;
    int         count = 0;
    for (node = first; node; node = node->next)
        count++;
    return count;
}

/*
 * Truncate (i.e. delete everything past current),
 * remove non-moves (marks),
 * merge rotates,
 * put rotates before the twists,
 * put opposite-face twists in canonical order,
 * merge same-face twists.
 * This is usually done in preparation for a "cheat" solve.
 *
 * FIX THIS-- this should be done on the fly, as the cheat-solve is happening
 * (doing it like this causes a long wait if the history is long).
 */
void History::compress()
{
    struct historynode *node, **nodeptr;
    struct historynode *first_on_this_face, *past_last_on_this_face;
    int         current_matrix[4][4], incmat[4][4], testmat[4][4],
        newcoords[4];
    struct stickerspec grip;
    int         face, dir, thisface, nextface, temp;

    /*
     * Truncate
     */
    truncate();

    /*
     * Remove all non-moves
     */
    for (nodeptr = &first; *nodeptr;)
    {
        if ((*nodeptr)->stickerid == -1)
            deleteNode(*nodeptr);
        else
            nodeptr = &(*nodeptr)->next;
    }

    /*
     * Sweep all rotates to beginning
     */
    IDENTMAT4(current_matrix);
    for (nodeptr = &last; *nodeptr;)
    {
        if ((1 << length) & ~(*nodeptr)->slicesmask)
        {
            /*
             * It's a twist (some slices stay and some move).
             * Apply the current matrix to the coords of
             * the grip.
             */
            grip.id_within_cube = (*nodeptr)->stickerid;
            polymgr->fillStickerspecFromIdAndLength(&grip, 3);
            VXM4i(grip.coords, grip.coords, current_matrix);
            polymgr->fillStickerspecFromCoordsAndLength(&grip, 3);
            (*nodeptr)->stickerid = grip.id_within_cube;

            nodeptr = &(*nodeptr)->prev;
        }
        else
        {
            /*
             * It's a rotate.  Just preconcatenate it
             * to the current matrix.
             */
            grip.id_within_cube = (*nodeptr)->stickerid;
            polymgr->fillStickerspecFromIdAndLength(&grip, 3);
            real angle = polymgr->getTwistTotalAngle(grip.dim, (*nodeptr)->dir);
            Math4d::get4dTwistMat(grip.coords, angle, incmat);
            MXM4i(current_matrix, incmat, current_matrix);

            deleteNode(*nodeptr);
        }
    }
    /*
     * The proper thing to do now would be to add the rotates
     * to the beginning of the history, but I'm not bothering,
     * since the only thing this function is used for anyway
     * is the cheat-solve.
     */

    /*
     * Put opposite-face twists in canonical order
     */
    for (node = first; node;)
    {
        if (node->slicesmask == 1 &&
            node->next && node->next->slicesmask == 1)
        {
            thisface = PolygonManager4D::faceOfGrip(node->stickerid);
            nextface = PolygonManager4D::faceOfGrip(node->next->stickerid);
            if (nextface < thisface &&
                nextface == polymgr->oppositeFace(thisface))
            {
                SWAP(node->stickerid, node->next->stickerid, temp);
                SWAP(node->dir, node->next->dir, temp);
                SWAP(node->slicesmask, node->next->slicesmask, temp);
                if (node->prev)
                    node = node->prev;
            }
            else
                node = node->next;
        }
        else
            node = node->next;
    }

    /*
     * Merge same-face twists
     */
    for (first_on_this_face = first; first_on_this_face;)
    {
        if (first_on_this_face->slicesmask == 1)
        {
            face = PolygonManager4D::faceOfGrip(first_on_this_face->stickerid);
            past_last_on_this_face = first_on_this_face->next;
            while (past_last_on_this_face &&
                   past_last_on_this_face->slicesmask == 1 &&
                   PolygonManager4D::faceOfGrip(
                       past_last_on_this_face->stickerid) == face)
            {
                past_last_on_this_face = past_last_on_this_face->next;
            }

            if (past_last_on_this_face != first_on_this_face->next)
            {
                /*
                 * There is more than one twist on this face.
                 * Concatenate together all the matrices of these
                 * twists, and then figure out how to accomplish it
                 * with one or two twists on a single grip.
                 */
                IDENTMAT4(current_matrix);
                for (node = first_on_this_face;
                     node != past_last_on_this_face; node = node->next)
                {
                    grip.id_within_cube = node->stickerid;
                    polymgr->fillStickerspecFromIdAndLength(&grip, 3);
                    real angle = polymgr->getTwistTotalAngle(grip.dim, node->dir);
                    Math4d::get4dTwistMat(grip.coords, angle, incmat);
                    MXM4i(current_matrix, current_matrix, incmat);
                }

                /*
                 * We now have all the information we need;
                 * delete the twists from the history
                 */
                while (first_on_this_face != past_last_on_this_face)
                {
                    struct historynode *temp = first_on_this_face;
                    first_on_this_face = first_on_this_face->next;
                    deleteNode(temp);
                }

                /*
                 * Find a sticker on this face that's not
                 * moved by the matrix; that will be the grip of the
                 * concatenated move.
                 */
                grip.face = face;
                for (grip.id_within_face = 0;
                     grip.id_within_face < 3 * 3 * 3; grip.id_within_face++)
                {
                    polymgr->fillStickerspecFromFaceAndIdAndLength
                        (&grip, 3);
                    if (grip.dim >= 3)
                        continue;
                    VXM4(newcoords, grip.coords, current_matrix);
                    if (EQVEC4(newcoords, grip.coords))
                    {
                        real        angle;
                        /*
                         * Found the right grip;
                         * see if any of the following work:
                         *  0 twists
                         *  1 twist CW
                         *  1 twist CCW
                         *  2 twists in random direction
                         */
                        IDENTMAT4(testmat);
                        if (EQMAT4(testmat, current_matrix))
                        {
                            /*
                             * Result is 0 twists.
                             */
                            break;
                        }
                        angle = polymgr->getTwistTotalAngle(grip.dim, CCW);
                        Math4d::get4dTwistMat(grip.coords, angle, testmat);
                        if (EQMAT4(testmat, current_matrix))
                        {
                            /*
                             * Result is 1 twist CCW.
                             */
                            insertNode(
                                                   past_last_on_this_face,
                                                   grip.id_within_cube,
                                                   CCW, 1, 0);
                            break;
                        }
                        angle = polymgr->getTwistTotalAngle(grip.dim, CW);
                        Math4d::get4dTwistMat(grip.coords, angle, testmat);
                        if (EQMAT4(testmat, current_matrix))
                        {
                            /*
                             * Result is 1 twist CW.
                             */
                            insertNode(
                                                   past_last_on_this_face,
                                                   grip.id_within_cube,
                                                   CW, 1, 0);
                            break;
                        }

                        dir = (rand() % 2 ? CW : CCW);
                        angle = polymgr->getTwistTotalAngle(grip.dim, CCW);
                        Math4d::get4dTwistMat(grip.coords, angle, testmat);
                        MXM4i(testmat, testmat, testmat);
                        if (EQMAT4(testmat, current_matrix))
                        {
                            /*
                             * Result is 2 twists
                             * in arbitrary direction.
                             */
                            insertNode(
                                                   past_last_on_this_face,
                                                   grip.id_within_cube,
                                                   dir, 1, 0);
                            insertNode(
                                                   past_last_on_this_face,
                                                   grip.id_within_cube,
                                                   dir, 1, 0);
                            break;
                        }
                        assert(0);
                    }
                }
                assert(grip.id_within_face < 3 * 3 * 3);
            }
            first_on_this_face = past_last_on_this_face;
        }
        else
            first_on_this_face = first_on_this_face->next;
    }
}                               /* history_compress_history */

struct History::historynode* History::getPrevious()
{
    /*
     * return most recent history node whether actual move or not
     */
    return (current ? current->prev : last);
}

/*
 * Back up one move in the history, returning a move
 * that would undo the last move.
 * Returns 1 on success, 0 if there is nothing to undo.
 */
int History::undo(
        struct stickerspec *sticker, /* OUTPUT */
        int *Dir,  /* OUTPUT */
        int *Slicesmask)   /* OUTPUT */
{
    struct historynode *node;
    /*
     * search backwards to the next actual move
     */
    for (node = getPrevious(); node != NULL; node = node->prev)
    {
        if (node->stickerid != -1)
            break;
    }

    if (!node)
        return 0;

    current = node;

    /* the following code is duplicated below */
    sticker->id_within_cube = current->stickerid;
    polymgr->fillStickerspecFromIdAndLength(sticker, 3);
    *Dir = current->dir;
    *Slicesmask = current->slicesmask;

    *Dir = -*Dir;

    if (debug)
        printf("History size is now %d\n", size());

    return 1;
}


/*
 * Go forward one move in the history, returning the move
 * to redo.  This is only valid if a move was undone.
 * Returns 1 on success, 0 if there is nothing to redo.
 */
int History::redo(struct stickerspec *sticker, /* OUTPUT */
                  int *Dir, /* OUTPUT */
                  int *Slicesmask) /* OUTPUT */
{
    if (!current)
        return 0;

    /* the following code is duplicated above */
    sticker->id_within_cube = current->stickerid;
    polymgr->fillStickerspecFromIdAndLength(sticker, 3);
    *Dir = current->dir;
    *Slicesmask = current->slicesmask;

    current = current->next;
    while (current && current->stickerid == -1)
        current = current->next;

    return 1;
    if (debug)
        printf("History size is now %d\n", size());
}


int History::goBackwardsTowardsMark(int mark,
                                    struct stickerspec *sticker, /* OUTPUT */
                                    int *Dir, /* OUTPUT */
                                    int *Slicesmask) /* OUTPUT */
{
    struct historynode* node;
    // Continue searching backwards for a potential undo
    for (node = getPrevious(); node; node = node->prev)
    {
        if (node->stickerid == -1 && node->mark == mark)
        {
            if (!undo(sticker, Dir, Slicesmask))
            {
                fprintf(stderr, "history_gotowards_mark: coudn't undo???\n");
                return 0;
            }
            return 1;
        }
    }
    return -1;
}

int History::goForwardsTowardsMark(int mark,
                                   struct stickerspec *sticker, /* OUTPUT */
                                   int *Dir, /* OUTPUT */
                                   int *Slicesmask) /* OUTPUT */
{
    struct historynode* node;
    // Search forwards for a potential redo
    for (node = (current ? current : 0);
         node; node = node->next)
    {
        if (node->stickerid == -1 && node->mark == mark)
        {
            if (!redo(sticker, Dir, Slicesmask))
            {
                fprintf(stderr, "history_gotowards_mark: coudn't redo???\n");
                return 0;
            }
            return 1;
        }
    }
    return -1;
}


/*
 * Executes a history_undo or history_redo and returns 1 on success.
 * Returns 0 if already at the mark, -1 if no such mark.  If
 * forward_first is true and we are not at the mark, then search
 * forward first and search backward only if the mark is not ahead of
 * us.  Otherwise, search backward first and search forward only if
 * the mark is not behind us.  Being able to choose which way to go
 * first makes it useful to have multiple marks with the same
 * identifier.
 */
int History::goTowardsMark(int mark, struct stickerspec *sticker, /* OUTPUT */
                           int *Dir, /* OUTPUT */
                           int *Slicesmask, /* OUTPUT */
                           bool forward_first)
{
    int status = -1;
    if (atMark(mark))
    {
        return 0;               /* already at the mark */
    }
    if (! forward_first)
    {
        status = this->goBackwardsTowardsMark(mark, sticker, Dir, Slicesmask);
        if (status >= 0)
        {
            return status;
        }
    }
    status = this->goForwardsTowardsMark(mark, sticker, Dir, Slicesmask);
    if (status >= 0)
    {
        return status;
    }
    if (forward_first)
    {
        status = this->goBackwardsTowardsMark(mark, sticker, Dir, Slicesmask);
    }
    return status;
}

/*
 * Make a note that the puzzle is currently in a solved state
 * so that hitting the "cheat" button will not make it go past
 * this state.  Actually this is probably not necessary since
 * the program can check by itself.
 */
void History::noteSolved()
{
    fprintf(stderr, "history_note_solved: not implemented\n");
}

void History::dump( FILE *fp)
{
    struct historynode *node;
    int         nwritten, stickerid;
    int         ngripsperface = 3 * 3 * 3;

    assert(isSane());
    nwritten = 0;
    for (node = first; node; node = node->next)
    {
        if (node == current)
            fprintf(fp, "c ");
        if (node->stickerid >= 0)
        {
            stickerid = node->stickerid;
            /*
             * If it's CW, use the opposite sticker.
             */
            if (node->dir == CW)
                stickerid = ROUNDDOWN(stickerid, ngripsperface) +
                    ngripsperface - 1 - stickerid % ngripsperface;
            fprintf(fp, "%d%d", stickerid / ngripsperface,
                    stickerid % ngripsperface);
            if (node->slicesmask != 1)
                fprintf(fp, ":%d", node->slicesmask);
        }
        else
        {
            fprintf(fp, "m%c", node->mark);
        }
        nwritten++;
        if (node->next)
        {
            if (nwritten % 10 == 0)
                fprintf(fp, "\n");
            else
                fprintf(fp, " ");
        }
    }
    fprintf(fp, ".\n");
}

#define lookc(fp) ungetc(getc(fp), fp)

int History::read( FILE *fp)
{
    char        inchar;
    int         c;
    int         face, stickeronface, slicesmask;
    int         ngripsperface = 3 * 3 * 3;
    struct historynode **who_will_point_to_current = 0; /* BLEAH! */

    clear();

    while (1)
    {
        while ((c = getc(fp)) != EOF && isspace(c))
            ;
        if (c == EOF)
            goto outahere;
        if (c == '.')
            break;
        if (isdigit(c))
        {
            slicesmask = 1;
            ungetc(c, fp);
            if (fscanf(fp, "%1d%d:%d", &face, &stickeronface, &slicesmask) < 2)
                goto outahere;
            append(
                face * ngripsperface + stickeronface,
                CCW, slicesmask);
        }
        else if (c == 'm')
        {
            if (fscanf(fp, "%c", &inchar) != 1)
                goto outahere;
            mark((int)inchar);
        }
        else if (c == 's')
        {
            noteSolved();
        }
        else if (c == 'c')
        {
            who_will_point_to_current = (last ? &last->next : &first);
        }
        else
            goto outahere;
    }
    if (who_will_point_to_current)
        current = *who_will_point_to_current;
    if (debug)
        printf("History size is now %d\n", size());
    return 1;
    {
    int status = read(fp);
    if (!isSane())
        fprintf(stderr, "Internal error: history is messed up.\n");
    return status;
    }

  outahere:
    fprintf(stderr, "Error reading history-- no history read\n");
    clear();
    return 0;
}


int History::countTwists()
{
    int         result = 0;
    struct historynode *cur_node;
    for (cur_node = first; cur_node; cur_node = cur_node->next)
    {
        if (cur_node->stickerid >= 0)
        {
            ++result;
        }
    }
    return result;
}

int History::atMark(int mark)
{
    struct historynode *node;
    /*
     * Go through all marks at the current position
     */
    for (node = (current ? current->prev : last);
         node && node->stickerid == -1;
         node = node->prev)
    {
        if (node->stickerid == -1 && node->mark == mark)
        {
            return 1;
        }
    }
    return 0;
}

int History::atMacroOpen()
{
    return atMark(MARK_MACRO_OPEN);
}

int History::atMacroClose()
{
    return atMark(MARK_MACRO_CLOSE);
}

int History::atScrambleBoundary()
{
    return atMark(MARK_SCRAMBLE_BOUNDARY);
}

// Local Variables:
// c-basic-offset: 4
// c-comment-only-line-offset: 0
// c-file-offsets: ((defun-block-intro . +) (block-open . 0) (substatement-open . 0) (statement-cont . +) (statement-case-open . +4) (arglist-intro . +) (arglist-close . +) (inline-open . 0))
// indent-tabs-mode: nil
// End: