ParallelParenthesesBalancingRunner

package reductions

import scala.annotation._
import org.scalameter._
import common._

object ParallelParenthesesBalancingRunner {

  @volatile var seqResult = false

  @volatile var parResult = false

  val standardConfig = config(
    Key.exec.minWarmupRuns -> 40,
    Key.exec.maxWarmupRuns -> 80,
    Key.exec.benchRuns -> 120,
    Key.verbose -> true) withWarmer (new Warmer.Default)

  def main(args: Array[String]): Unit = {
    val length = 100000000
    val chars = new Array[Char](length)
    val threshold = 10000
    val seqtime = standardConfig measure {
      seqResult = ParallelParenthesesBalancing.balance(chars)
    }
    println(s"sequential result = $seqResult")
    println(s"sequential balancing time: $seqtime ms")

    val fjtime = standardConfig measure {
      parResult = ParallelParenthesesBalancing.parBalance(chars, threshold)
    }
    println(s"parallel result = $parResult")
    println(s"parallel balancing time: $fjtime ms")
    println(s"speedup: ${seqtime / fjtime}")
  }
}

object ParallelParenthesesBalancing {

  // mine
  //Returns `true` iff the parentheses in the input `chars` are balanced.

  def balance(chars: Array[Char]): Boolean = {
    // pattern matching takes too long in run main !!! but passes coursera Autograder tests
    def count(txt: Array[Char], acc: Int): Boolean = {
      if (acc >= 0) {
        if (txt.length == 0) acc == 0
        else {
          txt.head match {
            case '\u0028' => count(txt.tail, acc + 1)
            case '\u0029' => count(txt.tail, acc - 1)
            case _ => count(txt.tail, acc)
          }
        }
      } else false
    }
    count(chars, 0) == true


    // OR THIS MORE MODULAR  FUNCTIONAL VERSION much faster solution
    /*if (chars.iterator.contains('\u0028') || chars.iterator.contains('\u0029')) {
      (chars.count(i => i == '\u0028') == chars.count(i => i == '\u0029')
        &&
        chars.indexOf('\u0028') < chars.indexOf('\u0029'))

    } else true

  */
    }

  /*but test failed [Test Description] balance should work for sequence of parentheses without nesting
[Observed Error] true did not equal false balance(())() should be false
[Lost Points] 5
*/

  def parBalance(chars: Array[Char], threshold: Int): Boolean = {

    var global = 0
    var segment = 0

    // sequential traversal
    def traverse(idx: Int, until: Int, openAcc: Int, closeAcc: Int): (Int, Int) = {
      var i = idx
      var open = openAcc
      var close = closeAcc
      var balance = 0

      while (i < until) {
        if (chars(i) == '\u0028') { open += 1; balance += 1 }
        else if (chars(i) == '\u0029') {
          // we close brackets as soon as we can
          if (balance > 0) { balance -= 1; open -= 1 } else { close += 1 }
        }
        i += 1
      }
      (close, open)
    }

    // parallel reduction
    def reduce(from: Int, until: Int): (Int, Int) = {
      if (until - from <= threshold) {
        traverse(from, until, 0, 0)
      } else {
        val mid = from + (until - from) / 2
        val (left, right) = parallel(reduce(from, mid), reduce(mid, until))
        // if an open bracket can be closed by next pair we close it
        List(left, right).reduceLeft((x, y) => if (x._2 >= y._1) { (x._1, math.abs(x._2 - y._1) + y._2) } else { (x._1 + math.abs(x._2 - y._1), y._2) })
      }
    }
    reduce(0, chars.length) == (0, 0)
  }
}