diff options
author | Martin Odersky <odersky@gmail.com> | 2009-02-13 11:59:49 +0000 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2009-02-13 11:59:49 +0000 |
commit | 04840e2ed4530df9a5ca59b984bf2b37a976dc70 (patch) | |
tree | 61394762e202f8ab60e0d3a8e8ac688404241bc3 /src/library | |
parent | 708baf94764e2a839e24ca6204060a8d0664d88c (diff) | |
download | scala-04840e2ed4530df9a5ca59b984bf2b37a976dc70.tar.gz scala-04840e2ed4530df9a5ca59b984bf2b37a976dc70.tar.bz2 scala-04840e2ed4530df9a5ca59b984bf2b37a976dc70.zip |
new version of collection libraries
Diffstat (limited to 'src/library')
74 files changed, 2876 insertions, 494 deletions
diff --git a/src/library/scalax/Tuple2.scala b/src/library/scalax/Tuple2.scala new file mode 100755 index 0000000000..4adb9e471b --- /dev/null +++ b/src/library/scalax/Tuple2.scala @@ -0,0 +1,97 @@ + +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Tuple2.scala 14794 2008-04-23 08:15:17Z washburn $ + +// generated by genprod on Wed Apr 23 10:06:16 CEST 2008 (with extra methods) + +package scalax + +import annotation.unchecked.uncheckedVariance + +object Tuple2 { + + import collection._ + import collection.generic._ + + class IterableOps[CC[+B] <: Iterable[B] with IterableTemplate[CC, B @uncheckedVariance], A1, A2](tuple: (CC[A1], Iterable[A2])) { + def zip: CC[(A1, A2)] = { + val elems1 = tuple._1.elements + val elems2 = tuple._2.elements + val b = tuple._1.newBuilder[(A1, A2)] + while (elems1.hasNext && elems2.hasNext) + b += ((elems1.next, elems2.next)) + b.result + } + def map[B](f: (A1, A2) => B): CC[B] = { + val elems1 = tuple._1.elements + val elems2 = tuple._2.elements + val b = tuple._1.newBuilder[B] + while (elems1.hasNext && elems2.hasNext) + b += f(elems1.next, elems2.next) + b.result + } + def flatMap[B](f: (A1, A2) => CC[B]): CC[B] = { + val elems1 = tuple._1.elements + val elems2 = tuple._2.elements + val b = tuple._1.newBuilder[B] + while (elems1.hasNext && elems2.hasNext) + b ++= f(elems1.next, elems2.next) + b.result + } + def foreach(f: (A1, A2) => Unit) { + val elems1 = tuple._1.elements + val elems2 = tuple._2.elements + while (elems1.hasNext && elems2.hasNext) + f(elems1.next, elems2.next) + } + def forall(p: (A1, A2) => Boolean): Boolean = { + val elems1 = tuple._1.elements + val elems2 = tuple._2.elements + while (elems1.hasNext && elems2.hasNext) + if (!p(elems1.next, elems2.next)) return false + true + } + def exists(p: (A1, A2) => Boolean): Boolean = { + val elems1 = tuple._1.elements + val elems2 = tuple._2.elements + while (elems1.hasNext && elems2.hasNext) + if (p(elems1.next, elems2.next)) return true + false + } + } + implicit def tupleOfIterableWrapper[CC[+B] <: Iterable[B] with IterableTemplate[CC, B], A1, A2](tuple: (CC[A1], Iterable[A2])) = + new IterableOps[CC, A1, A2](tuple) + + +/* A more general version which will probably not work. + implicit def tupleOfIterableWrapper[CC[+B] <: Iterable[B] with IterableTemplate[CC, B], A1, A2, B1 <: CC[A1]](tuple: B1, Iterable[A2]) = + new IterableOps[CC, A1, A2](tuple) +*/ + + // Adriaan: If you drop the type parameters it will infer the wrong types. + tupleOfIterableWrapper[collection.immutable.List, Int, Int]((collection.immutable.Nil, collection.immutable.Nil)) forall (_ + _ < 10) +} + +/** Tuple2 is the canonical representation of a @see Product2 + * + */ +case class Tuple2[+T1, +T2](_1:T1, _2:T2) + extends Product2[T1, T2] { + + override def toString() = { + val sb = new StringBuilder + sb.append('(').append(_1).append(',').append(_2).append(')') + sb.toString + } + + /** Swap the elements of the tuple */ + def swap: Tuple2[T2,T1] = Tuple2(_2, _1) + +} diff --git a/src/library/scalax/collection/Iterable.scala b/src/library/scalax/collection/Iterable.scala index 08bf338290..3dc181707c 100755 --- a/src/library/scalax/collection/Iterable.scala +++ b/src/library/scalax/collection/Iterable.scala @@ -13,6 +13,7 @@ package scalax.collection import generic._ import collection.immutable.{List, Nil, ::} +import annotation.unchecked.uncheckedVariance /** Collection classes mixing in this class provide a method * <code>elements</code> which returns an iterator over all the @@ -25,7 +26,7 @@ import collection.immutable.{List, Nil, ::} * @owner Martin Odersky * @version 2.8 */ -trait Iterable[+A] extends covariant.IterableTemplate[Iterable, A] { self => +trait Iterable[+A] extends IterableTemplate[Iterable, A @uncheckedVariance] { self => /** Creates a view of this iterable @see Iterable.View def view: View[Iterable, A] = new View[Iterable, A] { // !!! Martin: We should maybe infer the type parameters here? @@ -41,7 +42,7 @@ trait Iterable[+A] extends covariant.IterableTemplate[Iterable, A] { self => * @author Martin Odersky * @version 2.8 */ -object Iterable extends covariant.IterableFactory[Iterable] { +object Iterable extends IterableFactory[Iterable] with EmptyIterableFactory[Iterable] { /** The empty iterable */ val empty: Iterable[Nothing] = Nil @@ -76,16 +77,16 @@ object Iterable extends covariant.IterableFactory[Iterable] { } } - class IterableIterableOps[C[+B] <: Iterable[B] with covariant.IterableTemplate[C, B], A](self: C[C[A]]) { + class IterableIterableOps[C[+B] <: Iterable[B] with IterableTemplate[C, B @uncheckedVariance], A](self: C[C[A]]) { def flatten: C[A] = { - val b: Builder[C, A] = self.newBuilder[A] + val b: generic.Builder[C, A] = self.newBuilder[A] for (xs <- self) b ++= xs b.result } def transpose: C[C[A]] = { - val bs: Array[Builder[C, A]] = self.head.map(_ => self.newBuilder[A]).toArray + val bs: scala.Array[generic.Builder[C, A]] = self.head.map(_ => self.newBuilder[A]).toArray for (xs <- self) { var i = 0 for (x <- xs) { @@ -93,7 +94,6 @@ object Iterable extends covariant.IterableFactory[Iterable] { i += 1 } } - type CC[B] = C[C[B]] val bb = self.newBuilder[C[A]] for (b <- bs) bb += b.result bb.result @@ -117,16 +117,16 @@ object Iterable extends covariant.IterableFactory[Iterable] { new ComparableIterableOps(seq, cmp) implicit def numericIterableWrapper[A](seq: Iterable[A])(implicit num: Numeric[A]) = new NumericIterableOps(seq, num) - implicit def iterableIterableWrapper[C[+B] <: Iterable[B] with covariant.IterableTemplate[C, B], A](seq: C[C[A]]) = + implicit def iterableIterableWrapper[C[+B] <: Iterable[B] with IterableTemplate[C, B], A](seq: C[C[A]]) = new IterableIterableOps[C, A](seq) implicit def pairIterableWrapper[C[+B] <: Iterable[B], A1, A2](seq: C[(A1, A2)]) = new PairIterableOps[C, A1, A2](seq) - type View[+UC[B] <: Sequence[B], A] = IterableView[UC, A] + type View[A] = IterableView[UC, A] forSome { type UC[B] <: Iterable[B] } /** @deprecated use View instead */ - @deprecated type Projection[A] = View[C, A] forSome { type C[B] <: Iterable[B] } + @deprecated type Projection[A] = View[A] /** The minimum element of a non-empty sequence of ordered elements * @deprecated use seq.min instead diff --git a/src/library/scalax/collection/Iterator.scala b/src/library/scalax/collection/Iterator.scala index b858c91d2c..48eda407aa 100755 --- a/src/library/scalax/collection/Iterator.scala +++ b/src/library/scalax/collection/Iterator.scala @@ -29,15 +29,15 @@ object Iterator { } /** - * @param x the element + * @param elem the element * @return the iterator with one single element * @note Equivalent, but more efficient than Iterator(x) */ - def single[A](x: A) = new Iterator[A] { + def single[A](elem: A) = new Iterator[A] { private var hasnext = true def hasNext: Boolean = hasnext def next(): A = - if (hasnext) { hasnext = false; x } + if (hasnext) { hasnext = false; elem } else empty.next() } @@ -173,7 +173,7 @@ object Iterator { implicit def iteratorIteratorWrapper[A](its: Iterator[Iterator[A]]): IteratorIteratorOps[A] = new IteratorIteratorOps[A](its) - /** @deprecated use `xs.elements` instead + /** @deprecated use `xs.elements`, or `Iterator(x1, ..., xn)` instead */ @deprecated def fromValues[a](xs: a*) = xs.elements diff --git a/src/library/scalax/collection/Map.scala b/src/library/scalax/collection/Map.scala new file mode 100755 index 0000000000..602da06bb0 --- /dev/null +++ b/src/library/scalax/collection/Map.scala @@ -0,0 +1,21 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Map.scala 16884 2009-01-09 16:52:09Z cunei $ + + +package scalax.collection + +import generic._ + +trait Map[A, B] extends MapTemplate[A, B, Map] + +/* Factory object for `Map` class */ +object Map extends MapFactory[Map] { + def empty[A, B]: Map[A, B] = new immutable.EmptyMap[A, B] +} diff --git a/src/library/scalax/collection/OrderedIterable.scala b/src/library/scalax/collection/OrderedIterable.scala index 929618fc19..9a0b77e575 100755 --- a/src/library/scalax/collection/OrderedIterable.scala +++ b/src/library/scalax/collection/OrderedIterable.scala @@ -13,11 +13,10 @@ package scalax.collection import generic._ import immutable.Nil +import annotation.unchecked.uncheckedVariance /** An ordered collection is a collection with a fixed sequence of elements - * which corresponds to append order. In particular, it holds that - * - * (c1 ++ c2).elements = c1.elements ++ c2.elements + * which is the same in every run. * * for any two ordered collections c1 and c2. * Ordered collections support @@ -27,7 +26,7 @@ import immutable.Nil * @author Martin Odersky * @version 2.8 */ -trait OrderedIterable[+A] extends Iterable[A] with covariant.OrderedIterableTemplate[OrderedIterable, A] +trait OrderedIterable[+A] extends Iterable[A] with OrderedIterableTemplate[OrderedIterable, A @uncheckedVariance] /** Various utilities for instances of <a href="Iterable.html">Iterable</a>. * @@ -35,7 +34,7 @@ trait OrderedIterable[+A] extends Iterable[A] with covariant.OrderedIterableTemp * @author Martin Odersky * @version 2.8 */ -object OrderedIterable extends covariant.IterableFactory[OrderedIterable] { +object OrderedIterable extends IterableFactory[OrderedIterable] with EmptyIterableFactory[OrderedIterable] { val empty: OrderedIterable[Nothing] = Nil diff --git a/src/library/scalax/collection/Sequence.scala b/src/library/scalax/collection/Sequence.scala index 90212b3b5e..48081c99e8 100755 --- a/src/library/scalax/collection/Sequence.scala +++ b/src/library/scalax/collection/Sequence.scala @@ -13,6 +13,7 @@ package scalax.collection import generic._ import immutable.Nil +import annotation.unchecked.uncheckedVariance /** Class <code>Sequence[A]</code> represents finite sequences of elements * of type <code>A</code>. @@ -21,9 +22,9 @@ import immutable.Nil * @author Matthias Zenger * @version 1.0, 16/07/2003 */ -trait Sequence[+A] extends OrderedIterable[A] with SizedIterable[A] with generic.covariant.SequenceTemplate[Sequence, A] +trait Sequence[+A] extends OrderedIterable[A] with SizedIterable[A] with SequenceTemplate[Sequence, A @uncheckedVariance] -object Sequence extends covariant.SequenceFactory[Sequence] { +object Sequence extends SequenceFactory[Sequence] with EmptyIterableFactory[Sequence] { /** The empty sequence */ val empty : Sequence[Nothing] = immutable.Nil diff --git a/src/library/scalax/collection/Set.scala b/src/library/scalax/collection/Set.scala index 24829364b3..a7234d0261 100644 --- a/src/library/scalax/collection/Set.scala +++ b/src/library/scalax/collection/Set.scala @@ -12,12 +12,13 @@ package scalax.collection import generic._ -trait Set[A] extends OrderedIterable[A] with SetTemplate[Set, A] +trait Set[A] extends SetTemplate[Set, A] -/* Factory object for `Sequence` class */ +/* Factory object for `Set` class */ object Set extends IterableFactory[Set] { /** The empty set */ def apply[A](args: A*): Set[A] = null // !!! + } diff --git a/src/library/scalax/collection/Vector.scala b/src/library/scalax/collection/Vector.scala index d36c980df2..8224a8630b 100755 --- a/src/library/scalax/collection/Vector.scala +++ b/src/library/scalax/collection/Vector.scala @@ -12,10 +12,11 @@ package scalax.collection import generic._ import mutable.ArrayBuffer +import annotation.unchecked.uncheckedVariance -trait Vector[+A] extends Sequence[A] with covariant.VectorTemplate[Vector, A] +trait Vector[+A] extends Sequence[A] with VectorTemplate[Vector, A @uncheckedVariance] -object Vector extends covariant.SequenceFactory[Vector] { +object Vector extends SequenceFactory[Vector] with EmptyIterableFactory[Vector] { /** The empty sequence */ val empty : Vector[Nothing] = null // !!! todo: insert good immutable vector implementation here. diff --git a/src/library/scalax/collection/generic/Addable.scala b/src/library/scalax/collection/generic/Addable.scala new file mode 100755 index 0000000000..40a4f60e6e --- /dev/null +++ b/src/library/scalax/collection/generic/Addable.scala @@ -0,0 +1,64 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + +package scalax.collection.generic + +/** This class represents collections that can be augmented using a += operator. + * + * @autor Martin Odersky + * @owner Martin Odersky + * @version 2.8 + */ +trait Addable[+C <: Addable[C, A], A] { + + protected def thisCC: C + + /** Adds a single element to this collection and returns + * either the collection itself (if it is mutable), or a new collection + * with the added element. + * + * @param elem the element to add. + */ + def +(elem: A): C + + /** Adds two or more elements to this collection and returns + * either the collection itself (if it is mutable), or a new collection + * with the added elements. + * + * @param elem1 the first element to add. + * @param elem2 the second element to add. + * @param elems the remaining elements to add. + */ + def +(elem1: A, elem2: A, elems: A*): C = + thisCC + elem1 + elem2 ++ elems.asInstanceOf[Iterable[A]] // !@! + + /** Adds a number of elements provided by an iterable object + * via its <code>elements</code> method and returns + * either the collection itself (if it is mutable), or a new collection + * with the added elements. + * + * @param iter the iterable object. + */ + def ++(iter: Iterable[A]): C = (thisCC /: iter) (_ + _) + + /** Adds a number of elements provided by an iterator + * via its <code>elements</code> method and returns + * either the collection itself (if it is mutable), or a new collection + * with the added elements. + * + * @param iter the iterator + */ + def ++(iter: Iterator[A]): C = (thisCC /: iter) (_ + _) + +} + + + + diff --git a/src/library/scalax/collection/generic/AddableBuilder.scala b/src/library/scalax/collection/generic/AddableBuilder.scala new file mode 100644 index 0000000000..b1f3e4e522 --- /dev/null +++ b/src/library/scalax/collection/generic/AddableBuilder.scala @@ -0,0 +1,22 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListBuffer.scala 14378 2008-03-13 11:39:05Z dragos $ + +package scalax.collection.generic + +import collection.mutable.ListBuffer +import collection.immutable.{List, Nil, ::} + +class AddableBuilder[CC[B] <: Iterable[B] with Addable[CC[B], B], A](empty: CC[A]) extends Builder[CC, A] { + protected var elems: CC[A] = empty + def +=(x: A) { elems = elems + x } + def elements: Iterator[A] = elems.elements + def clear() { elems = empty } + def result: CC[A] = elems +} diff --git a/src/library/scalax/collection/Builder.scala b/src/library/scalax/collection/generic/Builder.scala index 2c80916d50..155ca553fa 100755 --- a/src/library/scalax/collection/Builder.scala +++ b/src/library/scalax/collection/generic/Builder.scala @@ -8,14 +8,14 @@ // $Id: ListBuffer.scala 14378 2008-03-13 11:39:05Z dragos $ -package scalax.collection +package scalax.collection.generic -trait Builder[+CC[B], A] extends generic.mutable.Growable[A] { +import generic._ + +trait Builder[+CC[B], A] extends Growable[A] { def +=(x: A) def elements: Iterator[A] def result: CC[A] - override def ++=(xs: Iterator[A]) { for (x <- xs) this += x } - override def ++=(xs: Iterable[A]) { for (x <- xs) this += x } def mapResult[DD[B]](f: CC[A] => DD[A]) = new Builder[DD, A] with Proxy { diff --git a/src/library/scalax/collection/generic/Cloneable.scala b/src/library/scalax/collection/generic/Cloneable.scala index 455c88e47b..acf9a16686 100644 --- a/src/library/scalax/collection/generic/Cloneable.scala +++ b/src/library/scalax/collection/generic/Cloneable.scala @@ -9,10 +9,11 @@ // $Id: CloneableCollection.scala 16893 2009-01-13 13:09:22Z cunei $ -package scala.collection.generic +package scalax.collection.generic /** A trait for cloneable collections. */ -trait Cloneable[A <: AnyRef] extends java.lang.Cloneable { +@cloneable +trait Cloneable[A <: AnyRef] { override def clone(): A = super.clone().asInstanceOf[A] } diff --git a/src/library/scalax/collection/generic/EmptyIterableFactory.scala b/src/library/scalax/collection/generic/EmptyIterableFactory.scala new file mode 100755 index 0000000000..7f110d13d2 --- /dev/null +++ b/src/library/scalax/collection/generic/EmptyIterableFactory.scala @@ -0,0 +1,17 @@ +package scalax.collection.generic + +import annotation.unchecked.uncheckedVariance + +trait EmptyIterableFactory[CC[+A] <: Iterable[A] with IterableTemplate[CC, A @uncheckedVariance]] extends IterableFactory[CC] { + + /** The empty collection of type CC */ + val empty: CC[Nothing] + + /** An override of newBuilder, to work off the empty object */ + override protected def newBuilder[A]: Builder[CC, A] = + empty.newBuilder[A] + + /** Create CC collection of specified elements */ + override def apply[A](args: A*): CC[A] = + empty ++ args.asInstanceOf[Iterable[A]] +} diff --git a/src/library/scalax/collection/generic/Growable.scala b/src/library/scalax/collection/generic/Growable.scala new file mode 100755 index 0000000000..960384f9d0 --- /dev/null +++ b/src/library/scalax/collection/generic/Growable.scala @@ -0,0 +1,58 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + +package scalax.collection.generic + +/** This class represents collections that can be augmented using a += operator. + * + * @autor Martin Odersky + * @owner Martin Odersky + * @version 2.8 + */ +trait Growable[A] { + + /** Adds a single element to this collection. + * + * @param elem the element to add. + */ + def +=(elem: A): Unit + + /** Adds two or more elements to this collection. + * + * @param elem1 the first element to add. + * @param elem2 the second element to add. + * @param elems the remaining elements to add. + */ + def +=(elem1: A, elem2: A, elems: A*) { + this += elem1 + this += elem2 + this ++= elems.asInstanceOf[Iterable[A]] // !@! + } + + /** Adds a number of elements provided by an iterator to this collection. + * + * @param iter the iterator. + */ + def ++=(iter: collection.Iterator[A]) { iter foreach += } + + /** Adds a number of elements provided by an iterable object to this collection. + * + * @param iter the iterable object. + */ + def ++=(iter: collection.Iterable[A]) { iter foreach += } + + /** Clears the collection contents. + */ + def clear() +} + + + + diff --git a/src/library/scalax/collection/generic/IterableFactory.scala b/src/library/scalax/collection/generic/IterableFactory.scala index 9570970abe..0cf9c8ac95 100755 --- a/src/library/scalax/collection/generic/IterableFactory.scala +++ b/src/library/scalax/collection/generic/IterableFactory.scala @@ -8,7 +8,7 @@ trait IterableFactory[CC[A] <: Iterable[A]] { protected def newBuilder[A]: Builder[CC, A] = apply().newBuilder[A].asInstanceOf[Builder[CC, A]] - // can't have an empty here because it is defined in subclass covariant.IterableFactory with type + // can't have an empty here because it is defined in subclass EmptyIterableFactory with type // CC[Nothing]. This type does not make sense for immutable iterables. /** Concatenate all the argument lists into a single list. @@ -88,10 +88,10 @@ trait IterableFactory[CC[A] <: Iterable[A]] { * increasing n. If `step > 0` the sequence terminates * with the largest value less than `end`. If `step < 0` * the sequence terminates with the smallest value greater than `end`. - * If `step == 0`, the sequence gors on infinitely (in that - * case the `range` operation might not terminate. + * If `step == 0`, an IllegalArgumentException is thrown. */ def range(start: Int, end: Int, step: Int): CC[Int] = { + if (step == 0) throw new IllegalArgumentException("zero step") val b = newBuilder[Int] var i = start while ((step <= 0 || i < end) && (step >= 0 || i > end)) { diff --git a/src/library/scalax/collection/generic/IterableForwarder.scala b/src/library/scalax/collection/generic/IterableForwarder.scala index 8613b18345..e38f030414 100644 --- a/src/library/scalax/collection/generic/IterableForwarder.scala +++ b/src/library/scalax/collection/generic/IterableForwarder.scala @@ -56,6 +56,4 @@ trait IterableForwarder[+A] extends Iterable[A] { override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = underlying.addString(b, start, sep, end) override def head: A = underlying.head - override def last: A = underlying.last - override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that) } diff --git a/src/library/scalax/collection/generic/IterableTemplate.scala b/src/library/scalax/collection/generic/IterableTemplate.scala index adbf5d2de7..cc562c308a 100755 --- a/src/library/scalax/collection/generic/IterableTemplate.scala +++ b/src/library/scalax/collection/generic/IterableTemplate.scala @@ -646,76 +646,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the b.result } - /** The last element of this iterable. - * - * @throws Predef.NoSuchElementException if the iterable is empty. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def last: A = { - var lst = head - for (x <- this) - lst = x - lst - } - - /** Returns as an option the last element of this iterable or - * <code>None</code> if iterable is empty. - * - * @return the last element as an option. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def lastOption: Option[A] = if (isEmpty) None else Some(last) - - /** An iterable consisting of all elements of this iterable except the last one. - * @throws Predef.UnsupportedOperationException if the stream is empty. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def init: CC[A] = { - if (isEmpty) throw new UnsupportedOperationException("empty.init") - var lst = head - val b = newBuilder[A] - for (x <- this) { - b += lst - lst = x - } - b.result - } - - /** Returns the rightmost <code>n</code> elements from this iterable. - * - * @param n the number of elements to take - * @note Might return different results for different runs, unless this iterable is ordered - */ - def takeRight(n: Int): CC[A] = { - val b = newBuilder[A] - val lead = elements drop n - var go = false - for (x <- this) { - if (go) b += x - else if (lead.hasNext) lead.next - else go = true - } - b.result - } - - /** Returns the iterable wihtout its rightmost <code>n</code> elements. - * - * @param n the number of elements to take - * @note Might return different results for different runs, unless this iterable is ordered - */ - def dropRight(n: Int): CC[A] = { - val b = newBuilder[A] - val lead = elements drop n - breakable { - for (x <- this) { - if (!lead.hasNext) break - lead.next - b += x - } - } - b.result - } - /** Split the iterable at a given point and return the two parts thus * created. * @@ -732,71 +662,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the (l.result, r.result) } - /** Returns the longest prefix of this iterable whose elements satisfy - * the predicate <code>p</code>. - * - * @param p the test predicate. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def takeWhile(p: A => Boolean): CC[A] = { - val b = newBuilder[A] - breakable { - for (x <- this) { - if (!p(x)) break - b += x - } - } - b.result - } - - /** Returns the longest suffix of this iterable whose first element - * does not satisfy the predicate <code>p</code>. - * - * @param p the test predicate. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def dropWhile(p: A => Boolean): CC[A] = { - val b = newBuilder[A] - var go = false - for (x <- this) { - if (go) b += x - else if (!p(x)) { go = true; b += x } - } - b.result - } - - /** Returns a pair consisting of the longest prefix of the iterable whose - * elements all satisfy the given predicate, and the rest of the iterable. - * - * @param p the test predicate - * @return a pair consisting of the longest prefix of the iterable whose - * elements all satisfy <code>p</code>, and the rest of the iterable. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def span(p: A => Boolean): (CC[A], CC[A]) = { - val l, r = newBuilder[A] - var toLeft = true - for (x <- this) { - toLeft = toLeft && p(x) - (if (toLeft) l else r) += x - } - (l.result, r.result) - } - - /** Checks if the other iterable object contains the same elements as this one. - * - * @note will not terminate for infinite-sized iterables. - * @param that the other iterable - * @return true, iff both iterables contain the same elements. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def sameElements[B >: A](that: OrderedIterable[B]): Boolean = { - val these = this.elements - val those = that.elements - while (these.hasNext && those.hasNext && these.next() == those.next()) {} - !these.hasNext && !those.hasNext - } - /** A sub-iterable view starting at index `from` * and extending up to (but not including) index `until`. * diff --git a/src/library/scalax/collection/generic/IterableView.scala b/src/library/scalax/collection/generic/IterableView.scala index 45a0a50be2..bb111e2252 100755 --- a/src/library/scalax/collection/generic/IterableView.scala +++ b/src/library/scalax/collection/generic/IterableView.scala @@ -25,7 +25,7 @@ trait IterableView[+UC[/*+*/B] <: Iterable[B], /*+*/A] extends Iterable[A] { sel case _ => origin } - private def isDelay = elements eq underlying.elements + protected def isDelay = elements eq underlying.elements private[this] var forced: UC[A] = _ private[this] var wasForced = false @@ -100,15 +100,6 @@ trait IterableView[+UC[/*+*/B] <: Iterable[B], /*+*/A] extends Iterable[A] { sel /** Non-strict variant of @see Iterable.slice */ override def slice(from: Int, until: Int): IterableView[UC, A] = newView(elements slice (from, until)) - /** Non-strict variant of @see Iterable.takeWhile */ - override def takeWhile(p: A => Boolean): IterableView[UC, A] = newView(elements takeWhile p) - - /** Non-strict variant of @see Iterable.dropWhile */ - override def dropWhile(p: A => Boolean): IterableView[UC, A] = newView(elements dropWhile p) - - /** Non-strict variant of @see Iterable.span */ - override def span(p: A => Boolean): (IterableView[UC, A], IterableView[UC, A]) = (takeWhile(p), dropWhile(p)) - /** The projection resulting from the concatenation of this projection with the <code>rest</code> projection. * @param rest The projection that gets appended to this projection * @deprecated Use ++ instead diff --git a/src/library/scalax/collection/LazyBuilder.scala b/src/library/scalax/collection/generic/LazyBuilder.scala index 185930a916..74764351b6 100755 --- a/src/library/scalax/collection/LazyBuilder.scala +++ b/src/library/scalax/collection/generic/LazyBuilder.scala @@ -8,7 +8,7 @@ // $Id: ListBuffer.scala 14378 2008-03-13 11:39:05Z dragos $ -package scalax.collection +package scalax.collection.generic import collection.mutable.ListBuffer import collection.immutable.{List, Nil, ::} @@ -18,7 +18,7 @@ abstract class LazyBuilder[+CC[B], A] extends Builder[CC, A] { def +=(x: A) = { parts += Iterator.single(x) } override def ++=(xs: Iterator[A]) { parts += xs } override def ++=(xs: Iterable[A]) { parts += xs.elements } - def elements: Iterator[A] = Iterator.iteratorIteratorWrapper(parts.elements).flatten // !!! drop the wrapper and get an error + def elements: Iterator[A] = Iterator.iteratorIteratorWrapper(parts.elements).flatten // !!! can remove the wrapper once new compiler is in starr def result: CC[A] def clear() { parts.clear() } } diff --git a/src/library/scalax/collection/generic/MapFactory.scala b/src/library/scalax/collection/generic/MapFactory.scala new file mode 100755 index 0000000000..d7413b8928 --- /dev/null +++ b/src/library/scalax/collection/generic/MapFactory.scala @@ -0,0 +1,9 @@ +package scalax.collection.generic + +trait MapFactory[CC[A, B] <: MapTemplate[A, B, CC]] { + + def empty[A, B]: CC[A, B] + + def apply[A, B](elems: (A, B)*): CC[A, B] = empty[A, B] ++ elems.asInstanceOf[Iterable[(A, B)]] // !@! + +} diff --git a/src/library/scalax/collection/generic/MapTemplate.scala b/src/library/scalax/collection/generic/MapTemplate.scala new file mode 100755 index 0000000000..6d1a9e3c93 --- /dev/null +++ b/src/library/scalax/collection/generic/MapTemplate.scala @@ -0,0 +1,247 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Map.scala 16884 2009-01-09 16:52:09Z cunei $ + + +package scalax.collection.generic + +import collection.immutable.Set +import collection.mutable.ArrayBuffer +import annotation.unchecked.uncheckedVariance + +/** <p> +* A map is a collection that maps each key to one or zero values. + * </p> + * <p> + * This trait provides a limited interface, only allowing reading of elements. + * There are two extensions of this trait, in packages + * <code><a href="mutable$content.html" target="contentFrame"> + * scala.collection.mutable</a></code> + * and <code><a href="immutable$content.html" target="contentFrame"> + * scala.collection.immutable</a></code>, which provide functionality for + * adding new key/value mappings to a map. The trait in the first package is + * for maps that are modified destructively, whereas the trait in + * the second package is for immutable maps which create a new map + * when something is added or removed from them. + * </p> + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 1.2, 31/12/2006 + */ +trait MapTemplate[A, B, +CC[A1, B1] <: Map[A1, B1] with MapTemplate[A1, B1, CC]] + extends PartialFunction[A, B] + with SizedIterable[(A, B)] + with Addable[CC[A, B], (A, B)] + with Subtractable[CC[A, B], A] { +self: CC[A, B] => + + def newBuilder[B]: Builder[SizedIterable, B] = new ArrayBuffer[B] + + override def thisCC: CC[A, B] = this + + /** This method returns a new map instance of the same class + * mapping keys of the same type to values of type <code>C</code>. + */ + def empty[C]: CC[A, C] + + /** Compute the number of key-to-value mappings. + * + * @return the number of mappings + */ + def size: Int + + /** Check if this map maps <code>key</code> to a value and return the + * value if it exists. + * + * @param key the key of the mapping of interest + * @return the value of the mapping, if it exists + */ + def get(key: A): Option[B] + + /** Check if this map maps <code>key</code> to a value. + * Return that value if it exists, otherwise return <code>default</code>. + */ + def getOrElse[B2 >: B](key: A, default: => B2): B2 = + get(key) match { + case Some(v) => v + case None => default + } + + /** Is this an empty map? + * + * @return <code>true</code> iff the map is empty. + */ + override def isEmpty: Boolean = size == 0 + + /** Retrieve the value which is associated with the given key. This + * method throws an exception if there is no mapping from the given + * key to a value. + * + * @param key the key + * @return the value associated with the given key. + */ + def apply(key: A): B = get(key) match { + case None => default(key) + case Some(value) => value + } + + /** Is the given key mapped to a value by this map? + * + * @param key the key + * @return <code>true</code> iff there is a mapping for key in this map + */ + def contains(key: A): Boolean = get(key) match { + case None => false + case Some(_) => true + } + + /** Does this map contain a mapping from the given key to a value? + * + * @param key the key + * @return <code>true</code> iff there is a mapping for key in this map + */ + def isDefinedAt(key: A) = contains(key) + + /** Creates an iterator for all keys. + * + * @return an iterator over all keys. + */ + def keys: Iterator[A] = new Iterator[A] { + val iter = self.elements + def hasNext = iter.hasNext + def next = iter.next._1 + } + + /** @return the keys of this map as a set. + */ + def keySet: Set[A] = new Set[A] { + def size = self.size + def contains(key : A) = self.contains(key) + def elements = self.elements.map(_._1) + def + (elem: A): Set[A] = immutable.Set[A]() ++ this + elem + def - (elem: A): Set[A] = immutable.Set[A]() ++ this - elem + override def newBuilder[B]: Builder[Set, B] = Set.newBuilder[B] + } + + /** Creates an iterator for a contained values. + * + * @return an iterator over all values. + */ + def values: Iterator[B] = new Iterator[B] { + val iter = self.elements + def hasNext = iter.hasNext + def next = iter.next._2 + } + + /** Creates a string representation for this map. + * + * @return a string showing all mappings + */ + override def toString() = + elements.toList.map(kv => kv._1 + " -> " + kv._2).mkString(stringPrefix + "(", ", ", ")") + + /** The default value for the map, returned when a key is not found + * The method implemented here yields an error, + * but it might be overridden in subclasses. + * + * @param key the given key value + * @throws Predef.NoSuchElementException + */ + def default(key: A): B = + throw new NoSuchElementException("key not found: " + key) + +/* + override def view: Map.View[A,B] = new Map.View[A, B] { + override def elements = self.elements + override def size = self.size + override def get(key: A): Option[B] = self.get(key) + } +*/ + def filterKeys(p: A => Boolean) = new MapView[CC, A, B] { + val origin = self + override def foreach(f: ((A, B)) => Unit): Unit = for (kv <- self) if (p(kv._1)) f(kv) + def elements = self.elements.filter(kv => p(kv._1)) + def size = { var sz = 0; foreach(_ => sz += 1); sz } + override def contains(key: A) = self.contains(key) && p(key) + def get(key: A) = if (!p(key)) None else self.get(key) + } + + def mapElements[C](f: B => C) = new MapView[CC, A,C] { + val origin = self + override def foreach(g: ((A, C)) => Unit): Unit = for ((k, v) <- self) g((k, f(v))) + def elements = for ((k, v) <- self.elements) yield (k, f(v)) + def size = self.size + override def contains(key: A) = self.contains(key) + def get(key: A) = self.get(key).map(f) + } + + /** Defines the prefix of this object's <code>toString</code> representation. + */ + override def stringPrefix: String = "Map" + + /** Add a key/value pair to this map. + * @param key the key + * @param value the value + * @return A new map with the new binding added to this map + */ + def update (key: A, value: B): CC[A, B] + + /** Add a key/value pair to this map. + * @param kv the key/value pair. + * @return A new map with the new binding added to this map + */ + def + (kv: (A, B)): CC[A, B] = update(kv._1, kv._2) + + /** Remove a key from this map + * @param key the key to be removed + * @return If the map does not contain a binding for <code>key</code> + * it is returned unchanged. Otherwise, return a new map + * without a binding for <code>key</code> + */ + def - (key: A): CC[A, B] + + /** This function transforms all the values of mappings contained + * in this map with function <code>f</code>. + * + * @param f A function over keys and values + * @return the updated map + */ + def transform[C](f: (A, B) => C): CC[A, C] = { + var res = empty[C] + for ((key, value) <- this) res += ((key, f(key, value))) + res + } + + /** Builds a new map with all key/value pairs of this map + * for which the predicate <code>p</code> returns <code>true</code>. + * + * @param p A predicate over key-value pairs + * @return the updated map + */ + override def filter(p: ((A, B)) => Boolean): CC[A, B] = { + var res = empty[B] + for (kv <- this) + if (p(kv)) res += kv + res + } + + /** Removes all the mappings for which the predicate + * <code>p</code> returns <code>false</code>. + * + * @param p A predicate over key-value pairs + * @return the updated map + */ + override def remove(p: ((A, B)) => Boolean): CC[A, B] = { + var res = this + for (kv <- this) + if (!p(kv)) res -= kv._1 + res + } +} diff --git a/src/library/scalax/collection/generic/MapView.scala b/src/library/scalax/collection/generic/MapView.scala new file mode 100644 index 0000000000..924fd1173e --- /dev/null +++ b/src/library/scalax/collection/generic/MapView.scala @@ -0,0 +1,44 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + +package scalax.collection.generic + +/** A non-strict view of a map. + * @author Martin Odersky + * @version 2.8 + */ +trait MapView[+UC[A1, B1] <: MapTemplate[A1, B1, UC] with Map[A1, B1], A, B] extends Map[A, B] { self => + + val origin: Map[A, _] + + def empty[C] = origin.empty[C] + + def elements: Iterator[(A, B)] + + val underlying: Map[A, _] = origin match { + case v: MapView[t, _, _] => v.underlying + case _ => origin + } + private[this] var forced: UC[A, B] = _ + private[this] var wasForced = false + + def force: UC[A, B] = { + if (!wasForced) { + forced = underlying.empty[B].asInstanceOf[UC[A, B]] ++ elements + wasForced = true + } + forced + } + + def update (key: A, value: B): UC[A, B] = force update (key, value) + def - (key: A): UC[A, B] = force - key +} + + diff --git a/src/library/scalax/collection/generic/MutableVectorTemplate.scala b/src/library/scalax/collection/generic/MutableVectorTemplate.scala new file mode 100755 index 0000000000..71c3f7bdf8 --- /dev/null +++ b/src/library/scalax/collection/generic/MutableVectorTemplate.scala @@ -0,0 +1,56 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2006-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Vector.scala 15437 2008-06-25 16:22:45Z stepancheg $ + +package scalax.collection.generic + +import collection.mutable.Vector +import collection.mutable.Vector._ + +/** Sequences that support O(1) element access and O(1) length computation. + * plus an update operation. + * @author Sean McDirmid + * @author Martin Odersky + * @version 2.8 + */ +trait MutableVectorTemplate[+CC[B] <: MutableVectorTemplate[CC, B] with Vector[B], A] extends VectorTemplate[CC, A] { +self => + + def update(idx: Int, elem: A) + + /** Creates a view of this iterable @see OrderedIterable.View + */ + override def view: MutableVectorView[CC, A] = new MutableVectorView[CC, A] { // !!! Martin: We should maybe infer the type parameters here? + val origin: Vector[_] = thisCC + val length: Int = self.length + def apply(idx: Int): A = self.apply(idx) + def update(idx: Int, elem: A) = self.update(idx, elem) + } + + /** A sub-sequence view starting at index `from` + * and extending up to (but not including) index `until`. + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + * @note The difference between `view` and `slice` is that `view` produces + * a view of the current sequence, whereas `slice` produces a new sequence. + * + * @note view(from, to) is equivalent to view.slice(from, to) + */ + override def view(from: Int, until: Int): MutableVectorView[CC, A] = view.slice(from, until) + + def readOnly: collection.Vector[A] = new collection.Vector[A] { //!!! just use a VectorProxy? + def length = self.length + def apply(idx : Int) = self.apply(idx) + def newBuilder[B]: Builder[collection.Vector, B] = self.newBuilder[B] //mapResult (_.readOnly) + override def foreach(f: A => Unit) = self.foreach(f) + override def stringPrefix = self.stringPrefix+"RO" + } +} + diff --git a/src/library/scalax/collection/generic/MutableVectorView.scala b/src/library/scalax/collection/generic/MutableVectorView.scala new file mode 100755 index 0000000000..450943f61d --- /dev/null +++ b/src/library/scalax/collection/generic/MutableVectorView.scala @@ -0,0 +1,95 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Sequence.scala 16092 2008-09-12 10:37:06Z nielsen $ + + +package scalax.collection.generic + +import collection.mutable.Vector +import collection.mutable.Vector._ + +/** A non-strict projection of an iterable. + * @author Sean McDirmid + * @author Martin Odersky + * @note this should really be a virtual class of SequenceFactory + */ +trait MutableVectorView[+UC[B] <: Vector[B], A] extends SequenceView[UC, A] with Vector[A] { +self => + + /** refined from Iterable.View */ + val origin: Vector[_] + + trait Transformed[B] extends super.Transformed[B] with MutableVectorView[UC, B] { + override val origin = self + override def elements: Iterator[B] = new Elements(0, length) + override protected def asCC = asInstanceOf[MutableVectorView[UC, B]] + } + + class Appended(that: Vector[A]) extends super.Appended[A](that) with Transformed[A] { + override def update(idx: Int, elem: A) { + val ll = self.length + if (idx < ll) self.update(idx, elem) else that.update(idx - ll, elem) + } + } + + class Sliced(from: Int, to: Int) extends super.Sliced(from, to) with Transformed[A] { + override def update(idx: Int, elem: A) { + if (idx >= 0 && idx < length) self.update(idx + from, elem) + else throw new IndexOutOfBoundsException(idx.toString) + } + override def slice(from1: Int, to1: Int) = + new self.Sliced(from + (from1 min length max 0) , to + (to1 min length max 0)) + } + + class Reversed extends super.Reversed with Transformed[A] { + override def update(idx: Int, elem: A) { + self.update(length - 1 - idx, elem) + } + } + + class Zipped[B](that: Vector[B]) extends super.Zipped[B](that) with Transformed[(A, B)] { + override def update(idx: Int, elem: (A, B)) { + self.update(idx, elem._1) + that.update(idx, elem._2) + } + } + + def ++(that: Vector[A]): MutableVectorView[UC, A] = + new Appended(that).asCC + + override def reverse: MutableVectorView[UC, A] = + (new Reversed).asCC + + private def toVector[B](xs: Iterable[B]): Vector[B] = xs match { + case ras: Vector[_] => ras.asInstanceOf[Vector[B]] + case _ => Vector() ++ xs + } + + override def zip[B](that: Iterable[B]): MutableVectorView[UC, (A, B)] = + new Zipped(toVector(that)).asCC + + override def zipWithIndex: MutableVectorView[UC, (A, Int)] = + zip((0 until length).asInstanceOf[Null]) // !@! + override def take(n: Int): MutableVectorView[UC, A] = + slice(0, n) + override def drop(n: Int): MutableVectorView[UC, A] = + slice(n, Math.MAX_INT) + override def splitAt(n: Int): (MutableVectorView[UC, A], MutableVectorView[UC, A]) = (take(n), drop(n)) + override def slice(from: Int, until: Int): MutableVectorView[UC, A] = + new Sliced(from, until).asCC + override def takeWhile(p: A => Boolean): MutableVectorView[UC, A] = + take(prefixLength(p)) + override def dropWhile(p: A => Boolean): MutableVectorView[UC, A] = + drop(prefixLength(p)) + override def span(p: A => Boolean): (MutableVectorView[UC, A], MutableVectorView[UC, A]) = { + val n = prefixLength(p) + (take(n), drop(n)) + } +} + diff --git a/src/library/scalax/collection/generic/OrderedIterableForwarder.scala b/src/library/scalax/collection/generic/OrderedIterableForwarder.scala new file mode 100755 index 0000000000..643f31d861 --- /dev/null +++ b/src/library/scalax/collection/generic/OrderedIterableForwarder.scala @@ -0,0 +1,37 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: IterableProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $ + + +package scalax.collection.generic + +/** This trait implements a forwarder for iterable objects. It forwards + * all calls to a different iterable object, except for + * + * - toString, hashCode, equals, stringPrefix + * - newBuilder, view + * - all calls creating a new iterable object of the same kind + * + * The above methods are forwarded by subclass IterableProxy + * + * @author Martin Odersky + * @version 2.8 + */ +trait OrderedIterableForwarder[+A] extends OrderedIterable[A] with IterableForwarder[A] { + + /** The iterable object to which calls are forwarded */ + protected def underlying: OrderedIterable[A] + + // Iterable delegates + // Iterable methods could be printed by cat IterableTemplate.scala | sed -n '/trait Iterable/,$ p' | egrep '^ (override )?def' + + override def last: A = underlying.last + override def lastOption: Option[A] = underlying.lastOption + override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that) +} diff --git a/src/library/scalax/collection/generic/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/OrderedIterableTemplate.scala index 9e61daa418..501cbf6447 100755 --- a/src/library/scalax/collection/generic/OrderedIterableTemplate.scala +++ b/src/library/scalax/collection/generic/OrderedIterableTemplate.scala @@ -13,6 +13,8 @@ package scalax.collection.generic import OrderedIterable._ +import util.control.Breaks._ + /** Ordered iterables are iterables where the `elements` method always returns elements in the same * order (namely the order in which elements were appended to the iterable). In particular, one has * for every two ordered iterables `xs` and `ys`: @@ -20,4 +22,140 @@ import OrderedIterable._ * `(xs ++ ys).elements = xs.elements ++ ys.elements */ trait OrderedIterableTemplate[+CC[/*+*/B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], /*+*/A] - extends IterableTemplate[CC, A] + extends IterableTemplate[CC, A] { + + /** The last element of this iterable. + * + * @throws Predef.NoSuchElementException if the iterable is empty. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def last: A = { + var lst = head + for (x <- this) + lst = x + lst + } + + /** Returns as an option the last element of this iterable or + * <code>None</code> if iterable is empty. + * + * @return the last element as an option. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def lastOption: Option[A] = if (isEmpty) None else Some(last) + + /** An iterable consisting of all elements of this iterable except the last one. + * @throws Predef.UnsupportedOperationException if the stream is empty. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def init: CC[A] = { + if (isEmpty) throw new UnsupportedOperationException("empty.init") + var lst = head + val b = newBuilder[A] + for (x <- this) { + b += lst + lst = x + } + b.result + } + + /** Returns the rightmost <code>n</code> elements from this iterable. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this iterable is ordered + */ + def takeRight(n: Int): CC[A] = { + val b = newBuilder[A] + val lead = elements drop n + var go = false + for (x <- this) { + if (go) b += x + else if (lead.hasNext) lead.next + else go = true + } + b.result + } + + /** Returns the iterable wihtout its rightmost <code>n</code> elements. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this iterable is ordered + */ + def dropRight(n: Int): CC[A] = { + val b = newBuilder[A] + val lead = elements drop n + breakable { + for (x <- this) { + if (!lead.hasNext) break + lead.next + b += x + } + } + b.result + } + + /** Returns the longest prefix of this iterable whose elements satisfy + * the predicate <code>p</code>. + * + * @param p the test predicate. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def takeWhile(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + breakable { + for (x <- this) { + if (!p(x)) break + b += x + } + } + b.result + } + + /** Returns the longest suffix of this iterable whose first element + * does not satisfy the predicate <code>p</code>. + * + * @param p the test predicate. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def dropWhile(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + var go = false + for (x <- this) { + if (go) b += x + else if (!p(x)) { go = true; b += x } + } + b.result + } + + /** Returns a pair consisting of the longest prefix of the iterable whose + * elements all satisfy the given predicate, and the rest of the iterable. + * + * @param p the test predicate + * @return a pair consisting of the longest prefix of the iterable whose + * elements all satisfy <code>p</code>, and the rest of the iterable. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def span(p: A => Boolean): (CC[A], CC[A]) = { + val l, r = newBuilder[A] + var toLeft = true + for (x <- this) { + toLeft = toLeft && p(x) + (if (toLeft) l else r) += x + } + (l.result, r.result) + } + + /** Checks if the other iterable object contains the same elements as this one. + * + * @note will not terminate for infinite-sized iterables. + * @param that the other iterable + * @return true, iff both iterables contain the same elements. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def sameElements[B >: A](that: OrderedIterable[B]): Boolean = { + val these = this.elements + val those = that.elements + while (these.hasNext && those.hasNext && these.next() == those.next()) {} + !these.hasNext && !those.hasNext + } +} diff --git a/src/library/scalax/collection/generic/OrderedIterableView.scala b/src/library/scalax/collection/generic/OrderedIterableView.scala new file mode 100755 index 0000000000..fd04daa0b6 --- /dev/null +++ b/src/library/scalax/collection/generic/OrderedIterableView.scala @@ -0,0 +1,85 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + +package scalax.collection.generic + +/** A non-strict projection of an iterable. + * @author Sean McDirmid + * @author Martin Odersky + * @note this should really be a virtual class of SequenceFactory + */ +trait OrderedIterableView[+UC[/*+*/B] <: Iterable[B], /*+*/A] extends IterableView[UC, A] with OrderedIterable[A] { self => + + val origin: OrderedIterable[_] + + /** Builds a new view object. This method needs to be overridden in subclasses + * which refine in IterableView type + */ + protected override def newView[B](elems: Iterator[B]) = new OrderedIterableView[UC, B] { + val origin = if (self.isDelay) self.origin else self + val elements = elems + } + + /** Non-strict variant of @see IterableLike.++ */ + override def ++[B >: A](that: Iterator[B]): OrderedIterableView[UC, B] = newView(elements ++ that) + + /** Non-strict variant of @see IterableLike.++ */ + override def ++[B >: A](that: Iterable[B]): OrderedIterableView[UC, B] = newView(elements ++ that.elements) + + /** Non-strict variant of @see IterableLike.map */ + override def map[B](f: A => B): OrderedIterableView[UC, B] = newView(elements map f) + + /** Non-strict variant of @see IterableLike.flatMap */ + override def flatMap[B](f: A => Iterable[B]): OrderedIterableView[UC, B] = newView(elements flatMap (f(_).elements)) + + /** Non-strict variant of @see IterableLike.filter */ + override def filter(p: A => Boolean): OrderedIterableView[UC, A] = newView(elements filter p) + + /** Non-strict variant of @see IterableLike.partition */ + override def partition(p: A => Boolean): (OrderedIterableView[UC, A], OrderedIterableView[UC, A]) = { + val (li, ri) = elements partition p + (newView(li), newView(ri)) + } + + /** Non-strict variant of @see IterableLike.zip */ + override def zip[B](other: Iterable[B]): OrderedIterableView[UC, (A, B)] = newView(elements zip other.elements) + + /** Non-strict variant of @see IterableLike.zipWithIndex */ + override def zipWithIndex: OrderedIterableView[UC, (A, Int)] = newView(elements.zipWithIndex) + + /* Non-strict variant of @see IterableLike.zipAll + * This is not enabled because it can't be specialized in VectorView: + * VectorView is not covariant, yet must maintain updatability. Impossible to do this + * with this type signature. + override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): OrderedIterableView[UC, (A1, B1)] = + newView(elements zipAll (that.elements, thisElem, thatElem)) + */ + + /** Non-strict variant of @see Iterable.take */ + override def take(n: Int): OrderedIterableView[UC, A] = newView(elements take n) + + /** Non-strict variant of @see Iterable.drop */ + override def drop(n: Int): OrderedIterableView[UC, A] = newView(elements drop n) + + /** Non-strict variant of @see Iterable.splitAt */ + override def splitAt(n: Int): (OrderedIterableView[UC, A], OrderedIterableView[UC, A]) = (take(n), drop(n)) + + /** Non-strict variant of @see Iterable.slice */ + override def slice(from: Int, until: Int): OrderedIterableView[UC, A] = newView(elements slice (from, until)) + + /** Non-strict variant of @see Iterable.takeWhile */ + override def takeWhile(p: A => Boolean): OrderedIterableView[UC, A] = newView(elements takeWhile p) + + /** Non-strict variant of @see Iterable.dropWhile */ + override def dropWhile(p: A => Boolean): OrderedIterableView[UC, A] = newView(elements dropWhile p) + + /** Non-strict variant of @see Iterable.span */ + override def span(p: A => Boolean): (OrderedIterableView[UC, A], OrderedIterableView[UC, A]) = (takeWhile(p), dropWhile(p)) +} diff --git a/src/library/scalax/collection/generic/SetFactory.scala b/src/library/scalax/collection/generic/SetFactory.scala index 0fbcf68466..458d4bbade 100644 --- a/src/library/scalax/collection/generic/SetFactory.scala +++ b/src/library/scalax/collection/generic/SetFactory.scala @@ -6,4 +6,6 @@ trait SetFactory[CC[A] <: SetTemplate[CC, A] with Set[A]] extends IterableFactor def apply[A](elems: A*): CC[A] = empty[A] ++ elems.asInstanceOf[Iterable[A]] // !@! + override def newBuilder[B]: Builder[CC, B] = new AddableBuilder[CC, B](empty) + } diff --git a/src/library/scalax/collection/generic/SetTemplate.scala b/src/library/scalax/collection/generic/SetTemplate.scala index 9c3056cc04..bd94f10fc0 100755 --- a/src/library/scalax/collection/generic/SetTemplate.scala +++ b/src/library/scalax/collection/generic/SetTemplate.scala @@ -31,7 +31,12 @@ package scalax.collection.generic * @author Martin Odersky * @version 2.8 */ -trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boolean) with SizedIterable[A] with OrderedIterableTemplate[CC, A] { +trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] + extends (A => Boolean) + with SizedIterable[A] + with IterableTemplate[CC, A] + with Addable[CC[A], A] + with Subtractable[CC[A], A] { /** Returns the number of elements in this set. * @@ -52,13 +57,13 @@ trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boo /** Create a new set with an additional element. */ - def +(elem: A): CC[A] + def + (elem: A): CC[A] /** Remove a single element from a set. * @param elem the element to be removed * @return a new set with the element removed. */ - def -(elem: A): CC[A] + def - (elem: A): CC[A] /** Checks if this set is empty. * @@ -76,43 +81,6 @@ trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boo */ def apply(elem: A): Boolean = contains(elem) - /** Add two or more elements to this set. - * @param elem1 the first element. - * @param elem2 the second element. - * @param elems the remaining elements. - * @return a new set with the elements added. - */ - def + (elem1: A, elem2: A, elems: A*): CC[A] = { - thisCC + elem1 + elem2 ++ elems.asInstanceOf[Iterable[A]] - } - - /** Remove two or more elements from this set. - * - * @param elem1 the first element. - * @param elem2 the second element. - * @param elems the remaining elements. - * @return a new set with the elements removed. - */ - def - (elem1: A, elem2: A, elems: A*): CC[A] = - this - elem1 - elem2 -- elems.asInstanceOf[Iterable[A]] - - /** Remove all the elements provided by an iterator - * of the iterable object <code>elems</code> from the set. - * - * @param elems An iterable object containing the elements to remove from the set. - * @return a new set with the elements removed. - */ - def -- (elems: Iterable[A]): CC[A] = this -- elems.elements - - /** Remove all the elements provided by an iterator - * <code>elems</code> from the set. - * - * @param elems An iterator containing the elements to remove from the set. - * @return a new set with the elements removed. - */ - def -- (elems: Iterator[A]): CC[A] = - (thisCC /: elems) (_ - _) - /** This method computes an intersection with set <code>that</code>. * It removes all the elements that are not present in <code>that</code>. * @@ -137,6 +105,9 @@ trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boo */ def subsetOf(that: Set[A]): Boolean = forall(that.contains) +/* What a mess! We need to remove these methods, but can't without breaking + * existing code. What to do? + /** Compares this set with another object and returns true, iff the * other object is also a set which contains the same elements as * this set. @@ -156,18 +127,22 @@ trait SetTemplate[+CC[B] <: SetTemplate[CC, B] with Set[B], A] extends (A => Boo false } - /* @deprecated hashCode is not stable for mutable sets. - * if you intend to have object identity hashCode and wish the deprecated warning + /* @deprecated Since the previous hashCode is not stable for mutable sets, + * the implementation of this method has been changed to + * standard address-based hashCode from java.lang.Object. + * If you relied on the old behavior, y + * IT has been + * if you intend to have object identity hashCode and wish the deprecated warning * to go away, cast this set to AnyRef before calling hashCode. */ @deprecated override def hashCode() = (0 /: this)((hash, e) => hash + e.hashCode()) - +*/ /** Defines the prefix of this object's <code>toString</code> representation. */ override def stringPrefix: String = "Set" /** Need to override string, so that it's not the Function1's string that gets mixed in. */ - override def toString = super[OrderedIterableTemplate].toString + override def toString = super[IterableTemplate].toString } diff --git a/src/library/scalax/collection/generic/Shrinkable.scala b/src/library/scalax/collection/generic/Shrinkable.scala new file mode 100755 index 0000000000..e6d3b085f3 --- /dev/null +++ b/src/library/scalax/collection/generic/Shrinkable.scala @@ -0,0 +1,54 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + +package scalax.collection.generic + +/** This class represents collections that can be reduced using a -= operator. + * + * @autor Martin Odersky + * @owner Martin Odersky + * @version 2.8 + */ +trait Shrinkable[A] { + + /** Removes a single element from this collection. + * + * @param elem the element to remove. + */ + def -=(elem: A): Unit + + /** Removes two or more elements from this collection. + * + * @param elem1 the first element to remove. + * @param elem2 the second element to remove. + * @param elems the remaining elements to remove. + */ + def -=(elem1: A, elem2: A, elems: A*) { + this -= elem1 + this -= elem2 + this --= elems.asInstanceOf[Iterable[A]] // !@! + } + + /** Removes a number of elements provided by an iterator from this collection. + * + * @param iter the iterator. + */ + def --=(iter: collection.Iterator[A]) { iter foreach -= } + + /** Removes a number of elements provided by an iterable object from this collection. + * + * @param iter the iterable object. + */ + def --=(iter: collection.Iterable[A]) { iter foreach -= } +} + + + + diff --git a/src/library/scalax/collection/generic/Subtractable.scala b/src/library/scalax/collection/generic/Subtractable.scala new file mode 100755 index 0000000000..93fe2f8190 --- /dev/null +++ b/src/library/scalax/collection/generic/Subtractable.scala @@ -0,0 +1,64 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + +package scalax.collection.generic + +/** This class represents collections that can be reduced using a -= operator. + * + * @autor Martin Odersky + * @owner Martin Odersky + * @version 2.8 + */ +trait Subtractable[+C <: Subtractable[C, A], A] { + + protected def thisCC: C + + /** Removes a single element from this collection and returns + * either the collection itself (if it is mutable), or a new collection + * with the removed element. + * + * @param elem the element to remove. + */ + def -(elem: A): C + + /** Removes two or more elements from this collection and returns + * either the collection itself (if it is mutable), or a new collection + * with the removed elements. + * + * @param elem1 the first element to remove. + * @param elem2 the second element to remove. + * @param elems the remaining elements to remove. + */ + def -(elem1: A, elem2: A, elems: A*): C = + thisCC - elem1 - elem2 -- elems.asInstanceOf[Iterable[A]] // !@! + + /** Removes a number of elements provided by an iterable object + * via its <code>elements</code> method and returns + * either the collection itself (if it is mutable), or a new collection + * with the removed elements. + * + * @param iter the iterable object. + */ + def --(iter: Iterable[A]): C = (thisCC /: iter) (_ - _) + + /** Removes a number of elements provided by an iterator + * via its <code>elements</code> method and returns + * either the collection itself (if it is mutable), or a new collection + * with the removed elements. + * + * @param iter the iterator + */ + def --(iter: Iterator[A]): C = (thisCC /: iter) (_ - _) + +} + + + + diff --git a/src/library/scalax/collection/generic/covartest/IterableForwarder.scala b/src/library/scalax/collection/generic/covartest/IterableForwarder.scala index cd4a754e97..58290cfc68 100755 --- a/src/library/scalax/collection/generic/covartest/IterableForwarder.scala +++ b/src/library/scalax/collection/generic/covartest/IterableForwarder.scala @@ -56,6 +56,4 @@ trait IterableForwarder[+A] extends Iterable[A] { override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = underlying.addString(b, start, sep, end) override def head: A = underlying.head - override def last: A = underlying.last - override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that) } diff --git a/src/library/scalax/collection/generic/covartest/IterableTemplate.scala b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala index 27772b2ece..791d698a75 100755 --- a/src/library/scalax/collection/generic/covartest/IterableTemplate.scala +++ b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala @@ -56,6 +56,11 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] */ def newBuilder[B]: Builder[CC, B] + /** Create a new builder for this IterableType + * with a hint what that its size should be size `sizeHint` + */ + def newBuilder[B](sizeHint: Int): Builder[CC, B] = newBuilder[B] + /** Is this collection empty? */ def isEmpty: Boolean = !elements.hasNext @@ -65,7 +70,7 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] */ def hasDefiniteSize = true - /** Create a new sequence of type CC which contains all elements of this sequence + /** Create a new iterable of type CC which contains all elements of this iterable * followed by all elements of Iterable `that' */ def ++[B >: A](that: Iterable[B]): CC[B] = { @@ -75,7 +80,7 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] b.result } - /** Create a new sequence of type IterableType which contains all elements of this sequence + /** Create a new iterable of type CC which contains all elements of this iterable * followed by all elements of Iterator `that' */ def ++[B >: A](that: Iterator[B]): CC[B] = { @@ -85,12 +90,12 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] b.result } - /** Returns the sequence resulting from applying the given function - * <code>f</code> to each element of this sequence. + /** Returns the iterable resulting from applying the given function + * <code>f</code> to each element of this iterable. * * @param f function to apply to each element. * @return <code>f(a<sub>0</sub>), ..., f(a<sub>n</sub>)</code> if this - * sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. + * iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. */ def map[B](f: A => B): CC[B] = { val b = newBuilder[B] @@ -99,11 +104,11 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] } /** Applies the given function <code>f</code> to each element of - * this sequence, then concatenates the results. + * this iterable, then concatenates the results. * * @param f the function to apply on each element. * @return <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if - * this sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. + * this iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. */ def flatMap[B](f: A => Iterable[B]): CC[B] = { val b = newBuilder[B] @@ -111,10 +116,10 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] b.result } - /** Returns all the elements of this sequence that satisfy the + /** Returns all the elements of this iterable that satisfy the * predicate <code>p</code>. The order of the elements is preserved. - * @param p the predicate used to filter the list. - * @return the elements of this list satisfying <code>p</code>. + * @param p the predicate used to filter the iterable. + * @return the elements of this iterable satisfying <code>p</code>. */ def filter(p: A => Boolean): CC[A] = { val b = newBuilder[A] @@ -128,7 +133,7 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] * predicate inversed. * * @param p the predicate to use to test elements - * @return the list without all elements which satisfy <code>p</code> + * @return the iterable without all elements which satisfy <code>p</code> */ def remove(p: A => Boolean): CC[A] = filter(!p(_)) @@ -203,6 +208,8 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] * predicate, if any. * * @note may not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @param p the predicate * @return an option containing the first element in the iterable object * satisfying <code>p</code>, or <code>None</code> if none exists. @@ -221,8 +228,10 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] * the value <code>z</code>. * * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...), - * a<sub>n</sub>)</code> if the list is + * a<sub>n</sub>)</code> if the iterable is * <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>. */ def foldLeft[B](z: B)(op: (B, A) => B): B = { @@ -232,32 +241,40 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] result } - /** Combines the elements of this list together using the binary + /** Combines the elements of this iterable together using the binary * function <code>f</code>, from right to left, and starting with * the value <code>z</code>. * * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code> - * if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. + * if the iterable is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. */ def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op) /** Similar to <code>foldLeft</code> but can be used as - * an operator with the order of list and zero arguments reversed. + * an operator with the order of iterable and zero arguments reversed. * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. */ def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op) /** An alias for <code>foldRight</code>. * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. */ def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op) /** Combines the elements of this iterable object together using the binary * operator <code>op</code>, from left to right * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @param op The operator to apply * @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code> if the iterable object has elements @@ -277,6 +294,8 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] /** Combines the elements of this iterable object together using the binary * operator <code>op</code>, from right to left * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. * @param op The operator to apply * * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> @@ -288,7 +307,7 @@ trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] def reduceRight[B >: A](op: (A, B) => B): B = elements.reduceRight(op) - /** Returns an iterable formed from this iterable and the specified list + /** Returns an iterable formed from this iterable and the specified iterable * `other` by associating each element of the former with * the element at the same position in the latter. * If one of the two iterables is longer than the other, its remaining elements are ignored. @@ -356,7 +375,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the } /** Fills the given array <code>xs</code> with at most `len` elements of - * this sequence starting at position `start`. + * this iterable starting at position `start`. * Copying will stop oce either the end of the current iterable is reached or * `len` elements have been copied. * @@ -378,7 +397,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the } /** Fills the given array <code>xs</code> with the elements of - * this sequence starting at position <code>start</code> + * this iterable starting at position <code>start</code> * until either the end of the current iterable or the end of array `xs` is reached. * * @note Will not terminate for infinite-sized collections. @@ -431,7 +450,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * same order in the sorted iterable as in the original. * * @param lt the comparison function - * @return a list sorted according to the comparison function + * @return a iterable sorted according to the comparison function * <code><(e1: a, e2: a) => Boolean</code>. * @ex <pre> * List("Steve", "Tom", "John", "Bob") @@ -454,7 +473,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * <code>sep</code>. * * @ex <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code> - * @note Will not terminate for infinite-sized collections. * @param start starting string. * @param sep separator string. * @param end ending string. @@ -467,7 +485,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * representations of elements (w.r.t. the method <code>toString()</code>) * are separated by the string <code>sep</code>. * - * @note Will not terminate for infinite-sized collections. * @param sep separator string. * @return a string representation of this iterable object. */ @@ -475,7 +492,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the addString(new StringBuilder(), sep).toString /** Converts a collection into a flat <code>String</code> by each element's toString method. - * @note Will not terminate for infinite-sized collections. */ def mkString = addString(new StringBuilder()).toString @@ -485,7 +501,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * <code>end</code>. Inside, the string representations of elements (w.r.t. * the method <code>toString()</code>) are separated by the string * <code>sep</code>. - * @note Will not terminate for infinite-sized collections. */ def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = { b append start @@ -501,28 +516,13 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the /** Write all elements of this string into given string builder. * The string representations of elements (w.r.t. the method <code>toString()</code>) * are separated by the string <code>sep</code>. - * @note Will not terminate for infinite-sized collections. */ - def addString(b: StringBuilder, sep: String): StringBuilder = { - var first = true - for (x <- this) { - if (first) first = false - else b append sep - b append x - } - b - } + def addString(b: StringBuilder, sep: String): StringBuilder = addString(b, "", sep, "") /** Write all elements of this string into given string builder without using * any separator between consecutive elements. - * @note Will not terminate for infinite-sized collections. */ - def addString(b: StringBuilder): StringBuilder = { - for (x <- this) { - b append x - } - b - } + def addString(b: StringBuilder): StringBuilder = addString(b, "") /** * returns a projection that can be used to call non-strict <code>filter</code>, @@ -547,7 +547,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the string } - /** Creates a view of this iterable @see IterableView */ def view: IterableView[CC, A] = new IterableView[CC, A] { // !!! Martin: We should maybe infer the type parameters here? @@ -557,10 +556,10 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the // The following methods return non-deterministic results, unless this iterable is an OrderedIterable - /** The first element of this sequence. + /** The first element of this iterable. * * @note Might return different results for different runs, unless this iterable is ordered - * @throws Predef.NoSuchAentException if the sequence is empty. + * @throws Predef.NoSuchElementException if the iterable is empty. */ def head: A = if (isEmpty) throw new NoSuchElementException else elements.next @@ -574,7 +573,7 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the def headOption: Option[A] = if (isEmpty) None else Some(head) /** @deprecated use headOption instead - * <code>None</code> if list is empty. + * <code>None</code> if iterable is empty. */ @deprecated def firstOption: Option[A] = headOption @@ -589,7 +588,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the * than <code>n</code> elements. * * @param n the number of elements to take - * @return a possibly projected sequence * @note Might return different results for different runs, unless this iterable is ordered */ def take(n: Int): CC[A] = { @@ -648,74 +646,6 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the b.result } - /** The last element of this iterable. - * - * @throws Predef.NoSuchElementException if the sequence is empty. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def last: A = { - var lst = head - for (x <- this) - lst = x - lst - } - - /** Returns as an option the last element of this iterable or - * <code>None</code> if iterable is empty. - * - * @return the last element as an option. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def lastOption: Option[A] = if (isEmpty) None else Some(last) - - /** An iterable consisting of all elements of this iterable except the last one. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def init: CC[A] = { - var lst = head - val b = newBuilder[A] - for (x <- this) { - b += lst - lst = x - } - b.result - } - - /** Returns the rightmost <code>n</code> elements from this iterable. - * - * @param n the number of elements to take - * @note Might return different results for different runs, unless this iterable is ordered - */ - def takeRight(n: Int): CC[A] = { - val b = newBuilder[A] - val lead = elements drop n - var go = false - for (x <- this) { - if (go) b += x - else if (lead.hasNext) lead.next - else go = true - } - b.result - } - - /** Returns the iterable wihtout its rightmost <code>n</code> elements. - * - * @param n the number of elements to take - * @note Might return different results for different runs, unless this iterable is ordered - */ - def dropRight(n: Int): CC[A] = { - val b = newBuilder[A] - val lead = elements drop n - breakable { - for (x <- this) { - if (!lead.hasNext) break - lead.next - b += x - } - } - b.result - } - /** Split the iterable at a given point and return the two parts thus * created. * @@ -732,82 +662,13 @@ b * @param thatElem element <code>thatElem</code> is used to fill up the (l.result, r.result) } - /** Returns the longest prefix of this sequence whose elements satisfy - * the predicate <code>p</code>. - * - * @param p the test predicate. - * @return the longest prefix of this sequence whose elements satisfy - * the predicate <code>p</code>. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def takeWhile(p: A => Boolean): CC[A] = { - val b = newBuilder[A] - breakable { - for (x <- this) { - if (!p(x)) break - b += x - } - } - b.result - } - - /** Returns the longest suffix of this sequence whose first element - * does not satisfy the predicate <code>p</code>. - * - * @param p the test predicate. - * @return the longest suffix of the sequence whose first element - * does not satisfy the predicate <code>p</code>. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def dropWhile(p: A => Boolean): CC[A] = { - val b = newBuilder[A] - var go = false - for (x <- this) { - if (go) b += x - else if (!p(x)) { go = true; b += x } - } - b.result - } - - /** Returns a pair consisting of the longest prefix of the list whose - * elements all satisfy the given predicate, and the rest of the list. - * - * @param p the test predicate - * @return a pair consisting of the longest prefix of the list whose - * elements all satisfy <code>p</code>, and the rest of the list. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def span(p: A => Boolean): (CC[A], CC[A]) = { - val l, r = newBuilder[A] - var toLeft = true - for (x <- this) { - toLeft = toLeft && p(x) - (if (toLeft) l else r) += x - } - (l.result, r.result) - } - - /** Checks if the other iterable object contains the same elements as this one. - * - * @note will not terminate for infinite-sized iterables. - * @param that the other iterable - * @return true, iff both iterables contain the same elements. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def sameElements[B >: A](that: OrderedIterable[B]): Boolean = { - val these = this.elements - val those = that.elements - while (these.hasNext && those.hasNext && these.next() == those.next()) {} - !these.hasNext && !those.hasNext - } - - /** A sub-sequence view starting at index `from` + /** A sub-iterable view starting at index `from` * and extending up to (but not including) index `until`. * * @param from The index of the first element of the slice * @param until The index of the element following the slice * @note The difference between `view` and `slice` is that `view` produces - * a view of the current sequence, whereas `slice` produces a new sequence. + * a view of the current iterable, whereas `slice` produces a new iterable. * * @note Might return different results for different runs, unless this iterable is ordered * @note view(from, to) is equivalent to view.slice(from, to) diff --git a/src/library/scalax/collection/generic/covartest/IterableView.scala b/src/library/scalax/collection/generic/covartest/IterableView.scala index 855e4d259b..43a1f68dc0 100755 --- a/src/library/scalax/collection/generic/covartest/IterableView.scala +++ b/src/library/scalax/collection/generic/covartest/IterableView.scala @@ -25,7 +25,7 @@ trait IterableView[+UC[+B] <: Iterable[B], +A] extends Iterable[A] { self => case _ => origin } - private def isDelay = elements eq underlying.elements + protected def isDelay = elements eq underlying.elements private[this] var forced: UC[A] = _ private[this] var wasForced = false @@ -100,15 +100,6 @@ trait IterableView[+UC[+B] <: Iterable[B], +A] extends Iterable[A] { self => /** Non-strict variant of @see Iterable.slice */ override def slice(from: Int, until: Int): IterableView[UC, A] = newView(elements slice (from, until)) - /** Non-strict variant of @see Iterable.takeWhile */ - override def takeWhile(p: A => Boolean): IterableView[UC, A] = newView(elements takeWhile p) - - /** Non-strict variant of @see Iterable.dropWhile */ - override def dropWhile(p: A => Boolean): IterableView[UC, A] = newView(elements dropWhile p) - - /** Non-strict variant of @see Iterable.span */ - override def span(p: A => Boolean): (IterableView[UC, A], IterableView[UC, A]) = (takeWhile(p), dropWhile(p)) - /** The projection resulting from the concatenation of this projection with the <code>rest</code> projection. * @param rest The projection that gets appended to this projection * @deprecated Use ++ instead diff --git a/src/library/scalax/collection/generic/covartest/OrderedIterableForwarder.scala b/src/library/scalax/collection/generic/covartest/OrderedIterableForwarder.scala new file mode 100755 index 0000000000..3a33dc6694 --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/OrderedIterableForwarder.scala @@ -0,0 +1,37 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: IterableProxy.scala 15458 2008-06-28 20:23:22Z stepancheg $ + + +package scalax.collection.generic.covartest + +/** This trait implements a forwarder for iterable objects. It forwards + * all calls to a different iterable object, except for + * + * - toString, hashCode, equals, stringPrefix + * - newBuilder, view + * - all calls creating a new iterable object of the same kind + * + * The above methods are forwarded by subclass IterableProxy + * + * @author Martin Odersky + * @version 2.8 + */ +trait OrderedIterableForwarder[+A] extends OrderedIterable[A] with IterableForwarder[A] { + + /** The iterable object to which calls are forwarded */ + protected def underlying: OrderedIterable[A] + + // Iterable delegates + // Iterable methods could be printed by cat IterableTemplate.scala | sed -n '/trait Iterable/,$ p' | egrep '^ (override )?def' + + override def last: A = underlying.last + override def lastOption: Option[A] = underlying.lastOption + override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = underlying.sameElements(that) +} diff --git a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala index 4316c9b34d..f3c509887c 100755 --- a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala +++ b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala @@ -13,6 +13,8 @@ package scalax.collection.generic.covartest import OrderedIterable._ +import util.control.Breaks._ + /** Ordered iterables are iterables where the `elements` method always returns elements in the same * order (namely the order in which elements were appended to the iterable). In particular, one has * for every two ordered iterables `xs` and `ys`: @@ -20,4 +22,140 @@ import OrderedIterable._ * `(xs ++ ys).elements = xs.elements ++ ys.elements */ trait OrderedIterableTemplate[+CC[+B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], +A] - extends IterableTemplate[CC, A] + extends IterableTemplate[CC, A] { + + /** The last element of this iterable. + * + * @throws Predef.NoSuchElementException if the iterable is empty. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def last: A = { + var lst = head + for (x <- this) + lst = x + lst + } + + /** Returns as an option the last element of this iterable or + * <code>None</code> if iterable is empty. + * + * @return the last element as an option. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def lastOption: Option[A] = if (isEmpty) None else Some(last) + + /** An iterable consisting of all elements of this iterable except the last one. + * @throws Predef.UnsupportedOperationException if the stream is empty. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def init: CC[A] = { + if (isEmpty) throw new UnsupportedOperationException("empty.init") + var lst = head + val b = newBuilder[A] + for (x <- this) { + b += lst + lst = x + } + b.result + } + + /** Returns the rightmost <code>n</code> elements from this iterable. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this iterable is ordered + */ + def takeRight(n: Int): CC[A] = { + val b = newBuilder[A] + val lead = elements drop n + var go = false + for (x <- this) { + if (go) b += x + else if (lead.hasNext) lead.next + else go = true + } + b.result + } + + /** Returns the iterable wihtout its rightmost <code>n</code> elements. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this iterable is ordered + */ + def dropRight(n: Int): CC[A] = { + val b = newBuilder[A] + val lead = elements drop n + breakable { + for (x <- this) { + if (!lead.hasNext) break + lead.next + b += x + } + } + b.result + } + + /** Returns the longest prefix of this iterable whose elements satisfy + * the predicate <code>p</code>. + * + * @param p the test predicate. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def takeWhile(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + breakable { + for (x <- this) { + if (!p(x)) break + b += x + } + } + b.result + } + + /** Returns the longest suffix of this iterable whose first element + * does not satisfy the predicate <code>p</code>. + * + * @param p the test predicate. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def dropWhile(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + var go = false + for (x <- this) { + if (go) b += x + else if (!p(x)) { go = true; b += x } + } + b.result + } + + /** Returns a pair consisting of the longest prefix of the iterable whose + * elements all satisfy the given predicate, and the rest of the iterable. + * + * @param p the test predicate + * @return a pair consisting of the longest prefix of the iterable whose + * elements all satisfy <code>p</code>, and the rest of the iterable. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def span(p: A => Boolean): (CC[A], CC[A]) = { + val l, r = newBuilder[A] + var toLeft = true + for (x <- this) { + toLeft = toLeft && p(x) + (if (toLeft) l else r) += x + } + (l.result, r.result) + } + + /** Checks if the other iterable object contains the same elements as this one. + * + * @note will not terminate for infinite-sized iterables. + * @param that the other iterable + * @return true, iff both iterables contain the same elements. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def sameElements[B >: A](that: OrderedIterable[B]): Boolean = { + val these = this.elements + val those = that.elements + while (these.hasNext && those.hasNext && these.next() == those.next()) {} + !these.hasNext && !those.hasNext + } +} diff --git a/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala b/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala index 5ada55f62d..47c512545d 100644 --- a/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala +++ b/src/library/scalax/collection/generic/covartest/SequenceForwarder.scala @@ -23,7 +23,7 @@ package scalax.collection.generic.covartest * @author Martin Odersky * @version 2.8 */ -trait SequenceForwarder[+A] extends Sequence[A] with IterableForwarder[A] { +trait SequenceForwarder[+A] extends Sequence[A] with OrderedIterableForwarder[A] { protected override def underlying: Sequence[A] diff --git a/src/library/scalax/collection/immutable/DefaultSet.scala b/src/library/scalax/collection/immutable/DefaultSet.scala new file mode 100644 index 0000000000..a9ce3fb3df --- /dev/null +++ b/src/library/scalax/collection/immutable/DefaultSet.scala @@ -0,0 +1,45 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashSet.scala 16884 2009-01-09 16:52:09Z cunei $ + +package scalax.collection.immutable + +import generic.SetTemplate + +/** A default implementation of immutable sets. + * This is currently implemented as a proxy for an immutable HashSet, + * except that its builder returns specialized representations EmptySet,Set1,..., Set4 + * for sets of size <= 4. + */ +class DefaultSet[A] private (hset: HashSet[A]) + extends Set[A] + with SetTemplate[Set, A] { + + def this() = this(new HashSet[A]) + + def contains(elem: A): Boolean = hset.contains(elem) + + def + (elem: A): Set[A] = hset + elem + + /** Keeps underlying HashSet representation, but switches back to EmptySet if + * result does not contain any elements + */ + def - (elem: A): Set[A] = { + val hset1 = hset - elem + if (hset1.isEmpty) new EmptySet[A] + else new DefaultSet(hset) + } + + def size: Int = hset.size + + def elements: Iterator[A] = hset.elements + + override def foreach(f: A => Unit): Unit = hset.foreach(f) +} + diff --git a/src/library/scalax/collection/immutable/EmptyMap.scala b/src/library/scalax/collection/immutable/EmptyMap.scala new file mode 100644 index 0000000000..c04d988f08 --- /dev/null +++ b/src/library/scalax/collection/immutable/EmptyMap.scala @@ -0,0 +1,34 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: EmptyMap.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class EmptyMap[A, B] extends Map[A, B] { + + def size: Int = 0 + + def get(key: A): Option[B] = None + + def elements: Iterator[(A, B)] = Iterator.empty + + def update (key: A, value: B): Map[A, B] = new Map1(key, value) + + def - (key: A): Map[A, B] = this +} + + + diff --git a/src/library/scalax/collection/immutable/EmptySet.scala b/src/library/scalax/collection/immutable/EmptySet.scala new file mode 100755 index 0000000000..32c4915a49 --- /dev/null +++ b/src/library/scalax/collection/immutable/EmptySet.scala @@ -0,0 +1,38 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: EmptySet.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +import collection.generic.Builder + +/** This class implements empty immutable sets + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class EmptySet[A] extends Set[A] { + + def size: Int = 0 + + def contains(elem: A): Boolean = false + + def + (elem: A): Set[A] = new Set1(elem) + + def - (elem: A): Set[A] = this + + def elements: Iterator[A] = Iterator.empty + + override def foreach(f: A => Unit): Unit = {} +} + + + diff --git a/src/library/scalax/collection/immutable/HashMap.scala b/src/library/scalax/collection/immutable/HashMap.scala new file mode 100644 index 0000000000..7d3595904d --- /dev/null +++ b/src/library/scalax/collection/immutable/HashMap.scala @@ -0,0 +1,162 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashMap.scala 16893 2009-01-13 13:09:22Z cunei $ + + +package scalax.collection.immutable + +import generic._ + +/** The canonical factory methods for <a href="HashMap.html">immutable HashMap's</a>. + * + * @author Martin Odersky + * @version 2.0, 19/01/2007 + */ +object HashMap extends MapFactory[HashMap] { + + /** The empty map of this type */ + def empty[A, B] = new HashMap[A, B] + +} + +/** This class implements immutable maps using a hash table. + * It is optimized for sequential accesses where the last updated table is accessed most often. + * It supports with reasonable efficiency accesses to previous versions of the table by keeping + * a change log that's regularly compacted. + * It needs to synchronize most methods, so it is less suitable for highly concurrent accesses. + * + * @author Martin Odersky + * @version 2.0, 19/01/2007 + */ +@serializable +class HashMap[A, B] extends Map[A,B] + with MapTemplate[A, B, HashMap] + with mutable.HashTable[A] { + + type Entry = mutable.DefaultEntry[A, Any] + + protected var later: HashMap[A, B] = null + protected var oldKey: A = _ + protected var oldValue: Option[B] = _ + protected var deltaSize: Int = _ + + def get(key: A): Option[B] = synchronized { + var m = this + var cnt = 0 + while (m.later != null) { + if (key == m.oldKey) return m.oldValue + cnt += 1 + m = m.later + } + if (cnt > logLimit) makeCopy(m) + val e = m.findEntry(key) + if (e == null) None + else Some(getValue(e)) + } + + def update(key: A, value: B): HashMap[A, B] = synchronized { + makeCopyIfUpdated() + val e = findEntry(key) + if (e == null) { + markUpdated(key, None, 1) + later.addEntry(new Entry(key, value)) + } else { + markUpdated(key, Some(getValue(e)), 0) + e.value = value + } + later + } + + def - (key: A): HashMap[A, B] = synchronized { + makeCopyIfUpdated() + val e = findEntry(key) + if (e == null) this + else { + markUpdated(key, Some(getValue(e)), -1) + later removeEntry key + later + } + } + + override def size: Int = synchronized { + var m = this + var cnt = 0 + var s = 0 + while (m.later != null) { + s -= m.deltaSize + cnt += 1 + m = m.later + } + s += m.tableSize + if (cnt > logLimit) makeCopy(m) + s + } + + def elements = synchronized { + makeCopyIfUpdated() + entries map {e => (e.key, getValue(e))} + } + + private def getValue(e: Entry) = + e.value.asInstanceOf[B] + + private def logLimit: Int = Math.sqrt(table.length).toInt + + private def markUpdated(key: A, ov: Option[B], delta: Int) { + val lv = loadFactor + later = new HashMap[A, B] { + override def initialSize = 0 + override def loadFactor = lv + table = HashMap.this.table + tableSize = HashMap.this.tableSize + threshold = HashMap.this.threshold + } + oldKey = key + oldValue = ov + deltaSize = delta + } + + private def makeCopy(last: HashMap[A, B]) { + def undo(m: HashMap[A, B]) { + if (m ne last) { + undo(m.later) + if (m.deltaSize == 1) removeEntry(m.oldKey) + else if (m.deltaSize == 0) findEntry(m.oldKey).value = m.oldValue.get + else if (m.deltaSize == -1) addEntry(new Entry(m.oldKey, m.oldValue.get)) + } + } + def copy(e: Entry): Entry = + if (e == null) null + else { + val rest = copy(e.next) + val result = new Entry(e.key, e.value) + result.next = rest + result + } + val ltable = last.table + val s = ltable.length + table = new scala.Array[mutable.HashEntry[A, Entry]](s) + var i = 0 + while (i < s) { + table(i) = copy(ltable(i).asInstanceOf[Entry]) + i += 1 + } + tableSize = last.tableSize + threshold = last.threshold + undo(this) + later = null + } + + private def makeCopyIfUpdated() { + var m = this + while (m.later != null) m = m.later + if (m ne this) makeCopy(m) + } +} + diff --git a/src/library/scalax/collection/immutable/HashSet.scala b/src/library/scalax/collection/immutable/HashSet.scala new file mode 100644 index 0000000000..56394b9bc6 --- /dev/null +++ b/src/library/scalax/collection/immutable/HashSet.scala @@ -0,0 +1,138 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashSet.scala 16884 2009-01-09 16:52:09Z cunei $ + +package scalax.collection.immutable + +import generic.{SetTemplate, SetFactory, AddableBuilder} + +/** The canonical factory methods for <a href="HashSet.html">immutable HashSet's<la>. + * + * @author Martin Odersky + * @version 2.8 + */ +object HashSet extends SetFactory[HashSet] { + + /** The empty set of this type. + */ + def empty[A] = new HashSet[A] + +} + +/** This class implements immutable maps/sets using a hash table. + * It is optimized for sequential accesses where the last updated table is accessed most often. + * It supports with reasonable efficiency accesses to previous versions of the table by keeping + * a change log that's regularly compacted. + * It needs to synchronize most methods, so it is less suitable for highly concurrent accesses. + * + * @author Martin Odersky + * @version 2.0, 19/01/2007 + */ +@serializable +class HashSet[A] extends Set[A] + with SetTemplate[HashSet, A] + with mutable.FlatHashTable[A] { + protected var later: HashSet[A] = null + protected var changedElem: A = _ + protected var deleted: Boolean = _ + + def contains(elem: A): Boolean = synchronized { + var m = this + var cnt = 0 + while (m.later != null) { + if (elem == m.changedElem) return m.deleted + cnt += 1 + m = m.later + } + if (cnt > logLimit) makeCopy(m) + m.containsEntry(elem) + } + + def + (elem: A): HashSet[A] = synchronized { + makeCopyIfUpdated() + if (containsEntry(elem)) this + else { + markUpdated(elem, false) + later addEntry elem + later + } + } + + def - (elem: A): HashSet[A] = synchronized { + makeCopyIfUpdated() + if (!containsEntry(elem)) this + else { + markUpdated(elem, true) + later removeEntry elem + later + } + } + + override def size: Int = synchronized { + var m = this + var cnt = 0 + var s = 0 + while (m.later != null) { + if (m.deleted) s += 1 else s -= 1 + cnt += 1 + m = m.later + } + s += m.tableSize + if (cnt > logLimit) makeCopy(m) + s + } + + override def elements = synchronized { + makeCopyIfUpdated() + // note need to cache because (later versions of) set might be mutated while elements are traversed. + val cached = new mutable.ArrayBuffer() ++ super.elements + cached.elements + } + + override def newBuilder[B]: generic.Builder[HashSet, B] = + new AddableBuilder[HashSet, B](HashSet.empty) + + private def logLimit: Int = Math.sqrt(table.length).toInt + + private def markUpdated(elem: A, del: Boolean) { + val lv = loadFactor + later = new HashSet[A] { + override def initialSize = 0 + override def loadFactor = lv + table = HashSet.this.table + tableSize = HashSet.this.tableSize + threshold = HashSet.this.threshold + } + changedElem = elem + deleted = del + } + + private def makeCopy(last: HashSet[A]) { + def undo(m: HashSet[A]) { + if (m ne last) { + undo(m.later) + if (m.deleted) addEntry(m.changedElem) + else removeEntry(m.changedElem) + } + } + table = new scala.Array[AnyRef](last.table.length) + scala.Array.copy(last.table, 0, table, 0, table.length) + tableSize = last.tableSize + threshold = last.threshold + undo(this) + later = null + } + + private def makeCopyIfUpdated() { + var m = this + while (m.later != null) m = m.later + if (m ne this) makeCopy(m) + } +} + diff --git a/src/library/scalax/collection/immutable/Iterable.scala b/src/library/scalax/collection/immutable/Iterable.scala index 07e1fed890..0e6bb8fae0 100644 --- a/src/library/scalax/collection/immutable/Iterable.scala +++ b/src/library/scalax/collection/immutable/Iterable.scala @@ -1,6 +1,7 @@ package scalax.collection.immutable -import generic.covariant +import generic._ +import annotation.unchecked.uncheckedVariance /** Collection classes mixing in this class provide a method * <code>elements</code> which returns an iterator over all the @@ -14,9 +15,9 @@ import generic.covariant * @version 2.8 */ trait Iterable[+A] extends collection.Iterable[A] - with covariant.IterableTemplate[Iterable, A] + with IterableTemplate[Iterable, A @uncheckedVariance] -object Iterable extends covariant.IterableFactory[Iterable] { +object Iterable extends IterableFactory[Iterable] with EmptyIterableFactory[Iterable] { val empty: Iterable[Nothing] = Nil } diff --git a/src/library/scalax/collection/immutable/List.scala b/src/library/scalax/collection/immutable/List.scala index 6851fb9769..cb5965a18a 100644 --- a/src/library/scalax/collection/immutable/List.scala +++ b/src/library/scalax/collection/immutable/List.scala @@ -12,7 +12,8 @@ package scalax.collection.immutable import mutable.ListBuffer -import generic.covariant.{SequenceTemplate, SequenceFactory} +import generic.{SequenceTemplate, SequenceFactory, EmptyIterableFactory, Builder} +import annotation.unchecked.uncheckedVariance /** A class representing an ordered collection of elements of type * <code>a</code>. This class comes with two implementing case @@ -23,7 +24,9 @@ import generic.covariant.{SequenceTemplate, SequenceFactory} * @author Martin Odersky and others * @version 2.8 */ -sealed abstract class List[+A] extends Stream[A] with SequenceTemplate[List, A] with Product { +sealed abstract class List[+A] extends Stream[A] + with SequenceTemplate[List, A @uncheckedVariance] + with Product { import collection.{Iterable, OrderedIterable, Sequence, Vector} @@ -572,7 +575,7 @@ final case class ::[B](private var hd: B, private[scalax] var tl: List[B]) exten * @author Martin Odersky and others * @version 1.0, 15/07/2003 */ -object List extends SequenceFactory[List] { +object List extends SequenceFactory[List] with EmptyIterableFactory[List] { override val empty: List[Nothing] = Nil @@ -721,7 +724,7 @@ object List extends SequenceFactory[List] { * in the same order * @deprecated use `array.toList` instead */ - def fromArray[A](arr: Array[A]): List[A] = fromArray(arr, 0, arr.length) + @deprecated def fromArray[A](arr: Array[A]): List[A] = fromArray(arr, 0, arr.length) /** Converts a range of an array into a list. * diff --git a/src/library/scalax/collection/immutable/Map.scala b/src/library/scalax/collection/immutable/Map.scala new file mode 100755 index 0000000000..923866fb8e --- /dev/null +++ b/src/library/scalax/collection/immutable/Map.scala @@ -0,0 +1,66 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Set.scala 16893 2009-01-13 13:09:22Z cunei $ + + +package scalax.collection.immutable + +import generic._ + +object Map extends MapFactory[Map] { + private val hashSeed = "Map".hashCode + def empty[A, B]: Map[A, B] = new EmptyMap[A, B] +} + +trait Map[A, B] extends MapTemplate[A, B, Map] with collection.Map[A, B] { self => + + def empty[B]: Map[A, B] = new EmptyMap[A, B] + + /** The same map with a given default function */ + def withDefault(d: A => B): Map[A, B] = new Map[A, B] { + def size = self.size + def get(key: A) = self.get(key) + def elements = self.elements + override def empty[C] = self.empty + def update (key: A, value: B): Map[A, B] = + self update (key, value) withDefault d + def - (key: A): Map[A, B] = + self - key withDefault d + override def default(key: A): B = d(key) + } + + /** The same map with a given default value */ + def withDefaultValue(d: B): Map[A, B] = withDefault(x => d) + + /** Compares this set with another object and returns true, iff the + * other object is also a set which contains the same elements as + * this set. + * + * @param that the other object + * @note not necessarily run-time type safe. + * @return <code>true</code> iff this set and the other set + * contain the same elements. + */ + override def equals(that: Any): Boolean = that match { + case other: Map[a, b] => + this.size == other.size && this.forall { + case (key, value) => other.get(key.asInstanceOf[a]) match { + case None => false + case Some(otherval) => value == otherval + } + } + case _ => false + } + + /** A hash method compatible with <code>equals</code> + */ + override def hashCode() = + (Map.hashSeed /: this) (_ * 41 + _.hashCode) + +} diff --git a/src/library/scalax/collection/immutable/Map1.scala b/src/library/scalax/collection/immutable/Map1.scala new file mode 100755 index 0000000000..f518c7cf17 --- /dev/null +++ b/src/library/scalax/collection/immutable/Map1.scala @@ -0,0 +1,39 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Map1.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +/** This class implements immutable maps with exactly one entry + * + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class Map1[A, B](key1: A, value1: B) extends Map[A, B] { + + def size = 1 + + def get(key: A): Option[B] = + if (key == key1) Some(value1) else None + + def elements = Iterator((key1, value1)) + + def update (key: A, value: B): Map[A, B] = + if (key == key1) new Map1(key1, value) + else null // new Map2(key1, value1, key, value) + + def - (key: A): Map[A, B] = + if (key == key1) empty else this +} + + + diff --git a/src/library/scalax/collection/immutable/Map2.scala b/src/library/scalax/collection/immutable/Map2.scala new file mode 100644 index 0000000000..f3f55c5828 --- /dev/null +++ b/src/library/scalax/collection/immutable/Map2.scala @@ -0,0 +1,44 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Map1.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +/** This class implements immutable maps with exactly one entry + * + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class Map2[A, B](key1: A, value1: B, key2: A, value2: B) extends Map[A, B] { + + def size = 2 + + def get(key: A): Option[B] = + if (key == key1) Some(value1) + else if (key == key2) Some(value2) + else None + + def elements = Iterator((key1, value1), (key2, value2)) + + def update (key: A, value: B): Map[A, B] = + if (key == key1) new Map2(key1, value, key2, value2) + else if (key == key2) new Map2(key1, value1, key2, value) + else new Map3(key1, value1, key2, value2, key, value) + + def - (key: A): Map[A, B] = + if (key == key1) new Map1(key2, value2) + else if (key == key2) new Map1(key1, value1) + else this +} + + + diff --git a/src/library/scalax/collection/immutable/Map3.scala b/src/library/scalax/collection/immutable/Map3.scala new file mode 100644 index 0000000000..3c8e6298cd --- /dev/null +++ b/src/library/scalax/collection/immutable/Map3.scala @@ -0,0 +1,47 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Map1.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +/** This class implements immutable maps with exactly one entry + * + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class Map3[A, B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B) extends Map[A, B] { + + def size = 3 + + def get(key: A): Option[B] = + if (key == key1) Some(value1) + else if (key == key2) Some(value2) + else if (key == key3) Some(value3) + else None + + def elements = Iterator((key1, value1), (key2, value2), (key3, value3)) + + def update (key: A, value: B): Map[A, B] = + if (key == key1) new Map3(key1, value, key2, value2, key3, value3) + else if (key == key2) new Map3(key1, value1, key2, value, key3, value3) + else if (key == key3) new Map3(key1, value1, key2, value2, key3, value) + else new Map4(key1, value1, key2, value2, key3, value3, key, value) + + def - (key: A): Map[A, B] = + if (key == key1) new Map2(key2, value2, key3, value3) + else if (key == key2) new Map2(key1, value1, key3, value3) + else if (key == key3) new Map2(key1, value1, key2, value2) + else this +} + + + diff --git a/src/library/scalax/collection/immutable/Map4.scala b/src/library/scalax/collection/immutable/Map4.scala new file mode 100644 index 0000000000..ad2dcd513b --- /dev/null +++ b/src/library/scalax/collection/immutable/Map4.scala @@ -0,0 +1,50 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Map1.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +/** This class implements immutable maps with exactly one entry + * + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class Map4[A, B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B, key4: A, value4: B) extends Map[A, B] { + + def size = 4 + + def get(key: A): Option[B] = + if (key == key1) Some(value1) + else if (key == key2) Some(value2) + else if (key == key3) Some(value3) + else if (key == key4) Some(value4) + else None + + def elements = Iterator((key1, value1), (key2, value2), (key3, value3), (key4, value4)) + + def update (key: A, value: B): Map[A, B] = + if (key == key1) new Map4(key1, value, key2, value2, key3, value3, key4, value4) + else if (key == key2) new Map4(key1, value1, key2, value, key3, value3, key4, value4) + else if (key == key3) new Map4(key1, value1, key2, value2, key3, value, key4, value4) + else if (key == key4) new Map4(key1, value1, key2, value2, key3, value3, key4, value) + else HashMap((key1, value1), (key2, value2), (key3, value3), (key4, value4), (key, value)) + + def - (key: A): Map[A, B] = + if (key == key1) new Map3(key2, value2, key3, value3, key4, value4) + else if (key == key2) new Map3(key1, value1, key3, value3, key4, value4) + else if (key == key3) new Map3(key1, value1, key2, value2, key4, value4) + else if (key == key4) new Map3(key1, value1, key2, value2, key3, value3) + else this +} + + + diff --git a/src/library/scalax/collection/immutable/OrderedIterable.scala b/src/library/scalax/collection/immutable/OrderedIterable.scala index 1c3fb67fb2..80fa418eec 100644 --- a/src/library/scalax/collection/immutable/OrderedIterable.scala +++ b/src/library/scalax/collection/immutable/OrderedIterable.scala @@ -1,6 +1,7 @@ package scalax.collection.immutable -import generic.covariant +import generic._ +import annotation.unchecked.uncheckedVariance /** Collection classes mixing in this class provide a method * <code>elements</code> which returns an iterator over all the @@ -13,11 +14,12 @@ import generic.covariant * @owner Martin Odersky * @version 2.8 */ -trait OrderedIterable[+A] extends Iterable[A] - with covariant.OrderedIterableTemplate[OrderedIterable, A] +trait OrderedIterable[+A] extends immutable.Iterable[A] + with OrderedIterableTemplate[OrderedIterable, A @uncheckedVariance] with collection.OrderedIterable[A] -object OrderedIterable extends covariant.IterableFactory[OrderedIterable] { +object OrderedIterable extends IterableFactory[OrderedIterable] + with EmptyIterableFactory[OrderedIterable] { val empty: OrderedIterable[Nothing] = Nil } diff --git a/src/library/scalax/collection/immutable/Sequence.scala b/src/library/scalax/collection/immutable/Sequence.scala index 10ae805106..78de3cbfaf 100644 --- a/src/library/scalax/collection/immutable/Sequence.scala +++ b/src/library/scalax/collection/immutable/Sequence.scala @@ -1,6 +1,7 @@ package scalax.collection.immutable -import generic.covariant +import generic._ +import annotation.unchecked.uncheckedVariance /** Collection classes mixing in this class provide a method * <code>elements</code> which returns an iterator over all the @@ -14,10 +15,10 @@ import generic.covariant * @version 2.8 */ trait Sequence[+A] extends OrderedIterable[A] - with covariant.SequenceTemplate[Sequence, A] + with SequenceTemplate[Sequence, A @uncheckedVariance] with collection.Sequence[A] -object Sequence extends covariant.SequenceFactory[Sequence] { +object Sequence extends SequenceFactory[Sequence] with EmptyIterableFactory[Sequence] { val empty: Sequence[Nothing] = Nil } diff --git a/src/library/scalax/collection/immutable/Set.scala b/src/library/scalax/collection/immutable/Set.scala index 5b39aaa3a4..9462cd3c5f 100755 --- a/src/library/scalax/collection/immutable/Set.scala +++ b/src/library/scalax/collection/immutable/Set.scala @@ -11,17 +11,19 @@ package scalax.collection.immutable -import collection.generic._ +import generic._ object Set extends generic.SetFactory[Set] { private val hashSeed = "Set".hashCode - def empty[A]: Set[A] = null // !!! + def empty[A]: Set[A] = new EmptySet[A] } trait Set[A] extends OrderedIterable[A] with collection.Set[A] with SetTemplate[Set, A] { + override def newBuilder[B]: Builder[Set, B] = Set.newBuilder[B] + /** Compares this set with another object and returns true, iff the * other object is also a set which contains the same elements as * this set. diff --git a/src/library/scalax/collection/immutable/Set1.scala b/src/library/scalax/collection/immutable/Set1.scala new file mode 100755 index 0000000000..276cd83bb0 --- /dev/null +++ b/src/library/scalax/collection/immutable/Set1.scala @@ -0,0 +1,46 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Set1.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +import collection.generic.Builder + +/** This class implements immutable sets with exactly one element. + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class Set1[A](elem1: A) extends Set[A] { + + def size: Int = 1 + + def contains(elem: A): Boolean = + elem == elem1 + + def + (elem: A): Set[A] = + if (contains(elem)) this + else new Set2(elem1, elem) + + def - (elem: A): Set[A] = + if (elem == elem1) new EmptySet[A] + else this + + def elements: Iterator[A] = + Iterator(elem1) + + override def foreach(f: A => Unit): Unit = { + f(elem1) + } +} + + + diff --git a/src/library/scalax/collection/immutable/Set2.scala b/src/library/scalax/collection/immutable/Set2.scala new file mode 100755 index 0000000000..828c52d053 --- /dev/null +++ b/src/library/scalax/collection/immutable/Set2.scala @@ -0,0 +1,47 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Set1.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +import collection.generic.Builder + +/** This class implements immutable sets with exactly one element. + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class Set2[A](elem1: A, elem2: A) extends Set[A] { + + def size: Int = 2 + + def contains(elem: A): Boolean = + elem == elem1 || elem == elem2 + + def + (elem: A): Set[A] = + if (contains(elem)) this + else new Set3(elem1, elem2, elem) + + def - (elem: A): Set[A] = + if (elem == elem1) new Set1(elem2) + else if (elem == elem2) new Set1(elem1) + else this + + def elements: Iterator[A] = + Iterator(elem1, elem2) + + override def foreach(f: A => Unit): Unit = { + f(elem1); f(elem2) + } +} + + + diff --git a/src/library/scalax/collection/immutable/Set3.scala b/src/library/scalax/collection/immutable/Set3.scala new file mode 100755 index 0000000000..f14253231f --- /dev/null +++ b/src/library/scalax/collection/immutable/Set3.scala @@ -0,0 +1,48 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Set1.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +import collection.generic.Builder + +/** This class implements immutable sets with exactly one element. + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class Set3[A](elem1: A, elem2: A, elem3: A) extends Set[A] { + + def size: Int = 3 + + def contains(elem: A): Boolean = + elem == elem1 || elem == elem2 || elem == elem3 + + def + (elem: A): Set[A] = + if (contains(elem)) this + else new Set4(elem1, elem2, elem3, elem) + + def - (elem: A): Set[A] = + if (elem == elem1) new Set2(elem2, elem3) + else if (elem == elem2) new Set2(elem1, elem3) + else if (elem == elem3) new Set2(elem1, elem2) + else this + + def elements: Iterator[A] = + Iterator(elem1, elem2, elem3) + + override def foreach(f: A => Unit): Unit = { + f(elem1); f(elem2); f(elem3) + } +} + + + diff --git a/src/library/scalax/collection/immutable/Set4.scala b/src/library/scalax/collection/immutable/Set4.scala new file mode 100755 index 0000000000..bef1b6588d --- /dev/null +++ b/src/library/scalax/collection/immutable/Set4.scala @@ -0,0 +1,49 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Set1.scala 16893 2009-01-13 13:09:22Z cunei $ + + + +package scalax.collection.immutable + +import collection.generic.Builder + +/** This class implements immutable sets with exactly one element. + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +@serializable +class Set4[A](elem1: A, elem2: A, elem3: A, elem4: A) extends Set[A] { + + def size: Int = 4 + + def contains(elem: A): Boolean = + elem == elem1 || elem == elem2 || elem == elem3 || elem == elem4 + + def + (elem: A): Set[A] = + if (contains(elem)) this + else new DefaultSet[A] + (elem1, elem2, elem3, elem4, elem) + + def - (elem: A): Set[A] = + if (elem == elem1) new Set3(elem2, elem3, elem4) + else if (elem == elem2) new Set3(elem1, elem3, elem4) + else if (elem == elem3) new Set3(elem1, elem2, elem4) + else if (elem == elem4) new Set3(elem1, elem2, elem3) + else this + + def elements: Iterator[A] = + Iterator(elem1, elem2, elem3, elem4) + + override def foreach(f: A => Unit): Unit = { + f(elem1); f(elem2); f(elem3); f(elem4) + } +} + + + diff --git a/src/library/scalax/collection/immutable/Stream.scala b/src/library/scalax/collection/immutable/Stream.scala index 3581ac5b5d..036fefe70c 100755 --- a/src/library/scalax/collection/immutable/Stream.scala +++ b/src/library/scalax/collection/immutable/Stream.scala @@ -12,7 +12,8 @@ package scalax.collection.immutable import mutable.ListBuffer -import generic.covariant.{SequenceTemplate, SequenceFactory} +import generic.{SequenceTemplate, SequenceFactory, EmptyIterableFactory, Builder, LazyBuilder} +import annotation.unchecked.uncheckedVariance /** * The object <code>Stream</code> provides helper functions @@ -21,7 +22,7 @@ import generic.covariant.{SequenceTemplate, SequenceFactory} * @author Martin Odersky, Matthias Zenger * @version 1.1 08/08/03 */ -object Stream extends SequenceFactory[Stream] { +object Stream extends SequenceFactory[Stream] with EmptyIterableFactory[Stream] { import collection.{Iterable, OrderedIterable, Sequence, Vector} @@ -417,7 +418,7 @@ import Stream._ * @version 1.1 08/08/03 */ abstract class Stream[+A] extends Sequence[A] - with SequenceTemplate[Stream, A] { + with SequenceTemplate[Stream, A @uncheckedVariance] { self => import collection.{Iterable, OrderedIterable, Sequence, Vector} diff --git a/src/library/scalax/collection/immutable/Vector.scala b/src/library/scalax/collection/immutable/Vector.scala index 3848304525..93e9601bd2 100644 --- a/src/library/scalax/collection/immutable/Vector.scala +++ b/src/library/scalax/collection/immutable/Vector.scala @@ -1,6 +1,7 @@ package scalax.collection.immutable -import generic.covariant +import generic._ +import annotation.unchecked.uncheckedVariance /** Collection classes mixing in this class provide a method * <code>elements</code> which returns an iterator over all the @@ -14,10 +15,10 @@ import generic.covariant * @version 2.8 */ trait Vector[+A] extends Sequence[A] - with covariant.VectorTemplate[Vector, A] + with VectorTemplate[Vector, A @uncheckedVariance] with collection.Vector[A] -object Vector extends covariant.SequenceFactory[Vector] { +object Vector extends SequenceFactory[Vector] with EmptyIterableFactory[Vector] { val empty: Vector[Nothing] = immutable.Vector.empty } diff --git a/src/library/scalax/collection/mutable/Array.scala b/src/library/scalax/collection/mutable/Array.scala index c2b4d19101..cf1e02008b 100755 --- a/src/library/scalax/collection/mutable/Array.scala +++ b/src/library/scalax/collection/mutable/Array.scala @@ -253,7 +253,7 @@ object Array extends SequenceFactory[Array] { * @author Martin Odersky * @version 1.0 */ -final class Array[A](_length: Int) extends Vector[A] with mutable.VectorTemplate[Array, A] { +final class Array[A](_length: Int) extends Vector[A] with MutableVectorTemplate[Array, A] { /** Multidimensional array creation * @deprecated use Array.ofDim instead diff --git a/src/library/scalax/collection/mutable/ArrayBuffer.scala b/src/library/scalax/collection/mutable/ArrayBuffer.scala index dbdb96e004..daf514c485 100644 --- a/src/library/scalax/collection/mutable/ArrayBuffer.scala +++ b/src/library/scalax/collection/mutable/ArrayBuffer.scala @@ -11,7 +11,7 @@ package scalax.collection.mutable -import generic.SequenceFactory +import generic.{SequenceFactory, MutableVectorTemplate, Builder} /* Factory object for `ArrayBuffer` class */ object ArrayBuffer extends SequenceFactory[ArrayBuffer] { @@ -31,7 +31,7 @@ object ArrayBuffer extends SequenceFactory[ArrayBuffer] { class ArrayBuffer[A](override protected val initialSize: Int) extends Buffer[A] with Vector[A] - with generic.mutable.VectorTemplate[ArrayBuffer, A] + with MutableVectorTemplate[ArrayBuffer, A] with Builder[ArrayBuffer, A] with ResizableArray[A] { diff --git a/src/library/scalax/collection/mutable/Buffer.scala b/src/library/scalax/collection/mutable/Buffer.scala index 502f99758a..3d0eaec84e 100644 --- a/src/library/scalax/collection/mutable/Buffer.scala +++ b/src/library/scalax/collection/mutable/Buffer.scala @@ -11,8 +11,7 @@ package scalax.collection.mutable -import generic.{SequenceFactory, SequenceTemplate} -import generic.mutable.{Growable, Shrinkable} +import generic._ /* Factory object for `Buffer` trait */ object Buffer extends SequenceFactory[Buffer] { @@ -29,12 +28,14 @@ object Buffer extends SequenceFactory[Buffer] { * @version 2.8 */ @cloneable -trait Buffer[A] extends mutable.Sequence[A] +trait Buffer[A] extends Sequence[A] with SequenceTemplate[Buffer, A] + with Addable[Buffer[A], A] + with Subtractable[Buffer[A], A] with Growable[A] with Shrinkable[A] // with Scriptable[Message[(Location, A)]] - with CloneableCollection + with Cloneable[Buffer[A]] { // Abstract methods from Vector: @@ -83,6 +84,10 @@ trait Buffer[A] extends mutable.Sequence[A] */ def +:(elem: A): this.type + /** Append a single element to this buffer and return the identity of the buffer + */ + def +(elem: A): this.type = { +=(elem); this } + /** Inserts new elements at the index <code>n</code>. Opposed to method * <code>update</code>, this method will not replace an element with a * one. Instead, it will insert a new element at index <code>n</code>. @@ -114,7 +119,7 @@ trait Buffer[A] extends mutable.Sequence[A] } /** Removes a single element from this buffer, at its first occurrence. - * If the list does not contain that element, it is unchanged + * If the buffer does not contain that element, it is unchanged. * * @param x the element to remove. */ @@ -123,6 +128,13 @@ trait Buffer[A] extends mutable.Sequence[A] if (i != -1) remove(i) } + /** Removes a single element from this buffer and returns the identity + * of the buffer. If the buffer does not contain that element, it is unchanged. + * + * @param x the element to remove. + */ + def -(elem: A): this.type = { -=(elem); this } + /** Prepend two ore more elements to this buffer and return * the identity of the buffer. * @param elem the element to prepend. @@ -235,12 +247,6 @@ trait Buffer[A] extends mutable.Sequence[A] } */ - /** Return a clone of this buffer. - * - * @return a buffer with the same elements. - */ - override def clone(): Buffer[A] = super.clone().asInstanceOf[Buffer[A]] - /** Defines the prefix of the string representation. */ override def stringPrefix: String = "Buffer" diff --git a/src/library/scalax/collection/mutable/CloneableCollection.scala b/src/library/scalax/collection/mutable/DefaultEntry.scala index 465995ac7e..2fb0f62226 100644 --- a/src/library/scalax/collection/mutable/CloneableCollection.scala +++ b/src/library/scalax/collection/mutable/DefaultEntry.scala @@ -6,14 +6,11 @@ ** |/ ** \* */ -// $Id: CloneableCollection.scala 12003 2007-06-13 12:14:15Z mihaylov $ +// $Id: DefaultEntry.scala 16893 2009-01-13 13:09:22Z cunei $ package scalax.collection.mutable -/** The J2ME version of the library defined this trait with a clone method - * to substitute for the lack of Object.clone there - */ -trait CloneableCollection { - override def clone(): AnyRef = super.clone() -} +@serializable +final class DefaultEntry[A, B](val key: A, var value: B) + extends HashEntry[A, DefaultEntry[A, B]] diff --git a/src/library/scalax/collection/mutable/DefaultMapModel.scala b/src/library/scalax/collection/mutable/DefaultMapModel.scala new file mode 100644 index 0000000000..fda7798e26 --- /dev/null +++ b/src/library/scalax/collection/mutable/DefaultMapModel.scala @@ -0,0 +1,44 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: DefaultMapModel.scala 16893 2009-01-13 13:09:22Z cunei $ + + +package scalax.collection.mutable + +/** This class is used internally. It implements the mutable <code>Map</code> + * class in terms of three functions: <code>findEntry</code>, + * <code>addEntry</code>, and <code>entries</code>. + * + * @author Matthias Zenger + * @version 1.0, 08/07/2003 + */ +trait DefaultMapModel[A, B] extends Map[A, B] { + + type Entry = DefaultEntry[A, B] + + protected def findEntry(key: A): Entry + protected def addEntry(e: Entry) + protected def entries: Iterator[Entry] + + def get(key: A): Option[B] = { + val e = findEntry(key) + if (e == null) None + else Some(e.value); + } + + def update(key: A, value: B): this.type = { + val e = findEntry(key) + if (e == null) addEntry(new Entry(key, value)) + else e.value = value + this + } + + def elements = entries map {e => (e.key, e.value)} +} + diff --git a/src/library/scalax/collection/mutable/FlatHashTable.scala b/src/library/scalax/collection/mutable/FlatHashTable.scala new file mode 100644 index 0000000000..c8fe2cede3 --- /dev/null +++ b/src/library/scalax/collection/mutable/FlatHashTable.scala @@ -0,0 +1,164 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: FlatHashTable.scala 16893 2009-01-13 13:09:22Z cunei $ + +package scalax.collection.mutable + +trait FlatHashTable[A] { + + /** The load factor for the hash table; must be < 500 (0.5) + */ + protected def loadFactor: Int = 450 + protected final def loadFactorDenum = 1000 + + /** The initial size of the hash table. + */ + protected def initialSize: Int = 16 + + private final val tableDebug = false + + /** The actual hash table. + */ + protected var table: scala.Array[AnyRef] = + if (initialSize == 0) null else new scala.Array(initialSize) + + /** The number of mappings contained in this hash table. + */ + protected var tableSize = 0 + + /** The next size value at which to resize (capacity * load factor). + */ + protected var threshold: Int = newThreshold(initialSize) + + /** Returns the number of entires in this hash table. + */ + def size: Int = tableSize + + def findEntry(elem: A): Option[A] = { + var h = index(elemHashCode(elem)) + var entry = table(h) + while (null != entry && entry != elem) { + h = (h + 1) % table.length + entry = table(h) + } + if (null == entry) None else Some(entry.asInstanceOf[A]) + } + + def containsEntry(elem: A): Boolean = { + var h = index(elemHashCode(elem)) + var entry = table(h) + while (null != entry && entry != elem) { + h = (h + 1) % table.length + entry = table(h) + } + null != entry + } + + def addEntry(elem: A) : Boolean = { + var h = index(elemHashCode(elem)) + var entry = table(h) + while (null != entry) { + if (entry == elem) return false + h = (h + 1) % table.length + entry = table(h) + } + table(h) = elem.asInstanceOf[AnyRef] + tableSize = tableSize + 1 + if (tableSize >= threshold) growTable() + true + } + + def removeEntry(elem: A) : Option[A] = { + if (tableDebug) checkConsistent() + def precedes(i: Int, j: Int) = { + val d = table.length >> 1 + if (i <= j) j - i < d + else i - j > d + } + var h = index(elemHashCode(elem)) + var entry = table(h) + while (null != entry) { + if (entry == elem) { + var h0 = h + var h1 = (h0 + 1) % table.length + while (null != table(h1)) { + val h2 = index(elemHashCode(table(h1).asInstanceOf[A])) + //Console.println("shift at "+h1+":"+table(h1)+" with h2 = "+h2+"? "+(h2 != h1)+precedes(h2, h0)+table.length) + if (h2 != h1 && precedes(h2, h0)) { + //Console.println("shift "+h1+" to "+h0+"!") + table(h0) = table(h1) + h0 = h1 + } + h1 = (h1 + 1) % table.length + } + table(h0) = null + tableSize -= 1 + if (tableDebug) checkConsistent() + return Some(entry.asInstanceOf[A]) + } + h = (h + 1) % table.length + entry = table(h) + } + None + } + + def elements = new Iterator[A] { + private var i = 0 + def hasNext: Boolean = { + while (i < table.length && (null == table(i))) i += 1; + i < table.length + } + def next(): A = + if (hasNext) { i += 1; table(i - 1).asInstanceOf[A] } + else Iterator.empty.next + } + + private def growTable() { + val oldtable = table + table = new scala.Array[AnyRef](table.length * 2) + tableSize = 0 + threshold = newThreshold(table.length) + var i = 0 + while (i < oldtable.length) { + val entry = oldtable(i) + if (null != entry) addEntry(entry.asInstanceOf[A]) + i += 1 + } + if (tableDebug) checkConsistent() + } + + private def checkConsistent() { + for (i <- 0 until table.length) + if (table(i) != null && !containsEntry(table(i).asInstanceOf[A])) + assert(false, i+" "+table(i)+" "+table.toString) + } + + protected def elemHashCode(elem: A) = elem.hashCode() + + protected final def improve(hcode: Int) = { + var h: Int = hcode + ~(hcode << 9) + h = h ^ (h >>> 14) + h = h + (h << 4) + h ^ (h >>> 10) + } + + protected final def index(hcode: Int) = improve(hcode) & (table.length - 1) + + private def newThreshold(size: Int) = { + val lf = loadFactor + assert(lf < (loadFactorDenum / 2), "loadFactor too large; must be < 0.5") + (size.toLong * lf / loadFactorDenum ).toInt + } + + protected def clear() { + var i = table.length - 1 + while (i >= 0) { table(i) = null; i -= 1 } + tableSize = 0 + } +} diff --git a/src/library/scalax/collection/mutable/HashMap.scala b/src/library/scalax/collection/mutable/HashMap.scala new file mode 100644 index 0000000000..4d3342636c --- /dev/null +++ b/src/library/scalax/collection/mutable/HashMap.scala @@ -0,0 +1,43 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashMap.scala 16893 2009-01-13 13:09:22Z cunei $ + + +package scalax.collection.mutable + +import generic._ + +/** This class implements mutable maps using a hashtable. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.8 + */ +object HashMap extends MapFactory[HashMap] { + + /** The empty map of this type */ + def empty[A, B] = new HashMap[A, B] + +} + +@serializable +class HashMap[A, B] + extends Map[A, B] + with MapTemplate[A, B, HashMap] + with HashTable[A] + with DefaultMapModel[A, B] { + + def empty[B] = HashMap.empty[A, B] + + def -= (key: A) { removeEntry(key) } + + override def clear() = super.clear() + + override def clone(): Map[A, B] = new HashMap[A, B] ++ this +} diff --git a/src/library/scalax/collection/mutable/HashSet.scala b/src/library/scalax/collection/mutable/HashSet.scala new file mode 100644 index 0000000000..601d0885c0 --- /dev/null +++ b/src/library/scalax/collection/mutable/HashSet.scala @@ -0,0 +1,48 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashSet.scala 16893 2009-01-13 13:09:22Z cunei $ + + +package scalax.collection.mutable + +import generic.{SetTemplate, SetFactory, AddableBuilder} + +/** Factory object for `HashSet` class */ +object HashSet extends SetFactory[HashSet] { + /** The empty set of this type */ + def empty[A] = new HashSet[A] +} + +/** This class implements mutable sets using a hashtable. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.0, 31/12/2006 + */ +@serializable +class HashSet[A] + extends Set[A] + with SetTemplate[HashSet, A] + with FlatHashTable[A] { + + def contains(elem: A): Boolean = containsEntry(elem) + + def +=(elem: A) { addEntry(elem) } + + def -=(elem: A) { removeEntry(elem) } + + override def clear() = super.clear() + + override def newBuilder[B]: generic.Builder[HashSet, B] = + new AddableBuilder[HashSet, B](HashSet.empty) + + override def clone(): HashSet[A] = new HashSet[A] ++ this +} + + diff --git a/src/library/scalax/collection/mutable/HashTable.scala b/src/library/scalax/collection/mutable/HashTable.scala new file mode 100644 index 0000000000..73ff61f3df --- /dev/null +++ b/src/library/scalax/collection/mutable/HashTable.scala @@ -0,0 +1,172 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://www.scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashTable.scala 16884 2009-01-09 16:52:09Z cunei $ + + +package scalax.collection.mutable + +/** This class can be used to construct data structures that are based + * on hashtables. Class <code>HashTable[A]</code> implements a hashtable + * that maps keys of type <code>A</code> to values of the fully abstract + * member type <code>Entry</code>. Classes that make use of <code>HashTable</code> + * have to provide an implementation for <code>Entry</code> + * + * There are mainly two parameters that affect the performance of a hashtable: + * the <i>initial size</i> and the <i>load factor</i>. The <i>size</i> + * refers to the number of <i>buckets</i> in the hashtable, and the <i>load + * factor</i> is a measure of how full the hashtable is allowed to get before + * its size is automatically doubled. Both parameters may be changed by + * overriding the corresponding values in class <code>HashTable</code>. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.0, 31/12/2006 + */ +trait HashTable[A] extends AnyRef { + + protected type Entry >: Null <: HashEntry[A, Entry] + + /** The load factor for the hash table (in 0.001 step). + */ + protected def loadFactor: Int = 750 // corresponds to 75% + protected final val loadFactorDenum = 1000; + + /** The initial size of the hash table. + */ + protected def initialSize: Int = 16 + + /** The initial threshold + */ + protected def initialThreshold: Int = newThreshold(initialSize) + + /** The actual hash table. + */ + protected var table: scala.Array[HashEntry[A, Entry]] = + if (initialSize == 0) null else new scala.Array(initialSize) + + /** The number of mappings contained in this hash table. + */ + protected var tableSize: Int = 0 + + /** The next size value at which to resize (capacity * load factor). + */ + protected var threshold: Int = initialThreshold + + /** Returns the size of this hash table. + */ + def size = tableSize + + protected def findEntry(key: A): Entry = { + val h = index(elemHashCode(key)) + var e = table(h).asInstanceOf[Entry] + while (e != null && !elemEquals(e.key, key)) e = e.next + e + } + + protected def addEntry(e: Entry) { + val h = index(elemHashCode(e.key)) + e.next = table(h).asInstanceOf[Entry] + table(h) = e + tableSize = tableSize + 1 + if (tableSize > threshold) + resize(2 * table.length) + } + + protected def removeEntry(key: A) : Option[Entry] = { + val h = index(elemHashCode(key)) + var e = table(h).asInstanceOf[Entry] + if (e != null) { + if (elemEquals(e.key, key)) { + table(h) = e.next + tableSize = tableSize - 1 + return Some(e) + } else { + var e1 = e.next + while (e1 != null && !elemEquals(e1.key, key)) { + e = e1 + e1 = e1.next + } + if (e1 != null) { + e.next = e1.next + tableSize = tableSize - 1 + return Some(e1) + } + } + } + None + } + + protected def entries: Iterator[Entry] = new Iterator[Entry] { + val iterTable = table + var idx = table.length - 1 + var es = iterTable(idx).asInstanceOf[Entry] + scan() + def hasNext = es != null + def next = { + val res = es + es = es.next + scan() + res + } + def scan() { + while (es == null && idx > 0) { + idx = idx - 1 + es = iterTable(idx).asInstanceOf[Entry] + } + } + } + + def clear() { + var i = table.length - 1 + while (i >= 0) { table(i) = null; i = i - 1 } + tableSize = 0 + } + + private def newThreshold(size: Int) = + ((size.toLong * loadFactor)/loadFactorDenum).toInt + + private def resize(newSize: Int) = { + val oldTable = table + table = new scala.Array(newSize) + var i = oldTable.length - 1 + while (i >= 0) { + var e = oldTable(i) + while (e != null) { + val h = index(elemHashCode(e.key)) + val e1 = e.next + e.next = table(h).asInstanceOf[Entry] + table(h) = e + e = e1 + } + i = i - 1 + } + threshold = newThreshold(newSize) + } + + protected def elemEquals(key1: A, key2: A): Boolean = (key1 == key2) + + protected def elemHashCode(key: A) = key.hashCode() + + protected final def improve(hcode: Int) = { + var h: Int = hcode + ~(hcode << 9) + h = h ^ (h >>> 14) + h = h + (h << 4) + h ^ (h >>> 10) + } + + protected final def index(hcode: Int) = improve(hcode) & (table.length - 1) +} + +trait HashEntry[A, E] { + val key: A + var next: E = _ +} + + + diff --git a/src/library/scalax/collection/mutable/ListBuffer.scala b/src/library/scalax/collection/mutable/ListBuffer.scala index dff29f6453..4d0ad7ec80 100644 --- a/src/library/scalax/collection/mutable/ListBuffer.scala +++ b/src/library/scalax/collection/mutable/ListBuffer.scala @@ -11,7 +11,7 @@ package scalax.collection.mutable -import generic.{SequenceForwarder, SequenceFactory, SequenceTemplate} +import generic._ import immutable.List import collection.immutable.{List, Nil, ::} @@ -31,6 +31,8 @@ object ListBuffer extends SequenceFactory[ListBuffer] { final class ListBuffer[A] extends Buffer[A] with SequenceTemplate[ListBuffer, A] + with Addable[ListBuffer[A], A] + with Subtractable[ListBuffer[A], A] with Builder[List, A] with SequenceForwarder[A] { diff --git a/src/library/scalax/collection/mutable/Map.scala b/src/library/scalax/collection/mutable/Map.scala new file mode 100755 index 0000000000..43f42df298 --- /dev/null +++ b/src/library/scalax/collection/mutable/Map.scala @@ -0,0 +1,75 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Map.scala 16884 2009-01-09 16:52:09Z cunei $ + + +package scalax.collection.mutable + +import generic._ + +/* Factory object for `Map` class */ +object Map extends MapFactory[Map] { + def empty[A, B]: Map[A, B] = new HashMap[A, B] +} + +trait Map[A, B] + extends collection.Map[A, B] + with MapTemplate[A, B, Map] + with Growable[(A, B)] + with Shrinkable[A] + with Cloneable[Map[A, B]] { +self => + + override def thisCC: Map[A, B] = this + + /** This method allows one to add a new mapping from <code>key</code> + * to <code>value</code> to the map. If the map already contains a + * mapping for <code>key</code>, it will be overridden by this + * function. + * + * @param key The key to update + * @param value The new value + */ + def update(key: A, value: B): this.type + + /** Add a key/value pair to this map. + * @param kv the key/value pair. + */ + def += (kv: (A, B)) { update(kv._1, kv._2) } + + /** Remove a key from this map, noop if key is not present. + * @param key the key to be removed + */ + def -= (key: A) + + def -(key: A): this.type = { -=(key); this } + + /** Removes all elements from the set for + * which the predicate <code>p</code> yields the value <code>false</code>. + */ + def retain(p: A => Boolean): Unit = for ((k, v) <- this) if (!p(k)) -=(k) + + /** Removes all elements from the set. After this operation is completed, + * the set will be empty. + */ + def clear() { for ((k, v) <- elements) -=(k) } + + override def clone(): Map[A, B] = empty[B] ++ this + + /** Return a read-only projection of this set !!! just us an (immutable) setProxy? */ + def readOnly : collection.Map[A, B] = new collection.Map[A, B] { + override def size = self.size + override def update(key: A, value: B) = self.update(key, value) + override def - (elem: A) = self - elem + override def elements = self.elements + override def foreach(f: ((A, B)) => Unit) = self.foreach(f) + override def empty[C] = self.empty[C] + def get(key: A) = self.get(key) + } +} diff --git a/src/library/scalax/collection/mutable/Set.scala b/src/library/scalax/collection/mutable/Set.scala index 40dc643012..78f3234336 100644 --- a/src/library/scalax/collection/mutable/Set.scala +++ b/src/library/scalax/collection/mutable/Set.scala @@ -12,14 +12,13 @@ package scalax.collection.mutable import collection.generic._ -import collection.generic.mutable.{Growable, Shrinkable} /** The canonical factory methods for <a href="Set.html">mutable sets</a>. * Currently these return <a href="HashSet.html">HashSet's</a>. */ object Set extends generic.SetFactory[Set] { /** The empty map of this type; this is implemented as a hashtable */ - def empty[A]: Set[A] = null // !!! new HashSet[A] + def empty[A]: Set[A] = new HashSet[A] } /** This class represents mutable sets. Concrete set implementations @@ -32,13 +31,13 @@ object Set extends generic.SetFactory[Set] { * @author Martin Odersky * @version 2.8 */ -@cloneable -trait Set[A] extends OrderedIterable[A] - with collection.Set[A] +trait Set[A] extends collection.Set[A] with SetTemplate[Set, A] + with Addable[Set[A], A] + with Subtractable[Set[A], A] with Growable[A] with Shrinkable[A] - with Cloneable[A] { + with Cloneable[Set[A]] { self => /** This method allows one to add or remove an element <code>elem</code> @@ -51,7 +50,7 @@ self => if (included) this += elem else this -= elem } - /** Add a new element to the set. + /** Adds a new element to the set. * * @param elem the element to be added */ @@ -62,18 +61,17 @@ self => */ def -=(elem: A) - // Bridge methods to methods in Growable/Shrinkable; - // we can't directly inherit these because they override nothing. - - override def - (elem: A): this.type = super.-(elem) - override def - (elem1: A, elem2: A, elems: A*): this.type = super.-(elem1, elem2, elems: _*) - override def -- (elems: collection.Iterable[A]): this.type = super.--(elems) - override def -- (elems: Iterator[A]): this.type = super.--(elems) + /** Adds a new element to the set and returns the set itself. + * + * @param elem the element to be added + */ + def +(elem: A): this.type = { +=(elem); this } - override def + (elem: A): this.type = super.+(elem) - override def + (elem1: A, elem2: A, elems: A*): this.type = super.+(elem1, elem2, elems: _*) - override def ++ (elems: collection.Iterable[A]): this.type = super.++(elems) - override def ++ (elems: Iterator[A]): this.type = super.++(elems) + /** Removed a new element from the set and returns the set itself. + * + * @param elem the element to be added + */ + def -(elem: A): this.type = { -=(elem); this } /** This method computes an intersection with set <code>that</code>. * It removes all the elements that are not present in <code>that</code>. @@ -90,14 +88,16 @@ self => /** Removes all elements from the set. After this operation is completed, * the set will be empty. */ - def clear() { elements foreach -= } + def clear() { foreach(-=) } + + override def clone(): Set[A] = { val b = newBuilder[A]; b ++= this; b.result } /** Send a message to this scriptable object. * * @param cmd the message to send. * @throws <code>Predef.UnsupportedOperationException</code> * if the message was not understood. - def <<(cmd: Message[A]): Unit = cmd match { + def <<(cmd: Message[A]): Unit = cmd match { case Include(elem) => this += elem case Remove(elem) => this -= elem case Reset() => clear diff --git a/src/library/scalax/collection/mutable/StringBuilder.scala b/src/library/scalax/collection/mutable/StringBuilder.scala index 3152182dc4..30aeba4aed 100755 --- a/src/library/scalax/collection/mutable/StringBuilder.scala +++ b/src/library/scalax/collection/mutable/StringBuilder.scala @@ -12,7 +12,6 @@ package scalax.collection.mutable import scalax.collection.generic._ -import scalax.collection.generic.mutable.Growable import scalax.runtime._ diff --git a/src/library/scalax/collection/mutable/Vector.scala b/src/library/scalax/collection/mutable/Vector.scala index aef1c75d94..1813172fbf 100644 --- a/src/library/scalax/collection/mutable/Vector.scala +++ b/src/library/scalax/collection/mutable/Vector.scala @@ -12,7 +12,7 @@ package scalax.collection.mutable import generic._ -trait Vector[A] extends Sequence[A] with collection.Vector[A] with generic.mutable.VectorTemplate[Vector, A] +trait Vector[A] extends Sequence[A] with collection.Vector[A] with MutableVectorTemplate[Vector, A] /* Factory object for `Vector` class */ object Vector extends SequenceFactory[Vector] { diff --git a/src/library/scalax/runtime/BoxedArray.scala b/src/library/scalax/runtime/BoxedArray.scala index 388d652882..47bb3a0d64 100755 --- a/src/library/scalax/runtime/BoxedArray.scala +++ b/src/library/scalax/runtime/BoxedArray.scala @@ -21,7 +21,7 @@ import collection.generic._ * @author Martin Odersky, Stephane Micheloud * @version 1.0 */ -abstract class BoxedArray[A] extends Vector[A] with mutable.VectorTemplate[BoxedArray, A] with Boxed { +abstract class BoxedArray[A] extends Vector[A] with MutableVectorTemplate[BoxedArray, A] with Boxed { /** The length of the array */ def length: Int diff --git a/src/library/scalax/runtime/StringVector.scala b/src/library/scalax/runtime/StringVector.scala index c12243bed7..a612b7d7a5 100644 --- a/src/library/scalax/runtime/StringVector.scala +++ b/src/library/scalax/runtime/StringVector.scala @@ -13,7 +13,8 @@ package scalax.runtime import collection.immutable.Vector import collection.mutable.ArrayBuffer -import collection.generic.covariant.VectorTemplate +import collection.generic.VectorTemplate +import annotation.unchecked.uncheckedVariance object StringVector { @@ -22,7 +23,7 @@ object StringVector { } @cloneable -abstract class StringVector[+A] extends VectorTemplate[StringVector, A] with Vector[A] { +abstract class StringVector[+A] extends VectorTemplate[StringVector, A @uncheckedVariance] with Vector[A] { /** The length of the string */ def length: Int |