diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rwxr-xr-x | playground/generate.sh (renamed from playground/generate-output.sh) | 4 | ||||
| -rwxr-xr-x | playground/native-calculate.sh | 8 | ||||
| -rw-r--r-- | src_c/opcut.c | 214 | ||||
| -rw-r--r-- | src_c/opcut.h | 23 | ||||
| -rw-r--r-- | src_doit/c.py | 2 | ||||
| -rw-r--r-- | src_py/opcut/calculate.py | 43 | ||||
| -rw-r--r-- | src_py/opcut/libopcut.py | 228 | ||||
| -rw-r--r-- | src_py/opcut/main.py | 2 |
9 files changed, 336 insertions, 191 deletions
@@ -3,7 +3,6 @@ /cache /node_modules /src_py/opcut/json_schema_repo.json -/src_py/opcut/libopcut.dll -/src_py/opcut/libopcut.so +/src_py/opcut/_libopcut.* /src_py/opcut/ui __pycache__ diff --git a/playground/generate-output.sh b/playground/generate.sh index 4e16a64..11f85f3 100755 --- a/playground/generate-output.sh +++ b/playground/generate.sh @@ -2,8 +2,6 @@ . $(dirname -- "$0")/env.sh -exec $PYTHON -m opcut generate-output \ - --output-type pdf \ +exec $PYTHON -m opcut generate \ < $RUN_PATH/result.json \ > $RUN_PATH/output.pdf \ - diff --git a/playground/native-calculate.sh b/playground/native-calculate.sh deleted file mode 100755 index d47035e..0000000 --- a/playground/native-calculate.sh +++ /dev/null @@ -1,8 +0,0 @@ -#!/bin/sh - -. $(dirname -- "$0")/env.sh - -exec $ROOT_PATH/src_py/opcut/bin/linux-opcut-calculate \ - --method greedy \ - --output result.json \ - params.json diff --git a/src_c/opcut.c b/src_c/opcut.c index 43345d3..855192a 100644 --- a/src_c/opcut.c +++ b/src_c/opcut.c @@ -104,37 +104,37 @@ static void mem_pool_free(mem_pool_t *pool, void *item) { } -static void sort_items(opcut_item_t **first, opcut_item_t **last) { +static void sort_panels(opcut_panel_t **first, opcut_panel_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; + 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 = item; - pivot_last = item; + pivot_last->next = panel; + pivot_last = panel; } - item = next; + panel = next; } - opcut_item_t *left_last; - opcut_item_t *right_last; - sort_items(&left_first, &left_last); - sort_items(&right_first, &right_last); + 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) @@ -145,37 +145,37 @@ static void sort_items(opcut_item_t **first, opcut_item_t **last) { } -static void sort_unused(opcut_unused_t **first, opcut_unused_t **last) { +static void sort_items(opcut_item_t **first, opcut_item_t **last) { if (!*first) { if (last) *last = NULL; return; } - opcut_unused_t *pivot_first = *first; - opcut_unused_t *pivot_last = *first; - opcut_unused_t *left_first = NULL; - opcut_unused_t *right_first = NULL; + 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_unused_t *unused = (*first)->next; unused;) { - opcut_unused_t *next = unused->next; - if (unused->area > pivot_first->area) { - unused->next = left_first; - left_first = unused; - } else if (unused->area < pivot_first->area) { - unused->next = right_first; - right_first = unused; + 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 = unused; - pivot_last = unused; + pivot_last->next = item; + pivot_last = item; } - unused = next; + item = next; } - opcut_unused_t *left_last; - opcut_unused_t *right_last; - sort_unused(&left_first, &left_last); - sort_unused(&right_first, &right_last); + 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) @@ -445,13 +445,13 @@ opcut_allocator_t *opcut_allocator_create(opcut_malloc_t malloc, if (!a) return NULL; - a->free = free; - a->panel = NULL; - a->item = NULL; - a->params = NULL; - a->used = NULL; - a->unused = NULL; - a->result = NULL; + *a = (opcut_allocator_t){.free = free, + .panel = NULL, + .item = NULL, + .params = NULL, + .used = NULL, + .unused = NULL, + .result = NULL}; a->panel = mem_pool_create(malloc, free, sizeof(opcut_panel_t)); if (!a->panel) @@ -508,7 +508,7 @@ void opcut_allocator_destroy(opcut_allocator_t *a) { } -opcut_panel_t *opcut_panel_create(opcut_allocator_t *a, char *id, double width, +opcut_panel_t *opcut_panel_create(opcut_allocator_t *a, int id, double width, double height, opcut_panel_t *next) { opcut_panel_t *panel = mem_pool_alloc(a->panel); if (!panel) @@ -524,7 +524,7 @@ opcut_panel_t *opcut_panel_create(opcut_allocator_t *a, char *id, double width, } -opcut_item_t *opcut_item_create(opcut_allocator_t *a, char *id, double width, +opcut_item_t *opcut_item_create(opcut_allocator_t *a, int id, double width, double height, bool can_rotate, opcut_item_t *next) { opcut_item_t *item = mem_pool_alloc(a->item); @@ -563,102 +563,46 @@ opcut_params_t *opcut_params_create(opcut_allocator_t *a, double cut_width, } -opcut_used_t *opcut_used_create(opcut_allocator_t *a, opcut_panel_t *panel, - opcut_item_t *item, double x, double y, - bool rotate, opcut_used_t *next) { - opcut_used_t *used = mem_pool_alloc(a->used); - if (!used) - return NULL; - - used->panel = panel; - used->item = item; - used->x = x; - used->y = y; - used->rotate = rotate; - used->next = next; - - return used; -} - - -opcut_unused_t *opcut_unused_create(opcut_allocator_t *a, opcut_panel_t *panel, - double width, double height, double x, - double y, bool rotate, - opcut_unused_t *next) { - opcut_unused_t *unused = mem_pool_alloc(a->unused); - if (!unused) - return NULL; - - unused->panel = panel; - unused->width = width; - unused->height = height; - unused->x = x; - unused->y = y; - unused->next = next; - unused->area = width * height; - unused->initial = true; - - return unused; -} - - -opcut_result_t *opcut_result_create(opcut_allocator_t *a, - opcut_params_t *params, opcut_used_t *used, - opcut_unused_t *unused) { - opcut_result_t *result = mem_pool_alloc(a->result); - if (!result) - return NULL; - - result->params = params; - result->used = used; - result->unused = unused; - - return result; -} - - -int opcut_calculate(opcut_allocator_t *a, int method, opcut_result_t *result) { - opcut_item_t *used_items = NULL; - opcut_item_t *unused_items = NULL; - - for (opcut_item_t *item = result->params->items; item;) { - bool is_used = false; - opcut_item_t *next = item->next; +int opcut_calculate(opcut_allocator_t *a, int method, opcut_params_t *params, + opcut_result_t **result) { + *result = mem_pool_alloc(a->result); + if (!*result) + return OPCUT_ERROR; - for (opcut_used_t *used = result->used; used && !is_used; - used = used->next) - is_used = used->item == item; + **result = (opcut_result_t){.params = params, .used = NULL, .unused = NULL}; - if (is_used) { - item->next = used_items; - used_items = item; + sort_panels(&(params->panels), NULL); + sort_items(&(params->items), NULL); - } else { - item->next = unused_items; - unused_items = item; - } + opcut_unused_t *unused = NULL; + for (opcut_panel_t *panel = params->panels; panel; panel = panel->next) { + opcut_unused_t *temp = mem_pool_alloc(a->unused); + if (!temp) + return OPCUT_ERROR; - item = next; + *temp = (opcut_unused_t){.panel = panel, + .width = panel->width, + .height = panel->height, + .x = 0, + .y = 0, + .next = unused, + .area = panel->area, + .initial = true}; + unused = temp; } - sort_items(&used_items, NULL); - sort_items(&unused_items, NULL); - - result->params->items = used_items; - for (opcut_item_t *item = result->params->items; item; item = item->next) { - if (!item->next) { - item->next = unused_items; - break; - } + while (unused) { + opcut_unused_t *next = unused->next; + unused->next = (*result)->unused; + (*result)->unused = unused; + unused = next; } - sort_unused(&(result->unused), NULL); - if (method == OPCUT_METHOD_GREEDY) - return calculate_greedy(a, result, unused_items, false); + return calculate_greedy(a, *result, params->items, false); if (method == OPCUT_METHOD_FORWARD_GREEDY) - return calculate_greedy(a, result, unused_items, true); + return calculate_greedy(a, *result, params->items, true); return OPCUT_ERROR; } diff --git a/src_c/opcut.h b/src_c/opcut.h index de4ae3c..2b7384a 100644 --- a/src_c/opcut.h +++ b/src_c/opcut.h @@ -20,7 +20,7 @@ typedef void (*opcut_free_t)(void *p); typedef struct opcut_allocator_t opcut_allocator_t; typedef struct opcut_panel_t { - char *id; + int id; double width; double height; @@ -30,7 +30,7 @@ typedef struct opcut_panel_t { } opcut_panel_t; typedef struct opcut_item_t { - char *id; + int id; double width; double height; bool can_rotate; @@ -85,26 +85,17 @@ opcut_allocator_t *opcut_allocator_create(opcut_malloc_t malloc, opcut_free_t free); void opcut_allocator_destroy(opcut_allocator_t *a); -opcut_panel_t *opcut_panel_create(opcut_allocator_t *a, char *id, double width, +opcut_panel_t *opcut_panel_create(opcut_allocator_t *a, int id, double width, double height, opcut_panel_t *next); -opcut_item_t *opcut_item_create(opcut_allocator_t *a, char *id, double width, +opcut_item_t *opcut_item_create(opcut_allocator_t *a, int id, double width, double height, bool can_rotate, opcut_item_t *next); opcut_params_t *opcut_params_create(opcut_allocator_t *a, double cut_width, bool min_initial_usage, opcut_panel_t *panels, opcut_item_t *items); -opcut_used_t *opcut_used_create(opcut_allocator_t *a, opcut_panel_t *panel, - opcut_item_t *item, double x, double y, - bool rotate, opcut_used_t *next); -opcut_unused_t *opcut_unused_create(opcut_allocator_t *a, opcut_panel_t *panel, - double width, double height, double x, - double y, bool rotate, - opcut_unused_t *next); -opcut_result_t *opcut_result_create(opcut_allocator_t *a, - opcut_params_t *params, opcut_used_t *used, - opcut_unused_t *unused); - -int opcut_calculate(opcut_allocator_t *a, int method, opcut_result_t *result); + +int opcut_calculate(opcut_allocator_t *a, int method, opcut_params_t *params, + opcut_result_t **result); #ifdef __cplusplus } diff --git a/src_doit/c.py b/src_doit/c.py index b5deb0d..bd9fd74 100644 --- a/src_doit/c.py +++ b/src_doit/c.py @@ -27,7 +27,7 @@ builds = [CBuild(src_paths=[*src_c_dir.rglob('*.c')], cc_flags=['-fPIC', '-O2']) for platform in platforms] -lib_paths = [src_py_dir / (f'opcut/libopcut{get_lib_suffix(platform)}') +lib_paths = [src_py_dir / (f'opcut/_libopcut{get_lib_suffix(platform)}') for platform in platforms] diff --git a/src_py/opcut/calculate.py b/src_py/opcut/calculate.py index 7ae14ce..e0a6752 100644 --- a/src_py/opcut/calculate.py +++ b/src_py/opcut/calculate.py @@ -1,33 +1,23 @@ import itertools from opcut import common +from opcut import libopcut def calculate(method: common.Method, params: common.Params ) -> common.Result: """Calculate cutting stock problem""" - unused = [common.Unused(panel=panel, - width=panel.width, - height=panel.height, - x=0, - y=0) - for panel in params.panels] - result = common.Result(params=params, - used=[], - unused=unused) if method == common.Method.GREEDY: - return _calculate_greedy(result) + return _calculate_greedy(_create_initial_result(params)) - elif method == common.Method.FORWARD_GREEDY: - return _calculate_forward_greedy(result) + if method == common.Method.FORWARD_GREEDY: + return _calculate_forward_greedy(_create_initial_result(params)) - elif method == common.Method.GREEDY_NATIVE: - return _calculate_greedy_native(result) - - elif method == common.Method.FORWARD_GREEDY_NATIVE: - return _calculate_forward_greedy_native(result) + if method in (common.Method.GREEDY_NATIVE, + common.Method.FORWARD_GREEDY_NATIVE): + return libopcut.calculate(method, params) raise ValueError('unsupported method') @@ -35,6 +25,17 @@ def calculate(method: common.Method, _fitness_K = 0.03 +def _create_initial_result(params): + return common.Result(params=params, + used=[], + unused=[common.Unused(panel=panel, + width=panel.width, + height=panel.height, + x=0, + y=0) + for panel in params.panels]) + + def _calculate_greedy(result): while not _is_done(result): new_result = None @@ -68,14 +69,6 @@ def _calculate_forward_greedy(result): return result -def _calculate_greedy_native(result): - raise NotImplementedError() - - -def _calculate_forward_greedy_native(result): - raise NotImplementedError() - - def _get_next_results(result): selected_item = None used_items = {used.item.id for used in result.used} diff --git a/src_py/opcut/libopcut.py b/src_py/opcut/libopcut.py new file mode 100644 index 0000000..1d31fd7 --- /dev/null +++ b/src_py/opcut/libopcut.py @@ -0,0 +1,228 @@ +from pathlib import Path +import ctypes +import sys + +from opcut import common + + +def calculate(method: common.Method, + params: common.Params + ) -> common.Result: + if not _lib: + raise Exception("native implementation not available") + + native_method = _encode_method(method) + + id_panels = {panel_id: panel + for panel_id, panel in enumerate(params.panels)} + id_items = {item_id: item + for item_id, item in enumerate(params.items)} + + a = _lib.opcut_allocator_create(ctypes.pythonapi.PyMem_Malloc, + ctypes.pythonapi.PyMem_Free) + if a is None: + raise Exception("allocation error") + + try: + native_panels = _encode_panels(a, id_panels) + native_items = _encode_items(a, id_items) + native_params = _encode_params(a, params, native_panels, native_items) + + native_result = ctypes.POINTER(_lib.opcut_result_t)() + ret = _lib.opcut_calculate(a, native_method, native_params, + ctypes.byref(native_result)) + + if ret == _lib.OPCUT_UNSOLVABLE: + raise common.UnresolvableError() + + if ret != _lib.OPCUT_SUCCESS: + raise Exception() + + used = list(_decode_used(native_result.contents.used, id_panels, + id_items)) + unused = list(_decode_unused(native_result.contents.unused, + id_panels)) + return common.Result(params=params, + used=used, + unused=unused) + + finally: + _lib.opcut_allocator_destroy(a) + + +def _encode_method(method): + if method == common.Method.GREEDY_NATIVE: + return _lib.OPCUT_METHOD_GREEDY + + if method == common.Method.FORWARD_GREEDY_NATIVE: + return _lib.OPCUT_METHOD_FORWARD_GREEDY + + raise ValueError('unsupported method') + + +def _encode_panels(a, id_panels): + panels = None + for panel_id, panel in id_panels.items(): + panels = _lib.opcut_panel_create(a, panel_id, panel.width, + panel.height, panels) + if panels is None: + raise Exception("allocation error") + return panels + + +def _encode_items(a, id_items): + items = None + for item_id, item in id_items.items(): + items = _lib.opcut_item_create(a, item_id, item.width, item.height, + item.can_rotate, items) + if items is None: + raise Exception("allocation error") + return items + + +def _encode_params(a, params, panels, items): + params = _lib.opcut_params_create(a, params.cut_width, + params.min_initial_usage, panels, items) + if params is None: + raise Exception("allocation error") + return params + + +def _decode_used(used, id_panels, id_items): + while used: + yield common.Used(panel=id_panels[used.contents.panel.contents.id], + item=id_items[used.contents.item.contents.id], + x=used.contents.x, + y=used.contents.y, + rotate=used.contents.rotate) + used = used.contents.next + + +def _decode_unused(unused, id_panels): + while unused: + yield common.Unused(panel=id_panels[unused.contents.panel.contents.id], + width=unused.contents.width, + height=unused.contents.height, + x=unused.contents.x, + y=unused.contents.y) + unused = unused.contents.next + + +class _Lib: + + def __init__(self, path: Path): + lib = ctypes.cdll.LoadLibrary(str(path)) + + self.OPCUT_SUCCESS = 0 + self.OPCUT_ERROR = 1 + self.OPCUT_UNSOLVABLE = 42 + + self.OPCUT_METHOD_GREEDY = 0 + self.OPCUT_METHOD_FORWARD_GREEDY = 1 + + self.opcut_malloc_t = ctypes.c_void_p + self.opcut_free_t = ctypes.c_void_p + self.opcut_allocator_t_p = ctypes.c_void_p + + self.opcut_panel_t = type('opcut_panel_t', (ctypes.Structure, ), {}) + self.opcut_panel_t._fields_ = [ + ('id', ctypes.c_int), + ('width', ctypes.c_double), + ('height', ctypes.c_double), + ('next', ctypes.POINTER(self.opcut_panel_t)), + ('area', ctypes.c_double)] + + self.opcut_item_t = type('opcut_item_t', (ctypes.Structure, ), {}) + self.opcut_item_t._fields_ = [ + ('id', ctypes.c_int), + ('width', ctypes.c_double), + ('height', ctypes.c_double), + ('can_rotate', ctypes.c_bool), + ('next', ctypes.POINTER(self.opcut_item_t)), + ('area', ctypes.c_double)] + + self.opcut_params_t = type('opcut_params_t', (ctypes.Structure, ), {}) + self.opcut_params_t._fields_ = [ + ('cut_width', ctypes.c_double), + ('min_initial_usage', ctypes.c_bool), + ('panels', ctypes.POINTER(self.opcut_panel_t)), + ('items', ctypes.POINTER(self.opcut_item_t)), + ('panels_area', ctypes.c_double)] + + self.opcut_used_t = type('opcut_used_t', (ctypes.Structure, ), {}) + self.opcut_used_t._fields_ = [ + ('panel', ctypes.POINTER(self.opcut_panel_t)), + ('item', ctypes.POINTER(self.opcut_item_t)), + ('x', ctypes.c_double), + ('y', ctypes.c_double), + ('rotate', ctypes.c_bool), + ('next', ctypes.POINTER(self.opcut_used_t))] + + self.opcut_unused_t = type('opcut_unused_t', (ctypes.Structure, ), {}) + self.opcut_unused_t._fields_ = [ + ('panel', ctypes.POINTER(self.opcut_panel_t)), + ('width', ctypes.c_double), + ('height', ctypes.c_double), + ('x', ctypes.c_double), + ('y', ctypes.c_double), + ('next', ctypes.POINTER(self.opcut_unused_t)), + ('area', ctypes.c_double), + ('initial', ctypes.c_bool)] + + self.opcut_result_t = type('opcut_result_t', (ctypes.Structure, ), {}) + self.opcut_result_t._fields_ = [ + ('params', ctypes.POINTER(self.opcut_params_t)), + ('used', ctypes.POINTER(self.opcut_used_t)), + ('unused', ctypes.POINTER(self.opcut_unused_t))] + + functions = [ + (self.opcut_allocator_t_p, + 'opcut_allocator_create', + [self.opcut_malloc_t, self.opcut_free_t]), + + (None, + 'opcut_allocator_destroy', + [self.opcut_allocator_t_p]), + + (ctypes.POINTER(self.opcut_panel_t), + 'opcut_panel_create', + [self.opcut_allocator_t_p, ctypes.c_int, ctypes.c_double, + ctypes.c_double, ctypes.POINTER(self.opcut_panel_t)]), + + (ctypes.POINTER(self.opcut_item_t), + 'opcut_item_create', + [self.opcut_allocator_t_p, ctypes.c_int, ctypes.c_double, + ctypes.c_double, ctypes.c_bool, + ctypes.POINTER(self.opcut_item_t)]), + + (ctypes.POINTER(self.opcut_params_t), + 'opcut_params_create', + [self.opcut_allocator_t_p, ctypes.c_double, ctypes.c_bool, + ctypes.POINTER(self.opcut_panel_t), + ctypes.POINTER(self.opcut_item_t)]), + + (ctypes.c_int, + 'opcut_calculate', + [self.opcut_allocator_t_p, ctypes.c_int, + ctypes.POINTER(self.opcut_params_t), + ctypes.POINTER(ctypes.POINTER(self.opcut_result_t))]) + ] + + for restype, name, argtypes in functions: + function = getattr(lib, name) + function.argtypes = argtypes + function.restype = restype + setattr(self, name, function) + + +if sys.platform == 'win32': + _lib_suffix = '.dll' +elif sys.platform == 'darwin': + _lib_suffix = '.dylib' +else: + _lib_suffix = '.so' + +try: + _lib = _Lib(Path(__file__).parent / f'_libopcut{_lib_suffix}') +except Exception: + _lib = None diff --git a/src_py/opcut/main.py b/src_py/opcut/main.py index f09fe71..958e135 100644 --- a/src_py/opcut/main.py +++ b/src_py/opcut/main.py @@ -59,7 +59,7 @@ def create_argument_parser() -> argparse.ArgumentParser: '--output', metavar='PATH', type=Path, default=Path('-'), help="output file path or - for stdout") generate.add_argument( - 'result', type=Path, default=Path('-'), + 'result', type=Path, default=Path('-'), nargs='?', help=f"input result file path or - for stdin ({result_schema_id})") server = subparsers.add_parser('server') |