Double-ended queue – mask integer

I’m having a hard time understanding what the mask integer is for (2nd line). I get that it regulates where values are placed in a double-ended queue, but I don’t get how exactly. This is part of the code from a double-ended queue just to have some context.

public class DEQueue {
    private int mask = (1 << 3) - 1;
    private String[] es = new String[mask + 1];
    private int head, tail;


    public void addFirst(String e) {
        es[head = (head - 1) & mask] = e;
        if (tail == head) {
            doubleCapacity();
        }
    }

    public String pollFirst() {
        String result = es[head];
        es[head] = null;
        if (tail != head) {
            head = (head + 1) & mask;
        }
        return result;
    }

    public String peekFirst() {
        return es[head];
    }

    public void addLast(String e) {
        es[tail] = e;
        tail = (tail + 1) & mask;
        if (tail == head) {
            doubleCapacity();
        }
    }

Answer

mask is used to wrap around the head and tail indices when new elements are added or removed. To be usable as bit mask, it is created by first shifting 1 a certain number of bits (here 3) and then performing - 1 to set all lower bits to 1.

In your example the initial value is (1 << 3) - 1, which is equivalent to binary 111. This represents an initial deque (double-ended queue) capacity of 8 (2³) due to the 0 being used as index as well.

Now let’s imagine for an empty deque addFirst(...) is called:

1. head is initially 0
2. head - 1 is -1, due to being in two’s complement this is equivalent to binary 1…111 (all bits are 1)
3. Applying & mask works as bit mask and only selects the bits which have the value 1 in mask, that is the lowest three bits, here: 1...111 & 111. This wraps the -1 from the previous step to a 7 (binary 111).

In the end that means the addFirst(...) call caused head to wrap around and place the element at es[7], the last position in the array.

Now let’s consider the similar situation of calling addLast(...) when tail already points to the last element of the array, assuming this index 7 here again. Note that in your implementation tail seems to point to the next free index at the end of the deque.

1. tail + 1 is 8, the binary representation is 1000
2. & mask again works as bit mask, 1000 & 111. It again only selects the lowest three bits, which are all 0 in this case. This effectively wraps the 8 to a 0, the first index in the array.

(The situation is the same for calls to pollFirst())

For all other calls to addFirst(...) and addLast(...) applying the bit mask & mask has no effect and leaves the indices unchanged because they are in range [0, array.length).