A sample code of linear search in Scala

LinearSearchTable.scala

import scala.collection.mutable

class LinearSearchTable[K, V] extends mutable.AbstractMap[K, V] {
  protected val table = new mutable.ArrayBuffer[(K,V)]

  private def lin_search(key: K): Int = {
    var (ix, result) = (0, -1)
    while (ix < table.size &&
           { if (key == table(ix)._1) { result = ix; false } else true })
      ix += 1
    result
  }

  protected def index(key: K): Int = lin_search(key)

  def get(key: K): Option[V] = {
    val ix = index(key)
    if (ix == -1)
      None
    else
      Some(table(ix)._2)
  }

  // put
  def addOne(kv: (K, V)) = {
    val (key, value) = kv
    val ix = index(key)
    if (ix == -1)
      table += kv
    else
      table(ix) = kv

    this
  }

  // remove
  def subtractOne(key: K) = {
    val ix = index(key)
    if (ix >= 0)
      table.remove(ix)

    this
  }

  def iterator = table.iterator

  override def size: Int = table.size
  override def clear(): Unit = table.clear()
}

Scala による線形探索プログラム例

線形探索のアルゴリズムは自明なので，このプログラムは Map の実装例を示すことが目的である。

Scala では AbstractMap トレートを継承すると，Map クラスの様々なメソッドが（自動的に）実装される。
ただし次のメソッドは自前で定義しなければならない。

• get(key: K): Option[V]
• addOne(elem: (K, V))
• subtractOne(key: K)
• iterator: Iterator[(K, V)]

get で key からvalue を得る，addOne でエントリーを追加する，subtractOne でエントリーを削除するメソッドを定義すればよい。
iterator は，全てのエントリーを得る，先頭のエントリーを得る，末尾のエントリーを得るといった操作を定義するために使用する。
このコードでは，たまたま 1行で記述できたが，通常は iteratorメソッドを定義するのが最も面倒である。

また実行性能を悪化させないため，size メソッド，clear() メソッドも独自に定義する。