Search method of Stack class always returning -1

Question

I have this class to hold two values:

public class Coord {

    public int x; 
    public int y;

    public Coord(int x, int y) { 
        this.x = x; 
        this.y = y; 
    }
}

I am trying to use it in a depth-first search algorithm:

x = this.move_to_x;
y = this.move_to_y;

Coord stack = new Coord(0, 0);

Stack<Coord> start = new Stack<Coord>();
Stack<Coord> visited = new Stack<Coord>();

start.push(stack);
visited.push(stack);

while (!start.empty()) {
    Coord tmp = (Coord)start.pop();

    int j,k;

    j = tmp.x;
    k = tmp.y;

    // there is only 8 possible ways to go (the neighbors)
    for (int a = -1; a < 2; a++) {
        tmp.x = j + a;

        for (int b = -1; b < 2; b++) {
            if (a == 0 && b == 0) {
                continue;
            }

            tmp.y = k + b;

            if (tmp.x < 0 || tmp.y < 0) {
                continue;
            }

            if (tmp.x > 5 || tmp.y > 5) {
                continue;
            }

            if (tmp.x == x && tmp.y == y) {
                System.out.println("end!");
                return;
            }

            Coord push = new Coord(tmp.x, tmp.y);

            System.out.println("visited: " + visited);

            if (visited.search(push) == -1) {
                System.out.println("added x " + push.x + " y " + push.y
                        + " " + visited.search(push));

                start.push(push);
                visited.push(push);
            } else {
                System.out.println("visited x " + tmp.x + " y " + tmp.y
                        + " index  " + visited.search(push));
            }
        }
    }
}

The problem is that the visited.search method is always returning -1. Here is the log:

visited: [Agent.ExampleAgent.Coord@1af6a711]
added x 0 y 1 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896]
added x 1 y 0 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896, Agent.ExampleAgent.Coord@5fbd8c6e]
added x 1 y 1 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896, Agent.ExampleAgent.Coord@5fbd8c6e, Agent.ExampleAgent.Coord@427a8ba4]
added x 0 y 0 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896, Agent.ExampleAgent.Coord@5fbd8c6e, Agent.ExampleAgent.Coord@427a8ba4, Agent.ExampleAgent.Coord@262f6be5]
added x 0 y 1 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896, Agent.ExampleAgent.Coord@5fbd8c6e, Agent.ExampleAgent.Coord@427a8ba4, Agent.ExampleAgent.Coord@262f6be5, Agent.ExampleAgent.Coord@199d4a86]

Note that the first element that is added to the visited stack is (0,1), however when it is searched for (0,1), later the method returns -1.

score 1 · Answer 1 · edited Mar 08 '13 at 23:34

1

You need to override the equals() method so it returns true if x and y of the parameter are equal to the object's x and y values.

You should also override the hashCode() method so that it "agrees" with the equals() method.

edited Mar 08 '13 at 23:34

mirzmaster

117
7

answered Mar 08 '13 at 02:49

Bohemian

412,405
93
575
722

I think my implementation of equals is correct, what about hashCode? http://pastebin.com/9WfVcP7b – Frederico Schardong Mar 08 '13 at 03:01
Having hashCode always returning 1 makes search method always return -1. It doesn't look right, – Frederico Schardong Mar 08 '13 at 03:18
@FredericoSchardong does your `Coord` class have the following?@Override public boolean equals(Object other) and @Override public int hashCode() – paulkore Mar 08 '13 at 03:18
@FredericoSchardong You might find [this topic](http://stackoverflow.com/questions/27581/overriding-equals-and-hashcode-in-java) useful. – paulkore Mar 08 '13 at 03:24
@FredericoSchardong Try replacing your implementation of `hashCode()` with this one-liner: `return x*17 + y*31;` – paulkore Mar 08 '13 at 03:43
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/25819/discussion-between-frederico-schardong-and-paul-k) – Frederico Schardong Mar 08 '13 at 03:45

paulkore · Accepted Answer · 2013-03-08T20:21:20.110

(Figured I'd post an answer outlining the progress we made in our chat discussion)

Assuming the following state of the Coord class:

public class Coord {

    public int x; 
    public int y;

    public Coord(int x, int y) { 
        this.x = x; 
        this.y = y; 
    }

    @Override
    public boolean equals(Object obj){

        if (obj == null)
            return false;
        if (obj.getClass() != Coord.class)
            return false;
        if (obj == this)
            return true;

        Coord a = (Coord)obj;
        return (a.x == this.x && a.y == this.y);
    }

    @Override
    public int hashCode() {
        return x*17 + y*31;
    }

    @Override
    public String toString() {
        return "("+x+", "+y+")";
    }
}

... that implements:

equals() as this is what stack search uses, according to its Javadoc
hashCode() as a best practice, accompanying equals()
toString() for clearer diagnostic output

The idea is to test the functionality of stack search in isolation from the rest of the code. If we can prove that stack search functions properly, then the problem is in elsewhere.

Proving that the stack search works can be done using a test class, such as this one:

public class CoordTest {

public static void main(String[] args) {
    System.out.println("Running tests...");

    System.out.println("Testing: equals");
    Coord c1a = new Coord(2,3);
    Coord c1b = new Coord(2,3);
    check(c1a.equals(c1b));

    System.out.println("Testing: not equals"); 
    Coord c2a = new Coord(2,3);
    Coord c2b = new Coord(6,8);
    Coord c2c = new Coord(2,8); 
    Coord c2d = new Coord(6,3);
    check(!c2a.equals(c2b));
    check(!c2a.equals(c2c));
    check(!c2a.equals(c2d));

    System.out.println("Testing: not found in empty stack"); 
    Stack<Coord> stack1 = new Stack<Coord>();
    int result1 = stack1.search(c1a);
    check(result1 == -1);

    System.out.println("Testing: not found in non-empty stack"); 
    Stack<Coord> stack2 = new Stack<Coord>();
    stack2.push(new Coord(4,5));
    stack2.push(new Coord(6,7));
    int result2 = stack2.search(c1a);
    check(result2 == -1);

    System.out.println("Testing: found in non-empty stack"); 
    Stack<Coord> stack3 = new Stack<Coord>();
    stack3.push(new Coord(4,5));
    stack3.push(new Coord(3,1));
    stack3.push(new Coord(6,7));        
    int result3 = stack3.search(new Coord(3,1));
    check(result3 == 2);        

    System.out.println("All tests completed successfully.");
}

private static void check(boolean condition) {
    if (!condition) {
        throw new RuntimeException("Condition failed!");
    }
}

}

Output:

Running tests...
Testing: equals
Testing: not equals
Testing: not found in empty stack
Testing: not found in non-empty stack
Testing: found in non-empty stack
All tests completed successfully.

Search method of Stack class always returning -1

2 Answers2