Comparing attribute of an object in implementation of priority queue

Question

I've attempted to implement a priority queue using an Array of Objects "Queue Items" which have some data (a string), and an integer which is the priority. I am trying to make those items comparable so that when I add a new object to the queue I can iterate through the items and add the new item in the correct location and move all items that are now behind it backwards, however when I add a new item to the queue I get a null pointer exception. I'll include all my code, but the toString method was just copied in from a queue so it won't work as expected.

class QueueItem implements Comparable<QueueItem> {
    String data;
    int pri;

    public QueueItem(String data, int pri) {
        this.data = data;
        this.pri = pri;
    }

    @Override
    public int compareTo(QueueItem item) {
        return this.data.compareTo(item.data);
    }
}

public class PriorityQueue implements Queue<String> {
    private QueueItem[] arr;
    private int frontPos, backPos;

    public PriorityQueue() {
        arr = new QueueItem[20];
        backPos = -1;
        frontPos = 0;
    }

    public boolean isEmpty() {
        return frontPos == (backPos + 1) % arr.length;
    }

    public String front() {
        if (frontPos == (backPos + 1) % arr.length)
            throw new QueueException("Empty Queue - front");
        return arr[frontPos].data;
    }

    public int frontPri() {
        if (frontPos == (backPos + 1) % arr.length)
            throw new QueueException("Empty Queue - frontPri");
        return arr[frontPos].pri;
    }

    public void addToPQ(String str, int x) {
        if (arr.length==0) {
            arr[frontPos] = new QueueItem(str, x);
            frontPos++;
            return;
        }
        else {
            for (int i = 0; i < arr.length; i++) {
                arr[i].compareTo(new QueueItem(str, x));
            }
        }
    }

    public void deleteFront() {
        if (frontPos==(backPos+1)%arr.length) {
            throw new QueueException("Empty Queue - deleteFront");
        }
        frontPos = (frontPos+1)%arr.length;
    }

    public String toString() {
        if (frontPos == (backPos + 1) % arr.length) {
            return "<>";
        }
        StringBuffer sb = new StringBuffer();

        sb.append('<');

        int pos = frontPos;
        while (pos != backPos) {
            sb.append(arr[pos]);
            sb.append(',');
            pos = (pos + 1) % arr.length;
        }

        sb.append(arr[backPos]);
        sb.append('>');

        return (sb.toString());
    }
}

public interface Queue<String> {
    public void addToPQ(String str, int x);

    public void deleteFront();

    public String front();

    public boolean isEmpty();

    public int frontPri();
}

class QueueException extends RuntimeException {
    QueueException(String s) {
        super("Tried to apply " + s + " to empty queue");
    }
}

public class pqTest {
    public static void main(String[] args) {
        PriorityQueue pQ = new PriorityQueue();
        if (pQ.isEmpty()) {
            System.out.println("Queue is Empty - isEmpty");
        }
        pQ.addToPQ("Dog", 4);
        pQ.addToPQ("Cat", 20);
        pQ.deleteFront();
        pQ.addToPQ("Fish", 2);
    }
}

Possible duplicate of [What is a NullPointerException, and how do I fix it?](http://stackoverflow.com/questions/218384/what-is-a-nullpointerexception-and-how-do-i-fix-it) — nhouser9, Feb 03 '17 at 17:23
you are using `arr.length == 0` to determine if your queue is empty. Yet your queue is initialized with size 20. Use a debugger to find the nullpointer exception. — user152468, Feb 03 '17 at 17:34

Chris Gong · Answer 1 · 2017-02-03T19:27:25.403

1

The problem is that arr is size 20 so the first element won't even be added through the if statement in your addToPQ method because arr.length != 0. So it will then go to your else statement, which iterates through every single element in arr. But arr has 20 null elements since each spot within the array of QueueItems has not been initialized. So you should change your condition in the if statement to frontPos == 0 and change the terminating condition in your loop to i < frontPos so that the method won't iterate through null elements within arr

public void addToPQ(String str, int x) {
        if (frontPos==0) {
            arr[frontPos] = new QueueItem(str, x);
            frontPos++;
            return;
        }
        else {
            QueueItem item = new QueueItem(str, x);
            for (int i = 0; i < frontPos; i++) {
                arr[i].compareTo(item);
            }
        }
    }

edited Feb 03 '17 at 19:27

answered Feb 03 '17 at 17:37

Chris Gong

8,031
4
30
51

That now works for handling the first item, now when I add a second item to the queue I get an OutOfMemoryError and it says cannot find local variable 'str'? – Chaz Feb 03 '17 at 18:38
@Chaz check my edit. I believe it was because u had `arr[i].compareTo(new QueueItem(str, x))` which is really inefficient because you're unnecessarily creating the same object multiple times. So what I did was make the new item once outside of the loop so that the loop can run efficiently when comparing to the new item. – Chris Gong Feb 03 '17 at 19:28

score 0 · Answer 2 · answered Feb 03 '17 at 17:32

0

You get NullPointerException, because when you are adding second item, you go to else statment where you iterate over array with one non-null element and 19 nulls. So you need to change your code to check if array element at i is null and if it is, assign new element to it.

answered Feb 03 '17 at 17:32

hya

1,708
2
15
22

no, it's already when adding the first element. Just debugged it. – user152468 Feb 03 '17 at 17:33

Comparing attribute of an object in implementation of priority queue

2 Answers2