WIP c implementation

1 files changed, 194 insertions, 42 deletions

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;
 }