WIP c implementation

5 files changed, 174 insertions, 83 deletions

diff --git a/src_c/common.c b/src_c/common.c
index 271c2f9..2026f51 100644
--- a/src_c/common.c
+++ b/src_c/common.c
@@ -103,11 +103,11 @@ static int write_params(opcut_params_t *params, FILE *stream) {
     if (fputs(",\"panels\":{", stream) < 0)
         return OPCUT_ERROR;
 
-    for (size_t i = 0; i < params->panels_len; ++i) {
-        if (write_panel(params->panels + i, stream))
+    for (opcut_panel_t *panel = params->panels; panel; panel = panel->next) {
+        if (write_panel(panel, stream))
             return OPCUT_ERROR;
 
-        if (i < params->panels_len - 1) {
+        if (panel->next) {
             if (fputs(",", stream) < 0)
                 return OPCUT_ERROR;
         }
@@ -116,11 +116,11 @@ static int write_params(opcut_params_t *params, FILE *stream) {
     if (fputs("},\"items\":{", stream) < 0)
         return OPCUT_ERROR;
 
-    for (size_t i = 0; i < params->items_len; ++i) {
-        if (write_item(params->items + i, stream))
+    for (opcut_item_t *item = params->items; item; item = item->next) {
+        if (write_item(item, stream))
             return OPCUT_ERROR;
 
-        if (i < params->items_len - 1) {
+        if (item->next) {
             if (fputs(",", stream) < 0)
                 return OPCUT_ERROR;
         }
@@ -336,9 +336,7 @@ static int read_params(char *json, opcut_params_t *params, jsmntok_t *tokens,
     params->cut_width = 0;
     params->min_initial_usage = false;
     params->panels = NULL;
-    params->panels_len = 0;
     params->items = NULL;
-    params->items_len = 0;
 
     for (size_t i = 0; i < params_token->size; ++i) {
         jsmntok_t *key_token = tokens + ((*pos)++);
@@ -358,38 +356,36 @@ static int read_params(char *json, opcut_params_t *params, jsmntok_t *tokens,
             if (value_token->type != JSMN_OBJECT)
                 goto error_cleanup;
 
-            if (params->panels) {
-                free(params->panels);
-                params->panels = NULL;
-            }
-
-            params->panels_len = value_token->size;
-            params->panels = malloc(value_token->size * sizeof(opcut_panel_t));
-            if (!params->panels)
-                goto error_cleanup;
+            for (size_t j = 0; j < value_token->size; ++j) {
+                opcut_panel_t *panel = malloc(sizeof(opcut_panel_t));
+                if (!panel)
+                    goto error_cleanup;
 
-            for (size_t j = 0; j < params->panels_len; ++j) {
-                if (read_panel(json, params->panels + j, tokens, pos))
+                if (read_panel(json, panel, tokens, pos)) {
+                    free(panel);
                     goto error_cleanup;
+                }
+
+                panel->next = params->panels;
+                params->panels = panel;
             }
 
         } else if (is_token_val(json, key_token, "items")) {
             if (value_token->type != JSMN_OBJECT)
                 goto error_cleanup;
 
-            if (params->items) {
-                free(params->items);
-                params->items = NULL;
-            }
-
-            params->items_len = value_token->size;
-            params->items = malloc(value_token->size * sizeof(opcut_item_t));
-            if (!params->items)
-                goto error_cleanup;
+            for (size_t j = 0; j < value_token->size; ++j) {
+                opcut_item_t *item = malloc(sizeof(opcut_item_t));
+                if (!item)
+                    goto error_cleanup;
 
-            for (size_t j = 0; j < params->items_len; ++j) {
-                if (read_item(json, params->items + j, tokens, pos))
+                if (read_item(json, item, tokens, pos)) {
+                    free(item);
                     goto error_cleanup;
+                }
+
+                item->next = params->items;
+                params->items = item;
             }
         }
     }
@@ -397,16 +393,7 @@ static int read_params(char *json, opcut_params_t *params, jsmntok_t *tokens,
     return OPCUT_SUCCESS;
 
 error_cleanup:
-    if (params->panels) {
-        free(params->panels);
-        params->panels = NULL;
-    }
-
-    if (params->items) {
-        free(params->items);
-        params->items = NULL;
-    }
-
+    opcut_params_destroy(params);
     return OPCUT_ERROR;
 }
 
@@ -436,11 +423,16 @@ int opcut_params_init(opcut_params_t *params, opcut_str_t *json) {
 
     jsmn_init(&parser);
     tokens_len = jsmn_parse(&parser, json->data, json->len, tokens, tokens_len);
-    if (tokens_len < 0)
+    if (tokens_len < 0) {
+        free(tokens);
         return OPCUT_ERROR;
+    }
 
     size_t pos = 0;
-    return read_params(json->data, params, tokens, &pos);
+    int result = read_params(json->data, params, tokens, &pos);
+
+    free(tokens);
+    return result;
 }
 
 
@@ -454,11 +446,11 @@ int opcut_result_write(opcut_result_t *result, FILE *stream) {
     if (fputs(",\"used\":[", stream) < 0)
         return OPCUT_ERROR;
 
-    for (size_t i = 0; i < result->used_len; ++i) {
-        if (write_used(result->used + i, stream))
+    for (opcut_used_t *used; used; used = used->next) {
+        if (write_used(used, stream))
             return OPCUT_ERROR;
 
-        if (i < result->used_len - 1) {
+        if (used->next) {
             if (fputs(",", stream) < 0)
                 return OPCUT_ERROR;
         }
@@ -467,11 +459,11 @@ int opcut_result_write(opcut_result_t *result, FILE *stream) {
     if (fputs("],\"unused\":[", stream) < 0)
         return OPCUT_ERROR;
 
-    for (size_t i = 0; i < result->unused_len; ++i) {
-        if (write_unused(result->unused + i, stream))
+    for (opcut_unused_t *unused; unused; unused = unused->next) {
+        if (write_unused(unused, stream))
             return OPCUT_ERROR;
 
-        if (i < result->unused_len - 1) {
+        if (unused->next) {
             if (fputs(",", stream) < 0)
                 return OPCUT_ERROR;
         }
@@ -491,18 +483,34 @@ void opcut_str_destroy(opcut_str_t *str) {
 
 
 void opcut_params_destroy(opcut_params_t *params) {
-    if (params->panels)
-        free(params->panels);
+    opcut_panel_t *panel = params->panels;
+    while (panel) {
+        opcut_panel_t *next_panel = panel->next;
+        free(panel);
+        panel = next_panel;
+    }
 
-    if (params->items)
-        free(params->items);
+    opcut_item_t *item = params->items;
+    while (item) {
+        opcut_item_t *next_item = item->next;
+        free(item);
+        item = next_item;
+    }
 }
 
 
 void opcut_result_destroy(opcut_result_t *result) {
-    if (result->used)
-        free(result->used);
+    opcut_used_t *used = result->used;
+    while (used) {
+        opcut_used_t *next_used = used->next;
+        free(used);
+        used = next_used;
+    }
 
-    if (result->unused)
-        free(result->unused);
+    opcut_unused_t *unused = result->unused;
+    while (unused) {
+        opcut_unused_t *next_unused = unused->next;
+        free(unused);
+        unused = next_unused;
+    }
 }
diff --git a/src_c/common.h b/src_c/common.h
index 660932f..c83f808 100644
--- a/src_c/common.h
+++ b/src_c/common.h
@@ -13,15 +13,9 @@
     ((opcut_params_t){.cut_width = 0,                                          \
                       .min_initial_usage = false,                              \
                       .panels = NULL,                                          \
-                      .panels_len = 0,                                         \
-                      .items = NULL,                                           \
-                      .items_len = 0})
+                      .items = NULL})
 #define OPCUT_RESULT_EMPTY                                                     \
-    ((opcut_result_t){.params = NULL,                                          \
-                      .used = NULL,                                            \
-                      .used_len = 0,                                           \
-                      .unused = NULL,                                          \
-                      .unused_len = 0})
+    ((opcut_result_t){.params = NULL, .used = NULL, .unused = NULL})
 
 #ifdef __cplusplus
 extern "C" {
@@ -32,22 +26,24 @@ typedef struct {
     size_t len;
 } opcut_str_t;
 
-typedef struct {
+typedef struct opcut_panel_t {
     opcut_str_t id;
     double width;
     double height;
 
     // internal
+    struct opcut_panel_t *next;
     double area;
 } opcut_panel_t;
 
-typedef struct {
+typedef struct opcut_item_t {
     opcut_str_t id;
     double width;
     double height;
     bool can_rotate;
 
     // internal
+    struct opcut_item_t *next;
     double area;
 } opcut_item_t;
 
@@ -55,20 +51,21 @@ typedef struct {
     double cut_width;
     bool min_initial_usage;
     opcut_panel_t *panels;
-    size_t panels_len;
     opcut_item_t *items;
-    size_t items_len;
 } opcut_params_t;
 
-typedef struct {
+typedef struct opcut_used_t {
     opcut_panel_t *panel;
     opcut_item_t *item;
     double x;
     double y;
     bool rotate;
+
+    // internal
+    struct opcut_used_t *next;
 } opcut_used_t;
 
-typedef struct {
+typedef struct opcut_unused_t {
     opcut_panel_t *panel;
     double width;
     double height;
@@ -76,6 +73,7 @@ typedef struct {
     double y;
 
     // internal
+    struct opcut_unused_t *next;
     double area;
     bool initial;
 } opcut_unused_t;
@@ -83,9 +81,7 @@ typedef struct {
 typedef struct {
     opcut_params_t *params;
     opcut_used_t *used;
-    size_t used_len;
     opcut_unused_t *unused;
-    size_t unused_len;
 
     // internal
     double panels_area;
diff --git a/src_c/csp.c b/src_c/csp.c
index 4137955..8ff94cc 100644
--- a/src_c/csp.c
+++ b/src_c/csp.c
@@ -10,6 +10,88 @@ typedef struct {
 } fitness_t;
 
 
+static void sort_panels(opcut_panel_t **first, opcut_panel_t **last) {
+    if (!*first) {
+        if (last)
+            *last = NULL;
+        return;
+    }
+
+    opcut_panel_t *pivot_first = *first;
+    opcut_panel_t *pivot_last = *first;
+    opcut_panel_t *left_first = NULL;
+    opcut_panel_t *right_first = NULL;
+
+    for (opcut_panel_t *panel = (*first)->next; panel;) {
+        opcut_panel_t *next = panel->next;
+        if (panel->area < pivot_first->area) {
+            panel->next = left_first;
+            left_first = panel;
+        } else if (panel->area > pivot_first->area) {
+            panel->next = right_first;
+            right_first = panel;
+        } else {
+            pivot_last->next = panel;
+            pivot_last = panel;
+        }
+        panel = next;
+    }
+
+    opcut_panel_t *left_last;
+    opcut_panel_t *right_last;
+    sort_panels(&left_first, &left_last);
+    sort_panels(&right_first, &right_last);
+
+    *first = (left_first ? left_first : pivot_first);
+    if (left_last)
+        left_last->next = pivot_first;
+    pivot_last->next = right_first;
+    if (last)
+        *last = (right_last ? right_last : pivot_last);
+}
+
+
+static void sort_items(opcut_item_t **first, opcut_item_t **last) {
+    if (!*first) {
+        if (last)
+            *last = NULL;
+        return;
+    }
+
+    opcut_item_t *pivot_first = *first;
+    opcut_item_t *pivot_last = *first;
+    opcut_item_t *left_first = NULL;
+    opcut_item_t *right_first = NULL;
+
+    for (opcut_item_t *item = (*first)->next; item;) {
+        opcut_item_t *next = item->next;
+        if (item->area > pivot_first->area) {
+            item->next = left_first;
+            left_first = item;
+        } else if (item->area < pivot_first->area) {
+            item->next = right_first;
+            right_first = item;
+        } else {
+            pivot_last->next = item;
+            pivot_last = item;
+        }
+        item = next;
+    }
+
+    opcut_item_t *left_last;
+    opcut_item_t *right_last;
+    sort_items(&left_first, &left_last);
+    sort_items(&right_first, &right_last);
+
+    *first = (left_first ? left_first : pivot_first);
+    if (left_last)
+        left_last->next = pivot_first;
+    pivot_last->next = right_first;
+    if (last)
+        *last = (right_last ? right_last : pivot_last);
+}
+
+
 static inline int compare_fitness(fitness_t *f1, fitness_t *f2) {
     return (f1->unused_initial_count == f2->unused_initial_count
                 ? f1->fitness - f2->fitness
@@ -20,13 +102,11 @@ static inline int compare_fitness(fitness_t *f1, fitness_t *f2) {
 static void calculate_fitness(opcut_result_t *result, fitness_t *fitness) {
     fitness->fitness = 0;
 
-    for (size_t i = 0; i < result->params->panels_len; ++i) {
-        opcut_panel_t *panel = result->params->panels + i;
-
+    for (opcut_panel_t *panel = result->params->panels; panel;
+         panel = panel->next) {
         double min_used_area = 0;
         double used_areas = 0;
-        for (size_t j = 0; j < result->used_len; ++j) {
-            opcut_used_t *used = result->used + i;
+        for (opcut_used_t *used = result->used; used; used = used->next) {
             if (used->panel != panel)
                 continue;
             if (min_used_area == 0 || used->item->area < min_used_area)
@@ -35,8 +115,8 @@ static void calculate_fitness(opcut_result_t *result, fitness_t *fitness) {
         }
 
         double max_unused_area = 0;
-        for (size_t j = 0; j < result->unused_len; ++j) {
-            opcut_unused_t *unused = result->unused + i;
+        for (opcut_unused_t *unused = result->unused; unused;
+             unused = unused->next) {
             if (unused->panel != panel)
                 continue;
             if (max_unused_area == 0 || unused->area > max_unused_area)
@@ -50,8 +130,8 @@ static void calculate_fitness(opcut_result_t *result, fitness_t *fitness) {
 
     fitness->unused_initial_count = 0;
     if (result->params->min_initial_usage) {
-        for (size_t i = 0; i < result->unused_len; ++i) {
-            opcut_unused_t *unused = result->unused + i;
+        for (opcut_unused_t *unused = result->unused; unused;
+             unused = unused->next) {
             if (unused->initial)
                 fitness->unused_initial_count += 1;
         }
@@ -109,14 +189,18 @@ static int cut_item_from_unused(opcut_item_t *item, opcut_unused_t *unused,
 }
 
 
+void opcut_sort_params(opcut_params_t *params) {
+    sort_panels(&(params->panels), NULL);
+    sort_items(&(params->items), NULL);
+}
+
+
 int opcut_calculate(opcut_method_t method, opcut_params_t *params,
                     opcut_result_t *result) {
 
     result->params = params;
     result->used = NULL;
-    result->used_len = 0;
     result->unused = NULL;
-    result->unused_len = 0;
     result->panels_area = 0;
 
     return OPCUT_SUCCESS;
diff --git a/src_c/csp.h b/src_c/csp.h
index 2cccf50..3a7cd45 100644
--- a/src_c/csp.h
+++ b/src_c/csp.h
@@ -13,6 +13,7 @@ typedef enum {
     OPCUT_METHOD_FORWARD_GREEDY
 } opcut_method_t;
 
+void opcut_sort_params(opcut_params_t *params);
 int opcut_calculate(opcut_method_t method, opcut_params_t *params,
                     opcut_result_t *result);
 
diff --git a/src_c/main.c b/src_c/main.c
index 9648f7c..85a8000 100644
--- a/src_c/main.c
+++ b/src_c/main.c
@@ -116,6 +116,8 @@ int main(int argc, char **argv) {
         goto cleanup;
     }
 
+    opcut_sort_params(&params);
+
     exit_code = opcut_calculate(args.method, &params, &result);
     if (exit_code) {
         fprintf(stderr, "calculation error\n");