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 is
List('1', '3', '5', '7', '9')
The 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.
Use short-circuit evaluation so that even an availability test of the second iterator is delayed until the first is exhausted:
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")
  }
}
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.
Delay both initial skipping and every later skipped entry until a caller actually requests availability or an output:
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
  }
}
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.
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:
final class Ones extends Iterator[Int] {
  def hasNext: Boolean = true
  def next(): Int = 1
}
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.
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 are
def hasNext: Boolean
def next(): T
The first reports availability; the second returns and consumes the next entry, or throws a NoSuchElementException 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]
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 potential
This 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 is
After 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:
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
  }
}
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.
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.
Figure 1.
A right rotation preserves inorder order and decreases the traversal potential by one
. Original seven-node example. Orange edges mark the right spine; nodes off that spine contribute to the left-size potential. The inorder labels remain 1 through 7 before and after the rotation. Details.
Split the index range at its middle:
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))
  }
}
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.
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:
def printInorder(root: Tree): Unit = {
  if (root != null) {
    printInorder(root.left)
    println(root.datum)
    printInorder(root.right)
  }
}
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.
The following class uses the node type supplied in the paper:
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
  }
}
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.
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 is
trait DoubleEndedQueue {
  def isEmpty: Boolean
  def addLeft(x: Int): Unit
  def getLeft(): Int
  def addRight(x: Int): Unit
  def getRight(): Int
}
The 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 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:
private var distinct = 0

def size: Int = distinct
Extend the representation invariant by
The 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 by
def 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
}
Only 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 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:
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)
  }
}
The representation invariant is that 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.