package pipelining:

  import minilog._

  object factory:

    /** Helper functions for building a pipelined multiplier. */
    
    def buildAdder0(aa: Bus, bb: Bus, c0v: Boolean) =
      new Bus(
      ((aa zip bb).scanLeft((aa.host.False, if c0v then aa.host.True else aa.host.False))) {
        case ((s,c),(a,b)) =>
          (a+b+c,(a && b)||(a && c)||(b && c))  // sum-mod-2, majority-of-3
      }.drop(1).map(_._1))
    end buildAdder0

    def buildAdder(aa: Bus, bb: Bus) = buildAdder0(aa, bb, false)

    /**
    * This task asks you to implement a builder for a pipelined multiplier
    * for two operands "aa" and "bb" with identical length n, where n is 
    * a positive integer power of 2.
    *
    * The multiplier takes as input the operand buses "aa" and "bb", and outputs
    * a bus of length 2*n that supplies the output from the pipeline. Let us
    * refer to the output bus as "result" in what follows.
    *
    * The multiplier must meet the following, more detailed specification.
    * All of the following requirements must be met:
    *
    * 1)
    * At every time step t=0,1,2,... we may feed a pair of operands 
    * into the multiplier by setting the input buses "aa" and "bb" equal to 
    * the values to be multiplied, and clocking the circuit. 
    * Let us refer to these operands as the _operands at time t_. 
    *
    * 2)
    * At time step t + log2(n) - 1 the value of "result" must be equal to the
    * product of the operands at time t, for every t=0,1,2,...
    * That is, the pipeline is to consist of log2(n) stages.
    *
    * 3)
    * The circuit depth must not exceed 20*n. 
    * [Bonus: you may want to use shallow adders from Round 3 to reduce 
    *         the depth further for large values of n!]
    *
    * Your function should return the bus "result".
    *
    * Hints: 
    * Please refer to the pictures illustrating pipelined circuits in the 
    * assignment material and the study material for Round 3. You will need 
    * to build internal state elements (that is, input elements) to connect 
    * the stages of the pipeline. You can do this by first getting the host 
    * circuit (e.g. by calling aa.host) and then requesting one more buses 
    * of input elements from the host. A multiplier can be constructed
    * by zeroing-or-shifting one operand 0,1,...,n-1 bits to the left and 
    * taking the sum of the n results. This sum can be structured as 
    * a perfect binary tree with log2(n) adders along any path from the root 
    * to a leaf. One approach to solve this assignment is to structure the 
    * stages of the pipeline so that each stage of the pipeline is 
    * essentially "one adder deep". That is, each stage carries out the 
    * summation associated with one _level_ in the perfect binary tree.
    * A helper function for building adders is given above. 
    * Use Trigger to test your design. 
    * Yet again the object "play" may be helpful. 
    *
    */
    def buildPipelinedMultiplier(aa: Bus, bb: Bus): Bus =
      ???
    end buildPipelinedMultiplier

minilog:
package minilog

import scala.collection.{SpecificIterableFactory, StrictOptimizedSeqOps, mutable}
import collection.SeqOps

/** A custom collection for bus-level building. */
sealed class Bus(gates: Seq[Gate]) extends Seq[Gate]
    with SeqOps[Gate, Seq, Bus]
    with StrictOptimizedSeqOps[Gate, Seq, Bus]:

  /* Relegate to underlying sequence object. */
  def host = gates.head.host
  def length = gates.length
  def apply(idx: Int) = gates.apply(idx)
  def apply(idxs: Seq[Int]) = new Bus(idxs.map(gates(_)))
  def iterator = gates.iterator

  /** Returns the values of the gates in the bus. */
  def values = gates.map(_.value)

  /** Returns the gate-wise AND of the gates in the left operand with the right operand. */
  def &&(that: Gate) = new Bus(this.map(_ && that))

  /** Returns the gate-wise OR of the gates in the left operand with the right operand. */
  def ||(that: Gate) = new Bus(this.map(_ || that))

  /** Returns the gate-wise XOR of the gates in the left operand with the right operand. */
  def +(that: Gate)  = new Bus(this.map(_ + that))

  /** Returns the NOT of all gates in the operand. */
  def unary_~        = this.map(!_)

  /** Returns the gate-wise AND of its operands. */
  def &(that: Bus)   = new Bus((this zip that).map(x => x._1 && x._2))

  /** Returns the gate-wise OR of its operands. */
  def |(that: Bus)   = new Bus((this zip that).map(x => x._1 || x._2))

  /** Returns the gate-wise XOR of its operands. */
  def ^(that: Bus)   = new Bus((this zip that).map(x => x._1 + x._2))

  /** Builds feedbacks to each gate (input element) in the bus from the corresponding 
    * gate in the operand. */
  def buildFeedback(that: Bus) : Unit =
    require(this.length == that.length,"Can only build feedback between buses of same length.")
    (this zip that).foreach(x => x._1.buildFeedback(x._2))
  end buildFeedback

  /* Because Bus is a custom collection (based on Seq) with SeqOps trait
     we need to override a a few methods so that it can inherit all of the
     standard operations from the trait while still behaving as a Bus as
     much as possible.
     If you are interested, see the RNA exampe at 
     https://docs.scala-lang.org/overviews/core/custom-collections.html#final-version-of-rna-strands-class
   */

  // Mandatory overrides of `fromSpecific`, `newSpecificBuilder`,
  // and `empty`, from `IterableOps`
  override protected def fromSpecific(coll: IterableOnce[Gate]): Bus =
    Bus.fromSpecific(coll)

  override protected def newSpecificBuilder: mutable.Builder[Gate, Bus] =
    Bus.newBuilder

  override def empty: Bus = Bus.empty

  // Overloading of `appended`, `prepended`, `appendedAll`, `prependedAll`,
  // `map`, `flatMap` and `concat` to return a `Bus` when possible
  def concat(suffix: IterableOnce[Gate]): Bus =
    strictOptimizedConcat(suffix, newSpecificBuilder)

  @inline final def ++ (suffix: IterableOnce[Gate]): Bus = concat(suffix)

  def appended(base: Gate): Bus =
    (newSpecificBuilder ++= this += base).result()

  def appendedAll(suffix: Iterable[Gate]): Bus =
    strictOptimizedConcat(suffix, newSpecificBuilder)

  def prepended(base: Gate): Bus =
    (newSpecificBuilder += base ++= this).result()

  def prependedAll(prefix: Iterable[Gate]): Bus =
    (newSpecificBuilder ++= prefix ++= this).result()

  def map(f: Gate => Gate): Bus =
    strictOptimizedMap(newSpecificBuilder, f)

  def flatMap(f: Gate => IterableOnce[Gate]): Bus =
    strictOptimizedFlatMap(newSpecificBuilder, f)

  // The class name will by default be shown as 'Seq', we don't want that.
  override def className = "Bus"

end Bus

/** A companion builder for class Bus. */
object Bus extends SpecificIterableFactory[Gate, Bus]:
  
  def empty: Bus = new Bus(Seq.empty)

  def newBuilder: mutable.Builder[Gate,Bus] =
    mutable.ArrayBuffer.newBuilder[Gate]
    .mapResult(s=>new Bus(s.toSeq))

  def fromSpecific(it: IterableOnce[Gate]): Bus = it match
    case seq: Seq[Gate] => new Bus(seq)
    case _ => new Bus(it.iterator.toSeq)

end Bus

package minilog

import collection.immutable.Queue

/** A host class for gates with factory methods for input elements and constant gates. */
sealed class Circuit():

  /* Hosting mechanisms for gates and input elements (internal to package). */

  /** Constructed gates register here. */
  private var gates  = Queue[Gate]()

  /** Returns the size of the circuit, i.e., the number of gates. */
  def numberOfGates(): Int = gates.size 

  /** Registers a gate with its host. */
  private[minilog] def registerGate(g: Gate) = 
    gates = gates :+ g
    dirty = true 
  end registerGate

  /** Constructed inputs register here. */
  private var ins = Queue[InputElement]()  

  /** Registers an input element with its host. */
  private[minilog] def registerInput(g: InputElement) = { ins = ins :+ g }

  /* Memoization and clean/dirty interface 
   * (internal to classes Gate and Circuit). */

  /** Flag: must recompute the memorized values (if any)? */
  private[minilog] var dirty = false

  /** Recomputes the memorized gate values. */ 
  private[minilog] def clean() = 
    dirty = false            // clear dirty before eval, otherwise infinite loop
    gates.foreach(_.clean()) // update and memorize values at gates
  end clean

  /** Circuit depth. */
  def depth =  if gates.isEmpty then 0 else gates.map(_.depth).max 

  /* Interface for feedback hooks. */

  /** Feedback hooks register here. */ 
  private var hooks = Queue[() => (() => Unit)]()

  /** Builds a feedback hook. */
  def buildFeedbackHook(hook: () =>  (() => Unit)) = { hooks = hooks :+ hook } 

  /** Executes feedback. */
  def clock() =
    val writehooks = hooks.map(_()) // run read hooks
    (ins zip ins.map(_.feedbackValue)).foreach((w,v) => w.set(v))
    writehooks.foreach(_())         // run write hooks
  end clock

  /* Static objects and builders. */

  /** A static gate that evaluates to false. */
  val False: Gate = new ConstantGate(this, false)

  /** A static gate that evaluates to true. */
  val True: Gate  = new ConstantGate(this, true)

  /** Returns a new input element. */
  def input()        = new InputElement(this)

  /** Returns a bus of n new input elements. */
  def inputs(n: Int) = new Bus((1 to n).map(x => input()))

  /** Returns a new bus of n constant gates that evaluate to false. */
  def falses(n: Int) = new Bus((1 to n).map(x => False))

  /** Returns a new bus of n constant gates that evaluate to true. */
  def trues(n: Int)  = new Bus((1 to n).map(x => True))

end Circuit

package minilog

/** The base class for gates.
  *
  * Build gates from existing gates with Boolean operators or
  * manufacture via factory methods in class Circuit.
  *
  */

sealed abstract class Gate(val host: Circuit):
  host.registerGate(this)       // register this gate with the host

  var depth = 0

  /** Convenience constructor for use by extending classes. */
  protected def this(inputs: Gate*) =
    this(inputs.head.host)      // host is the host of first input
    require(inputs.tail.forall(_.host == inputs.head.host))
      // fails unless all inputs have same host
    depth = 1 + inputs.map(_.depth).max
  end this

  /* Memoization and clean/dirty interface 
   * (internal to classes Gate and Circuit). */

  /** The memorized value of this gate. */
  private var memo = false              // defaults to false

  /** Updates memorized value, invoked by host. */
  private[minilog] def clean() = { memo = eval }

  /** Returns the value of this gate, implemented in extending classes. */
  protected def eval: Boolean

  /** Returns the (memorized) value of this gate. */
  def value = 
    if host.dirty then
      host.clean()       // recompute all memos if dirty
    memo                 // my memorized value is up to date, so return it

  /** Sets the value of this input element (fails on other gate types). */
  def set(v: Boolean) = { require(false) }         // fails unless input element

  /** Builds a feedback to this input element (fails on other gate types). */
  def buildFeedback(g: Gate) =
    require(false,"buildFeedback can only be called on InputElement gates. It is not possible to build feedback to non InputElement.")
  // fails unless input element

  /* Builders for basic types of gates. */

  /** Returns a new NOT-gate. */
  def unary_!     = new NotGate(this)

  /** Returns a new AND-gate. */
  def &&(that: Gate): Gate = new AndGate(this, that)

  /** Returns a new OR-gate. */
  def ||(that: Gate): Gate = new OrGate(this, that)

  /** Returns a new XOR-gate. */
  def +(that: Gate): Gate  = new XorGate(this, that)

  /** Returns a new XOR-gate. */
  def ^^(that: Gate): Gate = new XorGate(this, that)

end Gate

/** Implements an input element. */
sealed class InputElement(host: Circuit) extends Gate(host):
  host.registerInput(this)          // register the new input

  /** Value of this input element. */
  private var v = false                     // default value is false

  /** Sets the value of this input element. */
  override def set(s: Boolean) = 
    v = s                           // whenever an input is set ...
    host.dirty = true               // ... flag the host dirty 
  end set

  /** Returns the value of this input element. */
  protected def eval = v

  /** The gate from which this input element takes feedback. */
  private var feedback_from: Gate = this    // default feedback is from itself

  /** Builds a feedback to this input element. */
  override def buildFeedback(g: Gate) = 
    require(host == g.host)         // fail unless g has the same host
    feedback_from = g 
  end buildFeedback

  /** Returns the value of the feedback gate. */
  def feedbackValue = feedback_from.value
end InputElement

/** Implements a NOT gate. */
sealed class NotGate(in: Gate) extends Gate(in):
  protected def eval = !in.value
end NotGate

/** Implements an OR gate. */
sealed class OrGate(in1: Gate, in2: Gate) extends Gate(in1, in2):
  protected def eval = in1.value || in2.value
end OrGate

/** Implements an AND gate. */
sealed class AndGate(in1: Gate, in2: Gate) extends Gate(in1, in2):
  protected def eval = in1.value && in2.value
end AndGate

/** Implements a XOR gate. */
sealed class XorGate(in1: Gate, in2: Gate) extends Gate(in1, in2):
  protected def eval = (in1.value || in2.value) && !(in1.value && in2.value)
end XorGate

/** Implements a constant gate. */
sealed class ConstantGate(host: Circuit, v: Boolean) extends Gate(host):
  protected def eval = v
end ConstantGate