Programming language polymorphism lets a common interface or operation apply to values of more than one type. In subtype polymorphism, a variable typed by a base class or trait can refer to instances of different implementing classes. A method call is checked through that common interface, then dynamic dispatch selects the receiver's overriding implementation. For example, a consumer using
Iterator[Int] can accept either a filtering iterator or a concatenating iterator without knowing its concrete class.Inheritance can establish a subtype relationship, while method overriding provides distinct implementations of a shared method signature. The classes must still honour the common behavioural contract; sharing a name alone does not establish substitutability. Parametric polymorphism is different: the type parameter in
Iterator[T] or FiniteDist[T] lets a definition work uniformly over element types. Method overloading is a further form of software polymorphism in which the compiler selects a signature using the static argument types; it should not be confused with runtime receiver dispatch.For the implementations above the value isThe first half-iterator returns the odd-position characters while consuming the even-position characters as its required skips. By the time it is exhausted, it has consumed the entire shared underlying iterator. The second half-iterator consequently has no entries left when concatenation reaches it. Sharing one source does not create two independent traversals. Neither constructor consumes anything, so it also does not shift the first output before iteration begins. The source's implementation references here should be read as parts (d) and (e); the printed reference to (c) and (d) is a cross-reference slip.
List('1', '3', '5', '7', '9')Use short-circuit evaluation so that even an availability test of the second iterator is delayed until the first is exhausted:Each successful call returns from the first producer while it has entries, then from the second. There is no constructor-time request or element prefetch. This implements concatenation of the producers' remaining sequences, subject to their ordinary iterator contracts.
class ConcatIterator[T](first: Iterator[T], second: Iterator[T])
extends Iterator[T] {
def hasNext: Boolean = first.hasNext || second.hasNext
def next(): T = {
if (first.hasNext) first.next()
else if (second.hasNext) second.next()
else throw new java.util.NoSuchElementException("empty concatenation")
}
}Delay both initial skipping and every later skipped entry until a caller actually requests availability or an output:The state flag means that the next underlying entry, if present, must be skipped before the next selected entry can be exposed. It is initially false for odd positions and true for even positions. Returning a selected entry reinstates that obligation.
class HalfIterator[T](iter: Iterator[T], odd: Boolean)
extends Iterator[T] {
private var needSkip = !odd
def hasNext: Boolean = {
if (needSkip && iter.hasNext) {
iter.next()
needSkip = false
}
iter.hasNext
}
def next(): T = {
if (!hasNext)
throw new java.util.NoSuchElementException("empty half iterator")
val result = iter.next()
needSkip = true
result
}
}Construction does not call the underlying iterator at all. A successful availability check may discard the one required intervening entry, but does not fetch the selected entry. It then clears the flag, so repeated availability checks cannot skip again. To decide whether a second entry exists through this interface, consuming the preceding discarded entry is necessary. After
next() returns, it does not eagerly request the following skipped entry. This gives the intended laziness while retaining correct exhaustion behaviour, including an even-position iterator over a singleton input.Yes in special cases; an ordinary finite iterator that progresses through its input needs changing consumption state. For a genuine immutable counterexample, an iterator over an infinite constant sequence needs no changing fields:Removing the first entry of that sequence leaves the same sequence, so this satisfies the iterator behaviour without changing object state. A permanently empty iterator is another example.
final class Ones extends Iterator[Int] {
def hasNext: Boolean = true
def next(): Int = 1
}For a normal finite nonempty traversal, however, repeated
next() calls must eventually change the returned entry or availability, so the implementation needs mutable cursor state somewhere. Declaring only val fields is not a proof of deep immutability: those fields can refer to another mutable iterator, an array, or a stateful closure. The standard API's description of iterators as mutable captures the usual consuming case, rather than enforcing a mutable field in every possible implementation.The two abstract methods areThe first reports availability; the second returns and consumes the next entry, or throws a
def hasNext: Boolean
def next(): TNoSuchElementException if none exists. Other standard iterator operations are supplied in terms of this interface. Repeated availability checks must not lose entries, although they may perform preparatory internal work.[ref]Scala 2.13 iterator API documentation. Iterator, abstract members hasNext and next; class-level mutation and reuse contract
The iterator pattern exposes sequential traversal through a small interface while hiding the representation of the underlying data. A client asks whether another entry is available and requests the next entry; it need not know whether the producer uses an array, linked list, tree or generated sequence.
The key design benefit is encapsulation of traversal state and representation. The same consuming algorithm can work through the interface for different producers, and each traversal can keep its own cursor state when a fresh iterator is supplied. This independence requires separate consumption states; two references to one iterator share a cursor.
For a remaining tree , define the potentialThis counts the nodes not on the right spine, so . Consider a right rotation with old root , left child , and three untouched subtrees . Before the rotation the potential isAfter the rotation it is , so each rotation decreases by exactly one while preserving the number of remaining nodes. This supplies a nonnegative decreasing bound for the inner loop.
When the root has no left child, printing it and advancing to its right child leaves unchanged and decreases the remaining node count by one. Thus decreases on every rotation and every removal, proving termination of the whole procedure. Over the entire execution there are exactly printed nodes and exactly rotations, since the final potential is zero. Both quantities are at most , so the running time is for a nonempty tree, with constant auxiliary space. The nested syntax does not imply quadratic time: it is the total potential decrease across all iterations that bounds the inner work. The potential is a proof device and is not computed by the running program.
Repeated right rotations expose the next inorder entry without a recursion stack:A right rotation replaces a local shape with inorder order by another shape with exactly that same order. The inner loop therefore preserves the inorder sequence of the remaining tree while moving its next output closer to the root. When the left child is null, the root is exactly the first remaining inorder entry. Printing it and advancing to its right child removes that entry from the remaining traversal.
def printDestructively(input: Tree): Unit = {
var root = input
while (root != null) {
while (root.left != null) {
val child = root.left
root.left = child.right
child.right = root
root = child
}
println(root.datum)
root = root.right
}
}The outer-loop invariant is that the output already produced, followed by the inorder sequence of the current root, equals the original inorder sequence. Consequently the procedure prints every original entry once in order. It stores only a constant number of node references and uses auxiliary space. It changes the original links, as permitted; clients must not rely on the input tree retaining its earlier shape.
Split the index range at its middle:For , the child sizes are and , differing by at most one. Induction gives the same property at every descendant, so the result is nearly balanced. Its inorder traversal is the initial subrange, then , then the final subrange, reproducing exactly with every occurrence retained.
def MakeTree(u: Array[Int], a: Int, b: Int): Tree = {
require(0 <= a && a <= b && b <= u.length)
if (a == b) null
else {
val middle = a + (b - a) / 2
new Tree(u(middle),
MakeTree(u, a, middle),
MakeTree(u, middle + 1, b))
}
}There is one nonempty recursive call per constructed node and one constant-time base call per empty child position. Therefore construction takes time for , or including the empty case, and allocates exactly nodes. The balanced recursion has logarithmic stack depth. The input array need not be sorted: the required property concerns subtree sizes and inorder order, not a search-tree ordering.
Use the empty reference as the base case:Induction on the tree proves the order: the first recursive call prints exactly the left subtree, then the procedure prints the root, then the final call prints exactly the right subtree. A finite acyclic tree supplies decreasing proper subtrees, so the recursion terminates. The traversal is valid for arbitrary integer labels; sorted output would additionally require a binary search tree invariant.
def printInorder(root: Tree): Unit = {
if (root != null) {
printInorder(root.left)
println(root.datum)
printInorder(root.right)
}
}The following class uses the node type supplied in the paper:An insertion connects a fresh endpoint to the old chain and updates its reciprocal link. A removal reconnects the exposed endpoint to null; the singleton case also clears the opposite endpoint. The remaining chain therefore satisfies the same representation invariant and has exactly the abstract sequence required by the specification. Every operation performs pointer work, excluding allocation costs for a newly added node.
class DoublyLinkedDoubleEndedQueue extends DoubleEndedQueue {
private var first: Node = null
private var last: Node = null
def isEmpty: Boolean = first == null
def addLeft(x: Int): Unit = {
val node = new Node(x, null, first)
if (first == null) last = node
else first.prev = node
first = node
}
def addRight(x: Int): Unit = {
val node = new Node(x, last, null)
if (last == null) first = node
else last.next = node
last = node
}
def getLeft(): Int = {
require(!isEmpty)
val old = first
first = old.next
if (first == null) last = null
else first.prev = null
old.next = null
old.datum
}
def getRight(): Int = {
require(!isEmpty)
val old = last
last = old.prev
if (last == null) first = null
else last.next = null
old.prev = null
old.datum
}
}Keep private references
first and last, both initially null. A nonempty representation is a finite acyclic chain from first through next to last. Its representation invariant requires first.prev == null, last.next == null, and reciprocal links between every adjacent pair. The nodes reached by following prev from last are exactly the same nodes in reverse order. No internal node reference is exposed to clients.The abstraction function reads the
datum values along the forward chain, giving the abstract sequence from left to right. The empty representation has both endpoint references null; the invariant requires that either both are null or both are nonnull. A single node has both links null. Updating both endpoint references when removing that last node is therefore essential.Use a finite sequence as abstract state, initially empty. One Scala interface isThe emptiness query has no precondition; its result is and its postcondition is . Adding on the left has no precondition and gives . Adding on the right gives . Both return
trait DoubleEndedQueue {
def isEmpty: Boolean
def addLeft(x: Int): Unit
def getLeft(): Int
def addRight(x: Int): Unit
def getRight(): Int
}Unit.Each removal requires a nonempty incoming sequence.
getLeft() returns its first entry and leaves the remaining final sequence; getRight() returns its last entry and leaves the remaining initial sequence. These contracts remove exactly one occurrence, so duplicate values are permitted and do not collapse the sequence into a set.Store the number of positive buckets, initially zero:Extend the representation invariant byThe abstraction function for the multiset is unchanged. The size operation has no precondition beyond a valid receiver; it returns the cardinality of the multiset support and changes no state. Replace the modifying methods inside the class byOnly transitions from zero to one or from one to zero change the support. Additions to an already positive bucket and removals leaving it positive preserve
private var distinct = 0
def size: Int = distinctdef add(x: Int): Unit = {
require(inRange(x))
require(c(x) < Int.MaxValue)
if (c(x) == 0) distinct += 1
c(x) += 1
}
def remove(x: Int): Unit = {
require(inRange(x))
require(c(x) > 0)
c(x) -= 1
if (c(x) == 0) distinct -= 1
}distinct. Thus size takes time, independently of MAX, and the other operations retain constant-time array access. Initialization still takes time.Implement the count function directly in a private array:The representation invariant is that
class ArrayIntBag(val MAX: Int) extends IntBag {
require(MAX > 0)
private val c = new Array[Int](MAX)
private def inRange(x: Int): Boolean = 0 <= x && x < MAX
def add(x: Int): Unit = {
require(inRange(x))
require(c(x) < Int.MaxValue)
c(x) += 1
}
def remove(x: Int): Unit = {
require(inRange(x))
require(c(x) > 0)
c(x) -= 1
}
def count(x: Int): Int = {
require(inRange(x))
c(x)
}
}c has length MAX and every stored count is nonnegative. The abstraction function gives in range and zero outside it. Zero initialization establishes the invariant. An allowed addition changes exactly one entry without overflow; an allowed removal changes exactly one positive entry without making it negative; querying changes none. Thus each method implements its abstract postcondition as well as preserving the representation invariant. The private array prevents clients from bypassing those guarantees. There are unlisted articles, also show them or only show them.
