= Solution
The following class uses the bounded insertion contract from part (b). `slot` performs mathematical circular indexing with a wider intermediate, so even large legal indices do not overflow before reduction:
``
class ArrayDoubleEndedQueue(val MAX: Int) extends DoubleEndedQueue {
require(MAX > 0)
private val a = new Array[Int](MAX)
private var head = 0
private var size = 0
private def slot(offset: Int): Int =
((head.toLong + offset.toLong) % MAX.toLong).toInt
private def before(i: Int): Int = if (i == 0) MAX - 1 else i - 1
private def after(i: Int): Int = if (i == MAX - 1) 0 else i + 1
def isEmpty: Boolean = size == 0
def addLeft(x: Int): Unit = {
require(size < MAX)
head = before(head)
a(head) = x
size += 1
}
def addRight(x: Int): Unit = {
require(size < MAX)
a(slot(size)) = x
size += 1
}
def getLeft(): Int = {
require(size > 0)
val x = a(head)
head = after(head)
size -= 1
x
}
def getRight(): Int = {
require(size > 0)
val x = a(slot(size - 1))
size -= 1
x
}
}
``
For `addLeft`, moving the first position back one slot makes the old position the new logical index one; inserting at the new position prepends `x`. For `addRight`, the old `size` is the first unoccupied logical index, so writing there appends `x`. The removals read the appropriate endpoint and exclude that slot from the occupied interval. Every operation preserves the <representation invariant> and realizes the <abstraction function> postcondition. Old contents in unused slots cannot be observed through this interface. Each operation performs a fixed number of accesses and arithmetic operations, hence has <constant time> and <constant space> per call, apart from the class's $O(MAX)$ backing storage.
Back to article page
