The missing preconditions are for insertion and for deletion and indexing. The inclusive endpoint permits appending; deletion or access at the length is invalid. Specify the initial state, for example , as well as the read-only frame conditions: indexing returns the indicated character and preserves , while length returns and preserves .
The insertion and deletion clauses already describe the new sequence, but their returned values and effects should be interpreted against the old state. For a machine-sized length, insertion also requires . These clauses complete the document abstract data type without prescribing one storage representation.
A mutable character buffer supplies a cached length and constant-time indexed access:
class DocImp extends Doc {
  private val data = scala.collection.mutable.ArrayBuffer.empty[Char]

  def insert(pos: Int, ch: Char): Unit = {
    require(0 <= pos && pos <= data.length)
    require(data.length < Int.MaxValue)
    data.insert(pos, ch)
  }

  def delete(pos: Int): Char = {
    require(0 <= pos && pos < data.length)
    data.remove(pos)
  }

  def apply(pos: Int): Char = {
    require(0 <= pos && pos < data.length)
    data(pos)
  }

  def length: Int = data.length
}
The representation invariant is that data is a well-formed private dynamic array of at most Int.MaxValue characters. Its abstraction function is the buffer's character sequence. Initialization is empty; insertion and removal at the checked position implement exactly the required sequence edits, and the queries do not modify it.
length and indexing are because a dynamic array stores its used length and supports address arithmetic for indexed access. An insertion or deletion at position in a document of length shifts entries; insertion can additionally resize the backing storage, giving amortized time and worst-case for one operation. Deletion is with an additional constant term.
Building a document by appending the characters of a length- string costs amortized time, since geometric capacity growth copies a total of only entries. Thus this implementation does not have the quadratic append behavior of repeated immutable-string concatenation. A known final length can also be reserved in advance. The bounds use the usual amortized analysis of a dynamic array.[ref]
Use a fixed-size count array and protected hooks defining a stable character-to-slot mapping. The default hooks count the ASCII lowercase interval. The document must start empty, and all subsequent edits must pass through the mixin methods, as they do for new DocImp with CharCountPlugin.
trait CharCountPlugin extends Doc {
  protected def firstCounted: Char = 'a'
  protected def numberCounted: Int = 26
  protected def slot(ch: Char): Int = {
    val k = ch.toInt - firstCounted.toInt
    if (0 <= k && k < numberCounted) k else -1
  }
  private lazy val totals = Array.fill(numberCounted)(0)

  abstract override def insert(pos: Int, ch: Char): Unit = {
    val k = slot(ch)
    super.insert(pos, ch)
    if (k >= 0) totals(k) += 1
  }

  abstract override def delete(pos: Int): Char = {
    val removed = super.delete(pos)
    val k = slot(removed)
    if (k >= 0) totals(k) -= 1
    removed
  }

  def count(ch: Char): Int = {
    val k = slot(ch)
    require(k >= 0, "character is outside the counted alphabet")
    totals(k)
  }
}
The additional representation invariant is that each array slot equals the number of corresponding characters in the current document. Initially all counts are zero. Each successful underlying edit changes exactly one relevant count, while a failed position check throws before any count is changed. Returning the actual deleted character lets deletion adjust the correct slot.
count takes time for the fixed alphabet, as do the mixin's additions to edit cost. The lazy array avoids reading subclass-overridden size hooks during trait construction; the hooks must remain stable. An extension can override the interval hooks, or override slot with another fixed finite mapping. This is stackable modification by a trait: abstract override permits the method to call the next implementation of super, supplied here by DocImp.[ref]
Reuse the machinery with the digit interval:
trait DigitCountPlugIn extends CharCountPlugin {
  override protected def firstCounted: Char = '0'
  override protected def numberCounted: Int = 10
}
Its count precondition is now '0' <= ch && ch <= '9'. It counts digits while permitting all characters to be stored. This is an alternative configured counter, rather than a second independent lowercase counter in the same object; simultaneous independent alphabets would require separate counters or a combined mapping.
Construct the mixed object with a concrete document implementation beneath the plugin:
val doc: DocImp with CharCountPlugin = new DocImp with CharCountPlugin
Its type combines DocImp and CharCountPlugin, so document operations and count are available. For example, inserting two 'a' characters and then deleting one leaves doc.count('a') == 1. The plugin is on the right of the concrete superclass in Scala's composition, so its edit methods extend the underlying implementations.

Ancestors (10)

  1. Imperative programming (resit)
  2. 2022
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version