1 files changed, 92 insertions, 0 deletions
diff --git a/Week6 Sliding game solver/src/Node.java b/Week6 Sliding game solver/src/Node.java
new file mode 100644
index 0000000..cb5c900
--- /dev/null
+++ b/Week6 Sliding game solver/src/Node.java
@@ -0,0 +1,92 @@
+import java.util.ArrayList;
+
+/**
+ * For maintaining lists of T-elements enabling
+ * a structure suited for backwards traversal
+ * 
+ * @author Pieter Koopman, Sjaak Smetsers
+ * @author Camil Staps, s4498062
+ * 
+ * @param <T> The element this node is based on
+ */
+@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 final T item;
+    // a reference to the predecessor
+    private final Node<T> previous;
+
+    /* A constructor that initializes each node
+     * with the specified values
+     * @param from the node preceding the current node
+     * @param item the initial data item
+     */
+    public Node (Node<T> from, T item) {
+        this.previous    = from;
+        this.item        = item;
+    }
+
+    /* a getter for the item
+     * @return item
+     */
+    public T getItem() {
+        return item;
+    }
+
+    /*
+     * a getter for the predecessor
+     * @return previous
+     */
+    public Node<T> getPrevious() {
+        return previous;
+    }
+
+    /*
+     * determines the length of the current list
+     * @return the length as an integer
+     */
+    public int length () {
+        int length = 1;
+        Node<T> prev = previous;
+        while ( prev != null ) {
+            prev = prev.previous;
+            length++;
+        }
+        return length;
+    }
+    
+    @Override
+    public String toString() {
+        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);
+    }
+}