WIP c implementation

7 files changed, 265 insertions, 153 deletions

diff --git a/src_c/common.c b/src_c/common.c
index 2026f51..403fe87 100644
--- a/src_c/common.c
+++ b/src_c/common.c
@@ -327,7 +327,7 @@ static int read_item(char *json, opcut_item_t *item, jsmntok_t *tokens,
 }
 
 
-static int read_params(char *json, opcut_params_t *params, jsmntok_t *tokens,
+static int read_params(opcut_params_t *params, char *json, jsmntok_t *tokens,
                        size_t *pos) {
     jsmntok_t *params_token = tokens + ((*pos)++);
     if (params_token->type != JSMN_OBJECT)
@@ -337,52 +337,50 @@ static int read_params(char *json, opcut_params_t *params, jsmntok_t *tokens,
     params->min_initial_usage = false;
     params->panels = NULL;
     params->items = NULL;
+    params->panels_area = 0;
 
     for (size_t i = 0; i < params_token->size; ++i) {
         jsmntok_t *key_token = tokens + ((*pos)++);
         jsmntok_t *value_token = tokens + ((*pos)++);
         if (key_token->type != JSMN_STRING)
-            goto error_cleanup;
+            return OPCUT_ERROR;
 
         if (is_token_val(json, key_token, "cut_width")) {
             if (read_number(json, &(params->cut_width), value_token))
-                goto error_cleanup;
+                return OPCUT_ERROR;
 
         } else if (is_token_val(json, key_token, "min_initial_usage")) {
             if (read_bool(json, &(params->min_initial_usage), value_token))
-                goto error_cleanup;
+                return OPCUT_ERROR;
 
         } else if (is_token_val(json, key_token, "panels")) {
             if (value_token->type != JSMN_OBJECT)
-                goto error_cleanup;
+                return OPCUT_ERROR;
 
             for (size_t j = 0; j < value_token->size; ++j) {
-                opcut_panel_t *panel = malloc(sizeof(opcut_panel_t));
+                opcut_panel_t *panel = opcut_pool_alloc(params->panel_pool);
                 if (!panel)
-                    goto error_cleanup;
+                    return OPCUT_ERROR;
 
-                if (read_panel(json, panel, tokens, pos)) {
-                    free(panel);
-                    goto error_cleanup;
-                }
+                if (read_panel(json, panel, tokens, pos))
+                    return OPCUT_ERROR;
 
                 panel->next = params->panels;
                 params->panels = panel;
+                params->panels_area += panel->area;
             }
 
         } else if (is_token_val(json, key_token, "items")) {
             if (value_token->type != JSMN_OBJECT)
-                goto error_cleanup;
+                return OPCUT_ERROR;
 
             for (size_t j = 0; j < value_token->size; ++j) {
-                opcut_item_t *item = malloc(sizeof(opcut_item_t));
+                opcut_item_t *item = opcut_pool_alloc(params->item_pool);
                 if (!item)
-                    goto error_cleanup;
+                    return OPCUT_ERROR;
 
-                if (read_item(json, item, tokens, pos)) {
-                    free(item);
-                    goto error_cleanup;
-                }
+                if (read_item(json, item, tokens, pos))
+                    return OPCUT_ERROR;
 
                 item->next = params->items;
                 params->items = item;
@@ -391,24 +389,14 @@ static int read_params(char *json, opcut_params_t *params, jsmntok_t *tokens,
     }
 
     return OPCUT_SUCCESS;
-
-error_cleanup:
-    opcut_params_destroy(params);
-    return OPCUT_ERROR;
 }
 
 
-int opcut_str_resize(opcut_str_t *str, size_t size) {
-    char *data = realloc(str->data, size);
-    if (!data)
-        return OPCUT_ERROR;
-
-    str->data = data;
-    return OPCUT_SUCCESS;
-}
+int opcut_params_init(opcut_params_t *params, opcut_pool_t *panel_pool,
+                      opcut_pool_t *item_pool, opcut_str_t *json) {
+    params->panel_pool = panel_pool;
+    params->item_pool = item_pool;
 
-
-int opcut_params_init(opcut_params_t *params, opcut_str_t *json) {
     jsmn_parser parser;
     int tokens_len;
 
@@ -429,10 +417,10 @@ int opcut_params_init(opcut_params_t *params, opcut_str_t *json) {
     }
 
     size_t pos = 0;
-    int result = read_params(json->data, params, tokens, &pos);
+    int err = read_params(params, json->data, tokens, &pos);
 
     free(tokens);
-    return result;
+    return err;
 }
 
 
@@ -474,43 +462,3 @@ int opcut_result_write(opcut_result_t *result, FILE *stream) {
 
     return OPCUT_SUCCESS;
 }
-
-
-void opcut_str_destroy(opcut_str_t *str) {
-    if (str->data)
-        free(str->data);
-}
-
-
-void opcut_params_destroy(opcut_params_t *params) {
-    opcut_panel_t *panel = params->panels;
-    while (panel) {
-        opcut_panel_t *next_panel = panel->next;
-        free(panel);
-        panel = next_panel;
-    }
-
-    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) {
-    opcut_used_t *used = result->used;
-    while (used) {
-        opcut_used_t *next_used = used->next;
-        free(used);
-        used = next_used;
-    }
-
-    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 c83f808..3464a61 100644
--- a/src_c/common.h
+++ b/src_c/common.h
@@ -3,20 +3,12 @@
 
 #include <stdbool.h>
 #include <stdio.h>
+#include "pool.h"
 
 #define OPCUT_SUCCESS 0
 #define OPCUT_ERROR 1
 #define OPCUT_UNSOLVABLE 2
 
-#define OPCUT_STR_EMPTY ((opcut_str_t){.data = NULL, .len = 0})
-#define OPCUT_PARAMS_EMPTY                                                     \
-    ((opcut_params_t){.cut_width = 0,                                          \
-                      .min_initial_usage = false,                              \
-                      .panels = NULL,                                          \
-                      .items = NULL})
-#define OPCUT_RESULT_EMPTY                                                     \
-    ((opcut_result_t){.params = NULL, .used = NULL, .unused = NULL})
-
 #ifdef __cplusplus
 extern "C" {
 #endif
@@ -52,6 +44,11 @@ typedef struct {
     bool min_initial_usage;
     opcut_panel_t *panels;
     opcut_item_t *items;
+
+    // internal
+    opcut_pool_t *panel_pool;
+    opcut_pool_t *item_pool;
+    double panels_area;
 } opcut_params_t;
 
 typedef struct opcut_used_t {
@@ -84,18 +81,15 @@ typedef struct {
     opcut_unused_t *unused;
 
     // internal
-    double panels_area;
+    opcut_pool_t *used_pool;
+    opcut_pool_t *unused_pool;
 } opcut_result_t;
 
 
-int opcut_str_resize(opcut_str_t *str, size_t size);
-int opcut_params_init(opcut_params_t *params, opcut_str_t *json);
+int opcut_params_init(opcut_params_t *params, opcut_pool_t *panel_pool,
+                      opcut_pool_t *item_pool, opcut_str_t *json);
 int opcut_result_write(opcut_result_t *result, FILE *stream);
 
-void opcut_str_destroy(opcut_str_t *str);
-void opcut_params_destroy(opcut_params_t *params);
-void opcut_result_destroy(opcut_result_t *result);
-
 #ifdef __cplusplus
 }
 #endif
diff --git a/src_c/csp.c b/src_c/csp.c
index 8ff94cc..9cd25ec 100644
--- a/src_c/csp.c
+++ b/src_c/csp.c
@@ -24,10 +24,10 @@ static void sort_panels(opcut_panel_t **first, opcut_panel_t **last) {
 
     for (opcut_panel_t *panel = (*first)->next; panel;) {
         opcut_panel_t *next = panel->next;
-        if (panel->area < pivot_first->area) {
+        if (panel->area > pivot_first->area) {
             panel->next = left_first;
             left_first = panel;
-        } else if (panel->area > pivot_first->area) {
+        } else if (panel->area < pivot_first->area) {
             panel->next = right_first;
             right_first = panel;
         } else {
@@ -123,9 +123,11 @@ static void calculate_fitness(opcut_result_t *result, fitness_t *fitness) {
                 max_unused_area = unused->area;
         }
 
-        fitness->fitness += (panel->area - used_areas) / result->panels_area;
-        fitness->fitness -= FITNESS_K * min_used_area * max_unused_area /
-                            (result->panels_area * result->panels_area);
+        fitness->fitness +=
+            (panel->area - used_areas) / result->params->panels_area;
+        fitness->fitness -=
+            FITNESS_K * min_used_area * max_unused_area /
+            (result->params->panels_area * result->params->panels_area);
     }
 
     fitness->unused_initial_count = 0;
@@ -139,69 +141,219 @@ static void calculate_fitness(opcut_result_t *result, fitness_t *fitness) {
 }
 
 
-static int cut_item_from_unused(opcut_item_t *item, opcut_unused_t *unused,
-                                bool rotate, double cut_width, bool vertical,
-                                opcut_used_t *new_used,
-                                opcut_unused_t *new_unused,
-                                size_t *new_unused_len) {
+static inline bool item_fits_unused(opcut_item_t *item, opcut_unused_t *unused,
+                                    bool rotate) {
+    if (rotate && !item->can_rotate)
+        return false;
+
+    double item_width = (rotate ? item->height : item->width);
+    double item_height = (rotate ? item->width : item->height);
+
+    return unused->height >= item_height && unused->width >= item_width;
+}
+
+
+static int cut_item_from_unused(opcut_result_t *result, opcut_item_t *item,
+                                opcut_unused_t *unused, bool rotate,
+                                bool vertical) {
     double item_width = (rotate ? item->height : item->width);
     double item_height = (rotate ? item->width : item->height);
     if (unused->height < item_height || unused->width < item_width)
-        return OPCUT_UNSOLVABLE;
+        return OPCUT_ERROR;
+
+    opcut_used_t *used = opcut_pool_alloc(result->used_pool);
+    if (!used)
+        return OPCUT_ERROR;
+    *used = (opcut_used_t){.panel = unused->panel,
+                           .item = item,
+                           .x = unused->x,
+                           .y = unused->y,
+                           .rotate = rotate,
+                           .next = result->used};
+    result->used = used;
 
-    new_used->panel = unused->panel;
-    new_used->item = item;
-    new_used->x = unused->x;
-    new_used->y = unused->y;
-    new_used->rotate = rotate;
 
     double width;
     double height;
-    *new_unused_len = 0;
 
-    width = unused->width - item_width - cut_width;
+    width = unused->width - item_width - result->params->cut_width;
     if (width > 0) {
         height = (vertical ? unused->height : item_height);
-        new_unused[(*new_unused_len)++] =
-            (opcut_unused_t){.panel = unused->panel,
-                             .width = width,
-                             .height = height,
-                             .x = unused->x + item_width + cut_width,
-                             .y = unused->y,
-                             .area = width * height,
-                             .initial = false};
+        opcut_unused_t *new_unused = opcut_pool_alloc(result->unused_pool);
+        if (!new_unused)
+            return OPCUT_ERROR;
+        *new_unused = (opcut_unused_t){.panel = unused->panel,
+                                       .width = width,
+                                       .height = height,
+                                       .x = unused->x + item_width +
+                                            result->params->cut_width,
+                                       .y = unused->y,
+                                       .next = result->unused,
+                                       .area = width * height,
+                                       .initial = false};
+        result->unused = new_unused;
     }
 
-    height = unused->height - item_height - cut_width;
+    height = unused->height - item_height - result->params->cut_width;
     if (height > 0) {
         width = (vertical ? item_width : unused->width);
-        new_unused[(*new_unused_len)++] =
-            (opcut_unused_t){.panel = unused->panel,
-                             .width = width,
-                             .height = height,
-                             .x = unused->x,
-                             .y = unused->y + item_height + cut_width,
-                             .area = width * height,
-                             .initial = false};
+        opcut_unused_t *new_unused = opcut_pool_alloc(result->unused_pool);
+        if (!new_unused)
+            return OPCUT_ERROR;
+        *new_unused = (opcut_unused_t){.panel = unused->panel,
+                                       .width = width,
+                                       .height = height,
+                                       .x = unused->x,
+                                       .y = unused->y + item_height +
+                                            result->params->cut_width,
+                                       .next = result->unused,
+                                       .area = width * height,
+                                       .initial = false};
+        result->unused = new_unused;
     }
 
     return OPCUT_SUCCESS;
 }
 
 
-void opcut_sort_params(opcut_params_t *params) {
-    sort_panels(&(params->panels), NULL);
-    sort_items(&(params->items), NULL);
+static int copy_unused(opcut_result_t *result, opcut_unused_t *exclude) {
+    opcut_unused_t *unused = NULL;
+    for (opcut_unused_t *i = result->unused; i; i = i->next) {
+        if (i == exclude)
+            continue;
+
+        opcut_unused_t *temp = opcut_pool_alloc(result->unused_pool);
+        if (!temp)
+            return OPCUT_ERROR;
+
+        *temp = *i;
+        temp->next = unused;
+        unused = temp;
+    }
+
+    result->unused = NULL;
+    while (unused) {
+        opcut_unused_t *next = unused->next;
+        unused->next = result->unused;
+        result->unused = unused;
+        unused = next;
+    }
+
+    return OPCUT_SUCCESS;
 }
 
 
-int opcut_calculate(opcut_method_t method, opcut_params_t *params,
-                    opcut_result_t *result) {
+static void free_unused(opcut_result_t *result) {
+    while (result->unused) {
+        opcut_unused_t *next = result->unused->next;
+        opcut_pool_free(result->unused_pool, result->unused);
+        result->unused = next;
+    }
+}
+
+
+static void free_last_used(opcut_result_t *result) {
+    opcut_pool_free(result->used_pool, result->used);
+}
+
+
+static int calculate_greedy(opcut_result_t *result, opcut_item_t *items) {
+    for (opcut_item_t *item = items; item; item = item->next) {
+        opcut_result_t best_result;
+        fitness_t best_fitness;
+        bool solvable = false;
 
+        for (opcut_unused_t *unused = result->unused; unused;
+             unused = unused->next) {
+            for (size_t rotate = 0; rotate < 2; ++rotate) {
+                if (!item_fits_unused(item, unused, rotate))
+                    continue;
+
+                for (size_t vertical = 0; vertical < 2; ++vertical) {
+                    opcut_result_t temp_result = *result;
+                    if (copy_unused(&temp_result, unused))
+                        return OPCUT_ERROR;
+
+                    if (cut_item_from_unused(&temp_result, item, unused, rotate,
+                                             vertical))
+                        return OPCUT_ERROR;
+
+                    fitness_t temp_fitness;
+                    calculate_fitness(&temp_result, &temp_fitness);
+
+                    if (!solvable) {
+                        best_result = temp_result;
+                        best_fitness = temp_fitness;
+                        solvable = true;
+
+                    } else if (compare_fitness(&temp_fitness, &best_fitness) <
+                               0) {
+                        free_last_used(&best_result);
+                        free_unused(&best_result);
+                        best_result = temp_result;
+                        best_fitness = temp_fitness;
+
+                    } else {
+                        free_last_used(&temp_result);
+                        free_unused(&temp_result);
+                    }
+                }
+            }
+        }
+
+        if (!solvable)
+            return OPCUT_UNSOLVABLE;
+
+        free_unused(result);
+        *result = best_result;
+    }
+
+    return OPCUT_SUCCESS;
+}
+
+
+static int calculate_forward_greedy(opcut_result_t *result,
+                                    opcut_item_t *items) {
+    for (opcut_item_t *item = items; item; item = item->next) {
+    }
+
+    return OPCUT_SUCCESS;
+}
+
+
+int opcut_calculate(opcut_pool_t *used_pool, opcut_pool_t *unused_pool,
+                    opcut_method_t method, opcut_params_t *params,
+                    opcut_result_t *result) {
+    result->used_pool = used_pool;
+    result->unused_pool = unused_pool;
     result->params = params;
     result->used = NULL;
     result->unused = NULL;
-    result->panels_area = 0;
 
-    return OPCUT_SUCCESS;
+    sort_panels(&(params->panels), NULL);
+    sort_items(&(params->items), NULL);
+
+    for (opcut_panel_t *panel = params->panels; panel; panel = panel->next) {
+        opcut_unused_t *unused = opcut_pool_alloc(unused_pool);
+        if (!unused)
+            return OPCUT_ERROR;
+
+        *unused = (opcut_unused_t){.panel = panel,
+                                   .width = panel->width,
+                                   .height = panel->height,
+                                   .x = 0,
+                                   .y = 0,
+                                   .next = result->unused,
+                                   .area = panel->area,
+                                   .initial = true};
+        result->unused = unused;
+    }
+
+    if (method == OPCUT_METHOD_GREEDY)
+        return calculate_greedy(result, params->items);
+
+    if (method == OPCUT_METHOD_FORWARD_GREEDY)
+        return calculate_forward_greedy(result, params->items);
+
+    return OPCUT_ERROR;
 }
diff --git a/src_c/csp.h b/src_c/csp.h
index 3a7cd45..c88c749 100644
--- a/src_c/csp.h
+++ b/src_c/csp.h
@@ -1,5 +1,5 @@
-#ifndef OPCUT_POOL_H
-#define OPCUT_POOL_H
+#ifndef OPCUT_CSP_H
+#define OPCUT_CSP_H
 
 #include <stddef.h>
 #include "common.h"
@@ -13,8 +13,9 @@ 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,
+
+int opcut_calculate(opcut_pool_t *used_pool, opcut_pool_t *unused_pool,
+                    opcut_method_t method, opcut_params_t *params,
                     opcut_result_t *result);
 
 #ifdef __cplusplus
diff --git a/src_c/main.c b/src_c/main.c
index 85a8000..bf0b117 100644
--- a/src_c/main.c
+++ b/src_c/main.c
@@ -2,7 +2,6 @@
 #include <stdlib.h>
 #include <string.h>
 #include <argparse.h>
-#include "common.h"
 #include "csp.h"
 
 
@@ -65,9 +64,11 @@ static int read_stream(FILE *stream, opcut_str_t *json) {
 
     while (!(json->len < size)) {
         size += 4096;
-        if (opcut_str_resize(json, size))
+        char *data = realloc(json->data, size);
+        if (!data)
             return OPCUT_ERROR;
 
+        json->data = data;
         json->len += fread(json->data + json->len, 1, size - json->len, stream);
     }
 
@@ -76,14 +77,24 @@ static int read_stream(FILE *stream, opcut_str_t *json) {
 
 
 int main(int argc, char **argv) {
+    opcut_pool_t *panel_pool = opcut_pool_create(sizeof(opcut_panel_t));
+    opcut_pool_t *item_pool = opcut_pool_create(sizeof(opcut_item_t));
+    opcut_pool_t *used_pool = opcut_pool_create(sizeof(opcut_used_t));
+    opcut_pool_t *unused_pool = opcut_pool_create(sizeof(opcut_unused_t));
+
     args_t args;
     FILE *input_stream = NULL;
     FILE *output_stream = NULL;
-    opcut_str_t json = OPCUT_STR_EMPTY;
-    opcut_params_t params = OPCUT_PARAMS_EMPTY;
-    opcut_result_t result = OPCUT_RESULT_EMPTY;
+    opcut_str_t json = {.data = NULL, .len = 0};
+    opcut_params_t params;
+    opcut_result_t result;
     int exit_code;
 
+    if (!panel_pool || !item_pool || !used_pool || !unused_pool) {
+        fprintf(stderr, "error creating memory pools\n");
+        goto cleanup;
+    }
+
     exit_code = parse_args(&args, argc, argv);
     if (exit_code) {
         fprintf(stderr, "error parsing command line arguments\n");
@@ -110,15 +121,14 @@ int main(int argc, char **argv) {
         goto cleanup;
     }
 
-    exit_code = opcut_params_init(&params, &json);
+    exit_code = opcut_params_init(&params, panel_pool, item_pool, &json);
     if (exit_code) {
         fprintf(stderr, "error parsing calculation parameters\n");
         goto cleanup;
     }
 
-    opcut_sort_params(&params);
-
-    exit_code = opcut_calculate(args.method, &params, &result);
+    exit_code =
+        opcut_calculate(used_pool, unused_pool, args.method, &params, &result);
     if (exit_code) {
         fprintf(stderr, "calculation error\n");
         goto cleanup;
@@ -128,13 +138,20 @@ int main(int argc, char **argv) {
 
 cleanup:
 
-    opcut_result_destroy(&result);
-    opcut_params_destroy(&params);
-    opcut_str_destroy(&json);
+    if (json.data)
+        free(json.data);
     if (output_stream)
         fclose(output_stream);
     if (input_stream)
         fclose(input_stream);
+    if (unused_pool)
+        opcut_pool_destroy(unused_pool);
+    if (used_pool)
+        opcut_pool_destroy(used_pool);
+    if (item_pool)
+        opcut_pool_destroy(item_pool);
+    if (panel_pool)
+        opcut_pool_destroy(panel_pool);
 
     return exit_code;
 }
diff --git a/src_c/pool.c b/src_c/pool.c
index 619a97d..04968c8 100644
--- a/src_c/pool.c
+++ b/src_c/pool.c
@@ -66,7 +66,7 @@ void opcut_pool_destroy(opcut_pool_t *pool) {
 }
 
 
-void *opcut_pool_get(opcut_pool_t *pool) {
+void *opcut_pool_alloc(opcut_pool_t *pool) {
     if (!pool->items)
         allocate_block(pool);
 
@@ -78,7 +78,8 @@ void *opcut_pool_get(opcut_pool_t *pool) {
     return header + 1;
 }
 
-void opcut_pool_return(opcut_pool_t *pool, void *item) {
+
+void opcut_pool_free(opcut_pool_t *pool, void *item) {
     header_t *header = (header_t *)item - 1;
     header->next = pool->items;
     pool->items = header;
diff --git a/src_c/pool.h b/src_c/pool.h
index 784278e..6998df6 100644
--- a/src_c/pool.h
+++ b/src_c/pool.h
@@ -9,11 +9,10 @@ extern "C" {
 
 typedef struct opcut_pool_t opcut_pool_t;
 
-
 opcut_pool_t *opcut_pool_create(size_t item_size);
 void opcut_pool_destroy(opcut_pool_t *pool);
-void *opcut_pool_get(opcut_pool_t *pool);
-void opcut_pool_return(opcut_pool_t *pool, void *item);
+void *opcut_pool_alloc(opcut_pool_t *pool);
+void opcut_pool_free(opcut_pool_t *pool, void *item);
 
 #ifdef __cplusplus
 }