|
308
|
1 package jp.ac.u_ryukyu.ie.cr.jungle.traverser;
|
|
|
2
|
|
|
3 import jp.ac.u_ryukyu.ie.cr.jungle.core.Children;
|
|
|
4 import jp.ac.u_ryukyu.ie.cr.jungle.data.list.List;
|
|
|
5 import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode;
|
|
|
6 import jp.ac.u_ryukyu.ie.cr.jungle.util.DefaultEither;
|
|
|
7 import jp.ac.u_ryukyu.ie.cr.jungle.util.Either;
|
|
|
8 import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error;
|
|
|
9
|
|
|
10 import java.util.Iterator;
|
|
|
11
|
|
|
12 public class RedBlackTreeTraverser implements Traverser {
|
|
|
13 @Override
|
|
|
14 public Either<Error, Traversal> traverse(final TreeNode root, Evaluator evaluator) {
|
|
|
15 Either<Error, List<Direction<TreeNode>>> ret = _traverse(root, evaluator, -1);
|
|
|
16
|
|
|
17 if (ret.isA()) {
|
|
|
18 return DefaultEither.newA(ret.a());
|
|
|
19 }
|
|
|
20
|
|
|
21 List<Direction<TreeNode>> list = ret.b();
|
|
|
22
|
|
|
23 final Iterable<Direction<TreeNode>> iterable = list;
|
|
|
24 final TreeNode destination = ret.b().head().getTarget();
|
|
|
25
|
|
|
26 Traversal traversal = new Traversal() {
|
|
|
27 @Override
|
|
|
28 public Iterator<Direction<TreeNode>> iterator() {
|
|
|
29 return iterable.iterator();
|
|
|
30 }
|
|
|
31
|
|
|
32 @Override
|
|
|
33 public TreeNode destination() {
|
|
|
34 return destination;
|
|
|
35 }
|
|
|
36 };
|
|
|
37
|
|
|
38 return DefaultEither.newB(traversal);
|
|
|
39 }
|
|
|
40
|
|
|
41 private Either<Error, List<Direction<TreeNode>>> _traverse(TreeNode currentNode, Evaluator _evaluator, int pos) {
|
|
|
42 Evaluation e = _evaluator.evaluate(currentNode, pos);
|
|
|
43 Result r = e.result();
|
|
|
44 if (r == Result.LEFT) {
|
|
|
45 return left(currentNode, pos, e.evaluator());
|
|
|
46 }
|
|
|
47
|
|
|
48 if (r == Result.RIGHT) {
|
|
|
49 return right(currentNode, pos, e.evaluator());
|
|
|
50 }
|
|
|
51
|
|
|
52 if (r == Result.GOAL) {
|
|
|
53 return DefaultEither.newB(_goal(currentNode, pos));
|
|
|
54 }
|
|
|
55
|
|
|
56
|
|
|
57 return DefaultEither.newA(TraverserError.UNDEFINED_OPERATOR);
|
|
|
58 }
|
|
|
59
|
|
|
60 private List<Direction<TreeNode>> _goal(final TreeNode _current, final int _pos) {
|
|
|
61 Direction<TreeNode> d = new Direction<TreeNode>() {
|
|
|
62 @Override
|
|
|
63 public int getPosition() {
|
|
|
64 return _pos;
|
|
|
65 }
|
|
|
66
|
|
|
67 @Override
|
|
|
68 public TreeNode getTarget() {
|
|
|
69 return _current;
|
|
|
70 }
|
|
|
71 };
|
|
|
72
|
|
|
73 List<Direction<TreeNode>> list = new List();
|
|
|
74 List<Direction<TreeNode>> newList = list.addLast(d);
|
|
|
75
|
|
|
76 return newList;
|
|
|
77 }
|
|
|
78
|
|
|
79 private <T extends TreeNode> Either<Error, List<Direction<TreeNode>>> left(final T _current, final int _pos, Evaluator _evaluator) {
|
|
|
80 Children children = _current.getChildren();
|
|
|
81 TreeNode child = children.at(0).b();
|
|
|
82 Either<Error, List<Direction<TreeNode>>> either = _traverse(child, _evaluator, 0);
|
|
|
83 if (either.isA()) {
|
|
|
84 return either;
|
|
|
85 }
|
|
|
86
|
|
|
87 List<Direction<TreeNode>> list = either.b();
|
|
|
88 Direction<TreeNode> d = new Direction<TreeNode>() {
|
|
|
89 @Override
|
|
|
90 public int getPosition() {
|
|
|
91 return _pos;
|
|
|
92 }
|
|
|
93
|
|
|
94 @Override
|
|
|
95 public T getTarget() {
|
|
|
96 return _current;
|
|
|
97 }
|
|
|
98 };
|
|
|
99
|
|
|
100 List<Direction<TreeNode>> newList = list.addLast(d);
|
|
|
101 return DefaultEither.newB(newList);
|
|
|
102 }
|
|
|
103
|
|
|
104 private <T extends TreeNode> Either<Error, List<Direction<TreeNode>>> right(final T _current, final int _pos, Evaluator _evaluator) {
|
|
|
105 Children children = _current.getChildren();
|
|
|
106 TreeNode child = children.at(1).b();
|
|
|
107 Either<Error, List<Direction<TreeNode>>> either = _traverse(_current, _evaluator, 1);
|
|
|
108 if (either.isA()) {
|
|
|
109 return either;
|
|
|
110 }
|
|
|
111
|
|
|
112 List<Direction<TreeNode>> list = either.b();
|
|
|
113 Direction<TreeNode> d = new Direction<TreeNode>() {
|
|
|
114 @Override
|
|
|
115 public int getPosition() {
|
|
|
116 return _pos;
|
|
|
117 }
|
|
|
118
|
|
|
119 @Override
|
|
|
120 public T getTarget() {
|
|
|
121 return _current;
|
|
|
122 }
|
|
|
123 };
|
|
|
124
|
|
|
125 List<Direction<TreeNode>> newList = list.addLast(d);
|
|
|
126 return DefaultEither.newB(newList);
|
|
|
127 }
|
|
|
128 }
|
