Store the number of positive buckets, initially zero:
private var distinct = 0

def size: Int = distinct
Extend the representation invariant by
(1)
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.

Ancestors (11)

  1. 3
  2. Imperative programming (resit)
  3. 2021
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. 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