package scala.collection.parallel
import scala.collection.mutable.Builder
import scala.collection.mutable.ArrayBuffer
import scala.collection.IterableLike
import scala.collection.Parallel
import scala.collection.Parallelizable
import scala.collection.CustomParallelizable
import scala.collection.generic._
import scala.collection.GenIterableLike
import scala.collection.GenIterable
import scala.collection.GenTraversableOnce
import scala.collection.GenTraversable
import immutable.HashMapCombiner
import java.util.concurrent.atomic.AtomicBoolean
import annotation.unchecked.uncheckedVariance
trait ParIterableLike[+T, +Repr <: ParIterable[T], +Sequential <: Iterable[T] with IterableLike[T, Sequential]]
extends GenIterableLike[T, Repr]
with CustomParallelizable[T, Repr]
with Parallel
with HasNewCombiner[T, Repr]
{
self: ParIterableLike[T, Repr, Sequential] =>
import tasksupport._
def seq: Sequential
def repr: Repr = this.asInstanceOf[Repr]
trait ParIterator extends IterableSplitter[T] {
me: SignalContextPassingIterator[ParIterator] =>
var signalDelegate: Signalling = IdleSignalling
def repr = self.repr
def split: Seq[IterableSplitter[T]]
}
trait SignalContextPassingIterator[+IterRepr <: ParIterator] extends ParIterator {
abstract override def split: Seq[IterRepr] = {
val pits = super.split
pits foreach { _.signalDelegate = signalDelegate }
pits.asInstanceOf[Seq[IterRepr]]
}
}
def hasDefiniteSize = true
def nonEmpty = size != 0
protected[parallel] def splitter: IterableSplitter[T]
def iterator: Splitter[T] = splitter
override def par: Repr = repr
def isStrictSplitterCollection = true
def threshold(sz: Int, p: Int): Int = thresholdFromSize(sz, p)
protected def reuse[S, That](oldc: Option[Combiner[S, That]], newc: Combiner[S, That]): Combiner[S, That] = newc
type SSCTask[R, Tp] = StrictSplitterCheckTask[R, Tp]
trait TaskOps[R, Tp] {
def mapResult[R1](mapping: R => R1): ResultMapping[R, Tp, R1]
def compose[R3, R2, Tp2](t2: SSCTask[R2, Tp2])(resCombiner: (R, R2) => R3): SeqComposite[R, R2, R3, SSCTask[R, Tp], SSCTask[R2, Tp2]]
def parallel[R3, R2, Tp2](t2: SSCTask[R2, Tp2])(resCombiner: (R, R2) => R3): ParComposite[R, R2, R3, SSCTask[R, Tp], SSCTask[R2, Tp2]]
}
trait BuilderOps[Elem, To] {
trait Otherwise[Cmb] {
def otherwise(notbody: => Unit)(implicit m: ClassManifest[Cmb]): Unit
}
def ifIs[Cmb](isbody: Cmb => Unit): Otherwise[Cmb]
}
trait SignallingOps[PI <: DelegatedSignalling] {
def assign(cntx: Signalling): PI
}
protected implicit def task2ops[R, Tp](tsk: SSCTask[R, Tp]) = new TaskOps[R, Tp] {
def mapResult[R1](mapping: R => R1): ResultMapping[R, Tp, R1] = new ResultMapping[R, Tp, R1](tsk) {
def map(r: R): R1 = mapping(r)
}
def compose[R3, R2, Tp2](t2: SSCTask[R2, Tp2])(resCombiner: (R, R2) => R3) = new SeqComposite[R, R2, R3, SSCTask[R, Tp], SSCTask[R2, Tp2]](tsk, t2) {
def combineResults(fr: R, sr: R2): R3 = resCombiner(fr, sr)
}
def parallel[R3, R2, Tp2](t2: SSCTask[R2, Tp2])(resCombiner: (R, R2) => R3) = new ParComposite[R, R2, R3, SSCTask[R, Tp], SSCTask[R2, Tp2]](tsk, t2) {
def combineResults(fr: R, sr: R2): R3 = resCombiner(fr, sr)
}
}
protected def wrap[R](body: => R) = new NonDivisible[R] {
def leaf(prevr: Option[R]) = result = body
@volatile var result: R = null.asInstanceOf[R]
}
protected implicit def delegatedSignalling2ops[PI <: DelegatedSignalling](it: PI) = new SignallingOps[PI] {
def assign(cntx: Signalling): PI = {
it.signalDelegate = cntx
it
}
}
protected implicit def builder2ops[Elem, To](cb: Builder[Elem, To]) = new BuilderOps[Elem, To] {
def ifIs[Cmb](isbody: Cmb => Unit) = new Otherwise[Cmb] {
def otherwise(notbody: => Unit)(implicit m: ClassManifest[Cmb]) {
if (cb.getClass == m.erasure) isbody(cb.asInstanceOf[Cmb]) else notbody
}
}
}
protected[this] def bf2seq[S, That](bf: CanBuildFrom[Repr, S, That]) = new CanBuildFrom[Sequential, S, That] {
def apply(from: Sequential) = bf.apply(from.par.asInstanceOf[Repr])
def apply() = bf.apply()
}
protected[this] def sequentially[S, That <: Parallel](b: Sequential => Parallelizable[S, That]) = b(seq).par.asInstanceOf[Repr]
def mkString(start: String, sep: String, end: String): String = seq.mkString(start, sep, end)
def mkString(sep: String): String = seq.mkString("", sep, "")
def mkString: String = seq.mkString("")
override def toString = seq.mkString(stringPrefix + "(", ", ", ")")
def canEqual(other: Any) = true
def reduce[U >: T](op: (U, U) => U): U = {
executeAndWaitResult(new Reduce(op, splitter) mapResult { _.get })
}
def reduceOption[U >: T](op: (U, U) => U): Option[U] = if (isEmpty) None else Some(reduce(op))
def fold[U >: T](z: U)(op: (U, U) => U): U = {
executeAndWaitResult(new Fold(z, op, splitter))
}
def aggregate[S](z: S)(seqop: (S, T) => S, combop: (S, S) => S): S = {
executeAndWaitResult(new Aggregate(z, seqop, combop, splitter))
}
def /:[S](z: S)(op: (S, T) => S): S = foldLeft(z)(op)
def :\[S](z: S)(op: (T, S) => S): S = foldRight(z)(op)
def foldLeft[S](z: S)(op: (S, T) => S): S = seq.foldLeft(z)(op)
def foldRight[S](z: S)(op: (T, S) => S): S = seq.foldRight(z)(op)
def reduceLeft[U >: T](op: (U, T) => U): U = seq.reduceLeft(op)
def reduceRight[U >: T](op: (T, U) => U): U = seq.reduceRight(op)
def reduceLeftOption[U >: T](op: (U, T) => U): Option[U] = seq.reduceLeftOption(op)
def reduceRightOption[U >: T](op: (T, U) => U): Option[U] = seq.reduceRightOption(op)
def foreach[U](f: T => U) = {
executeAndWaitResult(new Foreach(f, splitter))
}
def count(p: T => Boolean): Int = {
executeAndWaitResult(new Count(p, splitter))
}
def sum[U >: T](implicit num: Numeric[U]): U = {
executeAndWaitResult(new Sum[U](num, splitter))
}
def product[U >: T](implicit num: Numeric[U]): U = {
executeAndWaitResult(new Product[U](num, splitter))
}
def min[U >: T](implicit ord: Ordering[U]): T = {
executeAndWaitResult(new Min(ord, splitter) mapResult { _.get }).asInstanceOf[T]
}
def max[U >: T](implicit ord: Ordering[U]): T = {
executeAndWaitResult(new Max(ord, splitter) mapResult { _.get }).asInstanceOf[T]
}
def maxBy[S](f: T => S)(implicit cmp: Ordering[S]): T = {
if (isEmpty) throw new UnsupportedOperationException("empty.maxBy")
reduce((x, y) => if (cmp.gteq(f(x), f(y))) x else y)
}
def minBy[S](f: T => S)(implicit cmp: Ordering[S]): T = {
if (isEmpty) throw new UnsupportedOperationException("empty.minBy")
reduce((x, y) => if (cmp.lteq(f(x), f(y))) x else y)
}
def map[S, That](f: T => S)(implicit bf: CanBuildFrom[Repr, S, That]): That = bf ifParallel { pbf =>
executeAndWaitResult(new Map[S, That](f, pbf, splitter) mapResult { _.result })
} otherwise seq.map(f)(bf2seq(bf))
def collect[S, That](pf: PartialFunction[T, S])(implicit bf: CanBuildFrom[Repr, S, That]): That = bf ifParallel { pbf =>
executeAndWaitResult(new Collect[S, That](pf, pbf, splitter) mapResult { _.result })
} otherwise seq.collect(pf)(bf2seq(bf))
def flatMap[S, That](f: T => GenTraversableOnce[S])(implicit bf: CanBuildFrom[Repr, S, That]): That = bf ifParallel { pbf =>
executeAndWaitResult(new FlatMap[S, That](f, pbf, splitter) mapResult { _.result })
} otherwise seq.flatMap(f)(bf2seq(bf))
def forall(pred: T => Boolean): Boolean = {
executeAndWaitResult(new Forall(pred, splitter assign new DefaultSignalling with VolatileAbort))
}
def exists(pred: T => Boolean): Boolean = {
executeAndWaitResult(new Exists(pred, splitter assign new DefaultSignalling with VolatileAbort))
}
def find(pred: T => Boolean): Option[T] = {
executeAndWaitResult(new Find(pred, splitter assign new DefaultSignalling with VolatileAbort))
}
protected[this] def cbfactory ={
() => newCombiner
}
def filter(pred: T => Boolean): Repr = {
executeAndWaitResult(new Filter(pred, cbfactory, splitter) mapResult { _.result })
}
def filterNot(pred: T => Boolean): Repr = {
executeAndWaitResult(new FilterNot(pred, cbfactory, splitter) mapResult { _.result })
}
def ++[U >: T, That](that: GenTraversableOnce[U])(implicit bf: CanBuildFrom[Repr, U, That]): That = {
if (that.isParallel && bf.isParallel) {
val other = that.asParIterable
val pbf = bf.asParallel
val copythis = new Copy(() => pbf(repr), splitter)
val copythat = wrap {
val othtask = new other.Copy(() => pbf(self.repr), other.splitter)
tasksupport.executeAndWaitResult(othtask)
}
val task = (copythis parallel copythat) { _ combine _ } mapResult {
_.result
}
executeAndWaitResult(task)
} else if (bf.isParallel) {
val pbf = bf.asParallel
val copythis = new Copy(() => pbf(repr), splitter)
val copythat = wrap {
val cb = pbf(repr)
for (elem <- that.seq) cb += elem
cb
}
executeAndWaitResult((copythis parallel copythat) { _ combine _ } mapResult { _.result })
} else {
val b = bf(repr)
this.splitter.copy2builder[U, That, Builder[U, That]](b)
for (elem <- that.seq) b += elem
b.result
}
}
def partition(pred: T => Boolean): (Repr, Repr) = {
executeAndWaitResult(new Partition(pred, cbfactory, splitter) mapResult { p => (p._1.result, p._2.result) })
}
def groupBy[K](f: T => K): immutable.ParMap[K, Repr] = {
executeAndWaitResult(new GroupBy(f, () => HashMapCombiner[K, T], splitter) mapResult {
rcb => rcb.groupByKey(cbfactory)
})
}
def take(n: Int): Repr = {
val actualn = if (size > n) n else size
if (actualn < MIN_FOR_COPY) take_sequential(actualn)
else executeAndWaitResult(new Take(actualn, cbfactory, splitter) mapResult {
_.result
})
}
private def take_sequential(n: Int) = {
val cb = newCombiner
cb.sizeHint(n)
val it = splitter
var left = n
while (left > 0) {
cb += it.next
left -= 1
}
cb.result
}
def drop(n: Int): Repr = {
val actualn = if (size > n) n else size
if ((size - actualn) < MIN_FOR_COPY) drop_sequential(actualn)
else executeAndWaitResult(new Drop(actualn, cbfactory, splitter) mapResult { _.result })
}
private def drop_sequential(n: Int) = {
val it = splitter drop n
val cb = newCombiner
cb.sizeHint(size - n)
while (it.hasNext) cb += it.next
cb.result
}
override def slice(unc_from: Int, unc_until: Int): Repr = {
val from = unc_from min size max 0
val until = unc_until min size max from
if ((until - from) <= MIN_FOR_COPY) slice_sequential(from, until)
else executeAndWaitResult(new Slice(from, until, cbfactory, splitter) mapResult { _.result })
}
private def slice_sequential(from: Int, until: Int): Repr = {
val cb = newCombiner
var left = until - from
val it = splitter drop from
while (left > 0) {
cb += it.next
left -= 1
}
cb.result
}
def splitAt(n: Int): (Repr, Repr) = {
executeAndWaitResult(new SplitAt(n, cbfactory, splitter) mapResult { p => (p._1.result, p._2.result) })
}
def scan[U >: T, That](z: U)(op: (U, U) => U)(implicit bf: CanBuildFrom[Repr, U, That]): That = if (bf.isParallel) {
val cbf = bf.asParallel
if (parallelismLevel > 1) {
if (size > 0) executeAndWaitResult(new CreateScanTree(0, size, z, op, splitter) mapResult {
tree => executeAndWaitResult(new FromScanTree(tree, z, op, cbf) mapResult {
cb => cb.result
})
}) else (cbf(self.repr) += z).result
} else seq.scan(z)(op)(bf2seq(bf))
} else seq.scan(z)(op)(bf2seq(bf))
def scanLeft[S, That](z: S)(op: (S, T) => S)(implicit bf: CanBuildFrom[Repr, S, That]) = seq.scanLeft(z)(op)(bf2seq(bf))
def scanRight[S, That](z: S)(op: (T, S) => S)(implicit bf: CanBuildFrom[Repr, S, That]) = seq.scanRight(z)(op)(bf2seq(bf))
def takeWhile(pred: T => Boolean): Repr = {
val cntx = new DefaultSignalling with AtomicIndexFlag
cntx.setIndexFlag(Int.MaxValue)
executeAndWaitResult(new TakeWhile(0, pred, cbfactory, splitter assign cntx) mapResult { _._1.result })
}
def span(pred: T => Boolean): (Repr, Repr) = {
val cntx = new DefaultSignalling with AtomicIndexFlag
cntx.setIndexFlag(Int.MaxValue)
executeAndWaitResult(new Span(0, pred, cbfactory, splitter assign cntx) mapResult {
p => (p._1.result, p._2.result)
})
}
def dropWhile(pred: T => Boolean): Repr = {
val cntx = new DefaultSignalling with AtomicIndexFlag
cntx.setIndexFlag(Int.MaxValue)
executeAndWaitResult(new Span(0, pred, cbfactory, splitter assign cntx) mapResult { _._2.result })
}
def copyToArray[U >: T](xs: Array[U]) = copyToArray(xs, 0)
def copyToArray[U >: T](xs: Array[U], start: Int) = copyToArray(xs, start, xs.length - start)
def copyToArray[U >: T](xs: Array[U], start: Int, len: Int) = if (len > 0) {
executeAndWaitResult(new CopyToArray(start, len, xs, splitter))
}
def sameElements[U >: T](that: GenIterable[U]) = seq.sameElements(that)
def zip[U >: T, S, That](that: GenIterable[S])(implicit bf: CanBuildFrom[Repr, (U, S), That]): That = if (bf.isParallel && that.isParSeq) {
val pbf = bf.asParallel
val thatseq = that.asParSeq
executeAndWaitResult(new Zip(pbf, splitter, thatseq.splitter) mapResult { _.result });
} else seq.zip(that)(bf2seq(bf))
def zipWithIndex[U >: T, That](implicit bf: CanBuildFrom[Repr, (U, Int), That]): That = this zip immutable.ParRange(0, size, 1, false)
def zipAll[S, U >: T, That](that: GenIterable[S], thisElem: U, thatElem: S)(implicit bf: CanBuildFrom[Repr, (U, S), That]): That = if (bf.isParallel && that.isParSeq) {
val pbf = bf.asParallel
val thatseq = that.asParSeq
executeAndWaitResult(new ZipAll(size max thatseq.length, thisElem, thatElem, pbf, splitter, thatseq.splitter) mapResult { _.result });
} else seq.zipAll(that, thisElem, thatElem)(bf2seq(bf))
protected def toParCollection[U >: T, That](cbf: () => Combiner[U, That]): That = {
executeAndWaitResult(new ToParCollection(cbf, splitter) mapResult { _.result });
}
protected def toParMap[K, V, That](cbf: () => Combiner[(K, V), That])(implicit ev: T <:< (K, V)): That = {
executeAndWaitResult(new ToParMap(cbf, splitter)(ev) mapResult { _.result })
}
def view = new ParIterableView[T, Repr, Sequential] {
protected lazy val underlying = self.repr
protected[this] def viewIdentifier = ""
protected[this] def viewIdString = ""
override def seq = self.seq.view
def splitter = self.splitter
def size = splitter.remaining
}
override def toArray[U >: T: ClassManifest]: Array[U] = {
val arr = new Array[U](size)
copyToArray(arr)
arr
}
override def toList: List[T] = seq.toList
override def toIndexedSeq[U >: T]: collection.immutable.IndexedSeq[U] = seq.toIndexedSeq[U]
override def toStream: Stream[T] = seq.toStream
override def toIterator: Iterator[T] = splitter
override def toBuffer[U >: T]: collection.mutable.Buffer[U] = seq.toBuffer
override def toTraversable: GenTraversable[T] = this.asInstanceOf[GenTraversable[T]]
override def toIterable: ParIterable[T] = this.asInstanceOf[ParIterable[T]]
override def toSeq: ParSeq[T] = toParCollection[T, ParSeq[T]](() => ParSeq.newCombiner[T])
override def toSet[U >: T]: immutable.ParSet[U] = toParCollection[U, immutable.ParSet[U]](() => immutable.ParSet.newCombiner[U])
override def toMap[K, V](implicit ev: T <:< (K, V)): immutable.ParMap[K, V] = toParMap[K, V, immutable.ParMap[K, V]](() => immutable.ParMap.newCombiner[K, V])
protected trait StrictSplitterCheckTask[R, Tp] extends Task[R, Tp] {
def requiresStrictSplitters = false
if (requiresStrictSplitters && !isStrictSplitterCollection)
throw new UnsupportedOperationException("This collection does not provide strict splitters.")
}
protected trait Accessor[R, Tp]
extends StrictSplitterCheckTask[R, Tp] {
protected[this] val pit: IterableSplitter[T]
protected[this] def newSubtask(p: IterableSplitter[T]): Accessor[R, Tp]
def shouldSplitFurther = pit.remaining > threshold(size, parallelismLevel)
def split = pit.split.map(newSubtask(_))
private[parallel] override def signalAbort = pit.abort
override def toString = this.getClass.getSimpleName + "(" + pit.toString + ")(" + result + ")(supername: " + super.toString + ")"
}
protected[this] trait NonDivisibleTask[R, Tp] extends StrictSplitterCheckTask[R, Tp] {
def shouldSplitFurther = false
def split = throw new UnsupportedOperationException("Does not split.")
}
protected[this] trait NonDivisible[R] extends NonDivisibleTask[R, NonDivisible[R]]
protected[this] abstract class Composite[FR, SR, R, First <: StrictSplitterCheckTask[FR, _], Second <: StrictSplitterCheckTask[SR, _]]
(val ft: First, val st: Second)
extends NonDivisibleTask[R, Composite[FR, SR, R, First, Second]] {
def combineResults(fr: FR, sr: SR): R
@volatile var result: R = null.asInstanceOf[R]
private[parallel] override def signalAbort() {
ft.signalAbort
st.signalAbort
}
protected def mergeSubtasks() {
ft mergeThrowables st
if (throwable eq null) result = combineResults(ft.result, st.result)
}
override def requiresStrictSplitters = ft.requiresStrictSplitters || st.requiresStrictSplitters
}
protected[this] abstract class SeqComposite[FR, SR, R, First <: StrictSplitterCheckTask[FR, _], Second <: StrictSplitterCheckTask[SR, _]]
(f: First, s: Second)
extends Composite[FR, SR, R, First, Second](f, s) {
def leaf(prevr: Option[R]) = {
executeAndWaitResult(ft)
executeAndWaitResult(st)
mergeSubtasks
}
}
protected[this] abstract class ParComposite[FR, SR, R, First <: StrictSplitterCheckTask[FR, _], Second <: StrictSplitterCheckTask[SR, _]]
(f: First, s: Second)
extends Composite[FR, SR, R, First, Second](f, s) {
def leaf(prevr: Option[R]) = {
val ftfuture = execute(ft)
executeAndWaitResult(st)
ftfuture()
mergeSubtasks
}
}
protected[this] abstract class ResultMapping[R, Tp, R1](val inner: StrictSplitterCheckTask[R, Tp])
extends NonDivisibleTask[R1, ResultMapping[R, Tp, R1]] {
@volatile var result: R1 = null.asInstanceOf[R1]
def map(r: R): R1
def leaf(prevr: Option[R1]) = {
result = map(executeAndWaitResult(inner))
}
private[parallel] override def signalAbort() {
inner.signalAbort
}
override def requiresStrictSplitters = inner.requiresStrictSplitters
}
protected trait Transformer[R, Tp] extends Accessor[R, Tp]
protected[this] class Foreach[S](op: T => S, protected[this] val pit: IterableSplitter[T]) extends Accessor[Unit, Foreach[S]] {
@volatile var result: Unit = ()
def leaf(prevr: Option[Unit]) = pit.foreach(op)
protected[this] def newSubtask(p: IterableSplitter[T]) = new Foreach[S](op, p)
}
protected[this] class Count(pred: T => Boolean, protected[this] val pit: IterableSplitter[T]) extends Accessor[Int, Count] {
@volatile var result: Int = 0
def leaf(prevr: Option[Int]) = result = pit.count(pred)
protected[this] def newSubtask(p: IterableSplitter[T]) = new Count(pred, p)
override def merge(that: Count) = result = result + that.result
}
protected[this] class Reduce[U >: T](op: (U, U) => U, protected[this] val pit: IterableSplitter[T]) extends Accessor[Option[U], Reduce[U]] {
@volatile var result: Option[U] = None
def leaf(prevr: Option[Option[U]]) = if (pit.remaining > 0) result = Some(pit.reduce(op))
protected[this] def newSubtask(p: IterableSplitter[T]) = new Reduce(op, p)
override def merge(that: Reduce[U]) =
if (this.result == None) result = that.result
else if (that.result != None) result = Some(op(result.get, that.result.get))
override def requiresStrictSplitters = true
}
protected[this] class Fold[U >: T](z: U, op: (U, U) => U, protected[this] val pit: IterableSplitter[T]) extends Accessor[U, Fold[U]] {
@volatile var result: U = null.asInstanceOf[U]
def leaf(prevr: Option[U]) = result = pit.fold(z)(op)
protected[this] def newSubtask(p: IterableSplitter[T]) = new Fold(z, op, p)
override def merge(that: Fold[U]) = result = op(result, that.result)
}
protected[this] class Aggregate[S](z: S, seqop: (S, T) => S, combop: (S, S) => S, protected[this] val pit: IterableSplitter[T])
extends Accessor[S, Aggregate[S]] {
@volatile var result: S = null.asInstanceOf[S]
def leaf(prevr: Option[S]) = result = pit.foldLeft(z)(seqop)
protected[this] def newSubtask(p: IterableSplitter[T]) = new Aggregate(z, seqop, combop, p)
override def merge(that: Aggregate[S]) = result = combop(result, that.result)
}
protected[this] class Sum[U >: T](num: Numeric[U], protected[this] val pit: IterableSplitter[T]) extends Accessor[U, Sum[U]] {
@volatile var result: U = null.asInstanceOf[U]
def leaf(prevr: Option[U]) = result = pit.sum(num)
protected[this] def newSubtask(p: IterableSplitter[T]) = new Sum(num, p)
override def merge(that: Sum[U]) = result = num.plus(result, that.result)
}
protected[this] class Product[U >: T](num: Numeric[U], protected[this] val pit: IterableSplitter[T]) extends Accessor[U, Product[U]] {
@volatile var result: U = null.asInstanceOf[U]
def leaf(prevr: Option[U]) = result = pit.product(num)
protected[this] def newSubtask(p: IterableSplitter[T]) = new Product(num, p)
override def merge(that: Product[U]) = result = num.times(result, that.result)
}
protected[this] class Min[U >: T](ord: Ordering[U], protected[this] val pit: IterableSplitter[T]) extends Accessor[Option[U], Min[U]] {
@volatile var result: Option[U] = None
def leaf(prevr: Option[Option[U]]) = if (pit.remaining > 0) result = Some(pit.min(ord))
protected[this] def newSubtask(p: IterableSplitter[T]) = new Min(ord, p)
override def merge(that: Min[U]) =
if (this.result == None) result = that.result
else if (that.result != None) result = if (ord.lteq(result.get, that.result.get)) result else that.result
override def requiresStrictSplitters = true
}
protected[this] class Max[U >: T](ord: Ordering[U], protected[this] val pit: IterableSplitter[T]) extends Accessor[Option[U], Max[U]] {
@volatile var result: Option[U] = None
def leaf(prevr: Option[Option[U]]) = if (pit.remaining > 0) result = Some(pit.max(ord))
protected[this] def newSubtask(p: IterableSplitter[T]) = new Max(ord, p)
override def merge(that: Max[U]) =
if (this.result == None) result = that.result
else if (that.result != None) result = if (ord.gteq(result.get, that.result.get)) result else that.result
override def requiresStrictSplitters = true
}
protected[this] class Map[S, That](f: T => S, pbf: CanCombineFrom[Repr, S, That], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[S, That], Map[S, That]] {
@volatile var result: Combiner[S, That] = null
def leaf(prev: Option[Combiner[S, That]]) = result = pit.map2combiner(f, reuse(prev, pbf(self.repr)))
protected[this] def newSubtask(p: IterableSplitter[T]) = new Map(f, pbf, p)
override def merge(that: Map[S, That]) = result = result combine that.result
}
protected[this] class Collect[S, That]
(pf: PartialFunction[T, S], pbf: CanCombineFrom[Repr, S, That], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[S, That], Collect[S, That]] {
@volatile var result: Combiner[S, That] = null
def leaf(prev: Option[Combiner[S, That]]) = result = pit.collect2combiner[S, That](pf, pbf(self.repr))
protected[this] def newSubtask(p: IterableSplitter[T]) = new Collect(pf, pbf, p)
override def merge(that: Collect[S, That]) = result = result combine that.result
}
protected[this] class FlatMap[S, That](f: T => GenTraversableOnce[S], pbf: CanCombineFrom[Repr, S, That], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[S, That], FlatMap[S, That]] {
@volatile var result: Combiner[S, That] = null
def leaf(prev: Option[Combiner[S, That]]) = result = pit.flatmap2combiner(f, pbf(self.repr))
protected[this] def newSubtask(p: IterableSplitter[T]) = new FlatMap(f, pbf, p)
override def merge(that: FlatMap[S, That]) = {
result = result combine that.result
}
}
protected[this] class Forall(pred: T => Boolean, protected[this] val pit: IterableSplitter[T]) extends Accessor[Boolean, Forall] {
@volatile var result: Boolean = true
def leaf(prev: Option[Boolean]) = { if (!pit.isAborted) result = pit.forall(pred); if (result == false) pit.abort }
protected[this] def newSubtask(p: IterableSplitter[T]) = new Forall(pred, p)
override def merge(that: Forall) = result = result && that.result
}
protected[this] class Exists(pred: T => Boolean, protected[this] val pit: IterableSplitter[T]) extends Accessor[Boolean, Exists] {
@volatile var result: Boolean = false
def leaf(prev: Option[Boolean]) = { if (!pit.isAborted) result = pit.exists(pred); if (result == true) pit.abort }
protected[this] def newSubtask(p: IterableSplitter[T]) = new Exists(pred, p)
override def merge(that: Exists) = result = result || that.result
}
protected[this] class Find[U >: T](pred: T => Boolean, protected[this] val pit: IterableSplitter[T]) extends Accessor[Option[U], Find[U]] {
@volatile var result: Option[U] = None
def leaf(prev: Option[Option[U]]) = { if (!pit.isAborted) result = pit.find(pred); if (result != None) pit.abort }
protected[this] def newSubtask(p: IterableSplitter[T]) = new Find(pred, p)
override def merge(that: Find[U]) = if (this.result == None) result = that.result
}
protected[this] class Filter[U >: T, This >: Repr](pred: T => Boolean, cbf: () => Combiner[U, This], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[U, This], Filter[U, This]] {
@volatile var result: Combiner[U, This] = null
def leaf(prev: Option[Combiner[U, This]]) = {
result = pit.filter2combiner(pred, reuse(prev, cbf()))
}
protected[this] def newSubtask(p: IterableSplitter[T]) = new Filter(pred, cbf, p)
override def merge(that: Filter[U, This]) = result = result combine that.result
}
protected[this] class FilterNot[U >: T, This >: Repr](pred: T => Boolean, cbf: () => Combiner[U, This], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[U, This], FilterNot[U, This]] {
@volatile var result: Combiner[U, This] = null
def leaf(prev: Option[Combiner[U, This]]) = {
result = pit.filterNot2combiner(pred, reuse(prev, cbf()))
}
protected[this] def newSubtask(p: IterableSplitter[T]) = new FilterNot(pred, cbf, p)
override def merge(that: FilterNot[U, This]) = result = result combine that.result
}
protected class Copy[U >: T, That](cfactory: () => Combiner[U, That], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[U, That], Copy[U, That]] {
@volatile var result: Combiner[U, That] = null
def leaf(prev: Option[Combiner[U, That]]) = result = pit.copy2builder[U, That, Combiner[U, That]](reuse(prev, cfactory()))
protected[this] def newSubtask(p: IterableSplitter[T]) = new Copy[U, That](cfactory, p)
override def merge(that: Copy[U, That]) = result = result combine that.result
}
protected[this] class Partition[U >: T, This >: Repr](pred: T => Boolean, cbf: () => Combiner[U, This], protected[this] val pit: IterableSplitter[T])
extends Transformer[(Combiner[U, This], Combiner[U, This]), Partition[U, This]] {
@volatile var result: (Combiner[U, This], Combiner[U, This]) = null
def leaf(prev: Option[(Combiner[U, This], Combiner[U, This])]) = result = pit.partition2combiners(pred, reuse(prev.map(_._1), cbf()), reuse(prev.map(_._2), cbf()))
protected[this] def newSubtask(p: IterableSplitter[T]) = new Partition(pred, cbf, p)
override def merge(that: Partition[U, This]) = result = (result._1 combine that.result._1, result._2 combine that.result._2)
}
protected[this] class GroupBy[K, U >: T](
f: U => K,
mcf: () => HashMapCombiner[K, U],
protected[this] val pit: IterableSplitter[T]
) extends Transformer[HashMapCombiner[K, U], GroupBy[K, U]] {
@volatile var result: Result = null
final def leaf(prev: Option[Result]) = {
val cb = mcf()
while (pit.hasNext) {
val elem = pit.next
cb += f(elem) -> elem
}
result = cb
}
protected[this] def newSubtask(p: IterableSplitter[T]) = new GroupBy(f, mcf, p)
override def merge(that: GroupBy[K, U]) = {
result = (result combine that.result).asInstanceOf[HashMapCombiner[K, U]]
}
}
protected[this] class Take[U >: T, This >: Repr](n: Int, cbf: () => Combiner[U, This], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[U, This], Take[U, This]] {
@volatile var result: Combiner[U, This] = null
def leaf(prev: Option[Combiner[U, This]]) = {
result = pit.take2combiner(n, reuse(prev, cbf()))
}
protected[this] def newSubtask(p: IterableSplitter[T]) = throw new UnsupportedOperationException
override def split = {
val pits = pit.split
val sizes = pits.scanLeft(0)(_ + _.remaining)
for ((p, untilp) <- pits zip sizes; if untilp <= n) yield {
if (untilp + p.remaining < n) new Take(p.remaining, cbf, p)
else new Take(n - untilp, cbf, p)
}
}
override def merge(that: Take[U, This]) = result = result combine that.result
override def requiresStrictSplitters = true
}
protected[this] class Drop[U >: T, This >: Repr](n: Int, cbf: () => Combiner[U, This], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[U, This], Drop[U, This]] {
@volatile var result: Combiner[U, This] = null
def leaf(prev: Option[Combiner[U, This]]) = result = pit.drop2combiner(n, reuse(prev, cbf()))
protected[this] def newSubtask(p: IterableSplitter[T]) = throw new UnsupportedOperationException
override def split = {
val pits = pit.split
val sizes = pits.scanLeft(0)(_ + _.remaining)
for ((p, withp) <- pits zip sizes.tail; if withp >= n) yield {
if (withp - p.remaining > n) new Drop(0, cbf, p)
else new Drop(n - withp + p.remaining, cbf, p)
}
}
override def merge(that: Drop[U, This]) = result = result combine that.result
override def requiresStrictSplitters = true
}
protected[this] class Slice[U >: T, This >: Repr](from: Int, until: Int, cbf: () => Combiner[U, This], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[U, This], Slice[U, This]] {
@volatile var result: Combiner[U, This] = null
def leaf(prev: Option[Combiner[U, This]]) = result = pit.slice2combiner(from, until, reuse(prev, cbf()))
protected[this] def newSubtask(p: IterableSplitter[T]) = throw new UnsupportedOperationException
override def split = {
val pits = pit.split
val sizes = pits.scanLeft(0)(_ + _.remaining)
for ((p, untilp) <- pits zip sizes; if untilp + p.remaining >= from || untilp <= until) yield {
val f = (from max untilp) - untilp
val u = (until min (untilp + p.remaining)) - untilp
new Slice(f, u, cbf, p)
}
}
override def merge(that: Slice[U, This]) = result = result combine that.result
override def requiresStrictSplitters = true
}
protected[this] class SplitAt[U >: T, This >: Repr](at: Int, cbf: () => Combiner[U, This], protected[this] val pit: IterableSplitter[T])
extends Transformer[(Combiner[U, This], Combiner[U, This]), SplitAt[U, This]] {
@volatile var result: (Combiner[U, This], Combiner[U, This]) = null
def leaf(prev: Option[(Combiner[U, This], Combiner[U, This])]) = result = pit.splitAt2combiners(at, reuse(prev.map(_._1), cbf()), reuse(prev.map(_._2), cbf()))
protected[this] def newSubtask(p: IterableSplitter[T]) = throw new UnsupportedOperationException
override def split = {
val pits = pit.split
val sizes = pits.scanLeft(0)(_ + _.remaining)
for ((p, untilp) <- pits zip sizes) yield new SplitAt((at max untilp min (untilp + p.remaining)) - untilp, cbf, p)
}
override def merge(that: SplitAt[U, This]) = result = (result._1 combine that.result._1, result._2 combine that.result._2)
override def requiresStrictSplitters = true
}
protected[this] class TakeWhile[U >: T, This >: Repr]
(pos: Int, pred: T => Boolean, cbf: () => Combiner[U, This], protected[this] val pit: IterableSplitter[T])
extends Transformer[(Combiner[U, This], Boolean), TakeWhile[U, This]] {
@volatile var result: (Combiner[U, This], Boolean) = null
def leaf(prev: Option[(Combiner[U, This], Boolean)]) = if (pos < pit.indexFlag) {
result = pit.takeWhile2combiner(pred, reuse(prev.map(_._1), cbf()))
if (!result._2) pit.setIndexFlagIfLesser(pos)
} else result = (reuse(prev.map(_._1), cbf()), false)
protected[this] def newSubtask(p: IterableSplitter[T]) = throw new UnsupportedOperationException
override def split = {
val pits = pit.split
for ((p, untilp) <- pits zip pits.scanLeft(0)(_ + _.remaining)) yield new TakeWhile(pos + untilp, pred, cbf, p)
}
override def merge(that: TakeWhile[U, This]) = if (result._2) {
result = (result._1 combine that.result._1, that.result._2)
}
override def requiresStrictSplitters = true
}
protected[this] class Span[U >: T, This >: Repr]
(pos: Int, pred: T => Boolean, cbf: () => Combiner[U, This], protected[this] val pit: IterableSplitter[T])
extends Transformer[(Combiner[U, This], Combiner[U, This]), Span[U, This]] {
@volatile var result: (Combiner[U, This], Combiner[U, This]) = null
def leaf(prev: Option[(Combiner[U, This], Combiner[U, This])]) = if (pos < pit.indexFlag) {
result = pit.span2combiners(pred, cbf(), cbf())
if (result._2.size > 0) pit.setIndexFlagIfLesser(pos)
} else {
result = (reuse(prev.map(_._2), cbf()), pit.copy2builder[U, This, Combiner[U, This]](reuse(prev.map(_._2), cbf())))
}
protected[this] def newSubtask(p: IterableSplitter[T]) = throw new UnsupportedOperationException
override def split = {
val pits = pit.split
for ((p, untilp) <- pits zip pits.scanLeft(0)(_ + _.remaining)) yield new Span(pos + untilp, pred, cbf, p)
}
override def merge(that: Span[U, This]) = result = if (result._2.size == 0) {
(result._1 combine that.result._1, that.result._2)
} else {
(result._1, result._2 combine that.result._1 combine that.result._2)
}
override def requiresStrictSplitters = true
}
protected[this] class Zip[U >: T, S, That](pbf: CanCombineFrom[Repr, (U, S), That], protected[this] val pit: IterableSplitter[T], val othpit: SeqSplitter[S])
extends Transformer[Combiner[(U, S), That], Zip[U, S, That]] {
@volatile var result: Result = null
def leaf(prev: Option[Result]) = result = pit.zip2combiner[U, S, That](othpit, pbf(self.repr))
protected[this] def newSubtask(p: IterableSplitter[T]) = unsupported
override def split = {
val pits = pit.split
val sizes = pits.map(_.remaining)
val opits = othpit.psplit(sizes: _*)
(pits zip opits) map { p => new Zip(pbf, p._1, p._2) }
}
override def merge(that: Zip[U, S, That]) = result = result combine that.result
override def requiresStrictSplitters = true
}
protected[this] class ZipAll[U >: T, S, That]
(len: Int, thiselem: U, thatelem: S, pbf: CanCombineFrom[Repr, (U, S), That], protected[this] val pit: IterableSplitter[T], val othpit: SeqSplitter[S])
extends Transformer[Combiner[(U, S), That], ZipAll[U, S, That]] {
@volatile var result: Result = null
def leaf(prev: Option[Result]) = result = pit.zipAll2combiner[U, S, That](othpit, thiselem, thatelem, pbf(self.repr))
protected[this] def newSubtask(p: IterableSplitter[T]) = unsupported
override def split = if (pit.remaining <= len) {
val pits = pit.split
val sizes = pits.map(_.remaining)
val opits = othpit.psplit(sizes: _*)
((pits zip opits) zip sizes) map { t => new ZipAll(t._2, thiselem, thatelem, pbf, t._1._1, t._1._2) }
} else {
val opits = othpit.psplit(pit.remaining)
val diff = len - pit.remaining
Seq(
new ZipAll(pit.remaining, thiselem, thatelem, pbf, pit, opits(0)),
new ZipAll(diff, thiselem, thatelem, pbf, immutable.repetition(thiselem, diff).splitter.asInstanceOf[IterableSplitter[T]], opits(1))
)
}
override def merge(that: ZipAll[U, S, That]) = result = result combine that.result
override def requiresStrictSplitters = true
}
protected[this] class CopyToArray[U >: T, This >: Repr](from: Int, len: Int, array: Array[U], protected[this] val pit: IterableSplitter[T])
extends Accessor[Unit, CopyToArray[U, This]] {
@volatile var result: Unit = ()
def leaf(prev: Option[Unit]) = pit.copyToArray(array, from, len)
protected[this] def newSubtask(p: IterableSplitter[T]) = unsupported
override def split = {
val pits = pit.split
for ((p, untilp) <- pits zip pits.scanLeft(0)(_ + _.remaining); if untilp < len) yield {
val plen = p.remaining min (len - untilp)
new CopyToArray[U, This](from + untilp, plen, array, p)
}
}
override def requiresStrictSplitters = true
}
protected[this] class ToParCollection[U >: T, That](cbf: () => Combiner[U, That], protected[this] val pit: IterableSplitter[T])
extends Transformer[Combiner[U, That], ToParCollection[U, That]] {
@volatile var result: Result = null
def leaf(prev: Option[Combiner[U, That]]) {
result = cbf()
while (pit.hasNext) result += pit.next
}
protected[this] def newSubtask(p: IterableSplitter[T]) = new ToParCollection[U, That](cbf, p)
override def merge(that: ToParCollection[U, That]) = result = result combine that.result
}
protected[this] class ToParMap[K, V, That](cbf: () => Combiner[(K, V), That], protected[this] val pit: IterableSplitter[T])(implicit ev: T <:< (K, V))
extends Transformer[Combiner[(K, V), That], ToParMap[K, V, That]] {
@volatile var result: Result = null
def leaf(prev: Option[Combiner[(K, V), That]]) {
result = cbf()
while (pit.hasNext) result += pit.next
}
protected[this] def newSubtask(p: IterableSplitter[T]) = new ToParMap[K, V, That](cbf, p)(ev)
override def merge(that: ToParMap[K, V, That]) = result = result combine that.result
}
protected[this] class CreateScanTree[U >: T](from: Int, len: Int, z: U, op: (U, U) => U, protected[this] val pit: IterableSplitter[T])
extends Transformer[ScanTree[U], CreateScanTree[U]] {
@volatile var result: ScanTree[U] = null
def leaf(prev: Option[ScanTree[U]]) = if (pit.remaining > 0) {
val trees = ArrayBuffer[ScanTree[U]]()
var i = from
val until = from + len
val blocksize = scanBlockSize
while (i < until) {
trees += scanBlock(i, math.min(blocksize, pit.remaining))
i += blocksize
}
result = mergeTrees(trees, 0, trees.length)
} else result = null
private def scanBlock(from: Int, len: Int): ScanTree[U] = {
val pitdup = pit.dup
new ScanLeaf(pitdup, op, from, len, None, pit.reduceLeft(len, op))
}
private def mergeTrees(trees: ArrayBuffer[ScanTree[U]], from: Int, howmany: Int): ScanTree[U] = if (howmany > 1) {
val half = howmany / 2
ScanNode(mergeTrees(trees, from, half), mergeTrees(trees, from + half, howmany - half))
} else trees(from)
protected[this] def newSubtask(pit: IterableSplitter[T]) = unsupported
override def split = {
val pits = pit.split
for ((p, untilp) <- pits zip pits.scanLeft(from)(_ + _.remaining)) yield {
new CreateScanTree(untilp, p.remaining, z, op, p)
}
}
override def merge(that: CreateScanTree[U]) = if (this.result != null) {
if (that.result != null) result = ScanNode(result, that.result)
} else result = that.result
override def requiresStrictSplitters = true
}
protected[this] class FromScanTree[U >: T, That]
(tree: ScanTree[U], z: U, op: (U, U) => U, cbf: CanCombineFrom[Repr, U, That])
extends StrictSplitterCheckTask[Combiner[U, That], FromScanTree[U, That]] {
@volatile var result: Combiner[U, That] = null
def leaf(prev: Option[Combiner[U, That]]) {
val cb = reuse(prev, cbf(self.repr))
iterate(tree, cb)
result = cb
}
private def iterate(tree: ScanTree[U], cb: Combiner[U, That]): Unit = tree match {
case ScanNode(left, right) =>
iterate(left, cb)
iterate(right, cb)
case ScanLeaf(p, _, _, len, Some(prev), _) =>
p.scanToCombiner(len, prev.acc, op, cb)
case ScanLeaf(p, _, _, len, None, _) =>
cb += z
p.scanToCombiner(len, z, op, cb)
}
def split = tree match {
case ScanNode(left, right) => Seq(
new FromScanTree(left, z, op, cbf),
new FromScanTree(right, z, op, cbf)
)
case _ => unsupportedop("Cannot be split further")
}
def shouldSplitFurther = tree match {
case ScanNode(_, _) => true
case ScanLeaf(_, _, _, _, _, _) => false
}
override def merge(that: FromScanTree[U, That]) = result = result combine that.result
}
protected[this] def scanBlockSize = (threshold(size, parallelismLevel) / 2) max 1
protected[this] trait ScanTree[U >: T] {
def beginsAt: Int
def pushdown(v: U): Unit
def leftmost: ScanLeaf[U]
def rightmost: ScanLeaf[U]
def print(depth: Int = 0): Unit
}
protected[this] case class ScanNode[U >: T](left: ScanTree[U], right: ScanTree[U]) extends ScanTree[U] {
right.pushdown(left.rightmost.acc)
right.leftmost.prev = Some(left.rightmost)
val leftmost = left.leftmost
val rightmost = right.rightmost
def beginsAt = left.beginsAt
def pushdown(v: U) {
left.pushdown(v)
right.pushdown(v)
}
def print(depth: Int) {
println((" " * depth) + "ScanNode, begins at " + beginsAt)
left.print(depth + 1)
right.print(depth + 1)
}
}
protected[this] case class ScanLeaf[U >: T]
(pit: IterableSplitter[U], op: (U, U) => U, from: Int, len: Int, var prev: Option[ScanLeaf[U]], var acc: U)
extends ScanTree[U] {
def beginsAt = from
def pushdown(v: U) = {
acc = op(v, acc)
}
def leftmost = this
def rightmost = this
def print(depth: Int) = println((" " * depth) + this)
}
private[parallel] def debugInformation = "Parallel collection: " + this.getClass
private[parallel] def brokenInvariants = Seq[String]()
def debugBuffer: ArrayBuffer[String] = null
private[parallel] def debugclear() = synchronized {
debugBuffer.clear
}
private[parallel] def debuglog(s: String) = synchronized {
debugBuffer += s
}
import collection.DebugUtils._
private[parallel] def printDebugBuffer() = println(buildString {
append =>
for (s <- debugBuffer) {
append(s)
}
})
}