Generates all productions of a given length for a regex-defined grammar. e.g. a*(a|b)b* -> val expr = Concat(Star(Literal('a')),Concat(Or(Literal('a'),Literal('b')), Star(Literal('b')))) expr.produce(5) = Set[String] = Set(abbbb, aaaab, bbbbb, aaabb, aaaaa, aabbb) The regex parser to generate the expression is a TODO for the reader :-)

Expr.scala

package com.gm.exer.regex

case class Limit(start:Int, end:Int) {
  def union(r2:Limit) =  new Limit(start.min(r2.start), end.max(r2.end))
  def concat(r2:Limit) = new Limit(start.max(r2.start), end + r2.end)  
  def toRange = start until end inclusive
}

abstract class Expr {
  def range(limit: Int): Limit
  def produce(lenght: Int): Set[String]
}

case class Literal(c:Char) extends Expr {
  val singleElem = new Limit(1,1)
  val emptySet:Set[String] = Set()
  
  def range(limit: Int): Limit = singleElem
  def produce(length:Int): Set[String] = {
    if (length ==  1) { 
      Set(c.toString)
    }
    else emptySet
  }
}

case class Star(child: Expr) extends Expr {
  def range(limit: Int) = new Limit(0,limit)
  
  def produce(length:Int):Set [String] = {
    if (length == 0) Set ()
	  def multiplyString(s:String, l:Int) = {
		 val sb = new StringBuilder;
		 (1 until l/s.length() inclusive).foreach(x=>{sb.append(s)})
		 sb.toString
	  }
	  def multiply(set: Set[String]) : Set[String] = {
	    set.map(x=> multiplyString(x,length))
	  }
	  def product(s0: Set[String], l: Int): Set[String]  = {
	    if (l == 0) s0 else product(s0.union(child.produce(l)), l-1) 
	  }
	  multiply(product(Set(), child.range(length).end))
  }
}

case class Or(left:Expr, right:Expr) extends Expr {
  def range(limit:Int) = left.range(limit).union(right.range(limit))
  def produce(length:Int):Set [String] = left.produce(length) union right.produce(length)
}

case class Concat(left:Expr, right:Expr) extends Expr {
  def range(limit:Int) = left.range(limit).concat(right.range(limit))
  def internalProduct(s1: Set[String], s2:Set[String]):Set[String] =  {
    for {x<-s1; y<-s2} yield x+y;
  }
  
  def produce(length:Int):Set[String] = { 
    val validCombinations = for {x<-left.range(length).toRange; y<-right.range(length).toRange; if (x+y==length) } yield (x,y)
    val product = validCombinations.flatMap({case (x,y) => internalProduct(left.produce(x), right.produce(y))})
    product.toSet[String]
  }

}