CODEWITHSUNDEEP
javaarrays
Damis Berzovitis
Damis Berzovitis

Reputation: 215

How to check if an array is filled enough in java?

I want to check if an array is at 75% filled with objects and if it's true i have to resize it. In the variable size i have my objects (!=null) and i have an array of integers ints

public class PQ {

private int[] pq;
private int size;

public PQ(int capacity) {
    if (capacity < 1) {
        throw new IllegalArgumentException();
    }
    this.pq = new int[capacity + 1];
    this.size = 0;
}

public void insert(int number) {
           //Code
}


private int[] resize() {
    int[] newPQ = new int[this.pq.length * 2];
    for (int i = 0; i < this.pq.length; i++) {
        newPQ[i] = this.pq[i];
    }
    return newPQ;
}
}

Upvotes: 2

Views: 4367

Answers (4)

Bahramdun Adil
Bahramdun Adil

Reputation: 6079

Use ArrayList do everything automatically for you in more efficient way.

Edited:

it is the initialization, all put -1

this.pq = new int[capacity + 1];
Arrays.fill(pq, -1);

then when you check you do like this:

if(pq[pq.length*.75] != -1) {
    // then is means that is has already filled up 75%
} else {
   // not filled 75% yet
}

Upvotes: -1

JosephG
JosephG

Reputation: 3253

Try this:

Whenever you add an element, we increment size (this will track the number of non-empty spaces so that you don't need to continually recount your array). Then we compare this number to the total length of your array. If count is at least 75% of the size of the array, we call your resize method and set pq to the new array it returns. I assume that you wish to add to the end of the array, and that you don't want empty indexs between numbers. If you want gaps you will need to use a loop which I am trying to avoid for efficiency's sake, if it isn't necessary. Assuming you don't, you can just add to your array at index size since this will be the first non-empty element.

//O(1) efficiency if you don't need to resize, O(n) if you do

public void insert(int number) {
       if(size / pq.length >= 75) {
           pq = resize();
       }
       pq[size] = number; //Since this will be the first non-empty index
       size++;
       return; //Doing it this way, if you can, is much more efficient than looping
}

If you call remove and take out from anything but the end you are going to have to shift everything down so that you don't have empty space.

If you are going to have empty indexes, try something like this (to insert at the first empty index encountered by the loop)...Let's use an Integer[] instead so that you can check for null and don't have to worry about any 0's in the array being counted as empty (int[] initiates everything to 0). That way we can check for empty space and 0's are not counted as empty space in case you use any in your int[].

    //O(n) efficiency if you don't need to resize, O(n^2) if you do

    public void insert(int number) {
           if(size / pq.length >= 75) {
               pq = resize(); 
               //You would have to make resize return an Integer[] and 
               //implement this throughout the code
           }
           for(int i = 0; i < pq.length; i++) {
                 if(pq[i] == null) {
                     pq[size] = number;
                     size++;
                     return;
                 }
           }
     }

Regardless: Remember when you call remove() to decrement size.

Upvotes: 3

Laogeodritt
Laogeodritt

Reputation: 760

You are explicitly storing the size as a variable. You also know the backing array's size. Compare them at the point when you need to check size: if(this.size > 3*this.pq/4).

Upvotes: 0

Chris Gong
Chris Gong

Reputation: 8229

What you could do is have an integer instance variable called count, that keeps track of the number of elements in the pq array. And whenever you insert an element into the array through the insert method, you can increment the count variable. Whenever you remove an element from the array through a remove method, you can decrement the count variable. Then, you can use this to check if the array is 75% filled at least,

if(pq.length * .75 <= size){
     //do what you need to do here
}

And the class would look like this,

public class PQ {

private int[] pq;
private int size;


public PQ(int capacity) {
    if (capacity < 1) {
        throw new IllegalArgumentException();
    }
    this.pq = new int[capacity + 1];
    this.size = 0;

}

public void insert(int number) {
           size++;
           //Code
}
public void remove(int number) {
           size--;
           //Code
}

private int[] resize() {
    int[] newPQ = new int[this.pq.length * 2];
    for (int i = 0; i < this.pq.length; i++) {
        newPQ[i] = this.pq[i];
    }
    return newPQ;
}
}

Upvotes: 1

Related Questions