0

The following code is from ArrayDeque in the standard java library. I chose it somewhat arbitrarily since there are many examples of this idea throughout the code.

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

Basically, as I read it, the value of head is reduced by one, and then bitwise "anded" with elements.length minus one. This operation determine which index of the array will hold the new value e, and allows cyclic wrapping back to the beginning of the array. OK so far (I hope it's not wrong).

But then we come to the line:

if (head == tail) doubleCapacity();

Head and tail are ints. Even if they would equal the same position in the array after being bitwise "anded" (implying the array is full and needs to expand), that doesn't make them equal as ints (which is what is being tested, right?).

So... I don't see how this works.

Can anyone help?

Edited to clarify I'm referring to the index of the array, not any of its elements.

RCM
  • 333
  • 2
  • 8
  • What do you mean by _that doesn't make them equal as ints_? If `head` stores the value of `10` and `tail` stores the value of `10`, they are equal. – Sotirios Delimanolis Jun 27 '17 at 19:05
  • I mean the int variables head and tail have different values. They point to the same position in the array after being boolean added...because of overflow...but they don't have the same values themselves. – RCM Jun 27 '17 at 19:08
  • 2
    `head` and `index` are indices into the array, not array elements. – Sotirios Delimanolis Jun 27 '17 at 19:09
  • Right...they are indices of the array. Not elements in the array. I can edit that, but the question doesn't change. – RCM Jun 27 '17 at 19:14
  • At that point they are already reduced modulo the array length, so this *is* "after being bitwise anded". – harold Jun 27 '17 at 19:18
  • I don't know what you're asking if you already understand that they are indices. Are you asking how this deque implementation works? – Sotirios Delimanolis Jun 27 '17 at 19:18
  • I think what I'm asking probably has to do with what harold said "at that point they are already reduced modulo the array length..." If that's true it makes sense, but it's not clear to me why it's true. – RCM Jun 27 '17 at 19:20
  • `tail` never gets modified in this method. `tail` can be _anything_ at this point. It can be equal, or not equal, to `(head - 1) & (elements.length - 1)`. – Louis Wasserman Jun 27 '17 at 19:25
  • `a & (b - 1)` computes `a % b` when `b` is a power of 2. – Radiodef Jun 27 '17 at 19:25
  • https://stackoverflow.com/questions/28314798/addfirst-method-of-arraydeque-class – Sotirios Delimanolis Jun 27 '17 at 19:26

1 Answers1

3

head and tail initially refer to the first index of the array - 0.

The initial length of the backing array is 16 by default, and is always a power of two. This is important for the snippet of code you quoted to work.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
head
tail

Now suppose you add 15 elements to the end of the queue. Each time you add an element to the end, the tail index is incremented, so after 15 additions you get:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^                                  ^
head                               tail

At this point, all the indices of the array except of 15 are occupied.

Now we get to the code you quoted:

When you call addFirst, head should be decremented (wrapping around to the end of the array if necessary), and the new element is added at the index of the new value of head.

Since head was 0, the new value of head, (head - 1) & (elements.length - 1), is -1 & 15 or (converting to binary) 11111111111111111111111111111111 & 00000000000000000000000000001111, which is equal to 15, the last index of the array.

At this point, both head and tail contain the last index of the array - 15.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
                                   ^
                                   head
                                   tail

This means the array is full and must be doubled.

The important thing to note here is that (head - 1) & (elements.length - 1) is equivalent to (head - 1) % elements.length. This is true only because elements.length is a power of 2.

Eran
  • 387,369
  • 54
  • 702
  • 768
  • oh, i see... head has actually been changed to the value of ((head-1) & (elements.length-1))...yeah, OK. – RCM Jun 27 '17 at 19:32
  • Will not the line elements[head = (head - 1) & (elements.length - 1)] = e; overwrite the tail element when head and tail both are 15?? – abstractnature Jun 27 '17 at 19:35
  • abstractnature--yeah, i think that is why the call to doubleCapacity--to grow the array and remove that problem. I basically just missed some order-of-operations stuff and didn't see that the value of head had been changed much more dramatically that I was assuming. – RCM Jun 27 '17 at 19:36
  • @abstractnature It won't, since `tail` points to the index at which the next element will be added to the end of the queue (when addLast is called), which is an unoccupied index of the array. – Eran Jun 27 '17 at 19:37
  • double capactiy is creating an array twice its size and copying the array to the left half, and finally putting head = 0 and tail = whatever the previous length was ( If I am correct), so what happened to the tail element? addFirst removed and overwrote it, is it gone? Thats my doubt. – abstractnature Jun 27 '17 at 19:38