/* 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 object Bound{ def apply[A](min:A, max:A)(implicit b:Bound.Boundable[A]) = new Bound(min, max)(b) 2017-07-30("use Bound.of[Double] instead (MinMax should not be specifically tied to a Double?)", "v0.2.15") val MinMax = Bound(Double.MinValue,Double.MaxValue)(Boundable.BoundableDouble) /** find iterates over a collection to create a min max, this is a very simple Stat but is general types have have Boundable typeclass*/ def find[A](it:Iterator[A])(implicit b:Bound.Boundable[A]):Option[Bound[A]] = { if(!it.hasNext) None else{ var min = it.next() var max = min while(it.hasNext){ val x = it.next() if(b.lessThan(x, min)) min = x if(b.lessThan(max, x)) max = x } Some(new Bound(min, max)(b)) } } def find[A](xs:Iterable[A])(implicit b:Bound.Boundable[A]):Option[Bound[A]] = xs.headOption.map{ head => val (min,max) = xs.foldLeft( (head,head) ){case ((min,max),x) => ( if(b.lessThan(x, min)) x else min, if(b.lessThan(max, x)) x else max )} new Bound(min, max)(b) } def of[A](implicit boundOf:BoundOf[A]):Bound[A] = boundOf.bound trait Boundable[A]{ def lessThan(a:A,b:A):Boolean def interpolate(min:A,max:A,ratio:Double):A def ratioOf(min:A,max:A,x:A):Double // interpolate needs to be invertible if this is required //---extra features if implmented, these should really be inside a separate typeclasss to check for capability at compile time def dist(min:A,max:A):Double = ??? // dist is a norm function that turns objects into a reported dist def gain(min:A,max:A):Double = ??? // gain is a norm function that calculates the relative scale (required for Log scales) def toString(a:A,b:A):String = s"Bound($a ~ $b)" //---override-able /**norm puts it into a canonical Bound form where the min < max */ 2017-07-30("try not to use this function, it was to specialized","0.2.13") def norm(b:Bound[A]):Bound[A] = if(lessThan(b.min,b.max)) b else b.swap def contains(b:Bound[A],v:A):Boolean = b.min == v || b.max == v || { //quick check for edge cases val ltMax = lessThan(v,b.max) //store value for the normalized and non-normalized case val ltMin = lessThan(v,b.min) !ltMin && ltMax || !ltMax && ltMin //inverted case should still test correctly } /**TODO this needs description because its hard to remember what this does*/ /** this version does not require the min to be less than the max norm puts it into a canonical Bound form where the min < max */ 2017-07-30("the 'normal' `contains` method should provide this functionality","0.2.13") def containsNorm(b:Bound[A],v:A):Boolean = contains(b,v) final def equals(a:A,b:A):Boolean = a == b final def lessThanOrEqual(a:A,b:A):Boolean = equals(a,b) || lessThan(a,b) //equals is a faster quick check final def min(a:A,b:A):A = if(lessThan(a,b)) a else b final def max(a:A,b:A):A = if(lessThan(a,b)) b else a } //TODO add some type safe way of differentiation invertible(domain) and range that doesn't require invertible bounds object Boundable{ implicit object BoundableByte extends Boundable[Byte]{ def lessThan(a:Byte,b:Byte) = a < b def interpolate(min:Byte,max:Byte, ratio:Double) = (min + ratio*(max-min)).round.toByte def ratioOf(min:Byte, max:Byte, x:Byte) = (x-min).toDouble/(max-min) override def dist(min:Byte,max:Byte) = (max.toDouble - min).abs override def gain(min:Byte,max:Byte) = (max.toDouble/min).abs } implicit object BoundableChar extends Boundable[Char]{ def lessThan(a:Char,b:Char) = a < b def interpolate(min:Char,max:Char, ratio:Double) = (min + ratio*(max-min)).round.toChar def ratioOf(min:Char, max:Char, x:Char) = (x-min).toDouble/(max-min) override def dist(min:Char,max:Char) = (max.toDouble - min).abs override def gain(min:Char,max:Char) = (max.toDouble/min).abs } implicit object BoundableShort extends Boundable[Short]{ def lessThan(a:Short,b:Short) = a < b def interpolate(min:Short,max:Short, ratio:Double) = (min + ratio*(max-min)).round.toShort def ratioOf(min:Short, max:Short, x:Short) = (x-min).toDouble/(max-min) override def dist(min:Short,max:Short) = (max - min).abs override def gain(min:Short,max:Short) = (max.toDouble/min).abs } implicit object BoundableInt extends Boundable[Int]{ def lessThan(a:Int,b:Int) = a < b def interpolate(min:Int,max:Int, ratio:Double) = (min + ratio*(max-min)).round.toInt def ratioOf(min:Int, max:Int, x:Int) = (x-min).toDouble/(max-min) override def dist(min:Int,max:Int) = (max.toDouble - min).abs override def gain(min:Int,max:Int) = (max.toDouble/min).abs } implicit object BoundableLong extends Boundable[Long]{ def lessThan(a:Long,b:Long) = a < b def interpolate(min:Long,max:Long, ratio:Double) = (min + ratio*(max-min)).round.toLong def ratioOf(min:Long, max:Long, x:Long) = (x-min).toDouble/(max-min) override def dist(min:Long,max:Long) = (max.toDouble - min).abs override def gain(min:Long,max:Long) = (max.toDouble/min).abs } implicit object BoundableDouble extends Boundable[Double]{ def lessThan(a:Double,b:Double) = a < b def interpolate(min:Double,max:Double, ratio:Double) = min + ratio*(max-min) def ratioOf(min:Double,max:Double, x:Double) = (x-min)/(max-min) override def dist(min:Double,max:Double):Double = (max - min).abs override def gain(min:Double,max:Double):Double = (max/min).abs //note negative } implicit object BoundableFloat extends Boundable[Float]{ def lessThan(a:Float,b:Float):Boolean = a < b def interpolate(min:Float,max:Float, ratio:Double):Float = (min + ratio*(max-min)).toFloat def ratioOf(min:Float,max:Float, x:Float):Double = (x-min).toDouble/(max-min) override def dist(min:Float,max:Float):Double = (max.toDouble - min).abs override def gain(min:Float,max:Float):Double = (max.toDouble/min).abs //note negative } implicit object BoundableColor extends Boundable[Color]{ def lessThan(a:Color,b:Color) = ??? def interpolate(min:Color,max:Color, ratio:Double) = (min lerp max)(ratio) def ratioOf(min:Color,max:Color, x:Color) = ??? // (x-min)/(max-min) } implicit object BoundableDate extends Boundable[Date]{ def lessThan(a:Date,b:Date) = a < b def interpolate(min:Date,max:Date, ratio:Double) = Date(min.ms + ratio*(max.ms - min.ms)) def ratioOf(min:Date,max:Date, x:Date) = (x.ms - min.ms).toDouble/(max.ms - min.ms) override def dist(min:Date,max:Date):Double = (max.ms - min.ms).toDouble.abs override def gain(min:Date,max:Date):Double = (max.ms/min.ms).toDouble.abs override def toString(min:Date,max:Date) = f"Bound(${Time(dist(min,max)*1E-3).format}%8s from ${min.date} to ${max.date})" } implicit object BoundableVec extends Boundable[Vec]{ def lessThan(a:Vec,b:Vec) = ??? def interpolate(min:Vec,max:Vec, ratio:Double) = min + (max-min)*ratio def ratioOf(min:Vec,max:Vec, x:Vec) = (x - min).norm/(max - min).norm //TODO FIXME this is not a true ratioOf because 2d, so use a line to find the closest point along the line override def dist(min:Vec,max:Vec):Double = (max - min).norm override def gain(min:Vec,max:Vec):Double = max.norm/min.norm override def toString(min:Vec,max:Vec) = f"Bound(${dist(min,max)} from $min to $max)" } } class BoundOps[A](private val minArg:A)(implicit b:Boundable[A]){ /**Bound construction since the Range constructor is deprecated*/ def till(maxArg:A):Bound[A] = Bound(minArg,maxArg)(b) //TODO switch `to` to be `boundTo` or `till` so it doesn't conflict with the ambiguous Range implicit } trait BoundOf[A]{ def bound:Bound[A] } object BoundOf{ implicit object BoundOfByte extends BoundOf[Byte] { val bound = Bound(Byte.MinValue, Byte.MaxValue) } implicit object BoundOfChar extends BoundOf[Char] { val bound = Bound(Char.MinValue, Char.MaxValue) } implicit object BoundOfShort extends BoundOf[Short] { val bound = Bound(Short.MinValue, Short.MaxValue) } implicit object BoundOfInt extends BoundOf[Int] { val bound = Bound(Int.MinValue, Int.MaxValue) } implicit object BoundOfLong extends BoundOf[Long] { val bound = Bound(Long.MinValue, Long.MaxValue) } implicit object BoundOfFloat extends BoundOf[Float] { val bound = Bound(Float.MinValue, Float.MaxValue) } implicit object BoundOfDouble extends BoundOf[Double]{ val bound = Bound(Double.MinValue, Double.MaxValue) } } //---stepper features final class BoundIterator[A](b:Bound[A], nextAfter:A => A) extends Iterator[A]{ private var theNext:A = b.min final def hasNext:Boolean = b.contains(theNext) //TODO add check for no steps infinite loop case final def next():A = {val res = theNext; theNext = nextAfter(theNext); res} } trait BoundStep[A,B]{ //required interface def next(a:A, stepSize:B):A //implemented interface final def step(b:Bound[A], stepSize:B):BoundIterator[A] = new BoundIterator(b, (x:A) => next(x,stepSize)) } object BoundStep{ implicit object BoundDateStep extends BoundStep[Date,Time]{ def next(a:Date, step:Time):Date = a + step } implicit object BoundTimeStep extends BoundStep[Time,Time]{ def next(a:Time, step:Time):Time = a + step } implicit object BoundDoubleStep extends BoundStep[Double,Double]{ def next(a:Double, step:Double):Double = a + step } implicit object BoundIntStep extends BoundStep[Int,Int]{ def next(a:Int, step:Int):Int = a + step } //TODO add other implicit stepper classes } //--TODO add Power scale Bounds // explore errors for ranges //val rep=1 << 8; for(i <- Bound(0, rep).ticks(20); x=3.k.log(rep); d=i**x; dn=(i+1)**x; dd=dn-d; dp = dd/d) Log(i,d,dd,dp) /**Log interpolate min ~ max ratio while preserving the original values and using the max and min to determine a scale range */ class Log[A](min:A, max:A)(implicit b:Bound.Boundable[A]) extends Bound[A](min,max)(b){ //y = $log_{base}(x)$ => `x.log(base)` //1-------2---e------------------------10----------------------------------20- //| 2 e 10 20 //| 2 e 10 //| 2 e 10 //0---|---|---|-------------------------|----------------------------------|----> x // 1 2 e 10 20 // |-bound-| | // |<---------base 10 ratio bound--->| //==================================================== //log: 0.0 0.25 0.5 0.75 1.0 //linE: 0 9/99 1 //--- //ex: 1 3.16 10 31.6 100 //ex: E^0 E^0.25 E^0.5 E^0.75 E //ex: 10 31.6 100 316. 1000 //ex: 10^1 10^1.5 10^2 10^2.5 10^3 //ex: e^2 e^3 e^4 e^5 e^6 // /**Note: it feels magical and incredible that the interpolation is independent of a log base value, but rather the max/min gain of the bound * */ final val gain = b.gain(min,max) //note this gain method needs to be overridden in the Boundable type class override def ratioOf(x:A):Double = ((gain-1)*super.ratioOf(x) + 1).log(gain) // p = (b-1)*r + 1 . log(b) override def lerp(p:Double):A = super.lerp( (gain**p - 1)/(gain-1) ) // b^p = (b-1)*r + 1 //---- // r = (b^p - 1)(b-1) // TODO steps && ticks should be log linear // def take(N:Int):Seq[A] = if(N==0) Seq() else if(N==1) Seq(lerp(0.5)) else (0 to (N-1)).map{i => lerp(i.toDouble/(N-1))} // override def ticks(n:Int)(implicit t:Tickable[A]):Iterable[A] = t.logTicks(n,this,base) // def ticksWithFormat(n:Int)(implicit t:Tickable[A]):Iterable[(A,String)] = t.logTicksWithFormat(n,this,base) def linearTicks(n:Int)(implicit t:Tickable[A]):Iterable[A] = t.ticks(n,this) override def ticks(n:Int)(implicit t:Tickable[A]):Iterable[A] = t.logTicks(n,this,10) //default to base 10 } //provide an argument like parser for common bound types implicit object ParsableBoundInt extends Parsable[Bound[Int]]{ def apply(str:String):Bound[Int] = { val vs = Parse.split[Int](str); Bound(vs(0), vs(1)) } } implicit object ParsableBoundDouble extends Parsable[Bound[Double]]{ def apply(str:String):Bound[Double] = { val vs = Parse.split[Double](str); Bound(vs(0), vs(1)) } } implicit object ParsableBoundDate extends Parsable[Bound[Date]]{ def apply(str:String):Bound[Date] = { val vs = Parse.split[Date](str); Bound(vs(0), vs(1)) } } } //a bound represents a set that includes the min and max, not this is not a case class so needs some extras there that usually come by default class Bound[A](override val min:A, override val max:A)(implicit b:Bound.Boundable[A]) extends LerpInv[A]{ //-- equality tests // def canEqual(that:Any):Boolean = that.isInstanceOf[Bound[A]] override def equals(that:Any):Boolean = that match { case that:Bound[_] => this.min == that.min && this.max == that.max case _ => false } // override def hashCode():Int = min.## + 31*max.## def isSingular:Boolean = min == max //-- Value containment tests def in_:(v:A):Boolean = contains(v) def out_:(v:A):Boolean = containsNot(v) // def op for this ???v:A):Boolean = containsNot(v) //∈ elemnt of operator def ∈:(v:A):Boolean = contains(v) def ∉:(v:A):Boolean = containsNot(v) def <(v:A):Boolean = b.lessThan(max,v) def >(v:A):Boolean = b.lessThan(v,min) override def contains(v:A):Boolean = b.contains(this,v) def containsNot(v:A):Boolean = !contains(v) 2017-07-30("the 'normal' `contains` method should provide this functionality","0.2.13") def containsNorm(v:A):Boolean = b.containsNorm(this,v) //-- Bound containment tests /** of any part is overlapped * cases | condition | a containsSome b | a containsAll b | a contains b is ambiguous (don't use) * a{ b( ) } total true true * a{ b( } ) partial true false * a{} b( ) none false false * b( a{} ) inside true false */ def containsSome(that:Bound[A]):Boolean = contains(that.min) || contains(that.max) || isInside(that) def containsAll(that:Bound[A]):Boolean = contains(that.min) && contains(that.max) /** convenience function to make containment tests read better where `a isInside b` == `b containsAll a` */ def isInside(b:Bound[A]):Boolean = b containsAll this /** convenience function to make containment tests read better with right associativity*/ def in_:(b:Bound[A]):Boolean = this containsAll b //--reverse lookups /**reverse lookup * while not mathematically sound a return of 0.5 is nice for visuals */ def ratioOf(x:A):Double = if(isSingular) 0.5 else b.ratioOf(min,max,x) def ratioOfOption(x:A):Option[Double] = if(isSingular) None else Some(b.ratioOf(min,max,x)) //--lookup methods /**type class based interpolator (0 to 1)*/ def lerp(ratio:Double):A = b.interpolate(min,max, ratio) /**alias for `lerp` or `apply`*/ final def %(ratio:Double):A = lerp(ratio) //use final so the main entry point of lerp is the one to be extended //TODO deprecate the apply variation on bound and only use it on double??? 2017-07-30("use `lerp` instead since bound now extends Lerp, `lerp` is the entry point and can be mixed in better, (it will help catch overloaded errors that extended the wrong function root function)","v0.2.15") final def apply(ratio:Double):A = lerp(ratio) /**simple way to lookup and keep within a bound*/ def sat(x:A):A = if(b.lessThan(x,min)) min else if(b.lessThan(max,x)) max else x /**simple way to lookup and return only if it is in the bound*/ def satOption(x:A):Option[A] = if(b.lessThan(x,min) || b.lessThan(max,x)) None else Some(x) /**produce a new bound that limits the current bound by the second * (Note: this is not an intersection because this operation is always defined but is also not associative) * */ def satBy(that:Bound[A]):Bound[A] = Bound(that sat min, that sat max) //who uses this now? def dist:Double = b.dist(min,max) /**a nice step by function that matches the scala.Range form, * Note: the implicit typeclass is used for bounds that can not be steped, like colors and also prevent * the requirement of a hard coded type parameter for Bounds*/ def by[B](stepSize:B)(implicit s:Bound.BoundStep[A,B]):Iterator[A] = s.step(this,stepSize) // def integrate(???) = ??? //----bound to scales ... //TODO add other --> constructors to simplfy bound generation or instead create an operator object!!! /**mapsTo, arrow, linear transformation, morphism ... https://www.wikiwand.com/en/Map_(mathematics)*/ def -->[B](that:Bound[B]) = Scale(this,that) //TODO add a --> to Lerp mapsTo possibly should be based on interpolator instead /**alias for `mapsTo`*/ def mapsTo[B](that:Bound[B]) = this --> that 2017-07-30("use --> insted of the harder to see and similar 'to' in Range()","v0.2.00") def to[B](that:Bound[B]) = Scale(this,that) 2017-07-30("use (a to b) instead of (b from a) to many verbs","v0.2.00") def from[B](that:Bound[B]) = Scale(that,this) //----log bounds def log:Bound.Log[A] = new Bound.Log(min,max)(b) //----bound adjusting /**merge(grow to a union) bound (useful for parallel processing)*/ def ++(that:Bound[A]):Bound[A] = Bound(b.min(this.min, that.min), b.max(this.max, that.max))(b) //TODO check if this works in both directions //TODO test subtract find the intersection regions Note: this operation is undefined if there is no intersections def --(that:Bound[A]):Option[Bound[A]] = { val min = b.max(this.min, that.min) val max = b.min(this.max, that.max) if(b.lessThan(min,max)) Some(Bound(min,max)) else None } //lazy val dist = b.sub(max,-min) //TODO assumes max is greater than min, may need to add a warning if this isn't the case (Note some scales break if this is 'abs') def extend(n:Int)(implicit t:Tickable[A]):Bound[A] = t.extend(n,this) /**Boundable has this as an overridable method that may be specific for some special classses*/ 2017-07-30("try not to use this function, it was to specialized","0.2.13") lazy val norm:Bound[A] = b.norm(this) def swap:Bound[A] = Bound(max,min) def reverse:Bound[A] = Bound(max,min) /**generic function mapping to convert one bound to another type (that is boundable)*/ def map[B](f:A=>B)(implicit b:Bound.Boundable[B]) :Bound[B] = Bound(f(min),f(max))(b) //explicit type parameter for generic mapping to boundable types /**scale with the pivot origin at min (simply applies the gain to the max value)*/ def scale(gain:Double):Bound[A] = Bound(min, lerp(gain)) // lerp(0*gain) ~ lerp(1.0*gain) this gain=1.0 keeps it in place, 1.1 puts it 10% further /**generic scale and translate without inverse lookup*/ def translate(ratio:Double):Bound[A] = Bound(lerp(ratio), lerp(1.0+ratio)) /**convenience function to help calculate translation ratios based on the bound values*/ def translateBy(from:A,to:A):Bound[A] = translate(ratioOf(to) - ratioOf(from)) /**convenience function for scaleAtRatio by using the imutable pivot lookup value*/ def scaleAt(gain:Double,pivot:A):Bound[A] = scaleAtRatio(gain, ratioOf(pivot)) /**generic scale and translate around an immutable pivot point without inverse lookup*/ def scaleAtRatio(gain:Double,pivot:Double):Bound[A] = this translate (pivot*(1-gain)) scale gain //see Notability:Bound Scale diagram //TODO def centerAt(pivot:A):Bound[A] = ratioOf(pivot) //TODO find out if these operators follow interval aritmetic and if they do then use that mathematically sound work /**operator form to scale from the middle `scaleAtRatio(gain,0.5)` */ def *(gain:Double):Bound[A] = scaleAtRatio(gain,0.5) //this is nice for scaling but what does it mean for interval arith?? def /(gain:Double):Bound[A] = scaleAtRatio(gain.inv,0.5) // def +(gain:Double):Bound[A] = translate(gain) // def -(gain:Double):Bound[A] = translate(gain.inv) //1~2 => 2 /* TODO `A` needs a zero concept offset from min location def +(offset:A):Bound[A] = translate(ratioOf(offset)) def -(offset:A):Bound[A] = ??? */ def ==(that:Bound[A]):Boolean = (this.min == that.min) && (this.max == that.max) //TODO not sure how equality of scala,java and hashCodes all fit into this equality test /**generic bisect algorithm with N steps for a function that turns from false to true *Note:this version requires the initial crossing occurs between min~max, or f(min) == false && f(max) == true) */ def bisect(f:A => Boolean, N:Int=64):A = { val mid = lerp(0.5) if(N <= 0) mid else (if( f(mid) ) Bound(min, mid) else Bound(mid,max)).bisect(f,N-1) } def bisectOption(f:A => Boolean, N:Int=64):Option[A] = if( !f(min) && f(max)) Some(bisect(f,N)) else None //def argMin //TODO add a argmin function override def toString = b.toString(min,max) }