Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 7 of 7

Thread: Priority Queue in Java which keeps track of each node's position

  1. #1
    Junior Member
    Join Date
    Aug 2011
    Posts
    6
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Angry Priority Queue in Java which keeps track of each node's position

    so I'm working on a lab for my class. I need to create a Priority Queue in Java using an array list. The kicker is that each node has to have a "handle" which is just an object which contains the index of of the node that it's associated with. I know that sounds weird but we have to implement it this way. Anyway, my priority queue seem to work fine except the handle values apparently aren't updating correctly because I fail the handle test. Also, I run into problems with handles only after extractMin() is called, so I figured the problem would be somewhere in that method but I've been through it a million times and it looks good to me.

    Here is my Priority Queue Class:

    package lab3;
     
    import java.util.ArrayList;
     
    /**
     * A priority queue class supporting operations needed for
     * Dijkstra's algorithm.
     */
     
    class PriorityQueue<T> {
     
    final static int INF = 1000000000;
    ArrayList<PQNode<T>> queue;
     
    /**
     * Constructor
     */
    public PriorityQueue() {
        queue = new ArrayList<PQNode<T>>();
    }
     
    /**
     * @return true iff the queue is empty.
     */
    public boolean isEmpty() {
        if (queue.size() <= 0)
            return true;
        return false;
    }
     
    /**
     * Insert a (key, value) pair into the queue.
     *
     * @return a Handle to this pair so that we can find it later.
     */
    Handle insert(int key, T value) {
        queue.add(new PQNode(key, value));    
     
        int loc = queue.size()-1;
        // Swap with parent until parent not larger
        while (loc > 0 && queue.get(loc).getKey() < queue.get(parent(loc)).getKey()) {
            swap(loc, parent(loc));
            loc = parent(loc);
        }
        return new Handle(loc);
    }
     
    private void swap(int i, int j) {
        PQNode t = queue.get(i);
     
        queue.set(i, queue.get(j));
        queue.get(i).setHandleIndex(i);
     
        queue.set(j, t);
        queue.get(j).setHandleIndex(j);
    }
     
     
    /**
     * @return the min key in the queue.
     */
    public int min() {
        if (isEmpty())
            return -INF;
        return queue.get(0).getKey();
    }
     
    /**
     * Find and remove the smallest (key, value) pair in the queue.
     *
     * @return the value associated with the smallest key
     */
     
    public T extractMin() {
        if (isEmpty())
            return null;
        else{
            T value = queue.get(0).getValue();
            swap(0, queue.size()-1);
            queue.get(queue.size()-1).setHandleIndex(-1);
            queue.remove(queue.size()-1);
            heapify(0);
            return value;
        }
    }
     
     
    private void heapify(int i) {
        int left = leftChild(i);
        int right = rightChild(i);
        int min;
     
        if (left <= queue.size()-1 && queue.get(left).getKey() < queue.get(i).getKey())
            min = left;
        else
            min = i;
        if (right <= queue.size()-1 && queue.get(right).getKey() < queue.get(min).getKey())
            min = right;
        if (min != i){
            swap(i, min);
            heapify(min);
        }
    }
    private static int parent(int i) {
        return (i-1)/2;
    }
     
    private static int leftChild(int i) {
        return 2*i + 1;
    }

    And my PQNode Class:
    package lab3;
     
    public class PQNode<T> {
     
    int key;
    T value;
    Handle handle;
     
    PQNode(int k, T v){
        key = k;
        value = v;
        handle = new Handle(0);
    }
     
    /**
     * @return the key
     */
    public int getKey() {
        return key;
    }
     
    /**
     * @param key the key to set
     */
    public void setKey(int key) {
        this.key = key;
    }
     
    /**
     * @return the value
     */
    public T getValue() {
        return value;
    }
     
    /**
     * @param value the value to set
     */
    public void setValue(T value) {
        this.value = value;
    }
     
    public void setHandle(Handle handle){
        this.handle = handle;
    }
     
    /**
     * @return the handle
     */
    public Handle getHandle() {
        return handle;
    }
    public int getHandleIndex(){
        return handle.getIndex();
    }
    public void setHandleIndex(int i){
        handle.setIndex(i);
    }
    }

    And my Handle Class:

    package lab3;
     
    public class Handle {
     
    int index;
     
     
    public Handle(int i) {
        index = i;
    }
     
    /**
     * @return the index
     */
    public int getIndex() {
        return index;
    }
     
    /**
     * @param index the index to set
     */
    public void setIndex(int index) {
        this.index = index;
    }
    }

    I can post the tests too if you'd like but I don't know if that would do much good. Just know that the queue works as is should, but the handles don't point to the right nodes after extractMin() is utilized. Please tell me if you'd like more information, I know this is all a little vague. Thanks so much guys.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,199
    Thanks
    49
    Thanked 2,174 Times in 2,147 Posts

    Default Re: Priority Queue in Java which keeps track of each node's position

    Can you post some print outs that shows what is wrong and add some comments to it saying what it should be?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Aug 2011
    Posts
    6
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Priority Queue in Java which keeps track of each node's position

    Sure, here is the test that I'm failing:

      @Test
        public void basicHandleAndDecreaseTest() {
            PriorityQueue<String> q = new PriorityQueue<String>();
            Map<String, Handle> valuesToHandles = new HashMap<String, Handle>();
            Map<String, Integer> valuesToKeys = new HashMap<String, Integer>();
            int seq = 0;
            // Generate random numbres for the keys.
            for (int i = 0; i < 20; i++) {
                int key = RAND.nextInt(100);
                String val = Integer.toString(seq); // guarantees that the value is unique.
                seq++;
                valuesToKeys.put(val, key);
            }
            // Keep track of handles and build queue.
            for (Map.Entry<String, Integer> entry : valuesToKeys.entrySet()) {
                int key = entry.getValue();
                String value = entry.getKey();
                Handle h = q.insert(key, value);
                assertEquals(key, q.handleGetKey(h));
                assertEquals(value, q.handleGetValue(h));
     
                valuesToHandles.put(value, h);
            }
     
            // Remove some of the elements.
            for (int i = 0; i < 5; i++) {
                String val = q.extractMin();
                valuesToKeys.remove(val);
                valuesToHandles.remove(val);
            }
            // Make sure the handles are still valid.
            for (Map.Entry<String, Integer> entry : valuesToKeys.entrySet()) {
                int key = entry.getValue();
                String value = entry.getKey();
                Handle h = valuesToHandles.get(value);
    	    assertEquals(value, q.handleGetValue(h)); <-- I fail here everytime
     
            }
     
            // Add some more elements.
            int limit = seq + 5;
            for (int i = seq; i < limit; i++) {
                int key = RAND.nextInt(100);
                String val = Integer.toString(seq);
                seq++;
                valuesToKeys.put(val, key);
                Handle h = q.insert(key, val);
                valuesToHandles.put(val, h);
            }
     
            // Decrease keys unnecessarily and verify that they still work.
            for (Map.Entry<String, Integer> entry : valuesToKeys.entrySet()) {
                int key = entry.getValue();
                String value = entry.getKey();
                Handle h = valuesToHandles.get(value);
                q.decreaseKey(h, key + 1);
                assertEquals(key, q.handleGetKey(h));
                assertEquals(value, q.handleGetValue(h));
            }
     
            // Change keys randomly, and check that the values remain attached to handles.
            for (Map.Entry<String, Integer> entry : valuesToKeys.entrySet()) {
                int key = entry.getValue();
                String value = entry.getKey();
                Handle h = valuesToHandles.get(value);
                int newKey = RAND.nextInt(100);
                q.decreaseKey(h, newKey);
                if (newKey < key) {
                    assertEquals(newKey, q.handleGetKey(h));
                } else {
                    assertEquals(key, q.handleGetKey(h));
                }
                assertEquals(value, q.handleGetValue(h));
            }
        }

    Failure output:
    org.junit.ComparisonFailure: expected:<1[9]> but was:<1[7]>
    at org.junit.Assert.assertEquals(Assert.java:115)
    at org.junit.Assert.assertEquals(Assert.java:144)
    at lab3.TestLab3.basicHandleAndDecreaseTest(TestLab3. java:98)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Nativ e Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(Unknow n Source)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Un known Source)
    at java.lang.reflect.Method.invoke(Unknown Source)
    at org.junit.runners.model.FrameworkMethod$1.runRefle ctiveCall(FrameworkMethod.java:47)
    at org.junit.internal.runners.model.ReflectiveCallabl e.run(ReflectiveCallable.java:12)
    at org.junit.runners.model.FrameworkMethod.invokeExpl osively(FrameworkMethod.java:44)
    at org.junit.internal.runners.statements.InvokeMethod .evaluate(InvokeMethod.java:17)
    at org.junit.runners.ParentRunner.runLeaf(ParentRunne r.java:271)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild( BlockJUnit4ClassRunner.java:70)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild( BlockJUnit4ClassRunner.java:50)
    at org.junit.runners.ParentRunner$3.run(ParentRunner. java:238)
    at org.junit.runners.ParentRunner$1.schedule(ParentRu nner.java:63)
    at org.junit.runners.ParentRunner.runChildren(ParentR unner.java:236)
    at org.junit.runners.ParentRunner.access$000(ParentRu nner.java:53)
    at org.junit.runners.ParentRunner$2.evaluate(ParentRu nner.java:229)
    at org.junit.runners.ParentRunner.run(ParentRunner.ja va:309)
    at org.eclipse.jdt.internal.junit4.runner.JUnit4TestR eference.run(JUnit4TestReference.java:50)
    at org.eclipse.jdt.internal.junit.runner.TestExecutio n.run(TestExecution.java:38)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRu nner.runTests(RemoteTestRunner.java:467)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRu nner.runTests(RemoteTestRunner.java:683)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRu nner.run(RemoteTestRunner.java:390)
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRu nner.main(RemoteTestRunner.java:197)

    I've marked for you the part i'm failing, thanks for your help so far. Really need to figure this out and I appreciate you helping me.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,199
    Thanks
    49
    Thanked 2,174 Times in 2,147 Posts

    Default Re: Priority Queue in Java which keeps track of each node's position

    How do you execute the code for testing? I don't see a main() method.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Member
    Join Date
    Feb 2014
    Posts
    180
    Thanks
    0
    Thanked 48 Times in 45 Posts

    Default Re: Priority Queue in Java which keeps track of each node's position

    (Just a quick one...) Norm, the code posted in post #3 is a JUnit unit test.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,199
    Thanks
    49
    Thanked 2,174 Times in 2,147 Posts

    Default Re: Priority Queue in Java which keeps track of each node's position

    Thanks. I've never used JUnit
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Member
    Join Date
    Feb 2014
    Posts
    180
    Thanks
    0
    Thanked 48 Times in 45 Posts

    Default Re: Priority Queue in Java which keeps track of each node's position

    MiniatureBeast, as you're using Eclipse, I'd suggest you use the built-in debugger to diagnose the problem.

    Since you suspect the error is a side-effect of calling extractMin(), you can place a breakpoint at "public T extractMin() {", run your unit test again, and then step through your code when its execution hits the breakpoint. Remember to check the value of the variables as you step through to confirm they are what you expect them to be.

Similar Threads

  1. Priority Queue Linked List Help
    By Freezer Boy in forum Collections and Generics
    Replies: 9
    Last Post: November 24th, 2013, 08:30 AM
  2. Priority Queue help
    By BuhRock in forum What's Wrong With My Code?
    Replies: 7
    Last Post: November 3rd, 2011, 06:37 PM
  3. generate priority queue from hashmap help
    By Scotty33 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: May 23rd, 2011, 09:32 PM
  4. Implementing a priority queue using a max heap
    By jsinclair1482 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: April 15th, 2011, 11:56 AM
  5. Priority Queue using comparable
    By jkalm in forum Collections and Generics
    Replies: 6
    Last Post: December 5th, 2010, 09:02 PM

Tags for this Thread