/* Functional Programming in Scala, Strictness and Lazinesss 
   Adapted by H. Conrad Cunningham from FPS Chapter 5 and associated
   notes.

1234567890123456789012345678901234567890123456789012345678901234567890

2016-04-XX: Adapted from FPS Ch. 5 code and notes
2019-03-12: Renamed Stream to be StreamC to avoid conflicts;
            Reformatted some lines

*/

import StreamC._
sealed trait StreamC[+A] {

  def headOption: Option[A] = this match {
    case Empty     => None
    case Cons(h,t) => Some(h()) // force thunk
  }

  def toListRecursive: List[A] = this match {
    case Cons(h,t) => h() :: t().toListRecursive // force thunks
    case _         => List()
  }

  def toList: List[A] = {
    @annotation.tailrec
    def go(s: StreamC[A], acc: List[A]): List[A] = s match {
      case Cons(h,t) => go(t(), h() :: acc) // force thunks
      case _         => acc
    }
    go(this, List()).reverse
  }

  def toListFast: List[A] = {
    val buf = new collection.mutable.ListBuffer[A]
    @annotation.tailrec
    def go(s: StreamC[A]): List[A] = s match {
      case Cons(h,t) =>
        buf += h() // force head thunk, add to end of buffer
        go(t())    // force tail thunk, process recursively
      case _         => buf.toList  // convert to immutable list
    }
    go(this)
  }

  def take(n: Int): StreamC[A] = this match {
    case Cons(h, t) if n > 1  => cons(h(), t().take(n - 1))
    case Cons(h, _) if n == 1 => cons(h(), empty)
    case _ => empty  // stream empty or n < 1
  }

  @annotation.tailrec
  final def drop(n: Int): StreamC[A] = this match {
    case Cons(_, t) if n > 0 => t().drop(n - 1)
    case _ => this
  }

  def takeWhile(p: A => Boolean): StreamC[A] = this match {
    case Cons(h,t) if p(h()) => cons(h(), t() takeWhile p)
    case _ => empty
  }

  def exists(p: A => Boolean): Boolean = this match {
    case Cons(h,t) => p(h()) || t().exists(p)
    case _         => false
  }

  def foldRight[B](z: => B)(f: (A, => B) => B): B = this match {
    case Cons(h,t) => f(h(), t().foldRight(z)(f)) 
    case _         => z
  }

  def exists2(p: A => Boolean): Boolean =
    foldRight(false)((a, b) => p(a) || b) 

  def map[B](f: A => B): StreamC[B] =
    foldRight(empty[B])((h,t) => cons(f(h), t))
			
  def filter(p: A => Boolean): StreamC[A] =
    foldRight(empty[A])((h,t) => if (p(h)) cons(h, t) else t)
			
  def append[B >: A](s: => StreamC[B]): StreamC[B] =
    foldRight(s)((h,t) => cons(h,t))

  def flatMap[B](f: A => StreamC[B]): StreamC[B] =
    foldRight(empty[B])((h,t) => f(h) append t)

  def withFilter = filter _

}

case object Empty extends StreamC[Nothing]
case class Cons[+A](h: () => A, t: () => StreamC[A])
    extends StreamC[A]

object StreamC {

  def cons[A](hd: => A, tl: => StreamC[A]): StreamC[A] = {
    lazy val head = hd    // cache values once computed
    lazy val tail = tl
    Cons(() => head, () => tail)  // create thunks for Cons
  }

  def empty[A]: StreamC[A] = Empty

  def apply[A](as: A*): StreamC[A] =
    if (as.isEmpty) empty else cons(as.head, apply(as.tail: _*))

  def constant[A](a: A): StreamC[A] = {
    lazy val tail: StreamC[A] = Cons(() => a, () => tail)
    tail
  }

  def from(n: Int): StreamC[Int] =
    cons(n, from(n+1))

  def unfold[A, S](z: S)(f: S => Option[(A, S)]): StreamC[A] =
    f(z) match {
      case Some((h,s)) => cons(h, unfold(s)(f))
      case None => empty
    }

  val onesViaUnfold = unfold(1)(_ => Some((1,1)))

  def constantViaUnfold[A](a: A) =
    unfold(a)(_ => Some((a,a)))

  def fromViaUnfold(n: Int) =
    unfold(n)(n => Some((n,n+1)))

  val fibsViaUnfold =
    unfold((0,1)) { case (f0,f1) => Some((f0,(f1,f0+f1))) }

}


object TestStreamC {

  def main(args: Array[String]) {

    println("")

    println(      "List(10,20,30,40,50).map(_ / 10).filter(_ % 2 == 1).map(_ * 100) = ")
    println(List(10,20,30,40,50).map(_ / 10).filter(_ % 2 == 1).map(_ * 100))
    println("")

    println("mfm(List(10,20,30,40,50)) = ")
    println(mfm(List(10,20,30,40,50)))
    println("")

    println("mfm2(List(10,20,30,40,50)) = ")
    println(mfm2(List(10,20,30,40,50)))
    println("")

    val seq =
      for (x <- StreamC(1,2,3,4) if x > 2; y <- StreamC(1,2)) yield x
    println("for (x <- StreamC(1,2,3,4) if x > 2; y <- StreamC(1,2)) yield x = ")
    println(seq.toList)
    println("")

    lazy val ones: StreamC[Int] = cons(1, ones)
    println(s"First 5 ones = ${ones.take(5).toList}")

    val fibs = {
      def go(f0: Int, f1: Int): StreamC[Int] =
        cons(f0, go(f1, f0+f1))
      go(0, 1)
    }

    println(s"First 25 fibs = ${fibs.take(25).toList}")

    def sieve(ints: StreamC[Int]): StreamC[Int] =
      ints.headOption match {
        case None    =>
          sys.error("Should never occur: No head on infinite list.")
        case Some(x) =>
          cons(x,sieve(ints drop 1 filter (_ % x > 0)))
      }

    val primes = sieve(from(2))

    println(s"First 50 primes: ${(primes take 50).toList}")
    println("")

    def isPrime(c: Int): Boolean =
      (primes filter (_ >= c) map (_ == c)).headOption getOrElse
        sys.error("Should not occur: No head on infinite list.")

    println(s"isPrime(37) = ${isPrime(37)}")
    println(s"isPrime(39) = ${isPrime(39)}")
}

  def mfm(xs: List[Int]): List[Int] = xs match {
    case Nil     => Nil 
    case (y::ys) => 
       val z = y / 10 
       if (z % 2 == 1) (z*100) :: mfm(ys) else mfm(ys) 
  }

  def mfm2(xs: List[Int]): List[Int] =
    xs collect { case y if ((y/10) % 2 == 1) => y*10 }

}