WIP native implementation

9 files changed, 94 insertions, 37 deletions

diff --git a/playground/calculate.sh b/playground/calculate.sh
index 9368a6d..9aa6a49 100755
--- a/playground/calculate.sh
+++ b/playground/calculate.sh
@@ -3,6 +3,6 @@
 . $(dirname -- "$0")/env.sh
 
 exec $PYTHON -m opcut calculate \
-    --method forward_greedy \
+    --method forward_greedy_native \
     --output $RUN_PATH/result.json \
     $RUN_PATH/params.json
diff --git a/playground/gdb-calculate.gdb b/playground/gdb-calculate.gdb
new file mode 100644
index 0000000..952559f
--- /dev/null
+++ b/playground/gdb-calculate.gdb
@@ -0,0 +1,5 @@
+set breakpoint pending on
+
+# break src_c/opcut.c:opcut_calculate
+
+run
diff --git a/playground/gdb-calculate.sh b/playground/gdb-calculate.sh
new file mode 100755
index 0000000..f2bf64b
--- /dev/null
+++ b/playground/gdb-calculate.sh
@@ -0,0 +1,20 @@
+#!/bin/sh
+
+set -e
+
+. $(dirname -- "$0")/env.sh
+
+PYTHON_BIN="$($PYTHON -c "import sys; print(sys.executable)")"
+
+
+cd $ROOT_PATH
+doit clean_all
+doit json_schema_repo c
+
+cd $RUN_PATH
+exec gdb --directory $ROOT_PATH \
+         --command $RUN_PATH/gdb-calculate.gdb \
+         --args $PYTHON_BIN -m opcut calculate \
+                            --method forward_greedy_native \
+                            --output $RUN_PATH/result.json \
+                            $RUN_PATH/params.json
diff --git a/playground/params.json b/playground/params.json
index 789505c..5aff8ca 100644
--- a/playground/params.json
+++ b/playground/params.json
@@ -1,5 +1,6 @@
 {
     "cut_width": 1,
+    "min_initial_usage": true,
     "panels": {
         "p1": {
             "width": 50,
@@ -8,9 +9,39 @@
     },
     "items": {
         "i1": {
+            "width": 1,
+            "height": 5,
+            "can_rotate": true
+        },
+        "i1_1": {
+            "width": 1,
+            "height": 5,
+            "can_rotate": true
+        },
+        "i1_2": {
+            "width": 1,
+            "height": 5,
+            "can_rotate": true
+        },
+        "i1_3": {
+            "width": 1,
+            "height": 5,
+            "can_rotate": true
+        },
+        "i1_4": {
+            "width": 1,
+            "height": 5,
+            "can_rotate": true
+        },
+        "i2": {
             "width": 5,
             "height": 5,
             "can_rotate": true
+        },
+        "i3": {
+            "width": 10,
+            "height": 10,
+            "can_rotate": true
         }
     }
 }
diff --git a/src_c/opcut.c b/src_c/opcut.c
index 9946d1c..494ef6d 100644
--- a/src_c/opcut.c
+++ b/src_c/opcut.c
@@ -4,6 +4,8 @@
 #define PAGE_SIZE 4096
 #define FITNESS_K 0.03
 
+typedef double (*sort_compare_fn)(opcut_params_t *params, size_t id1,
+                                  size_t id2);
 
 typedef struct mem_header_t {
     struct mem_header_t *next;
@@ -137,51 +139,39 @@ static inline void swap_ids(size_t *ids, size_t pos1, size_t pos2) {
 }
 
 
-static size_t partition_panel_ids(opcut_params_t *params, size_t *panel_ids,
-                                  size_t start, size_t stop) {
+static size_t partition_ids(opcut_params_t *params, sort_compare_fn cmp,
+                            size_t *ids, size_t start, size_t stop) {
     ssize_t pivot = start - 1;
     for (size_t i = start; i < stop; ++i)
-        if (params->panels[panel_ids[i]].area >=
-            params->panels[panel_ids[stop]].area)
-            swap_ids(panel_ids, ++pivot, i);
+        if (cmp(params, ids[i], ids[stop]) >= 0)
+            swap_ids(ids, ++pivot, i);
     pivot += 1;
-    swap_ids(panel_ids, pivot, stop);
+    swap_ids(ids, pivot, stop);
     return pivot;
 }
 
 
-static void sort_panel_ids(opcut_params_t *params, size_t *panel_ids,
-                           size_t start, size_t stop) {
+static void sort_ids(opcut_params_t *params, sort_compare_fn cmp, size_t *ids,
+                     size_t start, size_t stop) {
     if (start >= stop)
         return;
 
-    size_t pivot = partition_panel_ids(params, panel_ids, start, stop);
-    sort_panel_ids(params, panel_ids, start, pivot - 1);
-    sort_panel_ids(params, panel_ids, pivot + 1, stop);
+    size_t pivot = partition_ids(params, cmp, ids, start, stop);
+    if (pivot)
+        sort_ids(params, cmp, ids, start, pivot - 1);
+    sort_ids(params, cmp, ids, pivot + 1, stop);
 }
 
 
-static size_t partition_item_ids(opcut_params_t *params, size_t *item_ids,
-                                 size_t start, size_t stop) {
-    ssize_t pivot = start - 1;
-    for (size_t i = start; i < stop; ++i)
-        if (params->items[item_ids[i]].area >=
-            params->items[item_ids[stop]].area)
-            swap_ids(item_ids, ++pivot, i);
-    pivot += 1;
-    swap_ids(item_ids, pivot, stop);
-    return pivot;
+static double compare_panels(opcut_params_t *params, size_t panel_id1,
+                             size_t panel_id2) {
+    return params->panels[panel_id1].area - params->panels[panel_id2].area;
 }
 
 
-static void sort_item_ids(opcut_params_t *params, size_t *item_ids,
-                          size_t start, size_t stop) {
-    if (start >= stop)
-        return;
-
-    size_t pivot = partition_item_ids(params, item_ids, start, stop);
-    sort_item_ids(params, item_ids, start, pivot - 1);
-    sort_item_ids(params, item_ids, pivot + 1, stop);
+static double compare_items(opcut_params_t *params, size_t item_id1,
+                            size_t item_id2) {
+    return params->items[item_id1].area - params->items[item_id2].area;
 }
 
 
@@ -197,7 +187,7 @@ static size_t *create_initial_item_ids(opcut_allocator_t *a,
     for (size_t item_id = 0; item_id < params->items_len; ++item_id)
         item_ids[item_id] = item_id;
 
-    sort_item_ids(params, item_ids, 0, params->items_len - 1);
+    sort_ids(params, compare_items, item_ids, 0, params->items_len - 1);
 
     return item_ids;
 }
@@ -215,7 +205,7 @@ static opcut_unused_t *create_initial_unused(opcut_allocator_t *a,
     for (size_t panel_id = 0; panel_id < params->panels_len; ++panel_id)
         panel_ids[panel_id] = panel_id;
 
-    sort_panel_ids(params, panel_ids, 0, params->panels_len - 1);
+    sort_ids(params, compare_panels, panel_ids, 0, params->panels_len - 1);
 
     opcut_unused_t *unused = NULL;
     for (size_t i = 0; i < params->panels_len; ++i) {
@@ -245,7 +235,7 @@ static opcut_unused_t *create_initial_unused(opcut_allocator_t *a,
 }
 
 
-static inline int compare_fitness(fitness_t *f1, fitness_t *f2) {
+static inline double compare_fitness(fitness_t *f1, fitness_t *f2) {
     if (f1->unused_initial_count == f2->unused_initial_count)
         return f1->fitness - f2->fitness;
     return f1->unused_initial_count - f2->unused_initial_count;
@@ -367,6 +357,14 @@ static int cut_item_from_unused(opcut_allocator_t *a, opcut_params_t *params,
         result->unused = new_unused;
     }
 
+    if (result->unused && result->unused->next &&
+        result->unused->area > result->unused->next->area) {
+        opcut_unused_t *temp = result->unused->next;
+        result->unused->next = temp->next;
+        temp->next = result->unused;
+        result->unused = temp;
+    }
+
     return OPCUT_SUCCESS;
 }
 
diff --git a/src_doit/c.py b/src_doit/c.py
index bd9fd74..36257f6 100644
--- a/src_doit/c.py
+++ b/src_doit/c.py
@@ -21,10 +21,13 @@ platforms = [common.local_platform]
 if common.local_platform == common.Platform.LINUX_X86_64:
     platforms.append(common.Platform.WINDOWS_AMD64)
 
+cc_flags = ['-fPIC', '-O2']
+# cc_flags = ['-fPIC', '-O0', '-ggdb']
+
 builds = [CBuild(src_paths=[*src_c_dir.rglob('*.c')],
                  build_dir=build_c_dir / platform.name.lower(),
                  platform=platform,
-                 cc_flags=['-fPIC', '-O2'])
+                 cc_flags=cc_flags)
           for platform in platforms]
 
 lib_paths = [src_py_dir / (f'opcut/_libopcut{get_lib_suffix(platform)}')
diff --git a/src_js/states.js b/src_js/states.js
index bf3584e..bc50eb3 100644
--- a/src_js/states.js
+++ b/src_js/states.js
@@ -3,7 +3,7 @@ export const main = {
     form: {
         method: 'forward_greedy',
         cut_width: 0.3,
-        min_initial_usage: false,
+        min_initial_usage: true,
         panels: [],
         items: []
     },
diff --git a/src_py/opcut/libopcut.py b/src_py/opcut/libopcut.py
index b5531aa..d5120cd 100644
--- a/src_py/opcut/libopcut.py
+++ b/src_py/opcut/libopcut.py
@@ -31,7 +31,7 @@ def calculate(method: common.Method,
             raise common.UnresolvableError()
 
         if ret != _lib.OPCUT_SUCCESS:
-            raise Exception()
+            raise Exception("calculation error")
 
         used = list(_decode_used(params, native_used))
         unused = list(_decode_unused(params, native_unused))
diff --git a/src_py/opcut/main.py b/src_py/opcut/main.py
index 958e135..58b3060 100644
--- a/src_py/opcut/main.py
+++ b/src_py/opcut/main.py
@@ -41,7 +41,7 @@ def create_argument_parser() -> argparse.ArgumentParser:
         '--output', metavar='PATH', type=Path, default=Path('-'),
         help=f"output result file path or - for stdout ({result_schema_id})")
     calculate.add_argument(
-        'params', type=Path, default=Path('-'),
+        'params', type=Path, default=Path('-'), nargs='?',
         help=f"input params file path or - for stdin ({params_schema_id})")
 
     generate = subparsers.add_parser('generate')