001 import java.util.*;
002
003 /**
004 * NodeList is designed to hold a number of Nodes and to perform
005 * some operations, specific to the A* algoritm, on them*
006 */
007 public class NodeList{
008
009 /**
010 * No-arg constructor, creates the vector that is used inside NodeList
011 */
012 public NodeList(){
013 vNodeList = new Vector();
014 }
015
016 /**
017 * Adds Node n to the end of the list.
018 */
019 public void add(Node n){
020 vNodeList.add(n);
021 }
022
023 /**
024 * @return Node with index i from the list.
025 */
026 public Node get(int i){
027 return (Node)vNodeList.get(i);
028 }
029
030 /**
031 * @return The last (added) Node from the list
032 */
033 public Node lastElement(){
034 return (Node)vNodeList.lastElement();
035 }
036
037 /**
038 * @param _Node is removed from the list
039 */
040 public void remove(Node _Node){
041 vNodeList.remove(_Node);
042 }
043
044 /**
045 * @return A Node with the specified x and y values
046 */
047 public Node get(int x, int y){
048 Node temp = new Node();
049 int i;
050 for(i = 0; i < vNodeList.size(); i++){
051 temp = (Node)vNodeList.get(i);
052 if(temp.getX() == x && temp.getY() == y ){
053 break;
054 }
055 }
056 return (Node)vNodeList.get(i);
057 }
058
059 /**
060 * @return int with the lenght/size of the list.
061 */
062 public int size(){
063 return vNodeList.size();
064 }
065
066 /**
067 * @return the index in the NodeList of the requested location
068 */
069 public int nodeExist(int x, int y){
070 Node temp = new Node();
071 for(int i = 0; i < vNodeList.size(); i++){
072 temp = (Node)vNodeList.get(i);
073 if(temp.getX() == x && temp.getY() == y ){
074 return i;
075 }
076 }
077 return -1;
078 }
079
080 /**
081 * @return an array with the min/max values van x/y
082 */
083 public int[] worldBoundaries(){
084 int[] values = new int[4];
085 values[0] = 0;
086 values[1] = 0;
087 values[2] = 0;
088 values[3] = 0;
089 Node temp = new Node();
090 for(int i = 0; i < vNodeList.size(); i++){
091 temp = (Node)vNodeList.get(i);
092 if(temp.getX() < values[0]){values[0] = temp.getX();}
093 if(temp.getY() < values[1]){values[1] = temp.getY();}
094 if(temp.getX() > values[0]){values[2] = temp.getX();}
095 if(temp.getY() > values[0]){values[3] = temp.getY();}
096 }
097 return values;
098 }
099
100 /**
101 * Removes all node from the list where the X and Y values are the same.
102 */
103 public void removeEqualPoints(Node n) {
104 Node temp = new Node();
105 for(int i = 0; i < vNodeList.size(); i++){
106 temp = (Node)vNodeList.get(i);
107 if(n.isPointEqual(temp)){
108 vNodeList.removeElementAt(i);
109 }
110 }
111 }
112
113 /**
114 * @return Node with the lowest f(n) value of the Node. The f(n)
115 * value is the value used for A*. f(n) = g(n) + h(n).
116 * The returned Node is deleted (popped) as well.
117 */
118 public Node popNodeWithLowestF(){
119 double dLowest = 1000;
120 int iIndex = 0;
121 Node temp = new Node();
122 for(int i = 0; i < vNodeList.size(); i++){
123 temp = (Node)vNodeList.get(i);
124 if(temp.getF() < dLowest){
125 dLowest = temp.getF();
126 iIndex = i;
127 }
128 }
129 temp = (Node)vNodeList.get(iIndex);
130 vNodeList.removeElementAt(iIndex);
131 return temp;
132 }
133
134 /**
135 * Checks wheter a list is not empty.
136 * @return true if the list is not empty.
137 */
138 public boolean isNotEmpty(){
139 return (!vNodeList.isEmpty());
140 }
141
142 /**
143 * @return true if a location (x and y value the same) was visited before
144 * with a better f(n) value.
145 */
146 public boolean beenThereDoneThat(Node n){
147 Node temp = new Node();
148 for(int i = 0; i < vNodeList.size(); i++){
149 temp = (Node)vNodeList.get(i);
150 if(n.isPointEqual(temp)){
151 if(temp.getF() < n.getF()){
152 return true;
153 }
154 }
155 }
156 return false;
157 }
158
159 /**
160 * @return True if there is a Node with the specified x and y values
161 */
162 public boolean includesPoint(Point p){
163 Node temp = new Node();
164 for(int i = 0; i < vNodeList.size(); i++){
165 temp = (Node)vNodeList.get(i);
166 if(p.x == temp.getX() && p.y == temp.getY()){
167 return true;
168 }
169 }
170 return false;
171 }
172
173 /**
174 * @return string with all the nodes concatenated.
175 */
176 public String toString(){
177 String s = "";
178 for(int i = 0; i < vNodeList.size(); i++){
179 s += "" + vNodeList.get(i).toString() + ", ";
180 }
181 return s;
182 }
183
184 /**
185 * @return The Node that is set as CurrentNode
186 */
187 public Node getCurrentNode(){
188 return (Node)vNodeList.get(iCurrentNodeLocation);
189 }
190
191 /**
192 * @return The orientation that is set as CurrentOrientation (0 - 3)
193 */
194 public int getCurrentOrientation(){
195 return iCurrentOrientation;
196 }
197
198 /**
199 * Sets the current Node with its orientation
200 */
201 public void setCurrentNodeAndOrientation(Node _nCurrent, int _iOrientation){
202 iCurrentOrientation = _iOrientation;
203 iCurrentNodeLocation = nodeExist(_nCurrent.getX(), _nCurrent.getY());
204 }
205
206 private Vector vNodeList;
207 private int iCurrentNodeLocation;
208 private int iCurrentOrientation;
209 }