1 package cz.cuni.amis.pogamut.defcon.utils.quadtree;
2
3 import java.util.Iterator;
4 import java.util.LinkedList;
5 import java.util.NoSuchElementException;
6
7
8
9
10
11
12
13
14 public class QuadTreePostorderIterator implements Iterator<QuadTreeNode> {
15
16 private QuadTree tree;
17 private QuadTreeNode node = null;
18 private boolean finished = false;
19 private QuadTreeNode root = null;
20 private final LinkedList<Integer> branching = new LinkedList<Integer>();
21
22 public QuadTreePostorderIterator(QuadTree tree) {
23 if (tree == null)
24 throw new IllegalArgumentException("Tree cannot be null");
25
26 this.tree = tree;
27 this.setRoot(tree.getRoot());
28
29 }
30
31 @Override
32 public boolean hasNext() {
33
34 if (isFinished())
35 return false;
36
37 if (getNode() == null) {
38 if (getRoot() == null) {
39 return false;
40 } else {
41 return true;
42 }
43 }
44
45 return true;
46 }
47
48 @Override
49 public QuadTreeNode next() {
50
51 if (getNode() == null) {
52 if (isFinished() || getRoot() == null) {
53 throw new NoSuchElementException(
54 "No more elements in iterated QuadTree");
55 } else {
56 setNode(getRoot());
57
58 while (getNode().getNodes() != null) {
59 setNode(getNode().getFirst());
60 getBranching().add(0);
61 }
62
63 if (getNode() == getRoot()) {
64 setFinished(true);
65 }
66
67 return getNode();
68 }
69 }
70
71 if (getNode() == getRoot()) {
72 setFinished(true);
73 return getRoot();
74 } else {
75 setNode(getNode().getParent());
76
77 int next = getBranching().pollLast();
78
79 if (next == 3) {
80
81 if (getNode() == getRoot())
82 setFinished(true);
83
84 return getNode();
85 } else {
86
87 getBranching().add(++next);
88 setNode(getNode().getNodes()[next]);
89
90 while (getNode().getNodes() != null) {
91 setNode(getNode().getFirst());
92 getBranching().add(0);
93 }
94
95 return getNode();
96 }
97 }
98 }
99
100 @Override
101 public void remove() {
102 throw new UnsupportedOperationException(
103 "QuadTreeIterator does not support remove() method.");
104 }
105
106 protected LinkedList<Integer> getBranching() {
107 return branching;
108 }
109
110 protected void setNode(QuadTreeNode node) {
111 this.node = node;
112 }
113
114 protected QuadTreeNode getNode() {
115 return node;
116 }
117
118 protected void setRoot(QuadTreeNode root) {
119 this.root = root;
120 }
121
122 protected QuadTreeNode getRoot() {
123 return root;
124 }
125
126 protected void setFinished(boolean finished) {
127 this.finished = finished;
128 }
129
130 protected boolean isFinished() {
131 return finished;
132 }
133
134 }