Added move sequence comparison function

12 files changed, 222 insertions, 10 deletions

diff --git a/build b/build
index 98f227e..8c9e72f 100755
--- a/build
+++ b/build
@@ -282,7 +282,8 @@ build_cpp() {
         fi
 
         build_nissy || exit 1
-        run $CXX $(odflags) -std=c++20 -o runcpp cpp/nissy.cpp nissy.o $@
+        run $CXX $(odflags) -std=c++20 -o runcpp cpp/nissy.cpp nissy.o $@ \
+                || exit 1
         run ./runcpp
 }
 
diff --git a/cpp/nissy.cpp b/cpp/nissy.cpp
index 2c290a6..90fcf20 100644
--- a/cpp/nissy.cpp
+++ b/cpp/nissy.cpp
@@ -24,6 +24,7 @@ extern "C" {
             const unsigned char *, unsigned, char *, long long *,
             int (*)(void *), void *);
         long long nissy_countmoves(const char *);
+        long long nissy_comparemoves(const char *, const char *);
         long long nissy_setlogger(void (*)(const char *, void *), void *);
 }
 
@@ -53,6 +54,9 @@ namespace nissy {
         const status status::STOP{1};
         const status status::PAUSE{2};
 
+        const compare_result compare_result::EQUAL{0};
+        const compare_result compare_result::DIFFERENT{99};
+
         namespace size {
                 constexpr size_t CUBE = 24;
                 constexpr size_t TRANSFORMATION = 12;
@@ -210,6 +214,16 @@ namespace nissy {
                 return error{err};
         }
 
+        std::variant<error, compare_result>
+        compare_moves(const std::string& m1, const std::string& m2)
+        {
+                auto cmp = nissy_comparemoves(m1.c_str(), m2.c_str());
+                if (cmp < 0)
+                        return error{cmp};
+                else
+                        return compare_result{cmp};
+        }
+
         void set_logger(void (*log)(const char *, void *), void *data)
         {
                 nissy_setlogger(log, data);
diff --git a/cpp/nissy.h b/cpp/nissy.h
index 817307c..199af10 100644
--- a/cpp/nissy.h
+++ b/cpp/nissy.h
@@ -55,6 +55,14 @@ namespace nissy {
                 static const status PAUSE;
         };
 
+        class compare_result {
+        public:
+                long long value;
+
+                static const compare_result EQUAL;
+                static const compare_result DIFFERENT;
+        };
+
         class cube {
         public:
                 cube();
@@ -103,6 +111,8 @@ namespace nissy {
         };
 
         error count_moves(const std::string&);
+        std::variant<error, compare_result> compare_moves(
+            const std::string&, const std::string&);
         void set_logger(void (*)(const char *, void *), void *);
 }
 
diff --git a/python/nissy_module.c b/python/nissy_module.c
index 3e5ea08..a86b23f 100644
--- a/python/nissy_module.c
+++ b/python/nissy_module.c
@@ -345,6 +345,42 @@ countmoves(PyObject *self, PyObject *args)
         return long_result(count);
 }
 
+PyDoc_STRVAR(comparemoves_doc,
+"comparemoves(moves1, moves2)\n"
+"--\n\n"
+"Compare the two move sequences\n"
+"\n"
+"Parameters:\n"
+"  - moves1: the first sequence of moves\n"
+"  - moves2: the second sequence of moves\n"
+"\n"
+"Returns: a string describing how the two moves sequences compare. "
+"This can be one of:\n"
+"\"EQUAL\"      - The two sequences are equal up to swapping parallel moves\n"
+"\"DIFFERENT\"  - The two sequences are different\n"
+);
+PyObject *
+comparemoves(PyObject *self, PyObject *args)
+{
+        long long cmp;
+        const char *m1, *m2;
+
+        if (!PyArg_ParseTuple(args, "ss", &m1, &m2))
+                return NULL;
+
+        if ((cmp = nissy_comparemoves(m1, m2)) < 0)
+                return long_result(cmp);
+
+        switch (cmp) {
+        case NISSY_COMPARE_MOVES_EQUAL:
+                return string_result(cmp, "EQUAL");
+        case NISSY_COMPARE_MOVES_DIFFERENT:
+                return string_result(cmp, "DIFFERENT");
+        default:
+                return long_result(cmp);
+        }
+}
+
 static PyMethodDef nissy_methods[] = {
         { "inverse", inverse, METH_VARARGS, inverse_doc },
         { "applymoves", applymoves, METH_VARARGS, applymoves_doc },
@@ -355,6 +391,7 @@ static PyMethodDef nissy_methods[] = {
         { "checkdata", checkdata, METH_VARARGS, checkdata_doc },
         { "solve", solve, METH_VARARGS, solve_doc },
         { "countmoves", countmoves, METH_VARARGS, countmoves_doc },
+        { "comparemoves", comparemoves, METH_VARARGS, comparemoves_doc },
         { NULL, NULL, 0, NULL }
 };
 
diff --git a/shell/shell.c b/shell/shell.c
index a9a1bc7..8800094 100644
--- a/shell/shell.c
+++ b/shell/shell.c
@@ -18,6 +18,7 @@
 #define FLAG_COMMAND      "-command"
 #define FLAG_STR_CUBE     "-cubestr"
 #define FLAG_MOVES        "-moves"
+#define FLAG_MOVES2       "-moves2"
 #define FLAG_TRANS        "-trans"
 #define FLAG_SOLVER       "-solver"
 #define FLAG_NISSTYPE     "-nisstype"
@@ -39,6 +40,7 @@ typedef struct {
         char *str_command;
         char *str_cube;
         char *str_moves;
+        char *str_moves2;
         char *str_trans;
         char *str_solver;
         char *str_nisstype;
@@ -59,6 +61,7 @@ static int64_t gendata_exec(args_t *);
 static int64_t solve_exec(args_t *);
 static int64_t solve_scramble_exec(args_t *);
 static int64_t countmoves_exec(args_t *);
+static int64_t comparemoves_exec(args_t *);
 static int64_t help_exec(args_t *);
 
 static int parse_args(int, char **, args_t *);
@@ -69,6 +72,7 @@ static bool set_cube(int, char **, args_t *);
 static bool set_str_command(int, char **, args_t *);
 static bool set_str_cube(int, char **, args_t *);
 static bool set_str_moves(int, char **, args_t *);
+static bool set_str_moves2(int, char **, args_t *);
 static bool set_str_trans(int, char **, args_t *);
 static bool set_str_solver(int, char **, args_t *);
 static bool set_str_nisstype(int, char **, args_t *);
@@ -91,6 +95,7 @@ struct {
         OPTION(FLAG_COMMAND, 1, set_str_command),
         OPTION(FLAG_STR_CUBE, 1, set_str_cube),
         OPTION(FLAG_MOVES, 1, set_str_moves),
+        OPTION(FLAG_MOVES2, 1, set_str_moves2),
         OPTION(FLAG_TRANS, 1, set_str_trans),
         OPTION(FLAG_SOLVER, 1, set_str_solver),
         OPTION(FLAG_NISSTYPE, 1, set_str_nisstype),
@@ -185,6 +190,13 @@ struct {
                 countmoves_exec
         ),
         COMMAND(
+                "compare",
+                "compare " FLAG_MOVES " MOVES " FLAG_MOVES2 " MOVES2",
+                "Compare the two move sequences."
+                INFO_MOVESFORMAT,
+                comparemoves_exec
+        ),
+        COMMAND(
                 "help",
                 "help [" FLAG_COMMAND " COMMAND]",
                 "If no COMMAND is specified, prints some generic information "
@@ -476,6 +488,29 @@ countmoves_exec(args_t *args)
 }
 
 static int64_t
+comparemoves_exec(args_t *args)
+{
+        long long cmp;
+
+        if ((cmp = nissy_comparemoves(args->str_moves, args->str_moves2)) < 0)
+                return cmp;
+
+        switch (cmp) {
+        case NISSY_COMPARE_MOVES_EQUAL:
+                printf("The two move sequences are equal\n");
+                break;
+        case NISSY_COMPARE_MOVES_DIFFERENT:
+                printf("The two move sequences are different\n");
+                break;
+        default:
+                printf("Error: unknown case\n");
+                return -1;
+        }
+
+        return 0;
+}
+
+static int64_t
 help_exec(args_t *args)
 {
         int i;
@@ -512,6 +547,7 @@ parse_args(int argc, char **argv, args_t *args)
                 .cube = "",
                 .str_cube = "",
                 .str_moves = "",
+                .str_moves2 = "",
                 .str_trans = "",
                 .str_solver = "",
                 .str_nisstype = "",
@@ -632,6 +668,14 @@ set_str_moves(int argc, char **argv, args_t *args)
 }
 
 static bool
+set_str_moves2(int argc, char **argv, args_t *args)
+{
+        args->str_moves2 = argv[0];
+
+        return true;
+}
+
+static bool
 set_str_trans(int argc, char **argv, args_t *args)
 {
         args->str_trans = argv[0];
diff --git a/src/core/core_types.h b/src/core/core_types.h
index 2ad8938..19a9f42 100644
--- a/src/core/core_types.h
+++ b/src/core/core_types.h
@@ -1,4 +1,13 @@
+#define MOVES_STRUCT_MAXLEN 1000
+
 typedef struct {
         cube_t cube;
         uint8_t orientation;
 } oriented_cube_t;
+
+typedef struct {
+        size_t nnormal;
+        size_t ninverse;
+        uint8_t normal[MOVES_STRUCT_MAXLEN];
+        uint8_t inverse[MOVES_STRUCT_MAXLEN];
+} moves_struct_t;
diff --git a/src/core/moves.h b/src/core/moves.h
index d3ff4a3..9c8cc90 100644
--- a/src/core/moves.h
+++ b/src/core/moves.h
@@ -3,8 +3,12 @@
 
 STATIC uint8_t readmove(char);
 STATIC int64_t readmoves(const char *,
-    size_t, size_t, uint64_t *, uint64_t *, uint8_t *, uint8_t *);
+    size_t, size_t, size_t *, size_t *, uint8_t *, uint8_t *);
+STATIC int64_t readmoves_struct(const char *, moves_struct_t [static 1]);
 STATIC int64_t countmoves(const char *);
+STATIC bool moves_struct_equal(
+    const moves_struct_t [static 1], const moves_struct_t [static 1]);
+STATIC long long comparemoves(const char *, const char *);
 STATIC uint8_t readmodifier(char);
 STATIC int64_t writemoves(size_t, const uint8_t *, size_t, char *);
 
@@ -124,8 +128,8 @@ readmoves(
         const char *buf,
         size_t nsize,
         size_t invsize,
-        uint64_t *n,
-        uint64_t *i,
+        size_t *n,
+        size_t *i,
         uint8_t *normal,
         uint8_t *inverse
 )
@@ -154,6 +158,13 @@ readmoves(
 }
 
 STATIC int64_t
+readmoves_struct(const char *moves, moves_struct_t ret[static 1])
+{
+        return readmoves(moves, MOVES_STRUCT_MAXLEN, MOVES_STRUCT_MAXLEN,
+            &ret->nnormal, &ret->ninverse, ret->normal, ret->inverse);
+}
+
+STATIC int64_t
 countmoves(const char *buf)
 {
         uint8_t m;
@@ -168,6 +179,58 @@ countmoves(const char *buf)
         return count;
 }
 
+STATIC bool
+moves_struct_equal(
+        const moves_struct_t ms1[static 1],
+        const moves_struct_t ms2[static 1]
+)
+{
+        size_t i;
+
+        if (ms1->nnormal != ms2->nnormal || ms1->ninverse != ms2->ninverse)
+                return false;
+
+        for (i = 0; i < ms1->nnormal; i++)
+                if (ms1->normal[i] != ms2->normal[i])
+                        return false;
+
+        for (i = 0; i < ms1->ninverse; i++)
+                if (ms1->inverse[i] != ms2->inverse[i])
+                        return false;
+
+        return true;
+}
+
+STATIC long long
+comparemoves(const char *moves1, const char *moves2)
+{
+        int64_t err;
+        moves_struct_t ms1, ms2;
+
+        if ((err = readmoves_struct(moves1, &ms1)) < 0)
+                return err;
+        sortparallel_moves(ms1.nnormal, ms1.normal);
+        sortparallel_moves(ms1.ninverse, ms1.inverse);
+
+        if ((err = readmoves_struct(moves2, &ms2)) < 0)
+                return err;
+        sortparallel_moves(ms2.nnormal, ms2.normal);
+        sortparallel_moves(ms2.ninverse, ms2.inverse);
+
+        if (moves_struct_equal(&ms1, &ms2))
+                return NISSY_COMPARE_MOVES_EQUAL;
+
+        /*
+        TODO: more types of move comparison
+              - up to moving rotations around
+              - up to rotation
+              - up transformation (including mirror or not including it)
+              - ...
+        */
+
+        return NISSY_COMPARE_MOVES_DIFFERENT;
+}
+
 STATIC int64_t
 writemoves(
         size_t nmoves,
diff --git a/src/nissy.c b/src/nissy.c
index 93a4841..4b5d476 100644
--- a/src/nissy.c
+++ b/src/nissy.c
@@ -354,6 +354,18 @@ nissy_countmoves(
 }
 
 long long
+nissy_comparemoves(
+        const char *moves1,
+        const char *moves2
+)
+{
+        if (moves1 == NULL || moves2 == NULL)
+                return NISSY_ERROR_NULL_POINTER;
+
+        return comparemoves(moves1, moves2);
+}
+
+long long
 nissy_setlogger(
         void (*log)(const char *, void *),
         void *user_data
diff --git a/src/nissy.h b/src/nissy.h
index 0c1d18d..38fe656 100644
--- a/src/nissy.h
+++ b/src/nissy.h
@@ -42,6 +42,10 @@ for example 'rotation UF' or 'mirrored BL'.
 #define NISSY_STATUS_STOP   1
 #define NISSY_STATUS_PAUSE  2
 
+/* Possible results of move sequence comparison */
+#define NISSY_COMPARE_MOVES_EQUAL     0
+#define NISSY_COMPARE_MOVES_DIFFERENT 99
+
 /* The solved cube */
 #define NISSY_SOLVED_CUBE "ABCDEFGH=ABCDEFGHIJKL=A"
 
@@ -375,6 +379,24 @@ nissy_countmoves(
 );
 
 /*
+Parameters:
+   moves1 - The first sequence of moves to compare.
+   moves2 - The second sequence of moves to compare.
+
+Return values:
+   NISSY_ERROR_INVALID_MOVES     - One of the given moves sequences is invalid.
+   NISSY_ERROR_NULL_POINTER      - One of the arguments is NULL.
+   NISSY_COMPARE_MOVES_EQUAL     - The two moves sequences are indentical, up
+                                   to swapping parallel moves.
+   NISSY_COMPARE_MOVES_DIFFERENT - The two moves sequences are different.
+*/
+long long
+nissy_comparemoves(
+        const char *moves1,
+        const char *moves2
+);
+
+/*
 Set a global logger function used by this library. Setting the logger to NULL
 disables logging.
 
diff --git a/test/033_inverse_move/inverse_move_tests.c b/test/033_inverse_move/inverse_move_tests.c
index e9bad0c..5453f83 100644
--- a/test/033_inverse_move/inverse_move_tests.c
+++ b/test/033_inverse_move/inverse_move_tests.c
@@ -3,11 +3,11 @@
 extern char *movestr[];
 
 int64_t readmoves(const char *, size_t n, size_t m,
-    uint64_t *, uint64_t *, uint8_t [n], uint8_t [m]);
+    size_t *, size_t *, uint8_t [n], uint8_t [m]);
 uint8_t inverse_move(uint8_t);
 
 void run(void) {
-        uint64_t inv, nor;
+        size_t inv, nor;
         int64_t tot;
         uint8_t moves[2];
 
diff --git a/test/062_transform_move/transform_move_tests.c b/test/062_transform_move/transform_move_tests.c
index 17cb0b6..218c6a1 100644
--- a/test/062_transform_move/transform_move_tests.c
+++ b/test/062_transform_move/transform_move_tests.c
@@ -5,7 +5,7 @@
 cube_t applytrans(cube_t, const char *);
 uint8_t transform_move(uint8_t, uint8_t);
 int64_t readmoves(const char *, size_t n, size_t m,
-    uint64_t *, uint64_t *, uint8_t [n], uint8_t [m]);
+    size_t *, size_t *, uint8_t [n], uint8_t [m]);
 oriented_cube_t move_extended(oriented_cube_t, uint8_t);
 oriented_cube_t applymoves(oriented_cube_t, const char *);
 uint8_t readtrans(const char[static NISSY_SIZE_TRANSFORMATION]);
@@ -13,7 +13,7 @@ uint8_t readtrans(const char[static NISSY_SIZE_TRANSFORMATION]);
 void run(void) {
         char movestr[STRLENMAX], transtr[STRLENMAX], cubestr[STRLENMAX];
         uint8_t t, moves[MAXMOVES];
-        uint64_t i, n, ninv;
+        size_t i, n, ninv;
         int64_t tot;
         oriented_cube_t cube;
 
diff --git a/test/140_appendsolution/appendsolution_tests.c b/test/140_appendsolution/appendsolution_tests.c
index c9cd81f..d4c2a1f 100644
--- a/test/140_appendsolution/appendsolution_tests.c
+++ b/test/140_appendsolution/appendsolution_tests.c
@@ -14,7 +14,7 @@ See below for the output format.
 
 uint8_t readtrans(const char [NISSY_SIZE_TRANSFORMATION]);
 int64_t readmoves(const char *, size_t n, size_t m,
-    uint64_t *, uint64_t *, uint8_t [n], uint8_t [m]);
+    size_t *, size_t *, uint8_t [n], uint8_t [m]);
 void solution_moves_reset(solution_moves_t [static 1]);
 bool solution_list_init(solution_list_t [static 1], size_t n, char [n]);
 int64_t appendsolution(const solution_moves_t [static 1],
@@ -23,7 +23,7 @@ int64_t appendsolution(const solution_moves_t [static 1],
 void run(void) {
         int i, ntrans;
         int64_t tot;
-        uint64_t nm, np;
+        size_t nm, np;
         char str[STRLENMAX], buf[STRLENMAX];
         solution_moves_t moves;
         solution_settings_t settings;