Init commit.HEADmaster

6 files changed, 270 insertions, 0 deletions

diff --git a/src/pattern/next.c b/src/pattern/next.c
new file mode 100644
index 0000000..10261bc
--- /dev/null
+++ b/src/pattern/next.c
@@ -0,0 +1,79 @@
+#include "next.h"
+#include <stdlib.h>
+
+/*
+ * It gives the first point that:
+ *     - Isn't part of pattern->path
+ *     - Its index the lowest possible, but minimum min_index
+ *     - There isn't any point in-line between it and the last of the path
+ * Returns true if such a point exsist, otherwise returns false.
+ */
+bool free_point(struct pattern *pattern, int min_index, struct coord *new_point)
+{
+    //printf("min_index=%d\n", min_index);
+    struct coord result = index_to_coord(pattern->type.width, min_index);
+    struct coord *last = pattern->length > 0 ? &pattern->path[pattern->length - 1] : NULL;
+    while (result.y < pattern->type.height)
+    {
+        while (result.x < pattern->type.width)
+        {
+            if (last == NULL)
+            {
+                *new_point = result;
+                return true;
+            }
+            else if (find_in_pattern(pattern, &result) < 0 &&
+                     nothing_inbetween(pattern, &result))
+            {
+                //printf("fp(%d;%d)\n", result.x, result.y);
+                *new_point = result;
+                return true;
+            }
+            result.x++;
+        }
+        result.y++;
+        result.x = 0;
+    }
+    return false;
+}
+
+/*
+ * Changes pattern->path to the next possible pattern.
+ * It returns false if there's no possible pattern left,
+ * otherwise it returns true.
+ */
+bool next_point(struct pattern *pattern)
+{
+    struct coord next_point;
+    if (len_is_max(pattern))
+    {
+        do
+        {
+            if (pattern->length == 0)
+                return false; //Nincs több minta
+            next_point = pattern->path[--pattern->length];
+        } while (!free_point(
+            pattern,
+            coord_to_index(pattern->type.width, next_point) + 1,
+            &next_point));
+        //printf("(%d;%d)\n", next_point.x, next_point.y);
+        pattern->path[pattern->length++] = next_point;
+        if (pattern->length >= pattern->type.min_length)
+            return true;
+    }
+
+    do
+    {
+        if (free_point(pattern, 0, &next_point))
+        {
+            pattern->path[pattern->length++] = next_point;
+            //return true;
+        }
+    } while (pattern->length < pattern->type.min_length);
+
+    return true;
+
+    // Ha visszalépés volt, akkor az első újra előrelépésnél, csak nagyobb indexű
+    // elemre szabad lépni.
+    // Ha előrelépés volt, akkor a legkissebb indexű szabad elemre kell lépni.
+}
diff --git a/src/pattern/next.h b/src/pattern/next.h
new file mode 100644
index 0000000..c6aa380
--- /dev/null
+++ b/src/pattern/next.h
@@ -0,0 +1,9 @@
+#ifndef PLOC_GEN_PATTERN_NEXT_H
+#define PLOC_GEN_PATTERN_NEXT_H
+
+#include <stdbool.h>
+#include "pattern.h"
+
+bool next_point(struct pattern *pattern);
+
+#endif
\ No newline at end of file
diff --git a/src/pattern/pattern.c b/src/pattern/pattern.c
new file mode 100644
index 0000000..85e21c7
--- /dev/null
+++ b/src/pattern/pattern.c
@@ -0,0 +1,83 @@
+#include "pattern.h"
+#include <stdlib.h>
+#include "utils/utilities.h"
+
+/*
+ * Inline functions
+ */
+bool len_is_max(struct pattern *pattern);
+bool len_is_min(struct pattern *pattern);
+int coord_to_index(int width, struct coord point);
+struct coord index_to_coord(int width, int index);
+int pattern_point_to_index(struct pattern *pattern, int index);
+
+struct pattern_type gen_pattern_type(int side_len, int min, int max)
+{
+    struct pattern_type result;
+    result.width = side_len;
+    result.height = side_len;
+
+    int max_possible = side_len * side_len;
+    result.min_length = min >= 0 ? min : max_possible;
+    if (max >= 0 && max <= max_possible)
+        result.max_length = max;
+    else
+        result.max_length = max_possible;
+    return result;
+}
+
+int coord_cmp(const void *a, const void *b)
+{
+    const struct coord *ac = a;
+    const struct coord *bc = b;
+    if (ac->x == bc->x && ac->y == bc->y)
+        return 0;
+    //TODO: Handle when the inputs are not equal!
+    return -1;
+}
+
+bool is_in_line(struct coord a, struct coord c, struct coord b)
+{
+    if (!(monotonic(a.x, b.x, c.x) && monotonic(a.y, b.y, c.y)))
+        return false;
+    return ((b.x - a.x) * (c.y - a.y)) + ((b.y - a.y) * (a.x - c.x)) == 0;
+}
+
+int find_in_pattern(struct pattern *pattern, struct coord *coord)
+{
+    for (int i = 0; i < pattern->length; i++)
+    {
+        struct coord *current = &pattern->path[i];
+        if (current->x == coord->x && current->y == coord->y)
+            return i;
+    }
+    return -1;
+}
+
+int inbetween(int width, int height, struct coord *from, struct coord *to, struct coord *arr)
+{
+    int length = 0;
+    struct coord current;
+    for (current.y = 0; current.y < height; current.y++)
+        for (current.x = 0; current.x < width; current.x++)
+            if ((current.x != from->x || current.y != from->y) &&
+                (current.x != to->x || current.y != to->y))
+                if (is_in_line(*from, *to, current))
+                    arr[length++] = current;
+    return length;
+}
+
+bool nothing_inbetween(struct pattern *pattern, struct coord *next)
+{
+    if (pattern->length == 0)
+        return true;
+    struct coord *last = &pattern->path[pattern->length - 1];
+    struct coord arr[pattern->type.width * pattern->type.height];
+    size_t length = inbetween(pattern->type.width, pattern->type.height, last, next, arr);
+    if (length > pattern->length)
+        return false;
+    for (int i = 0; i < length; i++)
+        if (find_in_pattern(pattern, &arr[i]) < 0)
+            return false;
+    return true;
+}
diff --git a/src/pattern/pattern.h b/src/pattern/pattern.h
new file mode 100644
index 0000000..d53576e
--- /dev/null
+++ b/src/pattern/pattern.h
@@ -0,0 +1,93 @@
+#ifndef PLOC_GEN_PATTERN_PATTERN_H
+#define PLOC_GEN_PATTERN_PATTERN_H
+
+#include <stdbool.h>
+
+struct coord
+{
+    int x;
+    int y;
+};
+
+struct pattern_type
+{
+    int width;
+    int height;
+    int min_length;
+    int max_length;
+};
+
+struct pattern
+{
+    struct pattern_type type;
+    struct coord *path;
+    int length;
+};
+
+/*
+ * Creates a pattern_type.
+ * If max has an invalid value the max_length is set to the
+ * maximum possible length.
+ */
+struct pattern_type gen_pattern_type(int side_len, int min, int max);
+
+/*
+ * Returns 0 if a equals b.
+ */
+int coord_cmp(const void *a, const void *b);
+
+/*
+ * If the point happend to be on the line that connects start and end,
+ * the result is true, otherwise is false.
+ */
+bool is_in_line(struct coord a, struct coord c, struct coord b);
+
+/*
+ * Returns the index of coord in pattern->path.
+ * The return value is negative if coord not found in pattern->path.
+ */
+int find_in_pattern(struct pattern *pattern, struct coord *coord);
+
+/*
+ * Gives back the points in arr, that are between from and to.
+ */
+int inbetween(int width, int height, struct coord *from, struct coord *to, struct coord *arr);
+
+/*
+ * Returns true if there's no unvisited point between
+ * the last point of path and next.
+ */
+bool nothing_inbetween(struct pattern *pattern, struct coord *next);
+
+/*
+ * Inline functions.
+ */
+inline bool len_is_max(struct pattern *pattern)
+{
+    return pattern->length >= pattern->type.max_length;
+}
+
+inline bool len_is_min(struct pattern *pattern)
+{
+    return pattern->length <= pattern->type.min_length;
+}
+
+inline int coord_to_index(int width, struct coord point)
+{
+    return (point.y * width) + point.x;
+}
+
+inline struct coord index_to_coord(int width, int index)
+{
+    struct coord result;
+    result.y = index / width;
+    result.x = index % width;
+    return result;
+}
+
+inline int pattern_point_to_index(struct pattern *pattern, int index)
+{
+    return coord_to_index(pattern->type.width, pattern->path[index]);
+}
+
+#endif
\ No newline at end of file
diff --git a/src/pattern/random.c b/src/pattern/random.c
new file mode 100644
index 0000000..b7dba62
--- /dev/null
+++ b/src/pattern/random.c
@@ -0,0 +1 @@
+#include "random.h"
diff --git a/src/pattern/random.h b/src/pattern/random.h
new file mode 100644
index 0000000..68aeddc
--- /dev/null
+++ b/src/pattern/random.h
@@ -0,0 +1,5 @@
+#ifndef PLOC_GEN_PATTERN_RANDOM_H
+#define PLOC_GEN_PATTERN_RANDOM_H
+
+
+#endif
\ No newline at end of file