/*
   Copyright 2010 Aaron J. Radke

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/
package cc.drx

import scala.math.Ordering

import java.nio.charset.Charset
import java.nio.charset.StandardCharsets.UTF_8

//-- Collection functions organized by category  (Scala doc's do not sort well (alphabetically or inheritance don't give what we want))
/*
  //-- selection
  drop
  dropRight
  head
  headOption
  slice
  take
  takeRight
  takeWhile
  lift
  dropWhile
  init
  last
  lastOption
  tail

  //-- growing
  ++
  ++:

  lastIndexOf
  
  //-- filter
  find
  collect
  collectFirst
  filter
  filterNot
  flatMap
  withFilter (monadic)
  
  //-- tests
  exists
  forall
  sameElements
  startsWith
  isDefindedAt
  nonEmpty

  //-- join/reduce
  mkString      //IterableOnce
  reduce      //IterableOnce
  reduceLeft      //IterableOnce
  reduceLeftOption      //IterableOnce
  reduceOption      //IterableOnce

  //-- sumarize
  count      //IterableOnce
  length      //IterableOnce
  max      //IterableOnce
  min      //IterableOnce
  minBy      //IterableOnce
  sum      //IterableOnce
  product      //IterableOnce

  //-- grouping
  grouped
  sliding
  groupBy

  //-- separate
  partition
  span
  splitAt

  //-- iteration
  foreach
  par
  
  //-- folds, nests
  fold      //IterableOnce
  foldLeft      //IterableOnce
  foldRight      //IterableOnce
  /:      //IterableOnce
  :\      //IterableOnce
  zip
  zipWithIndex
  scan
  scanLeft
  scanRight

  //-- conversion
  toIterable
  iterator  // .toIterator before 2.13
  toStream
  toTraversable //note: since 2.13 Traversable is a deprecated class where Iterable should be used instead)
  toArray      //IterableOnce
  toList       //IterableOnce
  toMap        //IterableOnce
  toSet       ///IterableOnce
  toVector     //IterableOnce

  //-- re-shape
  flatten
  transpose
  unzip
  inits

  //--transform
  map
  flatMap

  //--Map functions
  retain
  keys
  values
  filterKeys


 */


//--Monkey ByteBuffer to make them more first class to work with scala
class DrxByteBuffer(bb:java.nio.ByteBuffer){
  //--Unsigned types
  def getU8  = U8(bb.get())
  def getU16 = U16(bb.getShort())
  def getU32 = U32(bb.getInt())
  def getU64 = U64(bb.getLong())

  //--nice toggle byte order
  def asLittle:Unit = {bb.order(java.nio.ByteOrder.LITTLE_ENDIAN); ()}
  def asBig:Unit    = {bb.order(java.nio.ByteOrder.BIG_ENDIAN);    ()}


  def asString:String = asString(UTF_8)
  /** direct view of the byte buffer as a string
   *  note although Input(bb).asString will work this is a more direct byte buffer to string without going through java InputStream's */
  def asString(charset:Charset):String = {
    //example taken from https://gist.github.com/reddikih/00ed63847f9f4e620e9d4772d69cbee5
    //
    val bytes:Array[Byte] = {
      if(bb.hasArray) bb.array //quick direct array if available
      else {
        bb.rewind //is this just to be safe?
        val bytes = new Array[Byte](bb.remaining) //empty byte array of size remaining
        bb.get(bytes) //fill the byte array
        bytes
      }
    }
    new String(bytes, charset)
  }
}

//--Monkey patch some Specialed Array types (Byte,Int,Long,Doubule)
class DrxArrayByte(xs:Array[Byte]){
  // type BA = Array[Byte]
  def toDoubleArray:Array[Double] = toDoubleArray(0,xs.size)
  def toDoubleArray(offset:Int,size:Int):Array[Double] = {
    val N = size/8  //java.lang.Double.SIZE/java.lang.Byte.SIZE => 64/8 => 8
    val ys = new Array[Double](N)
    val buffer = java.nio.ByteBuffer.wrap(xs,offset,size)
    var i = 0; while(i < N) { ys(i) = buffer.getDouble; i += 1 }
    ys
  }
  def toIntArray:Array[Int] = {
    val N = xs.size/4  //java.lang.Int.SIZE/java.lang.Byte.SIZE => 32/8 => 4
    val ys = new Array[Int](N)
    val buffer = java.nio.ByteBuffer.wrap(xs)
    var i = 0; while(i < N) { ys(i) = buffer.getInt; i += 1 }
    ys
  }
  def toLongArray:Array[Long] = {
    val N = xs.size/8  //java.lang.Long.SIZE/java.lang.Byte.SIZE => 64/8 => 8
    val ys = new Array[Long](N)
    val buffer = java.nio.ByteBuffer.wrap(xs)
    var i = 0; while(i < N) { ys(i) = buffer.getLong; i += 1 }
    ys
  }
  def compress(sg:StreamGenerator):Array[Byte] = {
    val out = Output.bytes //a byte array stream
    out.as(sg).write(xs)
    out.toByteArray
  }
  def expand(sg:StreamGenerator):Array[Byte] = {
    Input(xs).as(sg).toByteArray
  }
  //--byte buffer helpers
  2017-07-30("use toByteBuffer for uniform toConversions", "dq")
  def buffer:java.nio.ByteBuffer = toByteBuffer
  2017-07-30("use toByteBuffer for uniform toConversions", "dq")
  def buffer(offset:Int, length:Int):java.nio.ByteBuffer = toByteBuffer

  def toByteBuffer:java.nio.ByteBuffer = java.nio.ByteBuffer.wrap(xs)
  def toByteBuffer(offset:Int, length:Int):java.nio.ByteBuffer = java.nio.ByteBuffer.wrap(xs,offset,length)

  def unpack:Array[Array[Byte]] = BytePacker.unpack(xs)

  /**assuming utf8 now that this is nearly standard (make 90% use cases 10x more useable)*/
  def asString = new String(xs, UTF_8)
}
/**both of these classes are required since Array is not directly type checked as a Iterable*/
class DrxArrayArrayByte(xs:Array[Array[Byte]]){
  def pack:Array[Byte] = BytePacker.pack(xs)
}
class DrxTraversableArrayByte(xs:Iterable[Array[Byte]]){
  def pack:Array[Byte] = BytePacker.pack(xs)
}

/** very simple linear serialization simply prepending a byte blob by it's size*/
object BytePacker{
  def unapply(bytes:Array[Byte]):Option[Array[Array[Byte]]] = Some(unpack(bytes))
  def unpack(bytes:Array[Byte],index:Int, size:Int):Array[Array[Byte]] = {
    @tailrec def getNextFrom(index:Int, ts:List[Array[Byte]]=Nil):List[Array[Byte]] = {
      if(index >= size) ts
      else {
        val size = DrxInt.fromByteArray(bytes,index)
        val start = index+4
        val end = start+size
        getNextFrom(end, bytes.slice(start, end) :: ts)
      }
    }
    getNextFrom(index).reverse.toArray
  }
  def unpack(bytes:Array[Byte]):Array[Array[Byte]] = unpack(bytes,0,bytes.size)
  def pack(blobs:Iterable[Array[Byte]]):Array[Byte] = blobs.flatMap{blob => blob.size.toByteArray ++ blob}.toArray
}

class DrxArrayDouble(xs:Array[Double]){
  type D = Double; type Ds = Array[D]
  private def zipped(ys:Ds) = {
    require(xs.size == ys.size,"zipped array operations require matching sizes ${xs.size}!=${ys.size}")
    xs zip ys
    // xs.toIterable zip xs.toIterable
    // // (xs,ys).zipped
    // Tuple2(xs,ys).zipped
  }
  def *(ys:Ds):D  = zipped(ys).foldLeft(0.0){case (a,(x,y)) => a + x*y}
  def :*(ys:Ds):Ds = zipped(ys).map{case (a,b) => a*b}.toArray
  def +(ys:Ds):Ds = zipped(ys).map{case (a,b) => a+b}.toArray
  def -(ys:Ds):Ds = zipped(ys).map{case (a,b) => a-b}.toArray
  def /(s:D):Ds = xs.map{_/s}
  def *(s:D):Ds = xs.map{_*s}
  def normSq:D = xs.fold(0d){case(a,x) => a + x*x}
  def norm:D = normSq.sqrt
  def pnorm(p:Double):D = xs.fold(0d){case(a,x) => a + x.abs**p}**p.inv // http://mathworld.wolfram.com/VectorNorm.html
  def dist(ys:Ds):Double = (xs-ys).norm
  def unit:Ds = this/norm

  def toByteArray:Array[Byte] = {
    val N = xs.size
    val ys = new Array[Byte](N*8) //java.lang.Double.SIZE/java.lang.Byte.SIZE => 64/8 => 8
    val buffer = java.nio.ByteBuffer.wrap(ys)
    //for(x <- xs) buffer putDouble x
    var i = 0; while(i < N) { buffer putDouble xs(i); i += 1 }  //mutably unroll the for loop
    ys
  }
}

class DrxArrayInt(xs:Array[Int]){
  def toByteArray:Array[Byte] = {
    val N = xs.size
    val ys = new Array[Byte](N*4) //java.lang.Integer.SIZE/java.lang.Byte.SIZE => 32/8 => 4
    val buffer = java.nio.ByteBuffer.wrap(ys)
    //for(x <- xs) buffer putDouble x
    var i = 0; while(i < N) { buffer putInt xs(i); i += 1 }  //mutably unroll the for loop
    ys
  }
}

class DrxArrayLong(xs:Array[Long]){
  def toByteArray:Array[Byte] = {
    val N = xs.size
    val ys = new Array[Byte](N*8) //java.lang.Long.SIZE/java.lang.Byte.SIZE => 64/8 => 8
    val buffer = java.nio.ByteBuffer.wrap(ys)
    //for(x <- xs) buffer putLong x
    var i = 0; while(i < N) { buffer putLong xs(i); i += 1 }  //mutably unroll the for loop
    ys
  }
}

/**Array are indexSeq but are special in scala for java opt and need re-implementation???*/
final class DrxArray[A](val xs:Array[A]) extends AnyVal{
    private def iseq = new DrxIndexedSeq(xs.toIndexedSeq)
    private def iter = new DrxIterable(xs)
    // private def travOnce = new DrxTraversableOnce(xs)
    // private def it = new DrxIterator(xs)
    def sample(meanReductionSize:Int,from:Int=0,to:Int=xs.size)(implicit rand:Rand) =
      iseq.sample(meanReductionSize,from,to)
    def sampleWithIndex(meanReductionSize:Int,from:Int=0,to:Int=xs.size)(implicit rand:Rand) =
      iseq.sampleWithIndex(meanReductionSize,from,to)
   /**Binary tree search for a value with an mapping transformation, (Note: assumes sorted by B*/
    def searchBy[B](searchValue:B, from:Int=0,to:Int=xs.size-1)(elem:A=>B)
        (implicit ord: Ordering[B]):Int = iseq.searchBy(searchValue,from,to)(elem)(ord)
    def someIndexWhere(p:A=>Boolean):Option[Int] = iseq.someIndexWhere(p)
    def indicesWhere(p:A=>Boolean):IndexedSeq[Int] = {for((v,i) <- xs.iterator.zipWithIndex; if p(v)) yield i}.toIndexedSeq //indices filter {i => p(i)}
    def sliceWith(bound:Bound[Int]):Array[A] = xs.slice(bound.min, bound.max+1)

    def %(i:Int):A = {val j = i % xs.size;  if(j < 0) xs(xs.size + j) else xs(j) }
    def modOption(i:Int):Option[A] = if(xs.size == 0) None else Some(%(i))

    private def lerpIndex(t:Double):Int = {val N = xs.size -1; (t*N).round.toInt.sat(0,N)}
    def lerp(t:Double):A               = xs.apply(lerpIndex(t))
    def lerpOption(t:Double):Option[A] = if(t < 0 || t > 1) None else xs.lift(lerpIndex(t))

    /**create an Ordinal scale with equal bands steps in the range*/
    def -->[B](range:Bound[B]) = Scale(xs,range)
    /**create an Ordinal scale with mappings to range*/
    def -->[B](range:Iterable[B]) = Scale(xs,range)

    def rand(implicit r:Rand):Iterator[A] = iseq.rand(r)
    // def shuffle = java.util.Collections.shuffle(xs) //TODO add (implicit r:Rand)  to hold seed
    def toTuple2:Try[Tuple2[A,A]] = iter.toTuple2
}

//--helper classes that don't work well as internal classes in scala 2.10
class RandIterator[A](val xs:IndexedSeq[A])(implicit r:Rand) extends Iterator[A] {
  val N = xs.size - 1
  def hasNext = true //warning this guy is an infinite list
  def next():A = xs(r uniform N)
}
class ZippedIterable[A,B,C](xs:Iterable[A], ys:Iterable[B], f:(A,B)=>C) extends Iterable[C]{
  def iterator:Iterator[C] = (xs.iterator zip ys.iterator).map{case (x,y) => f(x,y)}
}

/**IndexedSeq are indexable*/
final class DrxIndexedSeq[A](val xs:IndexedSeq[A]) extends AnyVal{
   def get(i:Int):Option[A] = if(xs isDefinedAt i) Some(xs(i)) else None
   def getOrElse(i:Int, default: => A):A = if(xs isDefinedAt i) xs(i) else default
   def sample(meanReductionSize:Int,from:Int=0,to:Int=xs.size)(implicit rand:Rand):ArrayBuffer[A] = {
       val N = to - from
       //val meanReductionSize = math.round(reductionRatio*N).toInt
       if(meanReductionSize <= 0) ArrayBuffer[A]()
       else if(meanReductionSize >= N) ArrayBuffer[A]() ++ xs.slice(from,to)
       else{
          val ys:ArrayBuffer[A] = new ArrayBuffer[A](meanReductionSize)
          val step =  N.toFloat/meanReductionSize*2
          @tailrec def next(i:Int):Unit = {
             val inext = i + rand.uniform(step).toInt + 1
             if(inext < to){
                ys += xs(inext)
                next(inext)
             }
          }
          next(from)
          ys
       }
   }
   def sampleWithIndex(meanReductionSize:Int,from:Int=0,to:Int=xs.size)(implicit rand:Rand):ArrayBuffer[(A,Int)] = {
       val N = to - from
       //val meanReductionSize = math.round(reductionRatio*N).toInt
       if(meanReductionSize <= 0) ArrayBuffer[(A,Int)]()
       else if(meanReductionSize >= N) ArrayBuffer[(A,Int)]() ++ xs.slice(from,to).zipWithIndex
       else{
          val ys:ArrayBuffer[(A,Int)] = new ArrayBuffer[(A,Int)](meanReductionSize)
          val step =  N.toFloat/meanReductionSize*2
          @tailrec def next(i:Int):Unit = {
             val inext = i + rand.uniform(step).toInt + 1
             if(inext < to){
                ys += (xs(inext) -> inext)
                next(inext)
             }
          }
          next(from)
          ys
       }
   }


   def rand(implicit r:Rand):Iterator[A] = new RandIterator(xs)(r)

   def sliceWith(bound:Bound[Int]):IndexedSeq[A] = xs.slice(bound.min, bound.max+1)

   /**Binary tree search for a value with an mapping transformation, (Note: assumes sorted by B*/
   final def searchBy[B](searchValue:B, from:Int=0,to:Int=xs.size-1)(elem:A=>B)
        (implicit ord: Ordering[B]):Int = {
     //println("using binary tree search")
     @tailrec def _searchBy(from:Int, to:Int):Int = {
        if(to == from) from else {
          val i = from + (to - from - 1)/2
          val foundValue = elem(xs(i))
          math.signum(ord.compare(searchValue,foundValue)) match {
            case -1 => _searchBy(from, i)
            case  1 => _searchBy(i+1, to)
            case  _ => i
          }
        }
     }
     _searchBy(from,to)
   }
   def someIndexWhere(p:A=>Boolean):Option[Int] = {
     val i = xs indexWhere p
     if(i == -1) None else Some(i)
   }
   def indicesWhere(p:A=>Boolean):IndexedSeq[Int] = for((v,i) <- xs.zipWithIndex; if p(v)) yield i //indices filter {i => p(i)}

   def %(i:Int):A = {val j = i % xs.size;  if(j < 0) xs(xs.size + j) else xs(j) }
   def modOption(i:Int):Option[A] = if(xs.size == 0) None else Some(%(i))

   private def lerpIndex(t:Double):Int = {val N = xs.size -1; (t*N).round.toInt.sat(0,N)}
   def lerp(t:Double):A               = xs.apply(lerpIndex(t))
   def lerpOption(t:Double):Option[A] = if(t < 0 || t > 1) None else xs.lift(lerpIndex(t))
}
/**Seq have sort, reverse*/
final class DrxSeq[A](val xs:Seq[A]) extends AnyVal{
   //return the index of the first match unless it can not be found
   def someIndexWhere(p:A=>Boolean):Option[Int] = {
     val i = xs indexWhere p
     if(i == -1) None else Some(i)
   }
   /**Binary tree search for a value with an mapping transformation, (Note: assumes sorted by B*/
   final def searchBy[B](searchValue:B, from:Int=0)(elem:A=>B)(implicit ord: Ordering[B]):Int = {
     //println("using linear search")
     var i = from
     val it = xs.iterator
     while(it.hasNext){
       val foundValue = elem(it.next())
       if(ord.equiv(searchValue, foundValue))  return i
       else if(ord.lt(searchValue,foundValue)) return i
       i += 1
     }
     i //return last index point
   }
   def doesNotContain(x:A):Boolean = !xs.contains(x)

   def longestCommonSuffix(ys:Seq[A]) = (xs.reverse lcp ys.reverse).toSeq.reverse
   def longestCommonSubsequence(ys:Seq[A]):Seq[A] = ???  //TODO  this is a clever diff providing algorithm that would be nice to have see http://www.geeksforgeeks.org/longest-common-subsequence/ for implementation examples
   def longestRepeatedSubsequence:Seq[A] = ???  //see http://www.geeksforgeeks.org/longest-repeated-subsequence/

   //TODO add generic fields like this for regex, glob and fuzzy matches
   //TODO add an alternate toString view of the collection for the fuzzy find
   def find(fuzzy:Fuzzy):Option[A] = fuzzy.find(xs)
   def sort(fuzzy:Fuzzy):Seq[A] = fuzzy.sort(xs)
   def filter(fuzzy:Fuzzy):Seq[A] = fuzzy.filter(xs)
   def findBy(fuzzy:Fuzzy, asString:A => String):Option[A] = fuzzy.find(xs, asString)
   // def sortBy(fuzzy:Fuzzy, asString:A => String):Seq[A] = fuzzy.sort(xs, asString)
   // def filterby(fuzzy:Fuzzy, asString:A => String):Seq[A] = fuzzy.filter(xs, asString)

   def takeRightWhile(p:A=>Boolean):Seq[A] = xs.reverseIterator.takeWhile(p).toSeq.reverse
}

/*
class RateIterator[A](it:Iterator[A]) extends Iterator[A]{
  private var lastTime:Long = System.getNanos
  def next:A = it.next
  def hasNext:Boolean = hasNext
}
*/

object DrxIterable{
  // tailrec in 2.10 does not work on a monkey patched method
  @tailrec def containsSubsequence[A](xs:Iterable[A], ys:Iterable[A]):Boolean = {
    if(xs.isEmpty || ys.isEmpty) false
    else {
      val y = ys.head
      val ysRest = ys.drop(1)
      val xsRest = xs.dropWhile(_ != y) //step through src
      if(ysRest.isEmpty && xsRest.nonEmpty) true
      else containsSubsequence(xsRest.drop(1), ysRest)
    }
  }
}


/**iterables have zip, slidding*/
final class DrxIterable[A](val xs:Iterable[A]) extends AnyVal{// with DrxTraversable[A](xs){
  private def it:Iterator[A] = xs.iterator

  // def lcp(ys:Iterable[A]):Iterable[A] = (xs,ys).zipped.toIterable.takeWhile(_.same).unzip._1
  def lcp(ys:Iterable[A]):Iterable[A] = xs zip ys takeWhile (_.same) map {_._1}
  // def filterDuplicates = xs.headOption ++ xs.sliding(2).collect{case Seq(a,b) if a != b => b} //does not work in 2.10
  // def filterDuplicates = xs.headOption ++ (xs zip xs.tail).collect{case (a,b) if a != b => b} //does not work in 2.10
  // def filterDuplicates = xs.headOption ++ (xs zip xs.tail).flatMap{case (a,b) => if(a != b) Some(b) else None}
  // def filterDuplicatesOld = xs.headOption ++ xs.sliding(2).flatMap{
  //   case Seq(a,b) => if(a != b) Some(b) else None
  //   case _ =>  None
  // } //does not work in 2.10

  def filterDuplicates:Iterator[A] = slidingFlatMap(xs.headOption){case (a,b) => if(a != b) Some(b) else None}

  def slidingFlatMap[B](init:Option[B])(f: (A,A) => Option[B]):Iterator[B] = {
    init.iterator ++ xs.sliding(2,1).flatMap{ x =>
      x.toList match {
        case List(a,b) => f(a,b)
        case _ => None
      }
    }
  }

  // def groupWhile(test:(A,A) => Boolean):List[List[A]] = DrxList.groupWhile(xs.toList, test)
  // def groupRunsBy[B](f:A => B):List[List[A]] = groupWhile{case (a,b) => f(a) == f(b)}
  def groupWhile(test:(A,A) => Boolean) = it.groupWhile(test)
  def groupRunsBy[B](f:A => B)          = it.groupRunsBy(f)
  def groupRuns                         = it.groupRuns

  def shuffle(implicit r:Rand):Iterable[A] = r.shuffle(xs)

  //-- TODO proxy to DrxIterator methods TODO use  2.13 views instead
  // def evens = it.evens
  // def odds  = it.odds

  def mapFrom[B](f:A=>B):Map[B,A] =  it.mapFrom(f)
  def zipFrom[B](f:A=>B):Iterable[(B,A)] = xs map {x => f(x) -> x}

  def zipTo[B,C](ys:Iterable[B])(f:(A,B)=>C):Iterable[C] = new ZippedIterable(xs,ys,f)

  def getNonEmpty:Option[Iterable[A]] = if(xs.isEmpty) None else Some(xs)
  def mapWith[B](f:A=>B):Map[A,B] =  it.zipWith(f).toMap
  def zipWith[B](f:A=>B):Iterable[(A,B)] = xs map {x => x -> f(x)}

  //--filters
  def mapIf[B](pf:PartialFunction[A,B]):Map[A,B] = it.mapIf(pf)
  def zipIf[B](pf:PartialFunction[A,B]):Iterable[(A,B)] = for(x <- xs if pf isDefinedAt x) yield x -> pf(x)

  def countBy[B](f:A=>B):Map[B,Int] = it.countBy(f)

  /**Like mkString but fits(pads) rows to a size*/
  def fitString:String = it.fitString
  /**Like mkString but fits(pads) rows to a size*/
  def fitString(sizes:Int*):String = it.fitString(sizes:_*)

  def mkLines:String = xs.mkString("\n")
  def mkCommas:String = xs.mkString(", ")
  def mkSpaces:String = xs.mkString(" ")

  /**execute futures serially, alternatively provide grouped size*/
  def mapLinear[B](parLevel:Int)(f:A=>Future[B])(implicit ec:ExecutionContext):Future[Seq[B]] = {
    val asf0 = Future.successful(Seq.empty[B]) //initial accumulated results as a future init
    xs.grouped(parLevel).foldLeft(asf0){ case (asf, xs) =>
      //--fold/join separate grouped futures back into the one single future holding collected future results
      asf.flatMap{as =>
        val bsf = Future.sequence( xs.map{x =>  f(x)} ) //batched future runs: Seq[Future[B]]
        bsf.map{bs => as ++ bs}
      }
    }
  }

  /**async apply a function to a collection with a spaced time delay*/
  def foreachBy(dt:Time)(f: A => Unit)(implicit sc:ScheduledContext, ec:ExecutionContext):Future[Unit] = it.foreachBy(dt)(f)(sc,ec)

  def skip(skipSize:Int, takeSize:Int=1,offset:Int=0):Iterable[A] = {
    val modulus = takeSize + skipSize
    var i = -1
    xs filter {_ => i+=1; (i >= offset) && ((i-offset) % modulus < takeSize)}
  }
  def evens:Iterable[A] = skip(1,1,0)
  def odds:Iterable[A] = skip(1,1,1)

  def sampleByRatio(reductionRatio:Double)(implicit rand:Rand):Iterable[A] = {
    require(reductionRatio <= 1d, "reduction by more than 100% is an error")
    xs filter (_ => rand.uniform < reductionRatio) //TODO add a warning if reductionRatio is greater than 1
    //Use xs.iterator filter to make it compile under 2.13
  }

  //==Note: the ones bellow came from Traversable before moved into Iterable with scala-2.13...
  // FIXME remove this if it is not needed
  // def transposeSafe[B](implicit asIterable: A => collection.GenIterable[B]):Iterable[Iterable[B]] = {
  //   val minSize = xs.minBy{_.size}.size
  //   xs.map{asIterable(_) take minSize}.transpose
  // }

  def same:Boolean = xs.headOption.map{x => xs.forall(_ == x)}.getOrElse(true)

  /**create an Ordinal scale with equal bands steps in the range*/
  def -->[B](range:Bound[B]) = Scale(xs,range)
  /**create an Ordinal scale with mappings to range*/
  def -->[B](range:Iterable[B]) = Scale(xs,range)

  def toTuple2:Try[Tuple2[A,A]]   = {
    val vs = xs.take(2).toList
    if(vs.size == 2) Success( (vs.head, vs.last) ) else Failure(Exception.ArgumentSize)
  }
  def toTuple3:Try[Tuple3[A,A,A]] = {
    val vs = xs.take(3).toList
    if(vs.size == 3) Success( (vs.head, vs.tail.head, vs.last) )  else Failure(Exception.ArgumentSize)
  }
  def containsSubsequence(ys:Iterable[A]):Boolean = DrxIterable.containsSubsequence(xs,ys)

  /**trapezoidal integration*/
  def integrate(f: A => Double)(implicit num:Numeric[A]):Double = it.integrate(f)(num)

}

final class DrxIteratorDouble(val xs:Iterator[Double]) extends AnyVal{
  def deltas:Iterator[Double] = xs.zip(xs drop 1).map{case (a,b) => b - a}

  //**differentiation with respect to `ts` (behaves like zip) */
  def diff(ts:Iterator[Double]):Iterator[Double] = {
    (xs zip ts).sliding(2).collect{
      case Seq( (xa,ta), (xb,tb) ) =>  (xb-xa)/(tb-ta)
    }
  }
}

// final class DrxTraversableOnce[A](val xs:TraversableOnce[A]) extends AnyVal{
// final class DrxTraversableOnce[A](val xs:IterableOnce[A]) extends AnyVal{
final class DrxIterator[A](val xs:Iterator[A]) extends AnyVal{
  2017-07-30("use sampleByRatio instead for typesafety between Traverable and IndexedSeq samples","0.2.13")
  def sample(reductionRatio:Double)(implicit rand:Rand):Iterator[A] = sampleByRatio(reductionRatio)(rand)
  def sampleByRatio(reductionRatio:Double)(implicit rand:Rand):Iterator[A] = {
    require(reductionRatio <= 1d, "reduction by more than 100% is an error")
    xs filter (_ => rand.uniform < reductionRatio) //TODO add a warning if reductionRatio is greater than 1
    //Use xs.iterator filter to make it compile under 2.13
  }
  def skip(skipSize:Int, takeSize:Int=1,offset:Int=0):Iterator[A] = {
    val modulus = takeSize + skipSize
    var i = -1
    xs filter {_ => i+=1; (i >= offset) && ((i-offset) % modulus < takeSize)}
  }
  def evens:Iterator[A] = skip(1,1,0)
  def odds:Iterator[A] = skip(1,1,1)

  //#-- stats
  def statBy(f:A=>Double):Stat = xs.foldLeft( Stat()    ){(stat,x) => stat + f(x)}
  def statBy(f:A=>Vec):StatVec = xs.foldLeft( StatVec() ){(stat,x) => stat + f(x)}

  //(a && b && c)  => Seq(a,b,c).forall(a => a)
  //(a || b || c)  => Seq(a,b,c).exists(a => a)
  //

  /**Like mkString but fits(pads) rows to a size*/
  def fitString:String = if(xs.isEmpty) "" else {
    val strings = xs.map{_.toString}.toList
    val maxLength = strings.maxBy{_.size}.size
    strings.iterator.fitString(maxLength+1) //autodetect width with max string
  }
  /**Like mkString but fits(pads) rows to a size*/
  def fitString(sizes:Int*):String = {
    if(xs.isEmpty) ""
    else if(sizes.isEmpty) xs.fitString
    else {
      val ncols = sizes.size
      xs.grouped(ncols).map{row =>
        (row zip sizes).map{case (x,w) => x.toString.fit(w)}.mkString("")
      }.mkString("")
    }
  }

  def mkLines:String  = xs.mkString("\n")
  def mkCommas:String = xs.mkString(", ")
  def mkSpaces:String = xs.mkString(" ")

  2017-07-30("use mapWith(f) or mapBy(f)","0.1.8")
  def mkMap[B](f:A=>B):Map[A,B] = (xs map {x => x -> f(x)}).toMap
  2017-07-30("use mapFrom(f) since it is beter in line wiht the zipFrom command","0.2.13")
  def mapBy[B](f:A=>B):Map[B,A] =  zipFrom(f).toMap

  /**like zipWith but clobers uniq elements*/
  def mapWith[B](f:A=>B):Map[A,B] =  zipWith(f).toMap
  def zipWith[B](f:A=>B):Iterator[(A,B)] = xs map {x => x -> f(x)}

  /**collect like operations*/
  def mapIf[B](pf:PartialFunction[A,B]):Map[A,B] = zipIf(pf).toMap
  def zipIf[B](pf:PartialFunction[A,B]):Iterator[(A,B)] = for(x <- xs if pf isDefinedAt x) yield x -> pf(x)

  /**like group by but clobbers unique id's*/
  def mapFrom[B](f:A=>B):Map[B,A] =  zipFrom(f).toMap
  def zipFrom[B](f:A=>B):Iterator[(B,A)] = xs map {x => f(x) -> x}
  def zipTo[B,C](ys:Iterator[B])(f:(A,B)=>C):Iterator[C] = (xs zip ys).map{case (x,y) => f(x,y)} //TODO remove toSeq

  def ratioWhere(p:A => Boolean):Ratio = {
    var i = 0L
    var found = 0L
    for(x <- xs){ i += 1;  if(p(x)) found += 1}
    Ratio(found, i) //found per total
  }
  def countWhile(f:A => Boolean):Int = {
    var i = 0
    for(x <- xs) if(f(x)) i += 1
    i
  }
  /**SI-7365 a more efficient binning without using groupBy (the collection is lost here unless identity is used)*/
  def countBy[B](f:A=>B):Map[B,Int] = {
    val m = collection.mutable.Map.empty[B,Int].withDefaultValue(0)
    for(x <- xs){
      val k = f(x)
      m(k) = m(k) + 1
    }
    m.toMap
  }
  //note: creates a vector
  /**most generic base function to create group by like run length encodings, see also the simpler [[groupRuns]] and [[groupRunsBy]] */
  def groupWhile(f:(A,A)=>Boolean):Vector[Vector[A]] = {
    def pack(gs:Vector[Vector[A]], g:Vector[A], ps:Seq[(A,A)]):Vector[Vector[A]] = {
      if(ps.nonEmpty){
         val p = ps.head
         val (a,b) = p
         if( f(a,b) ) pack(     gs,   g :+ b , ps.tail)
         else         pack(gs :+ g, Vector(b), ps.tail)
      }
      else gs :+ g
    }

    val gs = Vector[Vector[A]]()
    if(xs.isEmpty) gs
    else{
      val _xs = xs.toSeq
      val g = Vector(_xs.head)
      val rest = _xs.tail
      if(rest.nonEmpty) pack(gs, g, _xs zip rest)
      else Vector(g)
    }
  }
  /** group matches similar runs see also [[groupRunsBy]] to group without an intermediate map */
  def groupRuns:Vector[Vector[A]] = groupWhile{case (a,b) => a == b}
  /** group runs that are equivalent after a transformation */
  def groupRunsBy[B](f:A => B):Vector[Vector[A]] = groupWhile{case (a,b) => f(a) == f(b)}

  2017-07-30("to much magic","v0.2.15")
  def /@[B](f:A=>B) = xs map f
  2017-07-30("to much magic","v0.2.15")
  def /@[B](f:Applicable[A,B]) = xs map {f.apply}

  /**async apply a function to a collection with a spaced time delay*/
  def foreachBy(dt:Time)(f: A => Unit)(implicit sc:ScheduledContext, ec:ExecutionContext):Future[Unit] = {
    // specialized next version from the generalized `linearize` from Klang @ https://stackoverflow.com/a/38848181/622016
    // should use/include something like the general form
    // 
    def next(it: Iterator[A],first:Boolean): Future[Unit] =
      //--done
      if(!it.hasNext) DrxFuture.unit
      //--don't delay on the first one
      else if(first) Future(f(it.next())) flatMap {_ => next(it,false) }
      //-- use a delay for the next one and make sure it returns a unit type
      else dt.delay(f(it.next())) flatMap { _ => next(it,false) } flatMap { _ => DrxFuture.unit}

    next(xs,true)
  }
  def mapLinear[B](f: A => Future[B])(implicit ec:ExecutionContext):Future[List[B]] = {
    xs.foldLeft(Future(List.empty[B])){ case (a,x) =>
      for(bs <- a; b <- f(x) ) yield b :: bs
    }.map{_.reverse}
  }
  /** this is useful for making sure things like maxBy won't fail*/
  def getNonEmpty:Option[Iterator[A]] = if(xs.isEmpty) None else Some(xs)

  /**trapezoidal integration*/
  def integrate(f: A => Double)(implicit num:Numeric[A]):Double =
    (xs zipWith f sliding 2).foldLeft(0d){case (a, Seq( (x0,y0), (x1,y1) )) =>
     val dx = num.toDouble(x1) - num.toDouble(x0)
     a + (y1 + y0)/2 * dx  //trapezoidal
    }
}

final class DrxMap[A,B](val xs:Map[A,B]) extends AnyVal{
  def mapKeys[C](f:A => C):Map[C,B] = xs.map{case (k,v) => f(k) -> v}.toMap
  def filterValues(p:B => Boolean):Map[A,B] = xs.filter{case (k,v) => p(v)}
  def doesNotContain(x:A):Boolean = !xs.contains(x)
  def containsWith(k:A)(vf:B=>Boolean):Boolean = xs.contains(k) && vf(xs(k))
  def inverted:Map[B,A] = xs.map{case (a,b) => (b,a)}.toMap
}
final class DrxSet[A](val xs:Set[A]) extends AnyVal{
  def doesNotContain(x:A):Boolean = !xs.contains(x)
  def elementOf_:(x:A):Boolean = xs.contains(x)
  def ?:(x:A):Boolean = xs.contains(x)
  //vim digraph: j3 and je repsectively ϵ  э  
}
final class DrxBitSet(val xs:BitSet) extends AnyVal{
   def base2(width:Int=80):String = {
     (0 until width).map{i => if(xs contains i) "1" else "0"}.mkString
   }
}

final class DrxList[A](val xs:List[A]) extends AnyVal{
   //Travis Brown  https://stackoverflow.com/a/14551666/622016  List solution
   //Alex Quach https://stackoverflow.com/a/29043918/622016 simpler with span
   def encodeRunLength:List[(Int,A)] = DrxList.encodeRunLength(xs)

   // def groupRuns:List[List[A]] = groupWhile{case (a,b) => a == b}
   // def groupRunsBy[B](f:A => B):List[List[A]] = groupWhile{case (a,b) => f(a) == f(b)}
   // def groupWhile(test:(A,A) => Boolean):List[List[A]] = DrxList.groupWhile(xs,test)
}

object DrxList {

   //Here is an example where a simple recursive function is simpler and clearer than a dedicated generic api, like iteraterWhile, TODO maybe add an example like this to the deprecation of iterateWhile
   //val ds = DrxList.iterateWhile(d0){d =>  println(s"add $dt to $d"); if(d > bound.max) None else Some(d + dt)}
  2017-07-30("a simple tailrec function is often simple and clearer than this dedicated api","v0.2.15")
  def iterateWhile[A](x0:A)(f:A => Option[A]):List[A] = {
    def appendWhile(x:A, ys:List[A]):List[A] = f(x) match {
      case None    => ys
      case Some(y) => appendWhile(y, y :: ys)
    }
    appendWhile(x0, Nil).reverse
  }
  def encodeRunLength[A](xs:List[A]):List[(Int,A)] = xs match {
    case Nil => List()
    case x :: rest => {
      val (front, back) = rest.span(_ == x)
      (front.length + 1, x) :: encodeRunLength(back) //implicit call to the run length func
    }
  }
  def groupWhile[A](xs:List[A], test:(A,A) => Boolean):List[List[A]] = xs match {
    case Nil => List()
    case x :: rest => {
      val (front, back) = rest.span(y => test(x,y))
      front :: groupWhile(back, test)
    }
  }

}

class DrxIterableIterable[A](val xss:Iterable[Iterable[A]]){
  //TODO it would be much nicer if this was an Iterator[Iterable[A]] but needs more mental work than available right now
  def enumerate:List[List[A]] = {
    def f(digits:List[List[A]], head:List[A]):List[List[A]] = digits match {
      case Nil => List(head)
      case ds :: rest => ds flatMap {d =>  f(rest, d :: head) }
    }
    f(xss.toList map {_.toList}, Nil).map{_.reverse}
  }
}

import scala.reflect.ClassTag
object RingBuffer{
  def empty[A:ClassTag] = new RingBuffer[A](4.k) //default ring buffer is a nice size for 4k monitor
  def empty[A:ClassTag](maxSize:Int) = new RingBuffer[A](maxSize)
}
class RingBuffer[A: reflect.ClassTag](maxSize:Int) extends Iterable[A]{
  private val buf:Array[A] = Array.ofDim(maxSize) //new Array[A](maxSize)
  private var iend:Int = -1 //pointer to last
  private var n:Int = 0 //size of available data
  /**to match feature like ArrayBuffer*/
  def clear:Unit = { iend = -1; n = 0 }
  override def size:Int = n

  override def lastOption:Option[A] = if(iend < 0) None else Some(apply(n-1))

  def isFull:Boolean = size == maxSize

  def +=(x:A):Unit = {
    iend += 1
    buf(iend % maxSize) = x
    if(n < maxSize) n += 1
  }

  @inline private def i0(i:Int):Int = (iend - n + 1 + i) % maxSize
  def apply(i:Int):A = buf(i0(i))
  def get(i:Int):Option[A] = if(i < maxSize) Some(apply(i)) else None

  // def foreach[U](f:A => U):Unit = 0 until n foreach {i => f( apply(i) ) }

  def iterator:Iterator[A] = (0 until n).iterator map apply

}