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? — nhouser9
– nhouser9, Commented Feb 3, 2017 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
– user152468, Commented Feb 3, 2017 at 17:34

Chris Gong · Accepted Answer · 2017-02-03 19:27:25Z

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 3, 2017 at 19:27

answered Feb 3, 2017 at 17:37

Chris Gong

8,2574 gold badges36 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Chaz Over a year ago

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'?

Chris Gong Over a year ago

@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.

hya · Accepted Answer · 2017-02-03 17:32:15Z

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 3, 2017 at 17:32

hya

1,7382 gold badges15 silver badges24 bronze badges

1 Comment

user152468 Over a year ago

no, it's already when adding the first element. Just debugged it.

Collectives™ on Stack Overflow

Comparing attribute of an object in implementation of priority queue

2 Answers 2

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related