checking if array is empty without getting NullPointerException

Question

I'm getting a NullPointerException error when I check if an array is empty. It should return null when the array is empty, but I cannot find why it's not working. Any hints on what I am doing wrong? Here's my entire code:

import java.lang.reflect.Array;

public class EventPriorityQueue {

    class Node {
        Event event;
        int priority;

        Node(Event event, int priority) {
            this.event = event;
            this.priority = priority;
        }
    }

    private int size;
    private Node[] array;

    public EventPriorityQueue() {
        this.size = 0;
        array = new Node[20];
    }

    public int size() {
        return size;
    }

    public void insert(Event event, int priority) {
        if (size == 0) {
            array[0] = new Node(event, priority);
            size++;
            return;
        }
        if (size == array.length) {
            Node[] array2 = new Node[size*2];
            System.arraycopy(array, 0, array2, 0, array.length);
            array = array2;
        }
        if (size > 0) {
            array[size] = new Node(event, priority);
            size++;
            percolateUp(size - 1);
        }
    }

    private void percolateUp(int index){
        int parentIndex = (index - 1) / 2;
        while (array[index].priority < array[parentIndex].priority) {
            Node temp = array[parentIndex];
            array[parentIndex] = array[index];
            array[index] = temp;
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    public Event peek() {
        return array[0].event;
    }

    public Event poll() {
        if (array[0] == null) {
            return null;
        }
        Node deletedElement = array[0];
        array[0] = array[size - 1];
        array[size - 1] = null;
        size--;
        percolateDown(0);
        return deletedElement.event;
    }

    private void percolateDown(int index) {
        int smallest = index;
        int rightChildIndex = (index * 2) + 2;
        int leftChildIndex = (index * 2) + 1;
        if (array[leftChildIndex] != null) {
            if (array[leftChildIndex].priority < array[smallest].priority) {
                smallest = leftChildIndex;
            }
        }
        if (array[rightChildIndex] != null) {
            if (array[rightChildIndex].priority < array[smallest].priority) {
                smallest = rightChildIndex;
            }
        }
        if (smallest != index) {
            Node temp = array[index];
            array[index] = array[smallest];
            array[smallest] = temp;
            index = smallest;
            percolateDown(smallest);
        }

    }

    public int[] toPrioritiesArray() {
        // DO NOT CHANGE THIS FUNCTION
        int[] result = new int[this.size];
        for (int i = 0; i < this.size; i++) {
            result[i] = this.array[i].priority;
        }
        return result;
    }

    public static boolean checkHeapProperty(int[] priorities) {
        for (int i = 0; i < priorities.length; i++) {
            if (2 * i + 1 < priorities.length && priorities[i] > priorities[2 * i + 1]) {
                return false;
            }
            if (2 * i + 2 < priorities.length && priorities[i] > priorities[2 * i + 2]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // initialize the queue
        EventPriorityQueue queue = new EventPriorityQueue();
        // add some numbers to the queue
        int NUM_EVENTS = 1;
        for (int i = NUM_EVENTS; i > 0; i--) {
            queue.insert(new Event(i), i);
            System.out.println("inserted " + i);
        }

        // poll everything
        for (int i = 1; i <= NUM_EVENTS + 1; i++) {
            int next = queue.poll().getTime();
            System.out.println("polled " + next);
        }

    }
}

I think my error is here:

public Event poll() {
    if (array[0] == null) {
        return null;
    }

Any hints/helps would be appreciated!!

That program logic is strange. You want to return `null` in `poll()` when an item in the array is null, ok, but way doesn't the method calling `poll()` bother to check if the returned value is `null` or not. It makes no sense to play with null when your code isn't able to deal with it correctly. — Tom, Nov 03 '19 at 06:08
Possible duplicate of [How can I check whether an array is null / empty?](https://stackoverflow.com/questions/2369967/how-can-i-check-whether-an-array-is-null-empty) — dSanders, Nov 03 '19 at 06:14
"Event poll() - returns and removes the next Event in the priority queue. Returns null if the queue is empty." This is a brief description of how `poll()` should work. Does my approach seem right? — devil0108, Nov 03 '19 at 06:22
Your `poll()` isn't the issue here. Something else in your code doesn't bother to check if the returned value is `null`, that's why you get the NullPointerException. — Tom, Nov 03 '19 at 06:25
Possible duplicate of [What is a NullPointerException, and how do I fix it?](https://stackoverflow.com/questions/218384/what-is-a-nullpointerexception-and-how-do-i-fix-it) — Johannes Kuhn, Nov 03 '19 at 06:32
`int next = queue.poll().getTime();`. Really? `queue.poll()` can return `null`. You don't check for that. So it throws a NullPointerException. Happens, as expected. You could have saved the time of a lot of people if you had posted the actual stack trace. — Johannes Kuhn, Nov 03 '19 at 06:33

Aaron Akhtar · Answer 1 · 2019-11-03T06:17:11.680

0

I did not understand the question too much, however I think I see the issue, try this -

public Event poll() {
    if (array.length == 0) {
        return null;
    }

Hope this helps!

edited Nov 03 '19 at 06:17

answered Nov 03 '19 at 06:10

Aaron Akhtar

36
7

@Tom oh my gosh, I did not read the question correctly ;( I will edit it now, sorry. – Aaron Akhtar Nov 03 '19 at 06:16
1

Ok, since that is fixed, to the actual issue from OP, the NPE. How does your code fix that? – Tom Nov 03 '19 at 06:23

Mohit Bansal · Answer 2 · 2019-11-03T07:01:43.040

0

for (int i = 1; i <= NUM_EVENTS + 1; i++) {
            int next = queue.poll().getTime();
            System.out.println("polled " + next);
        }

This loop is running twice. Please try removing + 1 . Then there will be no NullPointerException.

queue.poll() is null in 2nd iteration. So when you do getTime() on null. It throws NullPointerException.

edited Nov 03 '19 at 07:01

answered Nov 03 '19 at 06:25

Mohit Bansal

348
3
8

I purposely added the `+ 1` to check if the code would properly return null when `poll()` is called on an empty array. – devil0108 Nov 03 '19 at 07:38
In that case you should check for if(queue.poll()!=null) and then do queue.poll().getTime(); – Mohit Bansal Nov 03 '19 at 07:41
array[0] == null gives you true because array is holding a null object. – Mohit Bansal Nov 03 '19 at 07:43

checking if array is empty without getting NullPointerException

2 Answers2