Is there a way to quickly find if all positions in an array are “full”?

Question

If I have a 64 length java array i[], is there a quick way to find out if every position in that array is "full", other than looping through the entire array? I'm writing a Reversi AI and I need to know whether the entire array is full or not.

Answer 1

Keep a flags variable of type long (which is 64 bits) and use it to track which array entries are 'full' by setting or clearing the relevant bit as appropriate. (You need to keep this in sync with your array entries.)

If you use a 1 value for each bit to mean the relevant cell is full, the you can tell very quickly if the whole array is full by comparing the flag variable to -1L.

Example implementation

int[] grid = new int[64];
long  full = 0L;

// place a piece at a certain grid position
grid[17] = 1;   // pretend 1 is the code for black
full |= 1L << 17;   // set bit 17 in our "full" tracker

// is the grid full?
if (full == -1L)
     // yes it is!
else
     // no it isn't

---

You can be even more cunning, and use a flags variable to track the colour of each cell too, so you can avoid using arrays altogether. One variable tracks whether the given cell is occupied or not, and the other tracks the colour (0 for white, 1 for black, say).

long colour = 0L;
long full   = 0L;

// set position 17 to white
colour &= ~(1L << 17);    // clear the bit (white)
full   |=  (1L << 17);    // set it to occupied

// set position 42 to black
colour |=  (1L << 42);    // set the bit (black)
full   |=  (1L << 42);    // set it to occupied

// is position 25 occupied?
if ((full & (1L<<25)) != 0) {
    // yes, but what colour?
    if ((colour & (1L<<25)) != 0)
        // black
    else
        // white
}

// is the grid full?
if (full == -1L)
     // yes it is!
else
     // no it isn't

Answer 2

You can keep separately a number of "empty" cells, and update it after each move.

However I don't see a need for this optimization: loop of length 64 must be very fast. Please try to see if this is a real bottleneck and if the optimization is worth your effort.

Answer 3

You can use two BitSets for black-and-white (or free-and-iswhite).

Answer 4

Arrays.asList(i).contains(EMPTY) (possibly you are interpreting null to mean empty).