pyopcut - GREEDY and FOWARD_GREEDY implementation

2 files changed, 210 insertions, 40 deletions

diff --git a/src_py/opcut/csp.py b/src_py/opcut/csp.py
index 8d91697..04a6d39 100644
--- a/src_py/opcut/csp.py
+++ b/src_py/opcut/csp.py
@@ -1,67 +1,199 @@
-import collections
 import enum
+import itertools
 
+from opcut import util
 
-InputPanel = collections.namedtuple('InputPanel', ['width', 'height', 'label'])
-InputItem = collections.namedtuple('InputItem', ['width', 'height', 'label',
-                                                 'rotate'])
-OutputPanel = collections.namedtuple('OutputPanel', ['width', 'height',
-                                                     'label', 'items'])
-OutputItem = collections.namedtuple('OutputItem', ['width', 'height', 'label',
-                                                   'x', 'y'])
 
-Method = enum.Enum('Method', ['FORWARD_GREEDY'])
+State = util.namedtuple(
+    '_State',
+    ['cut_width', 'float'],
+    ['panels', 'List[Panel]'],
+    ['items', 'List[Item]'],
+    ['used', 'List[Used]'],
+    ['unused', 'List[Unused]'])
+
+Panel = util.namedtuple(
+    'Panel',
+    ['width', 'float'],
+    ['height', 'float'],
+    ['label', 'str'])
+
+Item = util.namedtuple(
+    'Item',
+    ['width', 'float'],
+    ['height', 'float'],
+    ['label', 'str'],
+    ['rotate', 'bool'])
+
+Used = util.namedtuple(
+    'Used',
+    ['panel', 'Panel'],
+    ['item', 'Item'],
+    ['x', 'float'],
+    ['y', 'float'],
+    ['rotate', 'bool'])
+
+Unused = util.namespace(
+    'Unused',
+    ['panel', 'Panel'],
+    ['width', 'float'],
+    ['height', 'float'],
+    ['x', 'float'],
+    ['y', 'float'])
+
+Method = enum.Enum('Method', [
+    'GREEDY',
+    'FORWARD_GREEDY'])
+
+
+class UnresolvableError(Exception):
+    pass
 
 
 def calculate(panels, items, cut_width, method):
     """Calculate cutting stock problem
 
     Args:
-        panels (List[InputPanel]): input panels
-        items (List[InputItem]): input items
+        panels (List[Panel]): input panels
+        items (List[Item]): input items
         cut_width (float): cut width
         method (Method): calculation method
 
     Returns:
-        List[OutputPanel]
+        State
 
     """
+    state = State(
+        cut_width=cut_width,
+        panels=panels,
+        items=items,
+        used=[],
+        unused=[Unused(panel=panel,
+                       width=panel.width,
+                       height=panel.height,
+                       x=0,
+                       y=0)
+                for panel in panels])
     return {
+        Method.GREEDY: _calculate_greedy,
         Method.FORWARD_GREEDY: _calculate_forward_greedy
-    }[method](panels, items)
+    }[method](state)
 
 
-def _calculate_forward_greedy(panels, items):
-    pass
+_fitness_K = 0.03
 
 
-_Part = collections.namedtuple('_Part', ['panel', 'width', 'height', 'x', 'y'])
-_State = collections.namedtuple('_State', ['inputs', 'outputs'])
-_fitness_K = 0.03
+def _calculate_greedy(state):
+    while not _is_done(state):
+        new_state = None
+        new_fitness = None
+        for next_state in _get_next_states(state):
+            next_state_fitness = _fitness(next_state)
+            if new_fitness is None or next_state_fitness < new_fitness:
+                new_state = next_state
+                new_fitness = next_state_fitness
+        if not new_state:
+            raise UnresolvableError()
+        state = new_state
+    return state
+
+
+def _calculate_forward_greedy(state):
+    while not _is_done(state):
+        new_state = None
+        new_fitness = None
+        for next_state in _get_next_states(state):
+            try:
+                next_state_fitness = _fitness(_calculate_greedy(next_state))
+            except UnresolvableError:
+                continue
+            if new_fitness is None or next_state_fitness < new_fitness:
+                new_state = next_state
+                new_fitness = next_state_fitness
+        if not new_state:
+            raise UnresolvableError()
+        state = new_state
+    return state
+
+
+def _get_next_states(state):
+    selected_item = None
+    used_items = {used.item for used in state.used}
+    for item in state.items:
+        if item in used_items:
+            continue
+        if (not selected_item or
+                max(item.width, item.height) >
+                max(selected_item.width, selected_item.height)):
+            selected_item = item
+    if not selected_item:
+        raise Exception('state is done')
+    return _get_next_states_for_item(state, selected_item)
+
+
+def _get_next_states_for_item(state, item):
+    ret = []
+    loop_iter = ((False, i, unused) for i, unused in enumerate(state.unused))
+    if item.rotate:
+        loop_iter = itertools.chain(
+            loop_iter,
+            ((True, i, unused) for i, unused in enumerate(state.unused)))
+    for rotate, i, unused in loop_iter:
+        for vertical in [True, False]:
+            new_used, new_unused = _cut_item_from_unused(
+                unused, item, rotate, state.cut_width, vertical)
+            if not new_used:
+                continue
+            ret.append(state._replace(
+                used=state.used + [new_used],
+                unused=state.unused[:i] + new_unused + state.unused[i+1:]))
+    return ret
+
+
+def _cut_item_from_unused(unused, item, rotate, cut_width, vertical):
+    item_width = item.width if not rotate else item.height
+    item_height = item.height if not rotate else item.width
+    if unused.height < item_height or unused.width < item_width:
+        return None, []
+    used = Used(panel=unused.panel,
+                item=item,
+                x=unused.x,
+                y=unused.y,
+                rotate=rotate)
+    new_unused = []
+    width = unused.width - item_width - cut_width
+    height = unused.height if vertical else item.height
+    if width > 0:
+        new_unused.append(Unused(panel=unused.panel,
+                                 width=width,
+                                 height=height,
+                                 x=unused.x + item_width + cut_width,
+                                 y=unused.y))
+    width = item_width if vertical else unused.width
+    height = unused.height - item_height - cut_width
+    if height > 0:
+        new_unused.append(Unused(panel=unused.panel,
+                                 width=width,
+                                 height=height,
+                                 x=unused.x,
+                                 y=unused.y + item_height + cut_width))
+    return used, new_unused
+
+
+def _is_done(state):
+    return len(state.items) == len(state.used)
 
 
 def _fitness(state):
-    panel_states = {}
-    for i in state.inputs:
-        if i.panel not in panel_states:
-            panel_states[i.panel] = _State([i], [])
-        else:
-            panel_states[i.panel].inputs.append(i)
-    for i in state.outputs:
-        if i.panel not in panel_states:
-            panel_states[i.panel] = _State([], [i])
-        else:
-            panel_states[i.panel].outputs.append(i)
-
-    total_area = sum(i.width * i.height for i in panel_states.keys())
+    total_area = sum(panel.width * panel.height for panel in state.panels)
     result = 0
-    for panel, panel_state in panel_states.items():
-        result += (panel.width * panel.height -
-                   sum(i.width * i.height
-                       for i in panel_state.outputs)) / total_area
+    for panel in state.panels:
+        used_areas = [used.item.width * used.item.height
+                      for used in panel.used]
+        unused_areas = [unused.width * unused.height
+                        for unused in panel.unused]
+        result += (panel.width * panel.height - sum(used_areas)) / total_area
         result -= (_fitness_K *
-                   min((i.width * i.height for i in panel_state.outputs),
-                       default=0) *
-                   max((i.width * i.height for i in panel_state.inputs),
-                       default=0)) / (total_area * total_area)
+                   min(used_areas, default=0) * max(unused_areas, default=0) /
+                   (total_area * total_area))
     return result
diff --git a/src_py/opcut/util.py b/src_py/opcut/util.py
index 3ceb843..a13cd14 100644
--- a/src_py/opcut/util.py
+++ b/src_py/opcut/util.py
@@ -1,6 +1,44 @@
 import contextlib
 import asyncio
 import sys
+import collections
+
+
+def namedtuple(name, *props):
+    """Create documented namedtuple
+
+    Args:
+        name (Union[str,Tuple[str,str]]):
+            named tuple's name or named tuple's name with documentation
+        props (Iterable[Union[str,Tuple[str,str],Tuple[str,str,Any]]]):
+            named tuple' properties with optional documentation and
+            optional default value
+
+    Returns:
+        class implementing collections.namedtuple
+
+    """
+    props = [(i, None) if isinstance(i, str) else list(i) for i in props]
+    cls = collections.namedtuple(name if isinstance(name, str) else name[0],
+                                 [i[0] for i in props])
+    default_values = []
+    for i in props:
+        if default_values and len(i) < 3:
+            raise Exception("property with default value not at end")
+        if len(i) > 2:
+            default_values.append(i[2])
+    if default_values:
+        cls.__new__.__defaults__ = tuple(default_values)
+    if not isinstance(name, str) and name[1]:
+        cls.__doc__ = name[1]
+    for i in props:
+        if i[1]:
+            getattr(cls, i[0]).__doc__ = i[1]
+    try:
+        cls.__module__ = sys._getframe(1).f_globals.get('__name__', '__main__')
+    except (AttributeError, ValueError):
+        pass
+    return cls
 
 
 def run_until_complete_without_interrupt(future):
@@ -14,7 +52,7 @@ def run_until_complete_without_interrupt(future):
 
     KeyboardInterrupt is suppressed (while event loop is running) and is mapped
     to single cancelation of running task. If multipple KeyboardInterrupts
-    occur, task is canceled only once.
+    occur, task is cancelled only once.
 
     """
     async def ping_loop():