8 files changed, 392 insertions, 69 deletions

diff --git a/TODO/2.1.md b/TODO/2.1.md
index 92e4555..d65eb93 100644
--- a/TODO/2.1.md
+++ b/TODO/2.1.md
@@ -1,5 +1,31 @@
 # TODO-list for version 2.1 (or is it 3.0 at this point?)
 
+## Alg and moveset changes (prerequisite for solve.h)
+
+### moveset.h
+* split off from alg.h
+
+### alg.h
+* There is a (future) bug in the way the solver checks if a move can
+be appended (allowed_next and similar): the last two moves are not enough.
+* Example: using QTM we have last 3 moves U U D. Considering only last 2,
+U could be appended, but it cannot (cancel to U').
+* Solution: the per-moveset bool allowed_next() should take an alg as
+parameter. There are going to be basically two versions, one for QTM and
+one for HTM (but more may be added).
+* Alg should be extended to remember the list of moves on inverse / normal
+separately (without looping over moves).
+* Maybe another parameter to know if it can assume there has not been
+any double switching, i.e. if the last moves are the only ones to
+be checked and there is no need to go back further (e.g. if alg is
+U (... stuff on inverse ...) D I don't want to have to check back
+to the U, but in practice we can often assume this does not happen).
+* Then we can remove last and lastinv from dfsdata.
+* move also can_niss to alg.h
+* the check for the order of the moves (to avoid counting L R and R L as
+different) can be made separately. Maybe add a "compare" function for moves,
+such that non-commuting moves are not comparable (return -1 0 1).
+
 ## Rework solver
 
 * The architecture is the following: solve.h contains a solve() public
@@ -24,7 +50,6 @@ necessary). Maybe cleanup solveoptions too (e.g. threads not necessary).
 * solve.h depends only on moves (dependency on step and trans is removed).
 * preparation step should be reworked, maybe removed or delegated to the
 specific implementations.
-* allowed_moves and cancel_niss are moved to move.h.
 * All dfs stuff in the same function. Maybe remove also solvestop.
 * Move two-step solve to a different module
 
diff --git a/src/alg.c b/src/alg.c
index 47e222b..2815599 100644
--- a/src/alg.c
+++ b/src/alg.c
@@ -84,30 +84,42 @@ append_move(Alg *alg, Move m, bool inverse)
         alg->move[alg->len] = m;
         alg->inv [alg->len] = inverse;
         alg->len++;
+
+        if (inverse)
+                alg->move_inverse[alg->len_inverse++] = m;
+        else
+                alg->move_normal[alg->len_normal++] = m;
 }
 
 static int
 axis(Move m)
 {
-        if (m == NULLMOVE)
-                return 0;
+        static int aux[] = {
+                [NULLMOVE] = 0,
 
-        if (m >= U && m <= B3)
-                return (m-1)/6 + 1;
-        
-        if (m >= Uw && m <= Bw3)
-                return (m-1)/6 - 2;
+                [U]  = 1, [U2]  = 1, [U3]  = 1,
+                [D]  = 1, [D2]  = 1, [D3]  = 1,
+                [Uw] = 1, [Uw2] = 1, [Uw3] = 1,
+                [Dw] = 1, [Dw2] = 1, [Dw3] = 1,
+                [E]  = 1, [E2]  = 1, [E3]  = 1,
+                [y]  = 1, [y2]  = 1, [y3]  = 1,
 
-        if (base_move(m) == E || base_move(m) == y)
-                return 1;
+                [R]  = 2, [R2]  = 2, [R3]  = 2,
+                [L]  = 2, [L2]  = 2, [L3]  = 2,
+                [Rw] = 2, [Rw2] = 2, [Rw3] = 2,
+                [Lw] = 2, [Lw2] = 2, [Lw3] = 2,
+                [M]  = 2, [M2]  = 2, [M3]  = 2,
+                [x]  = 2, [x2]  = 2, [x3]  = 2,
 
-        if (base_move(m) == M || base_move(m) == x)
-                return 2;
-
-        if (base_move(m) == S || base_move(m) == z)
-                return 3;
+                [F]  = 3, [F2]  = 3, [F3]  = 3,
+                [B]  = 3, [B2]  = 3, [B3]  = 3,
+                [Fw] = 3, [Fw2] = 3, [Fw3] = 3,
+                [Bw] = 3, [Bw2] = 3, [Bw3] = 3,
+                [S]  = 3, [S2]  = 3, [S3]  = 3,
+                [z]  = 3, [z2]  = 3, [z3]  = 3,
+        };
 
-        return -1;
+        return aux[m];
 }
 
 Move
@@ -137,7 +149,7 @@ compose_alg(Alg *alg1, Alg *alg2)
 void
 copy_alg(Alg *src, Alg *dst)
 {
-        dst->len = 0; /* Overwrites */
+        dst->len = dst->len_normal = dst->len_inverse = 0;
         compose_alg(dst, src);
 }
 
@@ -169,16 +181,6 @@ free_alglistnode(AlgListNode *aln)
         free(aln);
 }
 
-void
-inplace(Alg * (*f)(Alg *), Alg *alg)
-{
-        Alg *aux;
-
-        aux = f(alg);
-        copy_alg(aux, alg);
-        free(aux);
-}
-
 Alg *
 inverse_alg(Alg *alg)
 {
@@ -234,10 +236,14 @@ new_alg(char *str)
         Move j, m;
 
         alg = malloc(sizeof(Alg));
-        alg->move      = malloc(30 * sizeof(Move));
-        alg->inv       = malloc(30 * sizeof(bool));
-        alg->allocated = 30;
-        alg->len       = 0;
+        alg->allocated    = 30;
+        alg->move         = malloc(alg->allocated * sizeof(Move));
+        alg->inv          = malloc(alg->allocated * sizeof(bool));
+        alg->move_normal  = malloc(alg->allocated * sizeof(Move));
+        alg->move_inverse = malloc(alg->allocated * sizeof(Move));
+        alg->len          = 0;
+        alg->len_normal   = 0;
+        alg->len_inverse  = 0;
 
         niss = false;
         for (i = 0; str[i]; i++) {
@@ -246,13 +252,13 @@ new_alg(char *str)
 
                 if (str[i] == '(' && niss) {
                         fprintf(stderr, "Error reading moves: nested ( )\n");
-                        alg->len = 0;
+                        alg->len = alg->len_normal = alg->len_inverse = 0;
                         return alg;
                 }
 
                 if (str[i] == ')' && !niss) {
                         fprintf(stderr, "Error reading moves: unmatched )\n");
-                        alg->len = 0;
+                        alg->len = alg->len_normal = alg->len_inverse = 0;
                         return alg;
                 }
 
@@ -319,7 +325,7 @@ new_alg(char *str)
 
         if (niss) {
                 fprintf(stderr, "Error reading moves: unmatched (\n");
-                alg->len = 0;
+                alg->len = alg->len_normal = alg->len_inverse = 0;
         }
 
         return alg;
@@ -349,6 +355,19 @@ on_inverse(Alg *alg)
         return ret;
 }
 
+bool
+possible_next(Move m, Moveset *ms, Move l0, Move l1)
+{
+        bool allowed, order;
+        uint64_t mbit;
+
+        mbit    = ((uint64_t)1) << m;
+        allowed = mbit & ms->mask[l1][l0];
+        order   = !commute(l0, m) || l0 < m;
+
+        return allowed && order;
+}
+
 void
 print_alg(Alg *alg, bool l)
 {
@@ -404,8 +423,10 @@ realloc_alg(Alg *alg, int n)
                 fprintf(stderr, "something might go wrong.\n");
         }
 
-        alg->move = realloc(alg->move, n * sizeof(int));
-        alg->inv  = realloc(alg->inv,  n * sizeof(int));
+        alg->move         = realloc(alg->move,         n * sizeof(int));
+        alg->inv          = realloc(alg->inv,          n * sizeof(int));
+        alg->move_normal  = realloc(alg->move_normal,  n * sizeof(int));
+        alg->move_inverse = realloc(alg->move_inverse, n * sizeof(int));
         alg->allocated = n;
 }
 
@@ -455,14 +476,12 @@ unniss(Alg *alg)
 
         ret = new_alg("");
 
-        for (i = 0; i < alg->len; i++)
-                if (!alg->inv[i])
-                        append_move(ret, alg->move[i], false);
-        
-        for (i = alg->len-1; i >= 0; i--)
-                if (alg->inv[i])
-                        append_move(ret, inverse_move(alg->move[i]), false);
-        
+        for (i = 0; i < alg->len_normal; i++)
+                append_move(ret, alg->move_normal[i], false);
+
+        for (i = 0; i < alg->len_inverse; i++)
+                append_move(ret, inverse_move(alg->move_inverse[i]), false);
+
         return ret;
 }
 
@@ -483,7 +502,7 @@ init_moveset(Moveset *ms)
         for (l1 = 0; l1 < NMOVES; l1++) { 
                 for (l2 = 0; l2 < NMOVES; l2++) { 
                         ms->mask[l2][l1] = 0;
-                        for (l=0; ms->sorted_moves[l]!=NULLMOVE; l++) {
+                        for (l = 0; ms->sorted_moves[l] != NULLMOVE; l++) {
                                 m = ms->sorted_moves[l];
                                 if (ms->allowed_next(l2, l1, m))
                                         ms->mask[l2][l1] |= (one<<m);
diff --git a/src/alg.h b/src/alg.h
index 51e66b0..b65a55e 100644
--- a/src/alg.h
+++ b/src/alg.h
@@ -15,6 +15,11 @@ bool        allowed_eofb(Move m);
 bool        allowed_drud(Move m);
 bool        allowed_htr(Move m);
 bool        allowed_next_all(Move l2, Move l1, Move m);
+
+void        moveset_to_list(Moveset ms, Move *lst);
+void        init_moveset(Moveset *ms);
+bool        possible_next(Move m, Moveset *ms, Move l0, Move l1);
+
 void        append_alg(AlgList *l, Alg *alg);
 void        append_move(Alg *alg, Move m, bool inverse);
 Move        base_move(Move m);
@@ -23,12 +28,9 @@ bool        commute(Move m1, Move m2);
 void        copy_alg(Alg *src, Alg *dst);
 void        free_alg(Alg *alg);
 void        free_alglist(AlgList *l);
-void        inplace(Alg * (*f)(Alg *), Alg *alg);
 Alg *       inverse_alg(Alg *alg);
 Move        inverse_move(Move m);
 char *      move_string(Move m);
-void        movelist_to_position(Move *ml, int *pos);
-void        moveset_to_list(Moveset ms, Move *lst);
 Alg *       new_alg(char *str);
 AlgList *   new_alglist();
 Alg *       on_inverse(Alg *alg);
@@ -38,8 +40,6 @@ void        swapmove(Move *m1, Move *m2);
 char *      trans_string(Trans t); /* Here because similar to move_string, move? */
 Alg *       unniss(Alg *alg);
 
-void        init_moveset(Moveset *ms);
-
 /* Movesets ******************************************************************/
 
 #ifndef ALG_C
diff --git a/src/cubetypes.h b/src/cubetypes.h
index 565dddb..8d38904 100644
--- a/src/cubetypes.h
+++ b/src/cubetypes.h
@@ -122,6 +122,10 @@ alg
         bool *                    inv;
         int                       len;
         int                       allocated;
+        Move *                    move_normal;
+        int                       len_normal;
+        Move *                    move_inverse;
+        int                       len_inverse;
 };
 
 struct
diff --git a/src/solve.c b/src/solve.c
index df15cca..d5a8f3d 100644
--- a/src/solve.c
+++ b/src/solve.c
@@ -4,7 +4,6 @@
 
 /* Local functions ***********************************************************/
 
-static bool        allowed_next(Move move, Step *s, Move l0, Move l1);
 static bool        cancel_niss(DfsArg *arg);
 static void        copy_dfsarg(DfsArg *src, DfsArg *dst);
 static void        dfs(DfsArg *arg);
@@ -19,19 +18,6 @@ static bool        solvestop(int d, int op, SolveOptions *opts, AlgList *sols);
 /* Local functions ***********************************************************/
 
 static bool
-allowed_next(Move m, Step *s, Move l0, Move l1)
-{
-        bool allowed, order;
-        uint64_t mbit;
-
-        mbit    = ((uint64_t)1) << m;
-        allowed = mbit & s->moveset->mask[l1][l0];
-        order   = !commute(l0, m) || l0 < m;
-
-        return allowed && order;
-}
-
-static bool
 cancel_niss(DfsArg *arg)
 {
         Moveset *ms;
@@ -82,16 +68,14 @@ copy_dfsarg(DfsArg *src, DfsArg *dst)
                 dst->ind[i].t   = src->ind[i].t;
         }
 
-/*
         src->s->copy_extra(src, dst);
-*/
 }
 
 static void
 dfs(DfsArg *arg)
 {
         int i;
-        Move m;
+        Move m, l0, l1;
         DfsArg newarg;
 
         if (dfs_move_checkstop(arg))
@@ -105,9 +89,11 @@ dfs(DfsArg *arg)
 
         for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) {
                 m = arg->s->moveset->sorted_moves[i];
-                if (allowed_next(m, arg->s, arg->last[0], arg->last[1])) {
+                l0 = arg->last[0];
+                l1 = arg->last[1];
+                if (possible_next(m, arg->s->moveset, l0, l1)) {
                         copy_dfsarg(arg, &newarg);
-                        newarg.last[1] = arg->last[0];
+                        newarg.last[1] = l0;
                         newarg.last[0] = m;
                         append_move(arg->current_alg, m, newarg.niss);
                         dfs(&newarg);
diff --git a/tests/alg_tests.c b/tests/alg_tests.c
new file mode 100644
index 0000000..9ac1595
--- /dev/null
+++ b/tests/alg_tests.c
@@ -0,0 +1,266 @@
+#include "alg_tests.h"
+
+bool testmethod_append_move(void *);
+bool testmethod_new_alg(void *);
+/*
+bool testmethod_compose_alg(void *);
+bool testmethod_inverse_alg(void *);
+bool testmethod_on_inverse(void *);
+bool testmethod_unniss(void *);
+*/
+
+typedef struct {
+        Move *move;
+        bool *inv;
+        int len;
+        Move m;
+        bool inverse;
+} append_move_t;
+
+Move m_app1[] = {F, x, D3};
+bool i_app1[] = {true, false, false};
+append_move_t append_move_case1 = {
+        .move = m_app1,
+        .inv = i_app1,
+        .len = 3,
+        .m = L3,
+        .inverse = false,
+};
+
+Move m_app2[] = {S, U, x2, M2};
+bool i_app2[] = {true, false, true, true};
+append_move_t append_move_case2 = {
+        .move = m_app2,
+        .inv = i_app2,
+        .len = 4,
+        .m = R,
+        .inverse = true,
+};
+
+Move m_app3[] = {U, U, U, U, U};
+bool i_app3[] = {false, false, false, false, false};
+append_move_t append_move_case3 = {
+        .move = m_app3,
+        .inv = i_app3,
+        .len = 5,
+        .m = U,
+        .inverse = false,
+};
+
+append_move_t *append_move_cases[] = {
+        &append_move_case1,
+        &append_move_case2,
+        &append_move_case3,
+};
+
+Test test_append_move = {
+        .name  = "Appending a move to and alg",
+        .t     = testmethod_append_move,
+        .cases = (void **)append_move_cases,
+};
+
+typedef struct {
+        char *str;
+        Move *move;
+        bool *inv;
+        int len;
+        Move *move_normal;
+        int len_normal;
+        Move *move_inverse;
+        int len_inverse;
+} new_alg_t;
+
+/* Alg F U B' (L3 D) x M (S) y3 */
+Move m_new1[] = {F, U, B3, L3, D, x, M, S, y3};
+Move mn_new1[] = {F, U, B3, x, M, y3};
+Move mi_new1[] = {L3, D, S};
+bool i_new1[] = {false, false, false, true, true, false, false, true, false};
+new_alg_t new_alg_case1 = {
+        .str = "F U B' (L3 D) x M (S) y3",
+        .move = m_new1,
+        .inv = i_new1,
+        .len = 9,
+        .move_normal = mn_new1,
+        .len_normal = 6,
+        .move_inverse = mi_new1,
+        .len_inverse = 3,
+};
+new_alg_t *new_alg_cases[] = {&new_alg_case1};
+
+Test test_new_alg = {
+        .name  = "Initializing an alg from a string",
+        .t     = testmethod_new_alg,
+        .cases = (void **)new_alg_cases,
+};
+
+Test *alg_all_tests[] = {
+        &test_append_move,
+        &test_new_alg,
+/*
+        &test_append_alg,
+        &test_compose_alg,
+        &test_inverse_alg,
+        &test_on_inverse,
+        &test_unniss,
+*/
+        NULL
+};
+TestSuite alg_suite = {
+        .setup    = NULL,
+        .tests    = alg_all_tests,
+        .teardown = NULL,
+};
+
+TestSuite *alg_suites[] = {
+        &alg_suite,
+        NULL
+};
+
+bool
+testmethod_append_move(void *a)
+{
+        append_move_t *b = (append_move_t *)a;
+        int li, ln;
+        Alg *alg;
+
+        /* Small to test reallocation */
+        alg = malloc(sizeof(Alg));
+        alg->allocated    = 5;
+        alg->move         = malloc(alg->allocated * sizeof(Move));
+        alg->inv          = malloc(alg->allocated * sizeof(bool));
+        alg->len          = b->len;
+        memcpy(alg->move, b->move, alg->len * sizeof(Move));
+        memcpy(alg->inv,  b->inv,  alg->len * sizeof(bool));
+        alg->move_normal  = malloc(alg->allocated * sizeof(Move));
+        alg->move_inverse = malloc(alg->allocated * sizeof(Move));
+
+        li = ln = 0;
+        for (int i = 0; i < alg->len; i++) {
+                if (alg->inv[i])
+                        alg->move_inverse[li++] = alg->move[i];
+                else
+                        alg->move_normal[ln++] = alg->move[i];
+        }
+        alg->len_inverse = li;
+        alg->len_normal = ln;
+
+        append_move(alg, b->m, b->inverse);
+
+        if (alg->len != b->len + 1) {
+                printf("Alg has wrong len (%d instead of %d)\n",
+                        alg->len, b->len + 1);
+                goto append_move_fail;
+        }
+        if (alg->move[alg->len-1] != b->m) {
+                printf("Wrong last move (%s instead of %s)\n",
+                        move_string(alg->move[alg->len-1]),
+                        move_string(b->m));
+                goto append_move_fail;
+        }
+        if (alg->inv[alg->len-1] != b->inverse) {
+                printf("Wrong inverse flag for last move "
+                        "(%s instead of %s)\n",
+                        b->inverse ? "normal" : "inverse",
+                        b->inverse ? "inverse" : "normal");
+                goto append_move_fail;
+        }
+        if (b->inverse) {
+                if (alg->len_inverse != li + 1 ||
+                    alg->len_normal  != ln) {
+                        printf("%d moves on normal (should be %d)"
+                               " and %d on inverse (should be %d)\n",
+                               alg->len_normal, ln,
+                               alg->len_inverse, li + 1);
+                        goto append_move_fail;
+                }
+                if (alg->move_inverse[alg->len_inverse-1] != b->m) {
+                        printf("Wrong move on inverse (%s instead of %s)\n",
+                                move_string(alg->move_inverse[alg->len-1]),
+                                move_string(b->m));
+                        goto append_move_fail;
+                }
+        } else {
+                if (alg->len_inverse != li ||
+                    alg->len_normal  != ln + 1) {
+                        printf("%d moves on normal (should be %d)"
+                               " and %d on inverse (should be %d)\n",
+                               alg->len_normal, ln,
+                               alg->len_inverse, li + 1);
+                        goto append_move_fail;
+                }
+                if (alg->move_normal[alg->len_normal-1] != b->m) {
+                        printf("Wrong move on normal (%s instead of %s)\n",
+                                move_string(alg->move_normal[alg->len-1]),
+                                move_string(b->m));
+                        goto append_move_fail;
+                }
+        }
+
+        free(alg);
+        return true;
+
+append_move_fail:
+        free(alg);
+        return false;
+}
+
+bool
+testmethod_new_alg(void *a)
+{
+        new_alg_t *b = (new_alg_t *)a;
+        Alg *alg = new_alg(b->str);
+
+        if (alg->len != b->len) {
+                printf("Algs have different length (%d instead of %d)\n",
+                        alg->len, b->len);
+                goto new_alg_fail;
+        }
+
+        for (int i = 0; i < alg->len; i++) {
+                if (alg->move[i] != b->move[i] || alg->inv[i] != b->inv[i]) {
+                        printf("Algs differ on move %d\n", i);
+                        printf("Expected: %s\nActual:   ", b->str);
+                        print_alg(alg, false);
+                        goto new_alg_fail;
+                }
+        }
+
+        if (alg->len_normal != b->len_normal) {
+                printf("Algs have different number of moves on normal"
+                        " (%d instead of %d)\n",
+                        alg->len_normal, b->len_normal);
+                goto new_alg_fail;
+        }
+        for (int i = 0; i < alg->len_normal; i++) {
+                if (alg->move_normal[i] != b->move_normal[i]) {
+                        printf("Algs have different move %d on normal"
+                                " (%s instead of %s)\n", i,
+                                move_string(alg->move_normal[i]),
+                                move_string(b->move_normal[i]));
+                        goto new_alg_fail;
+                }
+        }
+
+        if (alg->len_inverse != b->len_inverse) {
+                printf("Algs have different number of moves on inverse"
+                        " (%d instead of %d)\n",
+                        alg->len_inverse, b->len_inverse);
+                goto new_alg_fail;
+        }
+        for (int i = 0; i < alg->len_inverse; i++) {
+                if (alg->move_inverse[i] != b->move_inverse[i]) {
+                        printf("Algs have different move %d on inverse:\n"
+                                " (%s instead of %s)\n", i,
+                                move_string(alg->move_inverse[i]),
+                                move_string(b->move_inverse[i]));
+                        goto new_alg_fail;
+                }
+        }
+
+        free(alg);
+        return true;
+
+new_alg_fail:
+        free(alg);
+        return false;
+}
diff --git a/tests/alg_tests.h b/tests/alg_tests.h
new file mode 100644
index 0000000..518b33e
--- /dev/null
+++ b/tests/alg_tests.h
@@ -0,0 +1,20 @@
+#ifndef ALG_TESTS_H
+#define ALG_TESTS_H
+
+#include "../src/alg.h"
+#include "test_common.h"
+
+extern Test test_append_move;
+extern Test test_new_alg;
+/*
+extern Test test_compose_alg;
+extern Test test_inverse_alg;
+extern Test test_on_inverse;
+extern Test test_unniss;
+*/
+
+extern TestSuite alg_suite;
+
+extern TestSuite *alg_suites[];
+
+#endif
diff --git a/tests/test.c b/tests/test.c
index a1a382c..8961de1 100644
--- a/tests/test.c
+++ b/tests/test.c
@@ -1,5 +1,6 @@
 #include <stdio.h>
 
+#include "alg_tests.h"
 #include "coord_tests.h"
 #include "fst_tests.h"
 
@@ -54,9 +55,11 @@ int main(int argc, char *argv[]) {
         init_trans();
         /**************************************/
 
+        TestModule alg   = { .name = "alg",   .suites = alg_suites };
         TestModule fst   = { .name = "fst",   .suites = fst_suites };
         TestModule coord = { .name = "coord", .suites = coord_suites };
         TestModule *modules[999] = {
+                &alg,
                 &fst,
                 &coord,
                 NULL