Boyer–Moore majority vote algorithm

MajorityElement.scala

import scala.collection.generic.Growable

/**
  * Boyer–Moore majority vote algorithm (https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm)
  * A Data structure that supports O(1) tracking of the majority element in streaming data
  * (i.e. something that occurs strictly > 50% of the time)
  */
class MajorityElement[A] extends Growable[A] {
  private[this] var majorityElement = Option.empty[A]
  private[this] var count = 0

  override def +=(elem: A) = add(elem = elem, freq = 1)

  /**
    * Adds this element, freq number of times
    */
  def add(elem: A, freq: Int): this.type = {
    require(freq >= 0)
    if (majorityElement.contains(elem)) {
      count += freq
    } else if (count > freq) {
      count -= freq
    } else if (count < freq) {
      count = freq - count
      majorityElement = Some(elem)
    } else {
      clear()
    }
    assert(count >= 0)
    assert(count == 0 ^ majorityElement.isDefined)
    this
  }

  /**
    * Get the current strict majority (i.e. > 50%) element
    * @return None if is no single majority element
    */
  def apply(): Option[A] = majorityElement

  override def clear() = {
    majorityElement = None
    count = 0
  }
}