blob: cb5c9008c7c76c5a6200fc98a3fe04f05f6a5536 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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);
}
}
|
