Scala example source code file (WorklistAlgorithm.scala)

This example Scala source code file (WorklistAlgorithm.scala) is included in my "Source Code Warehouse" project. The intent of this project is to help you more easily find Scala source code examples by using tags.

All credit for the original source code belongs to scala-lang.org; I'm just trying to make examples easier to find. (For my Scala work, see my Scala examples and tutorials.)

Scala tags/keywords

collection, compiler, elem, nsc, unit, wlist, worklistalgorithm

The WorklistAlgorithm.scala Scala example source code

/* NSC -- new Scala compiler
 * Copyright 2005-2013 LAMP/EPFL
 * @author  Martin Odersky
 */

package scala.tools.nsc
package backend

import scala.collection.mutable

/**
 * Simple implementation of a worklist algorithm. A processing
 * function is applied repeatedly to the first element in the
 * worklist, as long as the stack is not empty.
 *
 * The client class should mix-in this class and initialize the worklist
 * field and define the `processElement` method. Then call the `run` method
 * providing a function that initializes the worklist.
 *
 * @author  Martin Odersky
 * @version 1.0
 * @see     [[scala.tools.nsc.backend.icode.Linearizers]]
 */
trait WorklistAlgorithm {
  type Elem
  type WList = mutable.Stack[Elem]

  val worklist: WList

  /**
   * Run the iterative algorithm until the worklist remains empty.
   * The initializer is run once before the loop starts and should
   * initialize the worklist.
   */
  def run(initWorklist: => Unit) = {
    initWorklist

    while (worklist.nonEmpty)
      processElement(dequeue)
  }

  /**
   * Process the current element from the worklist.
   */
  def processElement(e: Elem): Unit

  /**
   * Remove and return the first element to be processed from the worklist.
   */
  def dequeue: Elem
}