Double-ended queue - mask integer

Question

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();
        }
    }

"Associative array" is a bit misleading because Java does not have associative arrays, see [this question](https://stackoverflow.com/q/5122913). Have removed it from the question. — Marcono1234, Mar 21 '22 at 17:34
@Marcono1234 Actually, Java does have them. They're called `maps` which take a `key/value` pair just like an `associative array` (which is what they are called in `Perl`). In `Python` they are called `dictionaries`. Check out [Associative Arrays](https://en.wikipedia.org/wiki/Associative_array) for more info. — WJS, Mar 21 '22 at 18:22
@WJS yes, you are right. From a theoretical standpoint Java has associative arrays in the form of `Map` implementations. But in the specific context of Java, you wouldn't call it "associative array" because it would be misleading. Either way this question is about regular index based array access and is unrelated to `Map` / associative arrays. — Marcono1234, Mar 21 '22 at 19:11

Marcono1234 · Accepted Answer · 2022-03-21T22:22:20.803

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:

head is initially 0
head - 1 is -1, due to being in two's complement this is equivalent to binary 1...111 (all bits are 1)
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.

tail + 1 is 8, the binary representation is 1000
& 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).

Double-ended queue - mask integer

1 Answers1