Use a minimum stack: each linked list node caches the minimum of all values from that node down to the bottom. This handles duplicate minima without searching when one is removed.The representation invariant is that the chain from
class Stack {
private class Node(val value: Int, val least: Int, val next: Node)
private var top: Node = null
def push(x: Int): Unit = {
val m = if (top == null) x else math.min(x, top.least)
top = new Node(x, m, top)
}
def pop(): Int = {
require(!isEmpty)
val x = top.value
top = top.next
x
}
def isEmpty: Boolean = top == null
def min: Int = {
require(!isEmpty)
top.least
}
}top is finite and acyclic, and every reachable node q satisfiesThe abstraction function takes the values along this chain in top-to-bottom order. Thus pushing changes to , and popping a nonempty returns its head and leaves its tail. The cached-minimum equation follows for a new node from the previously valid chain; removing a head leaves every surviving equation unchanged. ConsequentlyThe bounds use the usual constant-cost allocation and integer arithmetic model. Storage is linear in the number of entries. min and pop require a nonempty stack; min leaves it unchanged.Keep a running total in the mixin, and use only the inherited public operations. Updating after a successful superclass operation leaves the total unchanged if an empty For this trait mixed directly into
pop fails its precondition.trait SumPlugin extends Stack {
private var total = 0
override def push(x: Int): Unit = {
super.push(x)
total += x
}
override def pop(): Int = {
val x = super.pop()
total -= x
x
}
def sum: Int = total
}Stack, its representation invariant is , where is the abstract stack sequence. A successful push adds exactly its argument and a successful pop removes exactly its returned value. ThusThe mixin reads no private Stack fields. Its operations add constant time complexity. As in the paper's Int interface, an unbounded mathematical total requires excluding integer overflow, or replacing the accumulator with BigInt if the interface is allowed to change. A later mixin can transform a pushed value at a different point in the Scala trait linearization; the effect is analyzed in the next part.The doubling mixin delegates with a transformed argument.For
trait DoublePlugin extends Stack {
override def push(x: Int): Unit = super.push(2 * x)
}A, the relevant Scala trait linearization is A, DoublePlugin, SumPlugin, Stack. A push first doubles the argument, then SumPlugin sees and sums that doubled value. The physical values are and the total is .For Equivalently,This is stackable trait modification: the order determines which arguments an outer mixin observes. In particular, the running-total specification from part (b) holds for
B, the Scala trait linearization is B, SumPlugin, DoublePlugin, Stack. SumPlugin sums the original argument, while its super.push doubles the stored value. The physical values are still , but the counter is . Hence the two lines printed are12
6A but does not survive the transforming inner mixin in B. With the given implementation, popping from B would subtract the doubled stored value, demonstrating why mixing individually sensible traits can break a combined representation invariant. Articles by others on the same topic
There are currently no matching articles.