alvinalexander.com | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Scala example source code file (NondetWordAutom.scala)

This example Scala source code file (NondetWordAutom.scala) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Java - Scala tags/keywords

anyref, array, array, bitset, bitset, boolean, int, int, map, nondetwordautom, nondetwordautom, q, seq, t

The Scala NondetWordAutom.scala source code

/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2003-2011, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */


package scala.util.automata

import scala.collection.{ immutable, mutable }

/** A nondeterministic automaton. States are integers, where
 *  0 is always the only initial state. Transitions are represented
 *  in the delta function. Default transitions are transitions that
 *  are taken when no other transitions can be applied.
 *  All states are reachable. Accepting states are those for which
 *  the partial function 'finals' is defined.
 */
abstract class NondetWordAutom[T <: AnyRef] {
  import immutable.BitSet
  
  val nstates: Int
  val labels: Seq[T]
  val finals: Array[Int] // 0 means not final
  val delta: Array[mutable.Map[T, BitSet]]
  val default: Array[BitSet]

  /** returns true if the state is final */
  final def isFinal(state: Int) = finals(state) > 0

  /** returns tag of final state */
  final def finalTag(state: Int) = finals(state)
  
  /** returns true if the set of states contains at least one final state */
  final def containsFinal(Q: BitSet): Boolean = Q exists isFinal
  
  /** returns true if there are no accepting states */
  final def isEmpty = (0 until nstates) forall (x => !isFinal(x))

  /** returns a BitSet with the next states for given state and label */
  def next(q: Int, a: T): BitSet = delta(q).getOrElse(a, default(q))

  /** returns a BitSet with the next states for given state and label */
  def next(Q: BitSet, a: T): BitSet = next(Q, next(_, a))
  def nextDefault(Q: BitSet): BitSet = next(Q, default)
  
  private def next(Q: BitSet, f: (Int) => BitSet): BitSet =
    (Q map f).foldLeft(BitSet.empty)(_ ++ _)

  private def finalStates = 0 until nstates filter isFinal
  override def toString = {
    
    val finalString = Map(finalStates map (j => j -> finals(j)) : _*).toString
    val deltaString = (0 until nstates) .
      map (i => "   %d->%s\n    _>%s\n".format(i, delta(i), default(i))) mkString
    
    "[NondetWordAutom  nstates=%d  finals=%s  delta=\n%s".format(nstates, finalString, deltaString)
  }
}

Other Scala examples (source code examples)

Here is a short list of links related to this Scala NondetWordAutom.scala source code file:

... this post is sponsored by my books ...

#1 New Release!

FP Best Seller

 

new blog posts

 

Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.