1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/.ensime	Sun Aug 29 21:26:36 2010 -0600
     1.3 @@ -0,0 +1,19 @@
     1.4 +(
     1.5 + :server-root "/home/kmels/.emacs.d/scala/ensime-0.0.13/"
     1.6 + :server-cmd "/home/kmels/.emacs.d/scala/ensime-0.0.13/bin/servear.sh"
     1.7 + :server-host "localhost"
     1.8 + :server-env ()
     1.9 +
    1.10 + :project-package "gui"
    1.11 + :source ( :include("src/main/scala"
    1.12 +		    "src/test/scala"
    1.13 +		    ))
    1.14 + 
    1.15 + :use-sbt t
    1.16 + :dependency-jars("main")
    1.17 + :target "target/classes"
    1.18 +
    1.19 + :classpath("/home/kmels/.emacs.d/scala/ensime-0.0.13/lib/ensime.jar"
    1.20 +	    "/home/kmels/.emacs.d/scala/ensime-0.0.13/lib/scala-library.jar"
    1.21 + )
    1.22 +

     2.1 --- a/src/main/scala/Circuit.scala	Sun Aug 29 21:21:37 2010 -0600
     2.2 +++ b/src/main/scala/Circuit.scala	Sun Aug 29 21:26:36 2010 -0600
     2.3 @@ -6,7 +6,10 @@
     2.4      case _ => throw InputError("Output gate \""+outputName+"\" wasn't specified")
     2.5    }
     2.6  
     2.7 -
     2.8 +  /*
     2.9 +   * Computes the routes for this circuit
    2.10 +   *
    2.11 +   */
    2.12    val routes:List[Route] = {    
    2.13      def getRoutesFrom(id:String):List[List[String]] ={      
    2.14        if (inputNames.contains(id))
    2.15 @@ -20,44 +23,24 @@
    2.16        }
    2.17      }
    2.18      
    2.19 -    val routes = getRoutesFrom(outputGate.name)
    2.20 -
    2.21 -    val ruta = routes(1)
    2.22 -    //    println("Ruta 1: "+ruta)
    2.23 -    //   println("Ruta es valida: "+isValid(ruta))
    2.24 -    //println("RUTA 0: "+isValid(routes(0)))
    2.25 -    
    2.26 -
    2.27 -    routes.zipWithIndex.foreach(
    2.28 -      r => {
    2.29 -	val index = r._2
    2.30 -	val route = r._1
    2.31 -	println("RUTA "+index+" valida: "+isValid(route)+" \n\tRUTA: "+route+"\n\n")
    2.32 -      }
    2.33 +    val paths = getRoutesFrom(outputGate.name)
    2.34 +    paths.zipWithIndex.map(
    2.35 +      routeWithIndex => 
    2.36 +	Route(
    2.37 +	  routeWithIndex._2,
    2.38 +	  routeWithIndex._1,
    2.39 +	  isTruthful(routeWithIndex._1)
    2.40 +	)
    2.41      )
    2.42 -    /*    val merasMeras:List[Route] = routes.zipWithIndex.map(
    2.43 -     routeWithIndex => 
    2.44 -     Route(
    2.45 -     routeWithIndex._2,
    2.46 -     routeWithIndex._1,
    2.47 -     isValid(routeWithIndex._1)
    2.48 -     )
    2.49 -     )*/
    2.50 -
    2.51 -    //println("Meras meras: "+merasMeras.mkString("\n,"))
    2.52 -    //merasMeras
    2.53 -    List()
    2.54    }
    2.55 -
    2.56 -
    2.57 -
    2.58 +  
    2.59    /**
    2.60     * Checks if a route is valid
    2.61     * 
    2.62     * @param route the list of gates in order
    2.63     * @returns true if the route is valid within this circuit
    2.64     */
    2.65 -  private def isValid(route:List[String]):Boolean = {
    2.66 +  private def isTruthful(route:List[String]):Boolean = {
    2.67      import collection.mutable.ListBuffer
    2.68      val uncheckedStates = ListBuffer(sensitize(route)) //initial states is the sensitized values for this route
    2.69      val justifiedStates = ListBuffer[State]()
    2.70 @@ -68,27 +51,29 @@
    2.71      def isFinalState(state:State):Boolean = state.valuesIterator.forall(_ == true)
    2.72      
    2.73      /**
    2.74 -     * @returns true if there exists some incoherent value
    2.75 +     * @returns true if there exists some incoherent value or there exists a wire in the route whose value is set
    2.76       */ 
    2.77 -    def isInvalidState(state:State):Boolean = {
    2.78 +    def isInvalidState(path:List[String],state:State):Boolean = {
    2.79        val allWires:List[String] = state.keysIterator.toList.map(_._1)
    2.80        //there has to be only one value for a wire
    2.81 -      allWires.diff(allWires.toSet.toSeq) != Nil //if there's at least one repeated
    2.82 +      val hasIncoherences = allWires.diff(allWires.toSet.toSeq) != Nil //if there's at least one repeated
    2.83 +      //if it sets a value for a wire in the route (path), it's invalid too, i.e. at least one sensitized wire sets value for a wire in the path
    2.84 +      val valueSetInPath = allWires.filter(route.contains(_)).size >0
    2.85 +      
    2.86 +      hasIncoherences | valueSetInPath
    2.87      }
    2.88      
    2.89      while (!uncheckedStates.isEmpty){ //while there is no state left to check
    2.90 -      val newStates = nextStates(uncheckedStates.remove(0)) //get next states
    2.91 +      val newStates = justify(route,uncheckedStates.remove(0)) //get next states
    2.92        
    2.93 -      val (invalidStates,validStates) = newStates.partition( s => isInvalidState(s) )
    2.94 +      val (invalidStates,validStates) = newStates.partition( s => isInvalidState(route,s) )
    2.95        //we don't care about invalid states anymore, but there could be one final state (or more) within the valid states
    2.96 +
    2.97        val (finalStates,justValidStates) = validStates.partition(isFinalState(_))
    2.98 -
    2.99 -      println("encontro "+ finalStates.size +" estados finales")
   2.100        justifiedStates ++= finalStates
   2.101        uncheckedStates ++= justValidStates
   2.102      }
   2.103      
   2.104 -    println("en total: "+justifiedStates.size+" estados finales")
   2.105      justifiedStates.size > 0
   2.106    }
   2.107  }

     3.1 --- a/src/main/scala/Gate.scala	Sun Aug 29 21:21:37 2010 -0600
     3.2 +++ b/src/main/scala/Gate.scala	Sun Aug 29 21:26:36 2010 -0600
     3.3 @@ -14,6 +14,7 @@
     3.4      case "OR" => Some(false)
     3.5      case "AND" => Some(true)
     3.6      case "NAND" => Some(true)    
     3.7 +    case "NOR" => Some(false)
     3.8      case "NOT" => None
     3.9    }
    3.10  }

     4.1 --- a/src/main/scala/Justifier.scala	Sun Aug 29 21:21:37 2010 -0600
     4.2 +++ b/src/main/scala/Justifier.scala	Sun Aug 29 21:26:36 2010 -0600
     4.3 @@ -3,25 +3,23 @@
     4.4  trait Justifier extends Sensitizer {
     4.5    implicit def stateToSet(state:State):Set[State] = Set(state)
     4.6  
     4.7 -  def nextStates(state:State):Set[State] = { p(state)}
     4.8 -
     4.9 -  def p(state:State):Set[State] = 
    4.10 +  def justify(route:List[String],state:State):Set[State] = 
    4.11      state.find(checkedWire => checkedWire._2 == false) match { //find the first which hasn't been checked yet 
    4.12        case None => {	
    4.13  	Set() //empty set
    4.14        }
    4.15 -      case Some(nonCheckedWire) => {
    4.16 +      case Some(nonCheckedWire) => {	
    4.17  	val wireName = nonCheckedWire._1._1
    4.18  	val wireValue:Option[Boolean] = nonCheckedWire._1._2
    4.19 -	if (inputNames.contains(wireName)){
    4.20 +
    4.21 +	if (inputNames.contains(wireName))
    4.22  	  state.updated((wireName,wireValue),true) //mark the wire as checked
    4.23 -	}else{
    4.24 -	  //println("Gates: "+gates)
    4.25 +	else{
    4.26  	  val gate:Gate = gates.find(_.name == nonCheckedWire._1._1) match {
    4.27  	    case Some(gate) => gate
    4.28  	    case _ => {
    4.29  	      println("Could not found gate for "+nonCheckedWire._1._1)
    4.30 -	      throw new Exception()
    4.31 +	      throw new Exception("Could not found gate for "+nonCheckedWire._1._1)
    4.32  	    }
    4.33  	  }
    4.34  	  val gateValue:Option[Boolean] = nonCheckedWire._1._2
    4.35 @@ -30,66 +28,57 @@
    4.36  	    case binaryGate:BinaryGate => {
    4.37  	      wireValue match{
    4.38  		case Some(gateOutputValue) => {
    4.39 -		  val input1ShouldBe: (Boolean) => CheckedSensitizedWire = value => ((binaryGate.input1Name,Some(value)),false)
    4.40 +		  val input1ShouldBe: (Boolean) => CheckedSensitizedWire = value => {
    4.41 +		    ((binaryGate.input1Name,Some(value)),false)
    4.42 +		  }
    4.43 +
    4.44  		  val input2ShouldBe: (Boolean) => CheckedSensitizedWire = value => ((binaryGate.input2Name,Some(value)),false)
    4.45  		  val sensitizedGate:SensitizedWire = nonCheckedWire._1
    4.46  
    4.47  		  binaryGate.operationName match{
    4.48  		    case "AND" => {			  
    4.49 -//		      println("AND!")
    4.50  		      gateOutputValue match{
    4.51  			case true => //gate AND, with output 1. 
    4.52  			  state.updated(sensitizedGate,true) + (
    4.53  			    input1ShouldBe(true),input2ShouldBe(true)
    4.54  			  )
    4.55 -			case _ => { //gate AND, with output 0,
    4.56 -			  val state1:State = state.updated(sensitizedGate,true) + (			    
    4.57 -			    input1ShouldBe(false),input2ShouldBe(true)
    4.58 -			  )
    4.59 -
    4.60 -			  val state2:State = state.updated(sensitizedGate,true) + (			    
    4.61 -			    input1ShouldBe(true),input2ShouldBe(false)
    4.62 -			  )
    4.63 -
    4.64 -			  val state3:State = state.updated(sensitizedGate,true) + (			    
    4.65 -			    input1ShouldBe(false),input2ShouldBe(false)
    4.66 -			  )
    4.67 -
    4.68 -			  //return the three possible states
    4.69 -			  Set(state1,state2,state3)
    4.70 -			}
    4.71 +			case _ => //gate AND, with output 0,
    4.72 +			  atLeastOneInputMustBeFalse(binaryGate,route,sensitizedGate,state)
    4.73  		      }
    4.74  		    }
    4.75 -		    case "OR" => {
    4.76 -//		      println("OR!")
    4.77 +		    case "OR" => 
    4.78  		      gateOutputValue match{
    4.79 -			case true => {
    4.80 -			  val state1:State = state.updated(sensitizedGate,true) + (			    
    4.81 -			    input1ShouldBe(false),input2ShouldBe(true)
    4.82 -			  )
    4.83 -
    4.84 -			  val state2:State = state.updated(sensitizedGate,true) + (			    
    4.85 -			    input1ShouldBe(true),input2ShouldBe(false)
    4.86 -			  )
    4.87 -
    4.88 -			  val state3:State = state.updated(sensitizedGate,true) + (			    
    4.89 -			    input1ShouldBe(true),input2ShouldBe(true)
    4.90 -			  )
    4.91 -
    4.92 -			  //return the three possible states
    4.93 -			  Set(state1,state2,state3)
    4.94 -			}
    4.95 +			case true => atLeastOneInputMustBeTrue(binaryGate,route,sensitizedGate,state)
    4.96  			case _ => //OR output is 0, both inputs must be 0 as well
    4.97  			  state.updated(sensitizedGate,true) + (
    4.98  			    input1ShouldBe(false),input2ShouldBe(false)
    4.99  			  )			
   4.100 -		      }
   4.101 -		    }
   4.102 +		      }//end OR
   4.103 +		    case "NOR" => 
   4.104 +		      gateOutputValue match{
   4.105 +			case false =>{
   4.106 +			  //NOR output is 0, at least one input must be true
   4.107 +			  atLeastOneInputMustBeTrue(binaryGate,route,sensitizedGate,state)
   4.108 +			}
   4.109 +			case _ => //NOR output is 1, both inputs must be 0
   4.110 +			  state.updated(sensitizedGate,true) + (
   4.111 +			    input1ShouldBe(false),input2ShouldBe(false)
   4.112 +			  )
   4.113 +		      } //END NOR
   4.114 +		    case "NAND" => 
   4.115 +		      gateOutputValue match{
   4.116 +			case true => {
   4.117 +			  atLeastOneInputMustBeFalse(binaryGate,route,sensitizedGate,state)
   4.118 +			}
   4.119 +			case _ => { //NAND output is 0, both inputs must be 1
   4.120 +			  state.updated(sensitizedGate,true) + (
   4.121 +			    input1ShouldBe(true),input2ShouldBe(true)
   4.122 +			  )
   4.123 +			}
   4.124 +		      }//END NAND
   4.125  		  }
   4.126  		} //end if wire value is Some(_)
   4.127 -		case _ => {
   4.128 -		  state.updated(nonCheckedWire._1,true) //go to the next state, it's ok
   4.129 -		}
   4.130 +		case _ => state.updated(nonCheckedWire._1,true) //go to the next state, it's ok
   4.131  	      }	      
   4.132  	    }
   4.133  	    case unaryGate:UnaryGate => unaryGate.operationName match {
   4.134 @@ -109,4 +98,55 @@
   4.135  	
   4.136        } // end Some(noncheckedwire)
   4.137      } //end next states
   4.138 +
   4.139 +  private def atLeastOneInputMustBeFalse(binaryGate:BinaryGate,route:List[String],sensitizedGate:SensitizedWire,state:State):Set[State] ={
   4.140 +    val input1ShouldBe: (Boolean) => State = value => Map((binaryGate.input1Name,Some(value))->false)
   4.141 +    val input2ShouldBe: (Boolean) => State = value => Map((binaryGate.input2Name,Some(value))->false)
   4.142 +
   4.143 +    //return the three possible states
   4.144 +    if (sensitizedWireSetsValueInRoute(route,binaryGate.input1Name)){
   4.145 +      state.updated(sensitizedGate,true) ++ input2ShouldBe(false)
   4.146 +    }else 
   4.147 +      if (sensitizedWireSetsValueInRoute(route,binaryGate.input2Name)){
   4.148 +	state.updated(sensitizedGate,true) ++ input1ShouldBe(false)
   4.149 +      }
   4.150 +      else{
   4.151 +	val state1:State = state.updated(sensitizedGate,true) ++ input1ShouldBe(false) ++ input2ShouldBe(true)
   4.152 +	val state2:State = state.updated(sensitizedGate,true) ++ input1ShouldBe(true) ++ input2ShouldBe(false)
   4.153 +	val state3:State = state.updated(sensitizedGate,true) ++ input1ShouldBe(false) ++ input2ShouldBe(false)
   4.154 +	Set(state1,state2,state3)
   4.155 +      }
   4.156 +  }
   4.157 +
   4.158 +  private def atLeastOneInputMustBeTrue(binaryGate:BinaryGate,route:List[String],sensitizedGate:SensitizedWire,state:State):Set[State] ={
   4.159 +    val input1ShouldBe: (Boolean) => State = value => Map((binaryGate.input1Name,Some(value))->false)
   4.160 +    val input2ShouldBe: (Boolean) => State = value => Map((binaryGate.input2Name,Some(value))->false)
   4.161 +
   4.162 +    //return the three possible states
   4.163 +    if (sensitizedWireSetsValueInRoute(route,binaryGate.input1Name)){
   4.164 +      state.updated(sensitizedGate,true) ++ input2ShouldBe(true)
   4.165 +    }else 
   4.166 +      if (sensitizedWireSetsValueInRoute(route,binaryGate.input2Name)){
   4.167 +	state.updated(sensitizedGate,true) ++ input1ShouldBe(true)
   4.168 +      }
   4.169 +      else{
   4.170 +	val state1:State = state.updated(sensitizedGate,true) ++ input1ShouldBe(false) ++ input2ShouldBe(true)
   4.171 +	val state2:State = state.updated(sensitizedGate,true) ++ input1ShouldBe(true) ++ input2ShouldBe(false)
   4.172 +	val state3:State = state.updated(sensitizedGate,true) ++ input1ShouldBe(true) ++ input2ShouldBe(true)
   4.173 +	Set(state1,state2,state3)
   4.174 +      }
   4.175 +  }
   4.176 +
   4.177 +  private def sensitizedWireSetsValueInRoute(route:List[String],inputName:String):Boolean = 
   4.178 +    if (route.contains(inputName))
   4.179 +      true
   4.180 +    else
   4.181 +      gates.find(_.name == inputName) match{
   4.182 +	case Some(gate) => gate match{
   4.183 +	  case unaryGate:UnaryGate =>
   4.184 +	    sensitizedWireSetsValueInRoute(route,unaryGate.inputName)
   4.185 +	  case _ => false
   4.186 +	}
   4.187 +	case _ => false
   4.188 +      }//end match
   4.189  }

     5.1 --- a/src/main/scala/Main.scala	Sun Aug 29 21:21:37 2010 -0600
     5.2 +++ b/src/main/scala/Main.scala	Sun Aug 29 21:26:36 2010 -0600
     5.3 @@ -1,11 +1,12 @@
     5.4  package main
     5.5  
     5.6  object Main extends Application{
     5.7 -  val pathToFile = "/home/kmels/tmp/ie2005"
     5.8 +  val pathToFile = "/home/kmels/tmp/ie2005_3"
     5.9  
    5.10    try {
    5.11      val c:Option[Circuit] = Parser.parse(io.Source.fromFile(pathToFile).mkString)
    5.12      println(c)
    5.13 +    println(c.get.routes)
    5.14    } catch{
    5.15      case e:InputError => println(e.toString)
    5.16    }

     6.1 --- a/src/main/scala/Sensitizer.scala	Sun Aug 29 21:21:37 2010 -0600
     6.2 +++ b/src/main/scala/Sensitizer.scala	Sun Aug 29 21:26:36 2010 -0600
     6.3 @@ -11,7 +11,6 @@
     6.4    
     6.5    case class Route(val number:Int,val route:List[String], val isValid:Boolean)
     6.6  
     6.7 -
     6.8    def sensitize(route:List[String]):State = {
     6.9      val binaryGatesInRoute:List[BinaryGate] = route.map(gateName => gates.find(_.name == gateName)).flatten.flatMap({
    6.10        case binaryGate:BinaryGate => Some(binaryGate)