2.7 Discussion and Exercises

Most of the data structures described in this chapter are folklore. They can be found in implementations dating back over 30 years. For example, implementations of stacks, queues, and deques, which generalize easily to the ArrayStack, ArrayQueue and ArrayDeque structures described here, are discussed by Knuth [46, Section 2.2.2].

Brodnik et al. [13] seem to have been the first to describe the RootishArrayStack and prove a $ \sqrt{n}$ lower-bound like that in Section 2.6.2. They also present a different structure that uses a more sophisticated choice of block sizes in order to avoid computing square roots in the $ \mathtt{i2b(i)}$ method. Within their scheme, the block containing $ \mathtt{i}$ is block $ \lfloor\log (\ensuremath{\mathtt{i}}+1)\rfloor$, which is simply the index of the leading 1 bit in the binary representation of $ \ensuremath{\mathtt{i}}+1$. Some computer architectures provide an instruction for computing the index of the leading 1-bit in an integer. In Java, the Integer class provides a method $ \mathtt{numberOfLeadingZeros(i)}$ from which one can easily compute $ \lfloor\log (\ensuremath{\mathtt{i}}+1)\rfloor$.

A structure related to the RootishArrayStack is the two-level tiered-vector of Goodrich and Kloss [35]. This structure supports the $ \mathtt{get(i,x)}$ and $ \mathtt{set(i,x)}$ operations in constant time and $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i)}$ in $ O(\sqrt{\ensuremath{\mathtt{n}}})$ time. These running times are similar to what can be achieved with the more careful implementation of a RootishArrayStack discussed in Exercise 2.11.

Exercise 2..1   In the ArrayStack implementation, after the first call to $ \mathtt{remove(i)}$, the backing array, $ \mathtt{a}$, contains $ \ensuremath{\mathtt{n}}+1$ non- $ \mathtt{null}$ values despite the fact that the ArrayStack only contains $ \mathtt{n}$ elements. Where is the extra non- $ \mathtt{null}$ value? Discuss any consequences this non- $ \mathtt{null}$ value might have on the Java Runtime Environment's memory manager.

Exercise 2..2   The List method $ \mathtt{addAll(i,c)}$ inserts all elements of the Collection $ \mathtt{c}$ into the list at position $ \mathtt{i}$. (The $ \mathtt{add(i,x)}$ method is a special case where $ \ensuremath{\mathtt{c}}=\{\ensuremath{\mathtt{x}}\}$.) Explain why, for the data structures in this chapter, it is not efficient to implement $ \mathtt{addAll(i,c)}$ by repeated calls to $ \mathtt{add(i,x)}$. Design and implement a more efficient implementation.

Exercise 2..3   Design and implement a RandomQueue. This is an implementation of the Queue interface in which the $ \mathtt{remove()}$ operation removes an element that is chosen uniformly at random among all the elements currently in the queue. (Think of a RandomQueue as a bag in which we can add elements or reach in and blindly remove some random element.) The $ \mathtt{add(x)}$ and $ \mathtt{remove()}$ operations in a RandomQueue should run in constant time per operation.

Exercise 2..4   Design and implement a Treque (triple-ended queue). This is a List implementation in which $ \mathtt{get(i)}$ and $ \mathtt{set(i,x)}$ run in constant time and $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i)}$ run in time

$\displaystyle O(1+\min\{\ensuremath{\mathtt{i}}, \ensuremath{\mathtt{n}}-\ensur...
...}}, \vert\ensuremath{\mathtt{n}}/2-\ensuremath{\mathtt{i}}\vert\}) \enspace .
$

In other words, modifications are fast if they are near either end or near the middle of the list.

Exercise 2..5   Implement a method $ \mathtt{rotate(a,r)}$ that ``rotates'' the array $ \mathtt{a}$ so that $ \mathtt{a[i]}$ moves to $ \ensuremath{\mathtt{a}}[(\ensuremath{\mathtt{i}}+\ensuremath{\mathtt{r}})\bmod \ensuremath{\mathtt{a.length}}]$, for all $ \ensuremath{\mathtt{i}}\in\{0,\ldots,\ensuremath{\mathtt{a.length}}\}$.

Exercise 2..6   Implement a method $ \mathtt{rotate(r)}$ that ``rotates'' a List so that list item $ \mathtt{i}$ becomes list item $ (\ensuremath{\mathtt{i}}+\ensuremath{\mathtt{r}})\bmod \ensuremath{\mathtt{n}}$. When run on an ArrayDeque, or a DualArrayDeque, $ \mathtt{rotate(r)}$ should run in $ O(1+\min\{\ensuremath{\mathtt{r}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{r}}\})$ time.

Exercise 2..7   Modify the ArrayDeque implementation so that the shifting done by $ \mathtt{add(i,x)}$, $ \mathtt{remove(i)}$, and $ \mathtt{resize()}$ is done using the faster $ \mathtt{System.arraycopy(s,i,d,j,n)}$ method.

Exercise 2..8   Modify the ArrayDeque implementation so that it does not use the $ \mathtt{\text{\ttfamily\%}}$ operator (which is expensive on some systems). Instead, it should make use of the fact that, if $ \mathtt{a.length}$ is a power of 2, then

$\displaystyle \ensuremath{\mathtt{k\text{\ttfamily\%}a.length}}=\ensuremath{\mathtt{k\text{\ttfamily\&}(a.length-1)}} \enspace .
$

(Here, $ \mathtt{\text{\ttfamily\&}}$ is the bitwise-and operator.)

Exercise 2..9   Design and implement a variant of ArrayDeque that does not do any modular arithmetic at all. Instead, all the data sits in a consecutive block, in order, inside an array. When the data overruns the beginning or the end of this array, a modified $ \mathtt{rebuild()}$ operation is performed. The amortized cost of all operations should be the same as in an ArrayDeque.

Hint: Getting this to work is really all about how you implement the $ \mathtt{rebuild()}$ operation. You would like $ \mathtt{rebuild()}$ to put the data structure into a state where the data cannot run off either end until at least $ \ensuremath{\mathtt{n}}/2$ operations have been performed.

Test the performance of your implementation against the ArrayDeque. Optimize your implementation (by using $ \mathtt{System.arraycopy(a,i,b,i,n)}$) and see if you can get it to outperform the ArrayDeque implementation.

Exercise 2..10   Design and implement a version of a RootishArrayStack that has only $ O(\sqrt{\ensuremath{\mathtt{n}}})$ wasted space, but that can perform $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i,x)}$ operations in $ O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time.

Exercise 2..11   Design and implement a version of a RootishArrayStack that has only $ O(\sqrt{\ensuremath{\mathtt{n}}})$ wasted space, but that can perform $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i,x)}$ operations in $ O(1+\min\{\sqrt{\ensuremath{\mathtt{n}}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time. (For an idea on how to do this, see Section 3.3.)

Exercise 2..12   Design and implement a version of a RootishArrayStack that has only $ O(\sqrt{\ensuremath{\mathtt{n}}})$ wasted space, but that can perform $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i,x)}$ operations in $ O(1+\min\{\ensuremath{\mathtt{i}},\sqrt {\ensuremath{\mathtt{n}}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time. (See Section 3.3 for ideas on how to achieve this.)

Exercise 2..13   Design and implement a CubishArrayStack. This three level structure implements the List interface using $ O(\ensuremath{\mathtt{n}}^{2/3})$ wasted space. In this structure, $ \mathtt{get(i)}$ and $ \mathtt{set(i,x)}$ take constant time; while $ \mathtt{add(i,x)}$ and $ \mathtt{remove(i)}$ take $ O(\ensuremath{\mathtt{n}}^{1/3})$ amortized time.

opendatastructures.org