
package synchrony.iterators  

/** Synchrony iterators provide generalized synchronized iterations,
 *  e.g. performining a merge join, on multiple iterators. 
 *
 *  This module implements Synchrony's two main iterator structures,
 *  the "landmark track" (LmTrack) and the "experiment track" (ExTrack),
 *  where a landmark track "synchronizes" one or more "experiment track".
 *  Two predicates, isBefore and canSee, are used to define the
 *  synchronization. 
 *
 *  Intuitively, canSee(x,y) means the element x on an experiment
 *  track "can see" (i.e. is synchronized with the element y on the
 *  landmark track. And isBefore(x,y) means the position or locus of
 *  the element x on an experiment track corresponds to some position 
 *  or locus in front of the position or locus of the element y on 
 *  the landmark track.
 * 
 *  Synchrony makes some assumptions to efficiently synchronize
 *  iterators on the landmark and experiment tracks. These assumptions
 *  are the monotonocity conditions (i) and (ii), and the antimonotonicity
 *  conditions (iii) - (iv) below. Let x and y be elements on a 
 *  specific track (i.e. in the same file/iterator). Let x << y means
 *  the physical position of x is in front of the physical position of 
 *  y in the file/iterator (i.e. an iteration on the track is going to
 *  encounter x before y. Then the monotonicity and antimonotonicty
 *  conditions sufficient to ensure correctness are:
 * 
 *    (i) x << x' iff for all y in Y: y isBefore x implies y isBefore x'.
 * 
 *   (ii) y' << y iff for all x in X: y isBefore x implies y' isBefore x.
 * 
 *  (iii) If x << x', then for all y in Y: y isBefore x, and not y canSee x,
 *                                         implies not y canSee x'.
 * 
 *   (iv) If y << y', then for all x in X: not y isBefore x, and not y canSee x,
 *                                         implies not y' canSee x.
 * 
 * Wong Limsoon
 * 17 May 2020
 *
 */


object SyncFolds {


  import synchrony.iterators.SyncCollections._


  var DEBUG = true



  case class SyncFold[A, B, C](
    iter: (A, B, C) => C,
    zero: C,
    isBefore: (B, A) => Boolean,
    canSee: (B, A) => Boolean) {
  
    def apply(xs: Vector[A], ys: Vector[B]): C = {

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.
      // The monotonicity of isBefore can be guaranteed if 
      // xs and ys are sorted in a way consistent with isBefore.

      def aux(xs: Vector[A], ys: Vector[B], zs: Vector[B], acc: C): C = { 
   
        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {

          case (true, _, _)    => acc

          case (_, true, true) => acc

          case (_, true, false) => aux(xs, zs, Vector(), acc)

          case _ =>

            val (x,y) = (xs.head, ys.head)

            if (isBefore(y,x) && !canSee(y,x)) { 

              // isBefore(y,x) and !canSee(y,x) implies 
              // forall x' after x: !canSeee(y,x').
              // So y can be discarded safely, no need to save it in zs.

              aux(xs, ys.tail, zs, acc)
            }  

            else if (!isBefore(y,x) && !canSee(y,x)) {

              // !isBefore(y,x) and !canSee(y,x) implies 
              // forall y' after y: !canSee(y',x).
              // So x can be discarded safely. But the next x may still be
              // able to see some y saved earlier in zs. 

              aux(xs.tail, zs ++ ys, Vector(), acc) 
            }

            else if (ys.tail.isEmpty) {

              // At this point, canSee(y,x); so process (x,y) using iter.
              // If there is no more y, then we are finished with
              // this x; so move on to the next x.  Note that, 
              // the next x may still be able to see this y;
              // so save it in zs. 

              aux(xs.tail, zs ++ ys, Vector(), iter(x, y, acc))
            }

            else aux(xs, ys.tail, zs :+ y, iter(x, y, acc))
          }
        }

        aux(xs, ys, Vector(), zero)
      }



   def apply(xs: EIterator[A], ys: EIterator[B]): C = {

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(xs: EIterator[A], ys: EIterator[B], zs:Vector[B], acc: C): C = { 
   
        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {
          case (true, _, _)    => acc
          case (_, true, true) => acc
          case (_, true, false) => aux(xs, EIterator(zs), Vector(), acc)
          case _ =>
            val (x,y) = (xs.head, ys.head)
            if (isBefore(y,x) && !canSee(y,x)) { 
              aux(xs, ys.tail(), zs, acc) }  
            else if (!isBefore(y,x) && !canSee(y,x)) {
              aux(xs.tail(), zs ++: ys, Vector(), acc) 
            }
            else if (ys.lookahead(2).drop(1).isEmpty) {
              aux(xs.tail(), zs ++: ys, Vector(), iter(x, y, acc))
            }
            else {
              aux(xs, ys.tail(), zs :+ y, iter(x, y, acc))
            }
          }
        }

        try { aux(xs, ys, Vector(), zero) }
        finally { xs.close(); ys.close() }
      }

  }  // End class SyncFold



  case class SyncFoldGrp[A,B,C](
    iter:  (A, Vector[B], C) => C, 
    zero:  C,
    isBefore: (B,A) => Boolean,
    canSee: (B,A) => Boolean)  {


    def apply(xs: Vector[A], ys: Vector[B]): C = { 

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(xs: Vector[A], ys: Vector[B], zs: Vector[B], acc:C):C = { 

        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {

          case (true, _, _)     => acc

          case (_, true, true)  => acc

          case (_, true, false) => aux(xs, zs, Vector(), acc) 

          case _ =>
    
            val (x, y) = (xs.head, ys.head)
            if (isBefore(y, x) && !canSee(y, x)) {

              // isBefore(y,x) and !canSee(y,x) implies 
              // forall x' after x: !canSeee(y,x').
              // So y can be discarded safely, no need to save it in zs.

              aux(xs, ys.tail, zs, acc)
            }

            else if (!isBefore(y, x) && !canSee(y, x)) {

              // !isBefore(y,x) and !canSee(y,x) implies 
              // forall y' after y: !canSee(y',x).
              // So x can be discarded safely. But the next x may still be
              // able to see some y saved earlier in zs. Also, still need
              // to process x with iter and what's been accumulated so far
              // in zs. 

              aux(xs.tail, zs ++ ys, Vector(), iter(x, zs, acc) 
            }

            else if (ys.tail.isEmpty) {

              // At this point, canSee(y,x). If there is no more y, 
              // then we are finished with this x; so process x using
              // iter and what's been accumulated in zs so far. And
              // can also move on to the next x.  Note that, the next
              // x may still be able to see this y; so keep it in ys.  

              aux(xs.tail, zs++ys, Vector(), iter(x, zs, acc))
            }

            else {

              // At this poinr, canSee(y, x). But there maybe more y
              // in ys that can see x. So keep accumulating in zs.

              aux(xs, ys.tail, zs :+ y, acc) 
           }
        }
      }
  
      aux(xs, ys, Vector(), zero)
    }



   def apply(xs: EIterator[A], ys: EIterator[B]): C = { 

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(xs: EIterator[A], ys: EIterator[B], zs: Vector[B], acc: C): C = { 

        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {
          case (true, _, _)     => acc
          case (_, true, true)  => acc
          case (_, true, false) => aux(xs, EIterator(zs), Vector(), acc) 
          case _ =>
    
            val (x, y) = (xs.head, ys.head)

            if (isBefore(y, x) && !canSee(y, x)) {
              aux(xs, ys.tail, zs, acc)
            }
            else if (!isBefore(y, x) && !canSee(y, x)) {
              aux(xs.tail, zs ++ ys, Vector(), iter(x, zs, acc) 
            } 
            else if (ys.lookahead(2).drop(1).isEmpty) {
              aux(xs.tail, zs ++: ys, Vector(), iter(x, zs, acc))
            }
            else aux(xs, ys.tail, zs :+ y, acc) 
        }
      }
  
      aux(xs, ys, Vector(), zero)
    }

  }  // End class SyncFoldGrp





  case class SyncMap[A, B, C](
    iter: (A, B) => C,
    isBefore: (B, A) => Boolean,
    canSee: (B, A) => Boolean) {
  
    def apply(xs: Vector[A], ys: Vector[B]): Vector[C] = {

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(
        xs: Vector[A], 
        ys: Vector[B], 
        zs: Vector[B], 
        acc: Vector[C]): 
      Vector[C] = { 
   
        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {

          case (true, _, _)    => acc

          case (_, true, true) => acc

          case (_, true, false) => aux(xs, zs, Vector(), acc)

          case _ =>

            val (x,y) = (xs.head, ys.head)

            if (isBefore(y,x) && !canSee(y,x)) { 

              // isBefore(y,x) and !canSee(y,x) implies 
              // forall x' after x: !canSeee(y,x').
              // So y can be discarded safely, no need to save it in zs.

              aux(xs, ys.tail, zs, acc)
            }  

            else if (!isBefore(y,x) && !canSee(y,x)) {

              // !isBefore(y,x) and !canSee(y,x) implies 
              // forall y' after y: !canSee(y',x).
              // So x can be discarded safely. But the next x may still be
              // able to see some y saved earlier in zs. 

              aux(xs.tail, zs ++ ys, Vector(), acc) 
            }

            else if (ys.tail.isEmpty) {

              // At this point, canSee(y,x); so process (x,y) using iter.
              // If there is no more y, then we are finished with
              // this x; so move on to the next x.  Note that, 
              // the next x may still be able to see this y;
              // so save it in zs. 

              aux(xs.tail, zs ++ ys, Vector(), acc :+ iter(x, y))
            }

            else aux(xs, ys.tail, zs :+ y, acc :+ iter(x, y))
          }
        }

        aux(xs, ys, Vector(), Vector())
      }



   def apply(xs: EIterator[A], ys: EIterator[B]): Vector[C] = {

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(
        xs: EIterator[A], 
        ys: EIterator[B], 
        zs:Vector[B], 
        acc: Vector[C]): 
     Vector[C] = { 
   
        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {
          case (true, _, _)    => acc
          case (_, true, true) => acc
          case (_, true, false) => aux(xs, EIterator(zs), Vector(), acc)
          case _ =>
            val (x,y) = (xs.head, ys.head)
            if (isBefore(y,x) && !canSee(y,x)) { 
              aux(xs, ys.tail(), zs, acc) }  
            else if (!isBefore(y,x) && !canSee(y,x)) {
              aux(xs.tail(), zs ++: ys, Vector(), acc) 
            }
            else if (ys.lookahead(2).drop(1).isEmpty) {
              aux(xs.tail(), zs ++: ys, Vector(), acc :+ iter(x, y))
            }
            else {
              aux(xs, ys.tail(), zs :+ y, acc :+ iter(x, y))
            }
          }
        }

        try { aux(xs, ys, Vector(), Vector()) }
        finally { xs.close(); ys.close() }
      }

  }  // End SyncMap



  case class SyncMapGrp[A,B,C](
    iter:  (A, Vector[B]) => C, 
    isBefore: (B,A) => Boolean,
    canSee: (B,A) => Boolean)  {


    def apply(xs: Vector[A], ys: Vector[B]): Vector[C] = { 

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(
        xs: Vector[A], 
        ys: Vector[B], 
        zs: Vector[B], 
        acc: Vector[C]): 
      Vector[C] = { 

        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {
          case (true, _, _)     => acc
          case (_, true, true)  => acc
          case (_, true, false) => aux(xs, zs, Vector(), acc) 
          case _ =>
    
            val (x, y) = (xs.head, ys.head)
            if (isBefore(y, x) && !canSee(y, x)) {
              aux(xs, ys.tail, zs, acc)
            }
            else if (!isBefore(y, x) && !canSee(y, x)) {
              aux(xs.tail, zs ++ ys, Vector(), acc :+ iter(x, zs) 
            }
            else if (ys.tail.isEmpty) {
              aux(xs.tail, zs++ys, Vector(), acc :+ iter(x, zs))
            }
            else aux(xs, ys.tail, zs :+ y, acc) 
        }
      }
  
      aux(xs, ys, Vector(), zero)
    }



   def apply(xs: EIterator[A], ys: EIterator[B]): Vector[C] = { 

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(
        xs: EIterator[A], 
        ys: EIterator[B], 
        zs: Vector[B], 
        acc: Vector[C]): 
      Vector[C] = { 

        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {
          case (true, _, _)     => acc
          case (_, true, true)  => acc
          case (_, true, false) => aux(xs, EIterator(zs), Vector(), acc) 
          case _ =>
    
            val (x, y) = (xs.head, ys.head)

            if (isBefore(y, x) && !canSee(y, x)) {
              aux(xs, ys.tail, zs, acc)
            }
            else if (!isBefore(y, x) && !canSee(y, x)) {
              aux(xs.tail, zs ++: ys, Vector(), acc :+ iter(x, zs) 
            } 
            else if (ys.lookahead(2).drop(1).isEmpty) {
              aux(xs.tail, zs ++: ys, Vector(), acc :+ iter(x, zs))
            }
            else aux(xs, ys.tail, zs :+ y, acc) 
        }
      }
      aux(xs, ys, Vector(), zero)
    }

  }  // End class SyncMapGrp




  case class SyncFlatMap[A, B, C](
    iter: (A, B) => Vector[C],
    isBefore: (B, A) => Boolean,
    canSee: (B, A) => Boolean) {
  
    def apply(xs: Vector[A], ys: Vector[B]): Vector[C] = {

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(
        xs: Vector[A], 
        ys: Vector[B], 
        zs: Vector[B], 
        acc: Vector[C]): 
      Vector[C] = { 
   
        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {

          case (true, _, _)    => acc

          case (_, true, true) => acc

          case (_, true, false) => aux(xs, zs, Vector(), acc)

          case _ =>

            val (x,y) = (xs.head, ys.head)

            if (isBefore(y,x) && !canSee(y,x)) { 

              // isBefore(y,x) and !canSee(y,x) implies 
              // forall x' after x: !canSeee(y,x').
              // So y can be discarded safely, no need to save it in zs.

              aux(xs, ys.tail, zs, acc)
            }  

            else if (!isBefore(y,x) && !canSee(y,x)) {

              // !isBefore(y,x) and !canSee(y,x) implies 
              // forall y' after y: !canSee(y',x).
              // So x can be discarded safely. But the next x may still be
              // able to see some y saved earlier in zs. 

              aux(xs.tail, zs ++ ys, Vector(), acc) 
            }

            else if (ys.tail.isEmpty) {

              // At this point, canSee(y,x); so process (x,y) using iter.
              // If there is no more y, then we are finished with
              // this x; so move on to the next x.  Note that, 
              // the next x may still be able to see this y;
              // so save it in zs. 

              aux(xs.tail, zs ++ ys, Vector(), acc ++ iter(x, y))
            }

            else aux(xs, ys.tail, zs :+ y, acc ++ iter(x, y))
          }
        }

        aux(xs, ys, Vector(), Vector())
      }



   def apply(xs: EIterator[A], ys: EIterator[B]): Vector[C] = {

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(
        xs: EIterator[A], 
        ys: EIterator[B], 
        zs:Vector[B], 
        acc: Vector[C]): 
     Vector[C] = { 
   
        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {
          case (true, _, _)    => acc
          case (_, true, true) => acc
          case (_, true, false) => aux(xs, EIterator(zs), Vector(), acc)
          case _ =>
            val (x,y) = (xs.head, ys.head)
            if (isBefore(y,x) && !canSee(y,x)) { 
              aux(xs, ys.tail(), zs, acc) }  
            else if (!isBefore(y,x) && !canSee(y,x)) {
              aux(xs.tail(), zs ++: ys, Vector(), acc) 
            }
            else if (ys.lookahead(2).drop(1).isEmpty) {
              aux(xs.tail(), zs ++: ys, Vector(), acc ++ iter(x, y))
            }
            else {
              aux(xs, ys.tail(), zs :+ y, acc ++ iter(x, y))
            }
          }
        }

        try { aux(xs, ys, Vector(), Vector()) }
        finally { xs.close(); ys.close() }
      }

  }  // End SyncFlatMap



  case class SyncFlatMapGrp[A,B,C](
    iter:  (A, Vector[B]) => Vector[C], 
    isBefore: (B,A) => Boolean,
    canSee: (B,A) => Boolean)  {


    def apply(xs: Vector[A], ys: Vector[B]): Vector[C] = { 

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(
        xs: Vector[A], 
        ys: Vector[B], 
        zs: Vector[B], 
        acc: Vector[C]): 
      Vector[C] = { 

        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {
          case (true, _, _)     => acc
          case (_, true, true)  => acc
          case (_, true, false) => aux(xs, zs, Vector(), acc) 
          case _ =>
    
            val (x, y) = (xs.head, ys.head)
            if (isBefore(y, x) && !canSee(y, x)) {
              aux(xs, ys.tail, zs, acc)
            }
            else if (!isBefore(y, x) && !canSee(y, x)) {
              aux(xs.tail, zs ++ ys, Vector(), acc ++ iter(x, zs) 
            }
            else if (ys.tail.isEmpty) {
              aux(xs.tail, zs++ys, Vector(), acc ++ iter(x, zs))
            }
            else aux(xs, ys.tail, zs :+ y, acc) 
        }
      }
  
      aux(xs, ys, Vector(), zero)
    }



   def apply(xs: EIterator[A], ys: EIterator[B]): Vector[C] = { 

      // Requires: isBefore is monotonic wrt (xs, ys) 
      //      and  canSee is antimonotonic wrt isBefore.

      def aux(
        xs: EIterator[A], 
        ys: EIterator[B], 
        zs: Vector[B], 
        acc: Vector[C]): 
      Vector[C] = { 

        (xs.isEmpty, ys.isEmpty, zs.isEmpty) match {
          case (true, _, _)     => acc
          case (_, true, true)  => acc
          case (_, true, false) => aux(xs, EIterator(zs), Vector(), acc) 
          case _ =>
    
            val (x, y) = (xs.head, ys.head)

            if (isBefore(y, x) && !canSee(y, x)) {
              aux(xs, ys.tail, zs, acc)
            }
            else if (!isBefore(y, x) && !canSee(y, x)) {
              aux(xs.tail, zs ++: ys, Vector(), acc ++ iter(x, zs) 
            } 
            else if (ys.lookahead(2).drop(1).isEmpty) {
              aux(xs.tail, zs ++: ys, Vector(), acc ++ iter(x, zs))
            }
            else aux(xs, ys.tail, zs :+ y, acc) 
        }
      }
      aux(xs, ys, Vector(), zero)
    }

  }  // End class SyncFlatMapGrp




} // End SyncFolds






