2 files changed, 76 insertions, 5 deletions
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/dungeon/actions/tree/ActionTree.java b/src/main/java/kr/syeyoung/dungeonsguide/dungeon/actions/tree/ActionTree.java
index 009924cf..8afb9580 100755
--- a/src/main/java/kr/syeyoung/dungeonsguide/dungeon/actions/tree/ActionTree.java
+++ b/src/main/java/kr/syeyoung/dungeonsguide/dungeon/actions/tree/ActionTree.java
@@ -12,9 +12,9 @@ import java.util.Map;
 import java.util.Set;
 
 @Data
-public class ActionTree {
+public class ActionTree implements Cloneable {
     @EqualsAndHashCode.Exclude
-    private ActionTree parent;
+    private Set<ActionTree> parent;
     private Action current;
     private Set<ActionTree> children;
 
@@ -26,7 +26,7 @@ public class ActionTree {
         ActionRoot root = new ActionRoot();
         root.setPreRequisite(actions);
         ActionTree tree = new ActionTree();
-        tree.setParent(null);
+        tree.setParent(new HashSet<ActionTree>());
         tree.setCurrent(root);
         HashSet<ActionTree> set = new HashSet();
         for (Action action : actions) {
@@ -43,11 +43,17 @@ public class ActionTree {
 
     private static ActionTree buildActionTree(ActionTree parent, Action action, DungeonRoom dungeonRoom, Map<Action, ActionTree> alreadyBuilt) {
         if (action == null) return null;
-        if (alreadyBuilt.containsKey(action)) return alreadyBuilt.get(action);
+        if (alreadyBuilt.containsKey(action))  {
+            ActionTree tree = alreadyBuilt.get(action);
+            tree.getParent().add(parent);
+            return tree;
+        }
 
         ActionTree tree = new ActionTree();
         alreadyBuilt.put(action, tree);
-        tree.setParent(parent);
+        tree.setParent(new HashSet<ActionTree>());
+        if (parent != null)
+            tree.getParent().add(parent);
         tree.setCurrent(action);
         HashSet<ActionTree> set = new HashSet();
         for (Action action2 : action.getPreRequisites(dungeonRoom)) {
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/dungeon/actions/tree/ActionTreeUtil.java b/src/main/java/kr/syeyoung/dungeonsguide/dungeon/actions/tree/ActionTreeUtil.java
new file mode 100644
index 00000000..c55bc149
--- /dev/null
+++ b/src/main/java/kr/syeyoung/dungeonsguide/dungeon/actions/tree/ActionTreeUtil.java
@@ -0,0 +1,65 @@
+package kr.syeyoung.dungeonsguide.dungeon.actions.tree;
+
+import kr.syeyoung.dungeonsguide.dungeon.actions.Action;
+
+import java.util.*;
+
+public class ActionTreeUtil {
+    public static List<Action> linearifyActionTree(ActionTree input) {
+        ActionTree tree = copyActionTree(input);
+
+        List<Action> actions = new ArrayList<Action>();
+
+        int plsHalt = 0;
+        while (tree.getChildren().size() != 0) {
+            plsHalt ++;
+            if (plsHalt > 1000000) throw new IllegalStateException("Linearifying process ran for 1 million cycle");
+            Set<ActionTree> visited = new HashSet<ActionTree>();
+            ActionTree curr = tree;
+
+            int plsHalt2 = 0;
+            while (curr.getChildren().size() != 0) {
+                plsHalt2 ++;
+                if (plsHalt2 > 1000000) throw new IllegalStateException("Finding the leaf of tree ran for 1 million cycles");
+                if (visited.contains(curr)) throw new IllegalStateException("Circular Reference Detected");
+                visited.add(curr);
+                curr = curr.getChildren().iterator().next();
+            }
+
+            plsHalt2 =0;
+            while(curr.getChildren().size() == 0) {
+                plsHalt2 ++;
+                if (plsHalt2 > 1000000) throw new IllegalStateException("Building of array ran for 1 million cycles");
+
+                actions.add(curr.getCurrent());
+                if (curr.getParent().size() == 0) break;
+                for (ActionTree parentTree:curr.getParent())
+                    parentTree.getChildren().remove(curr);
+                curr = curr.getParent().iterator().next();
+            }
+        }
+        return actions;
+    }
+
+    public static ActionTree copyActionTree(ActionTree tree) {
+        Map<ActionTree, ActionTree> built = new HashMap<ActionTree, ActionTree>();
+        if (tree.getParent().size() != 0) throw new IllegalArgumentException("that is not head of tree");
+        return copyActionTree(tree, built);
+    }
+    private static ActionTree copyActionTree(ActionTree tree, Map<ActionTree, ActionTree> preBuilts) {
+        if (preBuilts.containsKey(tree)) return preBuilts.get(tree);
+
+        ActionTree clone = new ActionTree();
+        preBuilts.put(tree, clone);
+
+        clone.setCurrent(tree.getCurrent());
+        clone.setParent(new HashSet<ActionTree>());
+        clone.setChildren(new HashSet<ActionTree>());
+        for (ActionTree tree3 : tree.getChildren()) {
+            ActionTree clone3 = copyActionTree(tree3, preBuilts);
+            clone3.getParent().add(clone);
+            clone.getChildren().add(clone3);
+        }
+        return clone;
+    }
+}