From e326df2c225eefcfd058e19963d3a7fdf366637d Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Tue, 12 May 2009 14:30:04 +0000 Subject: This patch includes the following: 1) Default Ordering implementations for various built-in types, supplied by DrMacIver. Ticket #1303. 2) Implicits for scala.Numeric and scala.Ordering so classes implementing those can use punctuation and, more importantly, infix notation. Compare "minus(plus(x, y), z)" to "x + y - z". 3) A generic implementation of Range, but leaving the original Int-only Range untouched. A LongRange. 4) Numeric and Ordering implementations of BigInt, as required for the new BigIntRange. Ticket #931. 5) Numeric implementations for built-in types changed to the trait + implicit-object-extends-trait model so the implementation can be mixed into other objects - in particular one might easily want to combine Numeric[T] and Ordering[T] in one object. 6) Assorted tweaks to support all the above. --- src/library/scala/Fractional.scala | 5 + src/library/scala/Integral.scala | 6 + src/library/scala/Numeric.scala | 48 +++++++- src/library/scala/Ordering.scala | 245 +++++++++++++++++++++++++++++++++++++ src/library/scala/Range.scala | 137 ++++++++++++++++++++- 5 files changed, 434 insertions(+), 7 deletions(-) (limited to 'src/library') diff --git a/src/library/scala/Fractional.scala b/src/library/scala/Fractional.scala index 81366a80b9..c8905ce5fd 100755 --- a/src/library/scala/Fractional.scala +++ b/src/library/scala/Fractional.scala @@ -2,4 +2,9 @@ package scala trait Fractional[T] extends Numeric[T] { def div(x: T, y: T): T + + class FractionalOps(lhs: T) extends Ops(lhs) { + def /(rhs: T) = div(lhs, rhs) + } + override implicit def mkNumericOps(lhs: T): FractionalOps = new FractionalOps(lhs) } diff --git a/src/library/scala/Integral.scala b/src/library/scala/Integral.scala index bfd4bf9f48..425cccdb48 100755 --- a/src/library/scala/Integral.scala +++ b/src/library/scala/Integral.scala @@ -3,4 +3,10 @@ package scala trait Integral[T] extends Numeric[T] { def quot(x: T, y: T): T def rem(x: T, y: T): T + + class IntegralOps(lhs: T) extends Ops(lhs) { + def /(rhs: T) = quot(lhs, rhs) + def %(rhs: T) = rem(lhs, rhs) + } + override implicit def mkNumericOps(lhs: T): IntegralOps = new IntegralOps(lhs) } diff --git a/src/library/scala/Numeric.scala b/src/library/scala/Numeric.scala index 4f7e4749cf..ba48db9c1d 100755 --- a/src/library/scala/Numeric.scala +++ b/src/library/scala/Numeric.scala @@ -1,7 +1,24 @@ package scala object Numeric { - implicit object IntIsIntegral extends Integral[Int] { + trait BigIntIsIntegral extends Integral[BigInt] { + def plus(x: BigInt, y: BigInt): BigInt = x + y + def minus(x: BigInt, y: BigInt): BigInt = x - y + def times(x: BigInt, y: BigInt): BigInt = x * y + def quot(x: BigInt, y: BigInt): BigInt = x / y + def rem(x: BigInt, y: BigInt): BigInt = x % y + def negate(x: BigInt): BigInt = -x + def abs(x: BigInt): BigInt = if (x < 0) -x else x + def signum(x: BigInt): BigInt = if (x < 0) -1 else if (x > 0) 1 else 0 + def fromInt(x: Int): BigInt = BigInt(x) + def toInt(x: BigInt): Int = x.intValue + def toLong(x: BigInt): Long = x.longValue + def toFloat(x: BigInt): Float = x.longValue.toFloat + def toDouble(x: BigInt): Double = x.longValue.toDouble + } + implicit object BigIntIsIntegral extends BigIntIsIntegral + + trait IntIsIntegral extends Integral[Int] { def plus(x: Int, y: Int): Int = x + y def minus(x: Int, y: Int): Int = x - y def times(x: Int, y: Int): Int = x * y @@ -16,7 +33,9 @@ object Numeric { def toFloat(x: Int): Float = x def toDouble(x: Int): Double = x } - implicit object LongIsIntegral extends Integral[Long] { + implicit object IntIsIntegral extends IntIsIntegral + + trait LongIsIntegral extends Integral[Long] { def plus(x: Long, y: Long): Long = x + y def minus(x: Long, y: Long): Long = x - y def times(x: Long, y: Long): Long = x * y @@ -31,7 +50,9 @@ object Numeric { def toFloat(x: Long): Float = x def toDouble(x: Long): Double = x } - implicit object FloatIsFractional extends Fractional[Float] { + implicit object LongIsIntegral extends LongIsIntegral + + trait FloatIsFractional extends Fractional[Float] { def plus(x: Float, y: Float): Float = x + y def minus(x: Float, y: Float): Float = x - y def times(x: Float, y: Float): Float = x * y @@ -45,7 +66,9 @@ object Numeric { def toFloat(x: Float): Float = x def toDouble(x: Float): Double = x } - implicit object DoubleIsFractional extends Fractional[Double] { + implicit object FloatIsFractional extends FloatIsFractional + + trait DoubleIsFractional extends Fractional[Double] { def plus(x: Double, y: Double): Double = x + y def minus(x: Double, y: Double): Double = x - y def times(x: Double, y: Double): Double = x * y @@ -59,8 +82,9 @@ object Numeric { def toFloat(x: Double): Float = x.toFloat def toDouble(x: Double): Double = x } -} + implicit object DoubleIsFractional extends DoubleIsFractional +} trait Numeric[T] { def plus(x: T, y: T): T @@ -76,4 +100,18 @@ trait Numeric[T] { def toDouble(x: T): Double def zero = fromInt(0) def one = fromInt(1) + + class Ops(lhs: T) { + def +(rhs: T) = plus(lhs, rhs) + def -(rhs: T) = minus(lhs, rhs) + def *(rhs: T) = times(lhs, rhs) + def unary_-() = negate(lhs) + def abs(): T = Numeric.this.abs(lhs) + def signum(): T = Numeric.this.signum(lhs) + def toInt(): Int = Numeric.this.toInt(lhs) + def toLong(): Long = Numeric.this.toLong(lhs) + def toFloat(): Float = Numeric.this.toFloat(lhs) + def toDouble(): Double = Numeric.this.toDouble(lhs) + } + implicit def mkNumericOps(lhs: T): Ops = new Ops(lhs) } diff --git a/src/library/scala/Ordering.scala b/src/library/scala/Ordering.scala index 9b18cb7e0c..663af258dd 100644 --- a/src/library/scala/Ordering.scala +++ b/src/library/scala/Ordering.scala @@ -71,4 +71,249 @@ trait Ordering[T] extends PartialOrdering[T] { * y in the ordering. */ override def equiv(x: T, y: T): Boolean = compare(x, y) == 0 + + class Ops(lhs: T) { + def <(rhs: T) = lt(lhs, rhs) + def <=(rhs: T) = lteq(lhs, rhs) + def >(rhs: T) = gt(lhs, rhs) + def >=(rhs: T) = gteq(lhs, rhs) + def ===(rhs: T) = equiv(lhs, rhs) + def !==(rhs: T) = !equiv(lhs, rhs) + } + implicit def mkOrderingOps(lhs: T): Ops = new Ops(lhs) +} + +object Ordering +{ + def apply[T](implicit ord : Ordering[T]) = ord + + implicit val Unit : Ordering[Unit] = new Ordering[Unit] { + def compare(x : Unit, y : Unit) = 0; + } + + implicit val Boolean : Ordering[Boolean] = new Ordering[Boolean] { + def compare(x : Boolean, y : Boolean) = (x, y) match { + case (false, true) => -1; + case (true, false) => 1; + case _ => 0; + } + } + + implicit val Byte : Ordering[Byte] = new Ordering[Byte] { + def compare(x : Byte, y : Byte) = x.toInt - y.toInt; + } + + implicit val Char : Ordering[Char] = new Ordering[Char] { + def compare(x : Char, y : Char) = x.toInt - y.toInt; + } + + implicit val Short : Ordering[Short] = new Ordering[Short] { + def compare(x : Short, y : Short) = x.toInt - y.toInt; + } + + implicit val Int : Ordering[Int] = new Ordering[Int] { + def compare(x : Int, y : Int) = + if(x < y) -1; + else if (x == y) 0; + else 1 + } + + implicit val Long : Ordering[Long] = new Ordering[Long] { + def compare(x : Long, y : Long) = + if(x < y) -1; + else if (x == y) 0; + else 1 + } + + implicit val Float : Ordering[Float] = new Ordering[Float] { + def compare(x : Float, y : Float) = + if(x < y) -1; + else if (x == y) 0; + else 1 + } + + implicit val Double : Ordering[Double] = new Ordering[Double] { + def compare(x : Double, y : Double) = + if(x < y) -1; + else if (x == y) 0; + else 1 + } + + implicit val BigInt : Ordering[BigInt] = new Ordering[BigInt] { + def compare(x : BigInt, y : BigInt) = x.compare(y); + } + + implicit val String : Ordering[String] = new Ordering[String] { + def compare(x : String, y : String) = x.compareTo(y); + } + + implicit def Option[T](implicit ord : Ordering[T]) : Ordering[Option[T]] = + new Ordering[Option[T]] { + def compare(x : Option[T], y : Option[T]) = (x, y) match { + case (None, None) => 0; + case (None, _) => -1; + case (_, None) => 1 + case (Some(x), Some(y)) => ord.compare(x, y); + } + } + + implicit def Iterable[T](implicit ord : Ordering[T]) : Ordering[Iterable[T]] = + new Ordering[Iterable[T]] { + def compare(x : Iterable[T], y : Iterable[T]) : Int = { + val xe = x.elements; + val ye = y.elements; + + while (xe.hasNext && ye.hasNext){ + val res = ord.compare(xe.next, ye.next); + if (res != 0) return res; + } + + Boolean.compare(xe.hasNext, ye.hasNext); + } + } + + implicit def Tuple2[T1, T2](implicit ord1 : Ordering[T1], ord2 : Ordering[T2]) : Ordering[(T1, T2)] = + new Ordering[(T1, T2)]{ + def compare(x : Tuple2[T1, T2], y : Tuple2[T1, T2]) : Int = { + val compare1 = ord1.compare(x._1, y._1); + if (compare1 != 0) return compare1; + val compare2 = ord2.compare(x._2, y._2); + if (compare2 != 0) return compare2; + 0; + } + } + + implicit def Tuple3[T1, T2, T3](implicit ord1 : Ordering[T1], ord2 : Ordering[T2], ord3 : Ordering[T3]) : Ordering[(T1, T2, T3)] = + new Ordering[(T1, T2, T3)]{ + def compare(x : Tuple3[T1, T2, T3], y : Tuple3[T1, T2, T3]) : Int = { + val compare1 = ord1.compare(x._1, y._1); + if (compare1 != 0) return compare1; + val compare2 = ord2.compare(x._2, y._2); + if (compare2 != 0) return compare2; + val compare3 = ord3.compare(x._3, y._3); + if (compare3 != 0) return compare3; + 0; + } + } + + implicit def Tuple4[T1, T2, T3, T4](implicit ord1 : Ordering[T1], ord2 : Ordering[T2], ord3 : Ordering[T3], ord4 : Ordering[T4]) : Ordering[(T1, T2, T3, T4)] = + new Ordering[(T1, T2, T3, T4)]{ + def compare(x : Tuple4[T1, T2, T3, T4], y : Tuple4[T1, T2, T3, T4]) : Int = { + val compare1 = ord1.compare(x._1, y._1); + if (compare1 != 0) return compare1; + val compare2 = ord2.compare(x._2, y._2); + if (compare2 != 0) return compare2; + val compare3 = ord3.compare(x._3, y._3); + if (compare3 != 0) return compare3; + val compare4 = ord4.compare(x._4, y._4); + if (compare4 != 0) return compare4; + 0; + } + } + + implicit def Tuple5[T1, T2, T3, T4, T5](implicit ord1 : Ordering[T1], ord2 : Ordering[T2], ord3 : Ordering[T3], ord4 : Ordering[T4], ord5 : Ordering[T5]) : Ordering[(T1, T2, T3, T4, T5)] = + new Ordering[(T1, T2, T3, T4, T5)]{ + def compare(x : Tuple5[T1, T2, T3, T4, T5], y : Tuple5[T1, T2, T3, T4, T5]) : Int = { + val compare1 = ord1.compare(x._1, y._1); + if (compare1 != 0) return compare1; + val compare2 = ord2.compare(x._2, y._2); + if (compare2 != 0) return compare2; + val compare3 = ord3.compare(x._3, y._3); + if (compare3 != 0) return compare3; + val compare4 = ord4.compare(x._4, y._4); + if (compare4 != 0) return compare4; + val compare5 = ord5.compare(x._5, y._5); + if (compare5 != 0) return compare5; + 0; + } + } + + implicit def Tuple6[T1, T2, T3, T4, T5, T6](implicit ord1 : Ordering[T1], ord2 : Ordering[T2], ord3 : Ordering[T3], ord4 : Ordering[T4], ord5 : Ordering[T5], ord6 : Ordering[T6]) : Ordering[(T1, T2, T3, T4, T5, T6)] = + new Ordering[(T1, T2, T3, T4, T5, T6)]{ + def compare(x : Tuple6[T1, T2, T3, T4, T5, T6], y : Tuple6[T1, T2, T3, T4, T5, T6]) : Int = { + val compare1 = ord1.compare(x._1, y._1); + if (compare1 != 0) return compare1; + val compare2 = ord2.compare(x._2, y._2); + if (compare2 != 0) return compare2; + val compare3 = ord3.compare(x._3, y._3); + if (compare3 != 0) return compare3; + val compare4 = ord4.compare(x._4, y._4); + if (compare4 != 0) return compare4; + val compare5 = ord5.compare(x._5, y._5); + if (compare5 != 0) return compare5; + val compare6 = ord6.compare(x._6, y._6); + if (compare6 != 0) return compare6; + 0; + } + } + + implicit def Tuple7[T1, T2, T3, T4, T5, T6, T7](implicit ord1 : Ordering[T1], ord2 : Ordering[T2], ord3 : Ordering[T3], ord4 : Ordering[T4], ord5 : Ordering[T5], ord6 : Ordering[T6], ord7 : Ordering[T7]) : Ordering[(T1, T2, T3, T4, T5, T6, T7)] = + new Ordering[(T1, T2, T3, T4, T5, T6, T7)]{ + def compare(x : Tuple7[T1, T2, T3, T4, T5, T6, T7], y : Tuple7[T1, T2, T3, T4, T5, T6, T7]) : Int = { + val compare1 = ord1.compare(x._1, y._1); + if (compare1 != 0) return compare1; + val compare2 = ord2.compare(x._2, y._2); + if (compare2 != 0) return compare2; + val compare3 = ord3.compare(x._3, y._3); + if (compare3 != 0) return compare3; + val compare4 = ord4.compare(x._4, y._4); + if (compare4 != 0) return compare4; + val compare5 = ord5.compare(x._5, y._5); + if (compare5 != 0) return compare5; + val compare6 = ord6.compare(x._6, y._6); + if (compare6 != 0) return compare6; + val compare7 = ord7.compare(x._7, y._7); + if (compare7 != 0) return compare7; + 0; + } + } + + implicit def Tuple8[T1, T2, T3, T4, T5, T6, T7, T8](implicit ord1 : Ordering[T1], ord2 : Ordering[T2], ord3 : Ordering[T3], ord4 : Ordering[T4], ord5 : Ordering[T5], ord6 : Ordering[T6], ord7 : Ordering[T7], ord8 : Ordering[T8]) : Ordering[(T1, T2, T3, T4, T5, T6, T7, T8)] = + new Ordering[(T1, T2, T3, T4, T5, T6, T7, T8)]{ + def compare(x : Tuple8[T1, T2, T3, T4, T5, T6, T7, T8], y : Tuple8[T1, T2, T3, T4, T5, T6, T7, T8]) : Int = { + val compare1 = ord1.compare(x._1, y._1); + if (compare1 != 0) return compare1; + val compare2 = ord2.compare(x._2, y._2); + if (compare2 != 0) return compare2; + val compare3 = ord3.compare(x._3, y._3); + if (compare3 != 0) return compare3; + val compare4 = ord4.compare(x._4, y._4); + if (compare4 != 0) return compare4; + val compare5 = ord5.compare(x._5, y._5); + if (compare5 != 0) return compare5; + val compare6 = ord6.compare(x._6, y._6); + if (compare6 != 0) return compare6; + val compare7 = ord7.compare(x._7, y._7); + if (compare7 != 0) return compare7; + val compare8 = ord8.compare(x._8, y._8); + if (compare8 != 0) return compare8; + 0; + } + } + + implicit def Tuple9[T1, T2, T3, T4, T5, T6, T7, T8, T9](implicit ord1 : Ordering[T1], ord2 : Ordering[T2], ord3 : Ordering[T3], ord4 : Ordering[T4], ord5 : Ordering[T5], ord6 : Ordering[T6], ord7 : Ordering[T7], ord8 : Ordering[T8], ord9 : Ordering[T9]) : Ordering[(T1, T2, T3, T4, T5, T6, T7, T8, T9)] = + new Ordering[(T1, T2, T3, T4, T5, T6, T7, T8, T9)]{ + def compare(x : Tuple9[T1, T2, T3, T4, T5, T6, T7, T8, T9], y : Tuple9[T1, T2, T3, T4, T5, T6, T7, T8, T9]) : Int = { + val compare1 = ord1.compare(x._1, y._1); + if (compare1 != 0) return compare1; + val compare2 = ord2.compare(x._2, y._2); + if (compare2 != 0) return compare2; + val compare3 = ord3.compare(x._3, y._3); + if (compare3 != 0) return compare3; + val compare4 = ord4.compare(x._4, y._4); + if (compare4 != 0) return compare4; + val compare5 = ord5.compare(x._5, y._5); + if (compare5 != 0) return compare5; + val compare6 = ord6.compare(x._6, y._6); + if (compare6 != 0) return compare6; + val compare7 = ord7.compare(x._7, y._7); + if (compare7 != 0) return compare7; + val compare8 = ord8.compare(x._8, y._8); + if (compare8 != 0) return compare8; + val compare9 = ord9.compare(x._9, y._9); + if (compare9 != 0) return compare9; + 0; + } + } + } diff --git a/src/library/scala/Range.scala b/src/library/scala/Range.scala index 016ea5fc03..8a6ba86bff 100644 --- a/src/library/scala/Range.scala +++ b/src/library/scala/Range.scala @@ -8,12 +8,142 @@ // $Id$ - package scala import collection.immutable.Vector import collection.generic.VectorView +/**

+ * GenericRange is a generified version of the + * Range class which works with arbitrary types. + * It must be supplied with Integral and Ordering implementations + * of the range type. + * + * Built-in incarnations include BigIntRange and LongRange. + * 

+ *     val r1 = new Range(0, 100, 1)
+ *     val veryBig = Math.MAX_INT.toLong + 1
+ *     val r2 = new LongRange(veryBig, veryBig + 100, 1)
+ *     assert(r1 sameElements r2.map(_ - veryBig))
+ *
+ * + * @author Paul Phillips + * @version 2.8 + */ +class GenericRange[T] + (val start: T, val end: T, val step: T) + (implicit num: Integral[T], ord: Ordering[T]) +extends VectorView[T, Vector[T]] with RangeToString[T] { + import num._ + import ord._ + + // todo? - we could lift the length restriction by implementing a range as a sequence of + // subranges and limiting the subranges to MAX_INT. There's no other way around it because + // the generics we inherit assume integer-based indexing (as well they should.) + require(step !== zero) + require(genericLength <= fromInt(Math.MAX_INT), "Implementation restricts ranges to Math.MAX_INT elements.") + + protected def underlying = Vector.empty[T] + + /** Create a new range with the start and end values of this range and + * a new step. + */ + def by(step: T): GenericRange[T] = new GenericRange(start, end, step) + + override def foreach[U](f: T => U) { + var i = start + if (step > zero) { + while (i < end) { + f(i) + i = i + step + } + } else { + while (i > end) { + f(i) + i = i + step + } + } + } + + lazy val genericLength: T = { + def plen(start: T, end: T, step: T) = + if (end <= start) zero + else (end - start - one) / step + one + // if (lteq(end, start)) zero + // else plus(quot((minus(minus(end, start), one)), step), one) + + if (step > zero) plen(start, end, step) + else plen(end, start, -step) + } + lazy val length: Int = toInt(genericLength) + + // Since apply(Int) already exists, we are not allowed apply(T) since + // they erase to the same thing. + def apply(idx: Int): T = applyAt(fromInt(idx)) + def applyAt(idx: T): T = { + if (idx < zero || idx >= genericLength) throw new IndexOutOfBoundsException(idx.toString) + start + idx * step + } + + override def contains(_x: Any): Boolean = { + // XXX - can we avoid this cast and still have a contains method? + val x = + try { _x.asInstanceOf[T] } + catch { case _: ClassCastException => return false } + + if (step > zero) start <= x && x < end + else start >= x && x > end + } + + def inclusive = GenericRange.inclusive(start, end, step) +} + +private[scala] trait RangeToString[T] extends VectorView[T, Vector[T]] { + // The default toString() tries to print every element and will exhaust memory + // if the Range is unduly large. This interacts poorly with the REPL. + override def toString() = { + val MAX_PRINT = 512 // some arbitrary value + val str = (this take MAX_PRINT).toString + + if (length > MAX_PRINT) str.replaceAll("""\)$""", ", ...)") + else str + } +} + +object GenericRange { + import Numeric._ + import Ordering._ + + // This is very ugly, but modelled on the existing range class for now + private class Inclusive[T](start: T, end0: T, step: T)(implicit num: Integral[T], ord: Ordering[T]) + extends GenericRange( + start, + if (ord.gt(step, num.zero)) num.plus(end0, num.one) else num.minus(end0, num.one), + step) + { + self => + override def by(step: T): GenericRange[T] = new Inclusive(start, end0, step) + } + + def apply[T](start: T, end: T, step: T)(implicit num: Integral[T], ord: Ordering[T]) = + new GenericRange(start, end, step) + + def inclusive[T](start: T, end: T, step: T)(implicit num: Integral[T], ord: Ordering[T]): GenericRange[T] = + new GenericRange.Inclusive(start, end, step) +} + +class BigIntRange(start: BigInt, end: BigInt, step: BigInt) +extends GenericRange(start, end, step)(Numeric.BigIntIsIntegral, Ordering.BigInt) {} +class LongRange(start: Long, end: Long, step: Long) +extends GenericRange(start, end, step)(Numeric.LongIsIntegral, Ordering.Long) {} + +// Illustrating genericity with IntRange, which should have the same behavior +// as the original Range class. However we leave the original Range +// indefinitely, for performance and because the compiler seems to bootstrap +// off it and won't do so with our parameterized version without modifications. +class IntRange(start: Int, end: Int, step: Int) +extends GenericRange(start, end, step)(Numeric.IntIsIntegral, Ordering.Int) {} + /**

* The Range class represents integer values in range * [start;end) with non-zero step value step. @@ -28,7 +158,9 @@ import collection.generic.VectorView * @author Martin Odersky * @version 2.8 */ -class Range(val start: Int, val end: Int, val step: Int) extends VectorView[Int, Vector[Int]] { +class Range(val start: Int, val end: Int, val step: Int) +extends VectorView[Int, Vector[Int]] with RangeToString[Int] +{ require(step != 0) protected def underlying = Vector.empty[Int] @@ -71,6 +203,7 @@ class Range(val start: Int, val end: Int, val step: Int) extends VectorView[Int, def inclusive = Range.inclusive(start, end, step) } + object Range { /** @deprecated use Range.inclusive instead */ class Inclusive(start: Int, end0: Int, step: Int) -- cgit v1.2.3