diff options
Diffstat (limited to 'Week6/src/Node.java')
-rw-r--r-- | Week6/src/Node.java | 46 |
1 files changed, 40 insertions, 6 deletions
diff --git a/Week6/src/Node.java b/Week6/src/Node.java index 2a33cc4..cb5c900 100644 --- a/Week6/src/Node.java +++ b/Week6/src/Node.java @@ -1,16 +1,21 @@ +import java.util.ArrayList;
+
/**
* For maintaining lists of T-elements enabling
* a structure suited for backwards traversal
+ *
* @author Pieter Koopman, Sjaak Smetsers
- * @version 1.2
- * @date 28-02-2015
+ * @author Camil Staps, s4498062
+ *
+ * @param <T> The element this node is based on
*/
-public class Node<T>
+@SuppressWarnings("Convert2Diamond") // We disable these warnings for Java <=1.7 compatibility.
+public class Node<T extends Comparable> implements Comparable<Node<T>>
{
// the data field
- private T item;
+ private final T item;
// a reference to the predecessor
- private Node<T> previous;
+ private final Node<T> previous;
/* A constructor that initializes each node
* with the specified values
@@ -53,6 +58,35 @@ public class Node<T> @Override
public String toString() {
- throw new UnsupportedOperationException("toString : not supported yet.");
+ StringBuilder result = new StringBuilder();
+
+ ArrayList<Node<T>> path;
+ path = new ArrayList<Node<T>>();
+ Node<T> prev = this;
+ while ( prev != null ) {
+ path.add(prev);
+ prev = prev.previous;
+ }
+
+ for (int i = path.size() - 1; i >= 0; i--)
+ result.append(path.size() - i - 1).append(":\n").append(path.get(i).getItem().toString());
+
+ return result.toString();
+ }
+
+ /**
+ * Just comparing the items isn't very clever. The Manhattan distance is a fairly small number.
+ * With large queues, many nodes will then have the same priority. It's much better to select
+ * on both Manhattan distance and path length. That way, we will find shorter paths.
+ * Note though that since we're prioritizing on Manhattan distance primarily, this does not
+ * mean that we necessarily find the shortest path.
+ * @param t
+ * @return
+ */
+ @Override
+ public int compareTo(Node<T> t) {
+ if (this.item.compareTo(t.item) == 0)
+ return Integer.compare(length(), t.length());
+ return this.item.compareTo(t.item);
}
}
|