From 3f702ed231134d224ee5fd5525f627a8058909a1 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Fri, 13 Mar 2015 19:34:04 +0100
Subject: Solutions w6

---
 Week6/src/Node.java | 46 ++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 40 insertions(+), 6 deletions(-)

(limited to 'Week6/src/Node.java')

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);
     }
 }
-- 
cgit v1.2.3