diff options
Diffstat (limited to 'src/library')
53 files changed, 820 insertions, 425 deletions
diff --git a/src/library/scala/Array.scala b/src/library/scala/Array.scala index fad177d88c..0205d21a5c 100644 --- a/src/library/scala/Array.scala +++ b/src/library/scala/Array.scala @@ -187,7 +187,7 @@ object Array { * @author Martin Odersky * @version 1.0 */ -final class Array[A](_length: Int) extends Seq[A] { +final class Array[A](_length: Int) extends RandomAccessSeq[A] { /** The length of the array */ def length: Int = throw new Error() @@ -229,7 +229,7 @@ final class Array[A](_length: Int) extends Seq[A] { /** An iterator returning the elements of this array, starting from 0. */ - def elements: Iterator[A] = throw new Error() + override def elements: Iterator[A] = throw new Error() /** @deprecated use slice instead */ def subArray(from: Int, end: Int): Array[A] = throw new Error() diff --git a/src/library/scala/BufferedIterator.scala b/src/library/scala/BufferedIterator.scala index 38d81eb513..c0479f4eba 100644 --- a/src/library/scala/BufferedIterator.scala +++ b/src/library/scala/BufferedIterator.scala @@ -18,12 +18,60 @@ package scala * @version 1.0, 16/07/2003 */ trait BufferedIterator[+A] extends Iterator[A] { + /** returns the first <code>sz</code> elements that will be iterated by this iterator, + * or fewer if the iterator has less elements left to iterate over + */ + def peekList(sz : Int) : Seq[A] /** Checks what the next available element is. * * @return the current element */ - def head: A + def head: A = peek(0) + /** return the <code>n</code>th element that will be iterated by this iterator */ + def peek(n : Int) : A = { + var m = n + val lst = peekList(n + 1) + if (m == 0 && !lst.isEmpty) return lst(0) + for (a <- lst) { + if (m == 0) return a + m = m - 1 + } + return defaultPeek + } + /** element returned when no element left to iterate over; + * throws <code>NoSuchElementException</code> by default + */ + protected def defaultPeek : A = throw new Predef.NoSuchElementException + + /** iterates over and applies <code>f</code> to the next element + * if this iterator has a next element that <code>f</code> is defined for. + */ + def readIf[T](f : PartialFunction[A,T]) : Option[T] = + if (hasNext && f.isDefinedAt(head)) Some(f(next)) + else None + /** iterates over elements as long as <code>f</code> is true + * for each element, returns the elements iterated over + */ + def readWhile(f : A => Boolean) : Seq[A] = { + import scala.collection.mutable.ArrayBuffer + var read = new ArrayBuffer[A] + while (hasNext && f(head)) + read += next + read + } + /** true if elements of <code>seq</code> will be iterated over next in this iterator + */ + def startsWith(seq : Seq[Any]) : Boolean = { + var sz = seq.length + val j = peekList(sz).elements + val i = seq.elements + while (i.hasNext && j.hasNext) + if (i.next != j.next) return false + return !i.hasNext && !j.hasNext + } override def buffered: BufferedIterator[A] = this + override def hasNext = !peekList(1).isEmpty + override def toString = if (hasNext) "peek " + peekList(1).reverse else "empty" } diff --git a/src/library/scala/Collection.scala b/src/library/scala/Collection.scala index f187e88d23..530af51e9c 100644 --- a/src/library/scala/Collection.scala +++ b/src/library/scala/Collection.scala @@ -45,5 +45,11 @@ trait Collection[+A] extends Iterable[A] { if (idx2 != -1) string = string.substring(0, idx2) string } - + def equalWith[B](that : Collection[B], f : (A,B) => Boolean) : Boolean = { + if (size != that.size) return false + val i = elements + val j = that.elements + while (i.hasNext) if (!f(i.next, j.next)) return false + return true + } } diff --git a/src/library/scala/CountedIterator.scala b/src/library/scala/CountedIterator.scala index 9293197f9a..56850dd97a 100644 --- a/src/library/scala/CountedIterator.scala +++ b/src/library/scala/CountedIterator.scala @@ -17,9 +17,7 @@ package scala * @version 1.0, 16/07/2003 */ trait CountedIterator[+A] extends Iterator[A] { - /** counts the elements in this iterator; counts start at 0 */ def count: Int - } diff --git a/src/library/scala/DefaultBufferedIterator.scala b/src/library/scala/DefaultBufferedIterator.scala new file mode 100644 index 0000000000..6608230beb --- /dev/null +++ b/src/library/scala/DefaultBufferedIterator.scala @@ -0,0 +1,61 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala +import Predef._ +import collection.mutable.{Buffer, ListBuffer} + +abstract class DefaultBufferedIterator[+A] extends BufferedIterator[A] { + private[this] var lookahead : List[A] = Nil + + protected[this] def putBack(a : Any) : Unit = lookahead = a.asInstanceOf[A] :: lookahead + + override protected def defaultPeek : A = throw new NoSuchElementException + override def hasNext = !lookahead.isEmpty || super.hasNext + + /** used to fill lookahead buffer */ + protected def fill : Seq[A] + + override def peekList(sz : Int) : Seq[A] = { + if (sz == 0) return lookahead + else if (sz == 1) { + if (!lookahead.isEmpty) return lookahead + val next = fill + lookahead = next.toList + return lookahead + } + var sz0 = sz + var hd = lookahead + while (sz0 > 0) { + if (hd.isEmpty) { // add n elements + import scala.collection.mutable.ArrayBuffer + val buf0 = new ArrayBuffer[A] + while (sz0 > 0 && { + val next = fill + if (next.isEmpty) false + else { + buf0 ++= next + sz0 = sz0 - next.length + true + } + }) {} + lookahead = lookahead ::: buf0.toList + return lookahead + } + sz0 = sz0 - 1 + hd = hd.tail + } + lookahead + } + override def next : A = { + val lst = peekList(1) + if (lst.isEmpty) throw new NoSuchElementException + lookahead = lookahead.tail + lst(0) + } +} diff --git a/src/library/scala/Iterable.scala b/src/library/scala/Iterable.scala index 48bbf9eb9c..00f72e3529 100644 --- a/src/library/scala/Iterable.scala +++ b/src/library/scala/Iterable.scala @@ -69,6 +69,24 @@ object Iterable { val empty = new Iterable[Nothing] { def elements = Iterator.empty } + /** A non-strict projection of an iterable. + * @author Sean McDirmid + */ + trait Projection[+A] extends Iterable[A] { + override def projection = this + /** non-strict */ + override def filter(p : A => Boolean) : Projection[A] = new Projection[A] { + def elements = Projection.this.elements.filter(p) + } + /** non-strict */ + override def map[B](f: A => B) : Projection[B] = new Projection[B] { + def elements = Projection.this.elements.map(f) + } + /** non-strict */ + override def flatMap[B](f: A => Iterable[B]) : Projection[B] = new Projection[B] { + def elements = Projection.this.elements.flatMap(a => f(a).elements) + } + } } @@ -120,7 +138,7 @@ trait Iterable[+A] { * @return <code>f(a<sub>0</sub>), ..., f(a<sub>n</sub>)</code> * if this iterable is <code>a<sub>0</sub>, ..., an</code>. */ - def map[B](f: A => B): Collection[B] = { + def map[B](f: A => B): Iterable[B] = { val buf = new ArrayBuffer[B] val elems = elements while (elems.hasNext) buf += f(elems.next) @@ -135,7 +153,7 @@ trait Iterable[+A] { * @return <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if * this iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. */ - def flatMap[B](f: A => Iterable[B]): Collection[B] = { + def flatMap[B](f: A => Iterable[B]): Iterable[B] = { val buf = new ArrayBuffer[B] val elems = elements while (elems.hasNext) f(elems.next) copyToBuffer buf @@ -149,7 +167,7 @@ trait Iterable[+A] { * @param p the predicate used to filter the list. * @return the elements of this list satisfying <code>p</code>. */ - def filter(p: A => Boolean): Collection[A] = { + def filter(p: A => Boolean): Iterable[A] = { val buf = new ArrayBuffer[A] val elems = elements while (elems.hasNext) { val x = elems.next; if (p(x)) buf += x } @@ -428,53 +446,14 @@ trait Iterable[+A] { /** Is this collection empty? */ def isEmpty = elements.hasNext - private class ProjectionImpl[+B](elements0 : () => Iterator[B]) extends Iterable[B] { - def elements = elements0(); - } - - trait Projection { - /** Returns all the elements of this iterable that satisfy the - * predicate <code>p</code>. The order of the elements is preserved. - * Unlike <code>filter</code> in <code>Iterable</code>, this API is - * not strict and will terminate on infinite-sized collections. - * - * @param p the predicate used to filter the list. - * @return the elements of this list satisfying <code>p</code>. - */ - def filter(p : A => Boolean) : Iterable[A] = new ProjectionImpl[A](() => { - Iterable.this.elements.filter(p) - }) - /** Returns the iterable resulting from applying the given function - * <code>f</code> to each element of this iterable. Unlike <code>map</code> - * in <code>Iterable</code>, this API is not strict and will terminate on - * infinite-sized collections. - * - * @param f function to apply to each element. - * @return <code>f(a<sub>0</sub>), ..., f(a<sub>n</sub>)</code> - * if this iterable is <code>a<sub>0</sub>, ..., an</code>. - */ - def map[B](f: A => B) : Iterable[B] = new ProjectionImpl[B](() => { - Iterable.this.elements.map(f) - }) - /** Applies the given function <code>f</code> to each element of - * this iterable, then concatenates the results. Unlike <code>flatMap</code> - * in <code>Iterable</code>, - * this API is not strict and will terminate on infinite-sized collections. - * - * @param f the function to apply on each element. - * @return <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if - * this iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. - */ - def flatMap[B](f: A => Iterable[B]) : Iterable[B] = new ProjectionImpl[B](() => { - Iterable.this.elements.flatMap(a => f(a).elements) - }) - } /** - * returns a facade that can be used to call non-strict <code>filter</code>, + * returns a projection that can be used to call non-strict <code>filter</code>, * <code>map</code>, and <code>flatMap</code> methods that build projections * of the collection. */ - def projection : Projection = new Projection {}; + def projection : Iterable.Projection[A] = new Iterable.Projection[A] { + def elements = Iterable.this.elements + } /** returns true iff this collection has a bound size. * Only true if this iterable is a <code>Collection</code>. @@ -482,4 +461,5 @@ trait Iterable[+A] { * unbound sizes. */ final def hasDefiniteSize = this.isInstanceOf[Collection[Nothing]] + } diff --git a/src/library/scala/IterableProxy.scala b/src/library/scala/IterableProxy.scala index c28fa1e8a0..3a24d4fb51 100644 --- a/src/library/scala/IterableProxy.scala +++ b/src/library/scala/IterableProxy.scala @@ -28,9 +28,9 @@ trait IterableProxy[+A] extends Iterable[A] with Proxy { override def elements: Iterator[A] = self.elements @deprecated override def concat [B >: A](that: Iterable[B]): Collection[B] = self concat that - override def map[B](f: A => B): Collection[B] = self map f - override def flatMap[B](f: A => Iterable[B]): Collection[B] = self flatMap f - override def filter(p: A => Boolean): Collection[A] = self filter p + override def map[B](f: A => B): Iterable[B] = self map f + override def flatMap[B](f: A => Iterable[B]): Iterable[B] = self flatMap f + override def filter(p: A => Boolean): Iterable[A] = self filter p override def takeWhile(p: A => Boolean): Collection[A] = self takeWhile p override def dropWhile(p: A => Boolean): Collection[A] = self dropWhile p override def take(n: Int): Collection[A] = self take n diff --git a/src/library/scala/Iterator.scala b/src/library/scala/Iterator.scala index b4936d1a76..fd8992fb1d 100644 --- a/src/library/scala/Iterator.scala +++ b/src/library/scala/Iterator.scala @@ -60,13 +60,14 @@ object Iterator { new BufferedIterator[a] { private var i = start val end = if ((start + length) < xs.length) start else xs.length - def hasNext: Boolean = i < end - def next(): a = + override def hasNext: Boolean = i < end + def next: a = if (hasNext) { val x = xs(i) ; i += 1 ; x } else throw new NoSuchElementException("next on empty iterator") - def head: a = - if (hasNext) xs(i) - else throw new NoSuchElementException("head on empty iterator") + + override protected def defaultPeek : a = throw new NoSuchElementException("no lookahead") + override def peekList(sz : Int) : Seq[a] = + xs.slice(i, if (i + sz > xs.length) xs.length else i + sz) } /** @@ -77,9 +78,12 @@ object Iterator { new BufferedIterator[Char] { private var i = 0 private val len = str.length() - def hasNext = i < len - def next() = { val c = str charAt i; i += 1; c } - def head = str charAt i + override def hasNext = i < len + def next = { val c = str charAt i; i += 1; c } + + override protected def defaultPeek : Char = throw new NoSuchElementException + override def peekList(sz : Int) : Seq[Char] = + str.substring(i, if (i + sz > str.length) str.length else i + sz) } /** @@ -134,16 +138,13 @@ object Iterator { * @return the iterator with values in range <code>[start;end)</code>. */ def range(start: Int, end: Int, step: Int => Int): Iterator[Int] = - new BufferedIterator[Int] { + new Iterator[Int] { private var i = start def hasNext: Boolean = i < end def next(): Int = if (i < end) { val j = i; i = step(i); j } else throw new NoSuchElementException("next on empty iterator") - def head: Int = - if (i < end) i - else throw new NoSuchElementException("head on empty iterator") - } + } /** Create an iterator with elements * <code>e<sub>n+1</sub> = e<sub>n</sub> + 1</code> @@ -152,8 +153,7 @@ object Iterator { * @param start the start value of the iterator * @return the iterator starting at value <code>start</code>. */ - def from(start: Int): Iterator[Int] = - from(start, 1) + def from(start: Int): Iterator[Int] = from(start, 1) /** Create an iterator with elements * <code>e<sub>n+1</sub> = e<sub>n</sub> + step</code> @@ -163,13 +163,7 @@ object Iterator { * @param step the increment value of the iterator * @return the iterator starting at value <code>start</code>. */ - def from(start: Int, step: Int): Iterator[Int] = - new BufferedIterator[Int] { - private var i = start - def hasNext: Boolean = true - def next(): Int = { val j = i; i += step; j } - def head: Int = i - } + def from(start: Int, step: Int): Iterator[Int] = from(start, {x:Int => x + step}) /** Create an iterator with elements * <code>e<sub>n+1</sub> = step(e<sub>n</sub>)</code> @@ -179,14 +173,11 @@ object Iterator { * @param step the increment function of the iterator * @return the iterator starting at value <code>start</code>. */ - def from(start: Int, step: Int => Int): Iterator[Int] = - new BufferedIterator[Int] { - private var i = start - def hasNext: Boolean = true - def next(): Int = { val j = i; i = step(i); j } - def head: Int = i - } - + def from(start: Int, step: Int => Int): Iterator[Int] = new Iterator[Int] { + private var i = start + override def hasNext: Boolean = true + def next: Int = { val j = i; i = step(i); j } + } } /** Iterators are data structures that allow to iterate over a sequence @@ -278,24 +269,27 @@ trait Iterator[+A] { } else throw new NoSuchElementException("next on empty iterator") } - private def predicatedIterator(p: A => boolean, isFilter: boolean) = new BufferedIterator[A] { - private var hd: A = _ - private var ahead: Boolean = false - private def skip: Unit = - while (!ahead && Iterator.this.hasNext) { - hd = Iterator.this.next - ahead = !isFilter || p(hd) + protected class PredicatedIterator(p : A => Boolean) extends DefaultBufferedIterator[A] { + protected def skip0 : Seq[A] = fill + protected override def fill : Seq[A] = + if (!Iterator.this.hasNext) return Nil + else { + val ret = Iterator.this.next; + if (p(ret)) return ret :: Nil; + return skip0 } - def hasNext: Boolean = { - skip - ahead && p(hd) + } + protected class TakeWhileIterator(p : A => Boolean) extends PredicatedIterator(p) { + private var ended = false + override protected def skip0 : Seq[A] = { + ended = true + Nil } - def next(): A = - if (hasNext) { ahead = false; hd } - else throw new NoSuchElementException("next on empty iterator") - def head: A = { skip; hd } + override protected def fill : Seq[A] = + if (ended) Nil else super.fill } + /** Returns an iterator over all the elements of this iterator that * satisfy the predicate <code>p</code>. The order of the elements * is preserved. @@ -303,7 +297,7 @@ trait Iterator[+A] { * @param p the predicate used to filter the iterator. * @return the elements of this iterator satisfying <code>p</code>. */ - def filter(p: A => Boolean): Iterator[A] = predicatedIterator(p, true) + def filter(p: A => Boolean): Iterator[A] = new PredicatedIterator(p) /** Returns an iterator over the longest prefix of this iterator such that * all elements of the result satisfy the predicate <code>p</code>. @@ -312,7 +306,7 @@ trait Iterator[+A] { * @param p the predicate used to filter the iterator. * @return the longest prefix of this iterator satisfying <code>p</code>. */ - def takeWhile(p: A => Boolean): Iterator[A] = predicatedIterator(p, false) + def takeWhile(p: A => Boolean): Iterator[A] = new TakeWhileIterator(p) /** Skips longest sequence of elements of this iterator which satisfy given * predicate <code>p</code>, and returns an iterator of the remaining elements. @@ -502,18 +496,8 @@ trait Iterator[+A] { /** Returns a buffered iterator from this iterator. */ - def buffered: BufferedIterator[A] = new BufferedIterator[A] { - private var hd: A = _ - private var ahead: Boolean = false - def head: A = { - if (!ahead) { - hd = Iterator.this.next - ahead = true - } - hd - } - def next: A = if (ahead) { ahead = false; hd } else head - def hasNext: Boolean = ahead || Iterator.this.hasNext + def buffered: BufferedIterator[A] = new DefaultBufferedIterator[A] { + protected def fill = if (Iterator.this.hasNext) (Iterator.this.next) :: Nil else Nil } /** Returns a counted iterator from this iterator. @@ -577,6 +561,26 @@ trait Iterator[+A] { i += 1 } } + /** Fills the given array <code>xs</code> with the elements of + * this sequence starting at position <code>start</code>. Like <code>copyToArray</code>, + * but designed to accomodate IO stream operations. + * + * @param xs the array to fill. + * @param start the starting index. + * @param sz the maximum number of elements to be read. + * @pre the array must be large enough to hold <code>sz</code> elements. + */ + def readInto[B >: A](xs: Array[B], start : Int, sz : Int) : Unit = { + var i = start + while (hasNext && i - start < sz) { + xs(i) = next + i += 1 + } + } + def readInto[B >: A](xs : Array[B], start : Int) : Unit = readInto(xs, start, xs.length - start) + def readInto[B >: A](xs : Array[B]) : Unit = readInto(xs, 0, xs.length) + + /** Copy all elements to a buffer * @param The buffer to which elements are copied @@ -640,4 +644,5 @@ trait Iterator[+A] { } buf.append(end) } + override def toString = if (hasNext) "has" else "empty" } diff --git a/src/library/scala/List.scala b/src/library/scala/List.scala index 12fce2c20b..6763491ade 100644 --- a/src/library/scala/List.scala +++ b/src/library/scala/List.scala @@ -479,7 +479,7 @@ sealed abstract class List[+a] extends Seq[a] { * * @return an iterator on the list elements. */ - def elements: Iterator[a] = new Iterator[a] { + override def elements: Iterator[a] = new Iterator[a] { var these = List.this def hasNext: Boolean = !these.isEmpty def next: a = @@ -521,7 +521,7 @@ sealed abstract class List[+a] extends Seq[a] { * @return the last element of the list. * @throws Predef.UnsupportedOperationException if the list is empty. */ - def last: a = + override def last: a = if (isEmpty) throw new Predef.NoSuchElementException("Nil.last") else if (tail.isEmpty) head else tail.last diff --git a/src/library/scala/RandomAccessSeq.scala b/src/library/scala/RandomAccessSeq.scala new file mode 100644 index 0000000000..1af27e1798 --- /dev/null +++ b/src/library/scala/RandomAccessSeq.scala @@ -0,0 +1,59 @@ +package scala + +object RandomAccessSeq { + trait Projection[+A] extends Seq.Projection[A] with RandomAccessSeq[A] { + override def projection = this + protected class MapProjection[B](f : A => B) extends super.MapProjection(f) with Projection[B] + override def map[B](f: A => B) : Projection[B] = new MapProjection[B](f) + /** non-strict */ + override def drop(n: Int): Projection[A] = { + new Projection[A] { + def length = Projection.this.length - n + def apply(idx : Int) = Projection.this.apply(idx + n) + } + } + /** non-strict */ + override def take(n: Int): Projection[A] = { + if (n >= length) Projection.this + else new Projection[A] { + def length = n + def apply(idx : Int) = Projection.this.apply(idx) + } + } + /** non-strict */ + override def slice(from : Int, until : Int) : Projection[A] = drop(from).take(until) + /** non-strict */ + override def reverse : Projection[A] = new Projection[A] { + def length = Projection.this.length + def apply(idx : Int) = Projection.this.apply(length - idx - 1) + } + } +} + +/** Sequences that support O(1) element access + * @author Sean McDirmid + */ +trait RandomAccessSeq[+A] extends Seq[A] { + override def projection : RandomAccessSeq.Projection[A] = new RandomAccessSeq.Projection[A] { + def length = RandomAccessSeq.this.length + def apply(idx : Int) = RandomAccessSeq.this.apply(idx) + override def elements = RandomAccessSeq.this.elements + } + override def elements : Iterator[A] = new Iterator[A] { + var idx = 0 + def hasNext = idx < RandomAccessSeq.this.length + def next = { + if (!hasNext) throw new Predef.NoSuchElementException + val ret = RandomAccessSeq.this.apply(idx) + idx = idx + 1 + ret + } + } + /** Appends two random access sequences in a non-strict way */ + def +++[B >: A](that: RandomAccessSeq[B]): RandomAccessSeq.Projection[B] = new RandomAccessSeq.Projection[B] { + def length = RandomAccessSeq.this.length + that.length + def apply(idx : Int) = + if (idx < RandomAccessSeq.this.length) RandomAccessSeq.this(idx) + else that(idx) + } +}
\ No newline at end of file diff --git a/src/library/scala/Range.scala b/src/library/scala/Range.scala index 5718b8c5f2..b894d6ae5f 100644 --- a/src/library/scala/Range.scala +++ b/src/library/scala/Range.scala @@ -28,21 +28,37 @@ import Predef._ */ class Range(val start: Int, val end: Int, val step: Int) extends BufferedIterator[Int] { assert(step != 0) + assert(if (step > 0) end >= start else end <= start) private var i = start - def hasNext: Boolean = if (step > 0) i < end else i > end + override def hasNext: Boolean = if (step > 0) i < end else i > end - def next(): Int = + def next: Int = if (hasNext) { val j = i; i += step; j } else throw new NoSuchElementException("next on empty iterator") - def head: Int = - if (hasNext) i - else throw new NoSuchElementException("head on empty iterator") + def peekList(sz : Int) = new RandomAccessSeq[Int] { + def length = Math.min(sz, length0(i)); + def apply(idx : Int) = { + if (idx >= length) throw new IndexOutOfBoundsException + i + (idx * step) + } + } + protected override def defaultPeek : Int = throw new NoSuchElementException - def length: Int = - 1 + (Math.abs(start - end) - 1) / Math.abs(step) + private def length0(i : Int) = { + if (step > 0) length1(i, end, step) + else length1(end, i, -step) + } + private def length1(start : Int, end : Int, step : Int) = { + assert(start <= end && step > 0) + val n = (end - start) / step + val m = (end - start) % step + n + (if (m == 0) 0 else 1) + } + def length: Int = length0(start) def contains(x: Int): Boolean = Iterator.range(0, length) exists (i => x == start + i * step) + } diff --git a/src/library/scala/Seq.scala b/src/library/scala/Seq.scala index 31f74fa768..6ab277c88c 100644 --- a/src/library/scala/Seq.scala +++ b/src/library/scala/Seq.scala @@ -20,7 +20,7 @@ object Seq { val empty = new Seq[Nothing] { def length = 0 def apply(i: Int): Nothing = throw new NoSuchElementException("empty sequence") - def elements = Iterator.empty + override def elements = Iterator.empty } /** This method is called in a pattern match { case Seq(...) => }. @@ -37,7 +37,7 @@ object Seq { */ def single[A](x: A) = new Seq[A] { def length = 1 - def elements = Iterator.single(x) + override def elements = Iterator.single(x) override def isDefinedAt(x: Int): Boolean = (x == 0) def apply(i: Int) = x // caller's responsibility to check isDefinedAt } @@ -59,6 +59,39 @@ object Seq { } } */ + trait Projection[+A] extends Seq[A] with Iterable.Projection[A] { + override def projection = this + override def map[B](f: A => B) : Projection[B] = new MapProjection(f) + protected class MapProjection[B](f : A => B) extends Projection[B] { + def length = Projection.this.length + def elements = Projection.this.elements.map(f) + def apply(idx : Int) = f(Projection.this.apply(idx)) + } + override def flatMap[B](f: A => Iterable[B]): Projection[B] = new Projection[B] { + def elements = Projection.this.elements.flatMap(a => f(a).elements) + def length = { + var sz = 0 + Projection.this.foreach(a => sz = sz + f(a).asInstanceOf[Collection[B]].size) + sz + } + def apply(idx : Int) : B = { + var jdx = 0 + Projection.this.foreach(a => { + val i = f(a) + val length = i.asInstanceOf[Collection[B]].size + if (idx < jdx + length) { + val j = i.elements + while (jdx < idx) { + j.next; jdx += 1 + } + return j.next + } else jdx += length + }) + throw new IndexOutOfBoundsException + } + } + override def filter(p : A => Boolean) : Projection[A] = new Filter(p) + } } @@ -76,6 +109,7 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Collection[A] { * @return the sequence length. */ def length: Int + /** should always be <code>length</code> */ def size = length @@ -96,10 +130,17 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Collection[A] { buf } - /** Appends two iterable objects. + /** Returns the last element of this list. * - * @param that .. - * @return the new iterable object + * @return the last element of the list. + * @throws Predef.UnsupportedOperationException if the list is empty. + */ + def last: A = length match { + case 0 => throw new Predef.NoSuchElementException + case n => this(n - 1) + } + + /** Appends two iterable objects. */ override def ++ [B >: A](that: Iterable[B]): Seq[B] = { val buf = new ArrayBuffer[B] @@ -229,10 +270,6 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Collection[A] { /** Returns a subsequence starting from index <code>from</code> * consisting of <code>len</code> elements. - * - * @param from .. - * @param len .. - * @return .. */ def slice(from: Int, len: Int): Seq[A] = this.drop(from).take(len) @@ -252,7 +289,33 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Collection[A] { copyToArray(result, 0) result } + override def projection : Seq.Projection[A] = new Seq.Projection[A] { + def elements = Seq.this.elements + def length = Seq.this.length + def apply(idx : Int) = (Seq.this.apply(idx)) + } + class Filter(p : A => Boolean) extends Seq.Projection[A] { + override def elements = Seq.this.elements.filter(p) + override def apply(idx : Int) : A = { + var jdx = 0 + val i = Seq.this.elements + while (true) { + val a = i.next + if (p(a)) { + if (jdx == idx) return a + else jdx = jdx + 1 + } + } + throw new Predef.Error + } + override def length = { + var sz = 0 + val i = Seq.this.elements + while (i.hasNext) if (p(i.next)) sz = sz + 1 + sz + } + } } diff --git a/src/library/scala/Stream.scala b/src/library/scala/Stream.scala index a875b344a9..7046a3dfb6 100644 --- a/src/library/scala/Stream.scala +++ b/src/library/scala/Stream.scala @@ -198,7 +198,7 @@ trait Stream[+a] extends Seq[a] { /** An iterator returning the elements of this stream one by one. */ - def elements: Iterator[a] = new Iterator[a] { + override def elements: Iterator[a] = new Iterator[a] { var current = Stream.this def hasNext: Boolean = !current.isEmpty def next: a = { val result = current.head; current = current.tail; result } @@ -217,7 +217,7 @@ trait Stream[+a] extends Seq[a] { * @return the last element of the stream. * @throws Predef.NoSuchElementException if the stream is empty. */ - def last: a = + override def last: a = if (isEmpty) throw new NoSuchElementException("Stream.empty.last") else { def loop(s: Stream[a]): a = { diff --git a/src/library/scala/collection/Map.scala b/src/library/scala/collection/Map.scala index e059617e79..3dfa5d999f 100644 --- a/src/library/scala/collection/Map.scala +++ b/src/library/scala/collection/Map.scala @@ -13,6 +13,10 @@ package scala.collection import Predef._ +object Map { + trait Projection[A, +B] extends Iterable.Projection[(A,B)] with Map[A,B]; +} + /** <p> * A map is a collection that maps each key to one or zero values. @@ -164,16 +168,27 @@ trait Map[A, +B] extends PartialFunction[A, B] with Collection[(A, B)] { def default(key: A): B = throw new NoSuchElementException("key not found: " + key) - trait Projection extends super.Projection { - /** filter based on keys only */ - def filterKeys(p : A => Boolean) = filter(e => p(e._1)) - /** map elements using existing key set */ - def mapElements[C](f : B => C) : Map[A,C] = new Map[A,C] { - def elements = Map.this.elements.map(e => (e._1, f(e._2))) - def size = Map.this.size - override def contains(key : A) = Map.this.contains(key) - override def get(key : A) = Map.this.get(key).map(f) + override def projection : Map.Projection[A,B] = new Map.Projection[A,B] { + override def elements = Map.this.elements + override def size = Map.this.size + override def get(key : A) : Option[B] = Map.this.get(key) + } + /** non-strict filter based on keys only */ + def filterKeys(p : A => Boolean) : Map.Projection[A,B] = new Map.Projection[A,B] { + def elements = Map.this.elements.filter(x => p(x._1)) + def size = { + var sz = 0 + Map.this.foreach(x => if (p(x._1)) sz = sz + 1) + sz } + override def contains(key : A) = Map.this.contains(key) && p(key) + override def get(key : A) = if (!p(key)) None else Map.this.get(key) + } + /** non-strict map elements using existing key set */ + def mapElements[C](f : B => C) : Map.Projection[A,C] = new Map.Projection[A,C] { + def elements = Map.this.elements.map(e => (e._1, f(e._2))) + def size = Map.this.size + override def contains(key : A) = Map.this.contains(key) + override def get(key : A) = Map.this.get(key).map(f) } - override def projection : Projection = new Projection {} } diff --git a/src/library/scala/collection/Ranged.scala b/src/library/scala/collection/Ranged.scala index 50d01f3ff3..45bba6fe54 100644 --- a/src/library/scala/collection/Ranged.scala +++ b/src/library/scala/collection/Ranged.scala @@ -18,10 +18,10 @@ trait Ranged[K, +A] extends Iterable[A] { //protected type SortedSelf <: Ranged[K,A]; /** Returns the first key of the collection. */ - def first: K + def firstKey: K /** Returns the last key of the collection. */ - def last: K + def lastKey: K /** Comparison function that orders keys. */ def compare(k0: K, k1: K): Int diff --git a/src/library/scala/collection/RollbackIterator.scala b/src/library/scala/collection/RollbackIterator.scala new file mode 100644 index 0000000000..19eded61a1 --- /dev/null +++ b/src/library/scala/collection/RollbackIterator.scala @@ -0,0 +1,70 @@ +package scala.collection +import scala.collection.mutable.{ArrayBuffer} + +/** Rollback iterators are buffered iterators which allow for unbounded rollbacks + * + * @author Sean McDirmid + */ +class RollbackIterator[+A](underlying : Iterator[A]) extends DefaultBufferedIterator[A] { + private[this] var rollback : ArrayBuffer[A] = null + protected def fill : Seq[A] = if (underlying.hasNext) underlying.next :: Nil else Nil + + override def next : A = { + val ret = super.next + if (rollback != null) rollback += ret + ret + } + private def initRollback = if (rollback == null) { + rollback = new ArrayBuffer[A] + None + } else Some(rollback.length) + + /** will rollback all elements iterated during + * <code>f</code>'s execution if <code>f</code> return false + */ + def tryRead[T](f : => Option[T]) : Option[T] = { + val oldLength = initRollback + var g : Option[T] = None + try { + g = f + } finally { + if (g.isEmpty) { + //putBack(rollback(0)) + val sz = oldLength.getOrElse(0) + val i = rollback.drop(sz).reverse.elements + while (i.hasNext) putBack(i.next) + if (oldLength.isEmpty) rollback = null + else rollback.reduceToSize(sz) + } + } + if (!g.isEmpty && oldLength.isEmpty) + rollback = null + g + + } + /** remembers elements iterated over during <code>g</code>'s execution + * and provides these elements to the result of <code>g</code>'s execution + */ + def remember[T](g : => (Seq[A] => T)) : T = { + val oldLength = initRollback + var in : Seq[A] = Nil + val f = try { + g + } finally { + in = rollback.drop(oldLength.getOrElse(0)) + if (oldLength.isEmpty) rollback = null + } + f(in) + } + /** returns true if any elements are iterated over during <code>f</code>'s execution + */ + def read(f : => Unit) : Boolean = remember[Boolean]{ + f; seq => !seq.isEmpty + } + + /** if elements of <code>seq</code> will be iterated over next in this iterator, + * returns true and iterates over these elements + */ + def readIfStartsWith(seq : Seq[Any]) : Boolean = + !tryRead{if (seq.forall(a => hasNext && next == a)) Some(()) else None}.isEmpty +}
\ No newline at end of file diff --git a/src/library/scala/collection/SortedMap.scala b/src/library/scala/collection/SortedMap.scala index 57649a84e2..f645c9d9ba 100644 --- a/src/library/scala/collection/SortedMap.scala +++ b/src/library/scala/collection/SortedMap.scala @@ -15,8 +15,8 @@ package scala.collection; * @author Sean McDirmid */ trait SortedMap[K,+E] extends Map[K,E] with Sorted[K,Tuple2[K,E]] { - override def first : K = elements.next._1; - override def last : K = { + override def firstKey : K = elements.next._1; + override def lastKey : K = { val i = elements; var last : K = i.next._1; while (i.hasNext) last = i.next._1; diff --git a/src/library/scala/collection/SortedSet.scala b/src/library/scala/collection/SortedSet.scala index 058876c974..4b89edf8ab 100644 --- a/src/library/scala/collection/SortedSet.scala +++ b/src/library/scala/collection/SortedSet.scala @@ -18,13 +18,13 @@ trait SortedSet[A] extends Set[A] with Sorted[A, A] { override def keySet = this - override def first: A = { + override def firstKey: A = { val i = elements if (i.hasNext) i.next else throw new NoSuchElementException } - override def last: A = { + override def lastKey: A = { var last: A = null.asInstanceOf[A] val i = elements while (i.hasNext) last = i.next; diff --git a/src/library/scala/collection/immutable/Queue.scala b/src/library/scala/collection/immutable/Queue.scala index d04188a363..738c7ab55e 100644 --- a/src/library/scala/collection/immutable/Queue.scala +++ b/src/library/scala/collection/immutable/Queue.scala @@ -55,7 +55,7 @@ class Queue[+A](elem: A*) extends Seq[A] { /** Returns the elements in the list as an iterator */ - def elements: Iterator[A] = (out ::: in.reverse).elements + override def elements: Iterator[A] = (out ::: in.reverse).elements /** Checks if the queue is empty. * diff --git a/src/library/scala/collection/immutable/Stack.scala b/src/library/scala/collection/immutable/Stack.scala index 4201f7c67e..22f257b99f 100644 --- a/src/library/scala/collection/immutable/Stack.scala +++ b/src/library/scala/collection/immutable/Stack.scala @@ -93,7 +93,7 @@ class Stack[+A] extends Seq[A] { * * @return an iterator over all stack elements. */ - def elements: Iterator[A] = new Iterator[A] { + override def elements: Iterator[A] = new Iterator[A] { var that: Stack[A] = Stack.this; def hasNext = !that.isEmpty; def next = diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala index 078da93281..0b0bb6a9a4 100644 --- a/src/library/scala/collection/immutable/TreeMap.scala +++ b/src/library/scala/collection/immutable/TreeMap.scala @@ -50,8 +50,8 @@ extends RedBlack[A] with SortedMap[A, B] { val ntree = tree.range(from,until) new TreeMap[A,B](ntree.count, ntree) } - override def first = t.first - override def last = t.last + override def firstKey = t.first + override def lastKey = t.last override def compare(k0: A, k1: A): Int = k0.compare(k1) diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala index 794293835c..645308a658 100644 --- a/src/library/scala/collection/immutable/TreeSet.scala +++ b/src/library/scala/collection/immutable/TreeSet.scala @@ -102,7 +102,7 @@ class TreeSet[A <% Ordered[A]](val size: int, t: RedBlack[A]#Tree[Unit]) val tree = this.tree.range(from,until) newSet(tree.count, tree) } - override def first = tree.first - override def last = tree.last + override def firstKey = tree.first + override def lastKey = tree.last override def compare(a0 : A, a1 : A) = a0.compare(a1) } diff --git a/src/library/scala/collection/jcl/ArrayList.scala b/src/library/scala/collection/jcl/ArrayList.scala index d6ca5ee42c..93b7cdff61 100644 --- a/src/library/scala/collection/jcl/ArrayList.scala +++ b/src/library/scala/collection/jcl/ArrayList.scala @@ -14,7 +14,7 @@ package scala.collection.jcl; * * @author Sean McDirmid */ -class ArrayList[A](override val underlying : java.util.ArrayList) extends CollectionWrapper[A] with BufferWrapper[A] { +class ArrayList[A](override val underlying : java.util.ArrayList) extends BufferWrapper[A] { def this() = this(new java.util.ArrayList); override def elements = super[BufferWrapper].elements; } diff --git a/src/library/scala/collection/jcl/Buffer.scala b/src/library/scala/collection/jcl/Buffer.scala index 359c5ec5db..62479172e8 100644 --- a/src/library/scala/collection/jcl/Buffer.scala +++ b/src/library/scala/collection/jcl/Buffer.scala @@ -14,22 +14,32 @@ package scala.collection.jcl; * * @author Sean McDirmid */ -trait Buffer[A] extends MutableSeq[A] with Collection[A] with Ranged[Int,A] { +trait Buffer[A] extends Ranged[Int,A] with MutableSeq[A] with Collection[A] { final protected type SortedSelf = Buffer[A]; - trait MutableSeqProjection extends super[MutableSeq].Projection; - trait Projection extends MutableSeqProjection with super[Collection].Projection { - override def filter(p : A => Boolean) = super[MutableSeqProjection].filter(p); + override def projection : Buffer.Projection[A] = new Buffer.Projection[A] { + override def elements = Buffer.this.elements + override def length = Buffer.this.length + override def apply(idx : Int) = Buffer.this.apply(idx) + override def transform(f : A => A) = Buffer.this.transform(f) } - override def projection = new Projection {} - override def elements : BufferIterator[Int,A]; + protected class DefaultBufferIterator extends DefaultSeqIterator with BufferIterator[Int,A] { + override def set(a : A) = { + if (index == 0) throw new NoSuchElementException + Buffer.this.set(index - 1, a) + } + override def add(a : A) = { + Buffer.this.add(index, a) + } + } + override def elements : BufferIterator[Int,A] = new DefaultBufferIterator /** The first index of a buffer is 0. */ - override def first = 0; + override def firstKey = 0; /** The last index of a buffer is its size - 1. */ - override def last = size - 1; + override def lastKey = size - 1; /** Indices are compared through subtraction. */ final def compare(k0 : Int, k1 : Int) = k0 - k1; @@ -120,7 +130,7 @@ trait Buffer[A] extends MutableSeq[A] with Collection[A] with Ranged[Int,A] { else until.get; } else super.length; } - def elements : BufferIterator[Int,A] = new RangeIterator; + override def elements : BufferIterator[Int,A] = new RangeIterator; class RangeIterator extends BufferIterator[Int,A] { val underlying = Buffer.this.elements; if (from != None) underlying.seek(from.get); @@ -167,3 +177,8 @@ trait Buffer[A] extends MutableSeq[A] with Collection[A] with Ranged[Int,A] { } } } +object Buffer { + trait Projection[A] extends MutableSeq.Projection[A] with Collection.Projection[A] with Buffer[A] { + override def projection = this + } +} diff --git a/src/library/scala/collection/jcl/BufferWrapper.scala b/src/library/scala/collection/jcl/BufferWrapper.scala index c056899fa0..1a3e9a35e6 100644 --- a/src/library/scala/collection/jcl/BufferWrapper.scala +++ b/src/library/scala/collection/jcl/BufferWrapper.scala @@ -15,13 +15,13 @@ package scala.collection.jcl; * @author Sean McDirmid */ trait BufferWrapper[A] extends Buffer[A] with CollectionWrapper[A] { - protected def underlying : java.util.List; + def underlying : java.util.List; override def elements : BufferIterator[Int,A] = new IteratorWrapper(underlying.listIterator); override def remove(idx : Int) = underlying.remove(idx).asInstanceOf[A]; override def add(a : A) = underlying.add(a); override def add(idx : Int, a : A) = underlying.add(idx,a); override def addAll(idx : Int, that : Iterable[A]) = that match { - case that : CollectionWrapper[_] => underlying.addAll(idx, that.underlying0); {} + case that : CollectionWrapper[_] => underlying.addAll(idx, that.underlying); {} case _ => super.addAll(idx, that); } override def indexOf(a : A) = { diff --git a/src/library/scala/collection/jcl/Collection.scala b/src/library/scala/collection/jcl/Collection.scala index 74ed7345af..0df2f74f4b 100644 --- a/src/library/scala/collection/jcl/Collection.scala +++ b/src/library/scala/collection/jcl/Collection.scala @@ -12,6 +12,9 @@ package scala.collection.jcl; object Collection { val DEFAULT_FILTER : Any => Boolean = x => true; + trait Projection[A] extends Collection[A] with MutableIterable.Projection[A] { + override def projection = this + } } /** Analogous to a Java collection. @@ -54,33 +57,11 @@ trait Collection[A] extends MutableIterable[A] { * @param f * @return <code>true</code> if the collection is actually updated. */ - def transform(f: A => A): Boolean; - - trait Projection extends super.Projection { - override def filter(p : A => Boolean) : MutableIterable[A] = new Filter(p); - } - override def projection : Projection = new Projection {} - - - /** Base implementation of a filtered collection */ - class Filter(p : A => Boolean) extends Collection[A] { - def transform(f : A => A) = - Collection.this.transform(a => if (p(a)) f(a) else a); - override def add(a : A) = { - if (!p(a)) throw new IllegalArgumentException; - Collection.this.add(a); - } - override def has(a : A) = if (!p(a)) false else Collection.this.has(a); - override def remove(a : A) = { - if (!p(a)) throw new IllegalArgumentException; - Collection.this.remove(a); - } - class Projection extends super.Projection { - override def filter(p0 : A => Boolean) : MutableIterable[A] = - Collection.this.projection.filter(a => p(a) && p0(a)); - } - override def projection : Projection = new Projection; - def elements = Collection.this.elements.filter(p); - def size = size0; + def transform(f: A => A): Boolean + override def projection : Collection.Projection[A] = new Collection.Projection[A] { + override def elements = Collection.this.elements + override def size = Collection.this.size + override def add(a: A): Boolean = Collection.this.add(a) + override def transform(f : A => A) = Collection.this.transform(f); } } diff --git a/src/library/scala/collection/jcl/CollectionWrapper.scala b/src/library/scala/collection/jcl/CollectionWrapper.scala index 279e3f8a07..0116a4e790 100644 --- a/src/library/scala/collection/jcl/CollectionWrapper.scala +++ b/src/library/scala/collection/jcl/CollectionWrapper.scala @@ -18,8 +18,7 @@ trait CollectionWrapper[A] extends Collection[A] with IterableWrapper[A] { /** Override to specify the collection being accessed through this wrapper. ** Collection operations are then routed through the wrapped Java collection. **/ - protected def underlying : java.util.Collection; - private[jcl] final def underlying0 = underlying; + def underlying : java.util.Collection; override def has(a : A) = underlying.contains(a); override def elements : MutableIterator[A] = super.elements; diff --git a/src/library/scala/collection/jcl/IterableWrapper.scala b/src/library/scala/collection/jcl/IterableWrapper.scala index 6e556e3199..8b488499ab 100644 --- a/src/library/scala/collection/jcl/IterableWrapper.scala +++ b/src/library/scala/collection/jcl/IterableWrapper.scala @@ -15,7 +15,7 @@ package scala.collection.jcl; * @author Sean McDirmid */ trait IterableWrapper[A] extends MutableIterable[A] { - protected def underlying: java.util.Collection; + def underlying: java.util.Collection; override def remove(a: A) = underlying.remove(a); override def removeAll(that: Iterable[A]) = that match { case that: IterableWrapper[_] => underlying.removeAll(that.underlying); diff --git a/src/library/scala/collection/jcl/Map.scala b/src/library/scala/collection/jcl/Map.scala index 34b5d92918..96dddd6add 100644 --- a/src/library/scala/collection/jcl/Map.scala +++ b/src/library/scala/collection/jcl/Map.scala @@ -22,11 +22,11 @@ trait Map[K,E] extends MutableIterable[Tuple2[K,E]] with scala.collection.mutabl /** The values of this map as a projection, which means removals from the returned collection will remove the element from this map. @returns a projection of this map's elements. */ - def valueSet : MutableIterable[E] = projection.map(._2); + def valueSet : MutableIterable.Projection[E] = projection.map(._2); def put(key : K, elem : E) : Option[E]; def putAll(that : Iterable[Tuple2[K,E]]) : Unit = that.foreach(p => put(p._1, p._2)); - def remove(key : K) : Option[E] = { + def removeKey(key : K) : Option[E] = { val i = elements; while (!i.hasNext) { val result = i.next; @@ -48,43 +48,48 @@ trait Map[K,E] extends MutableIterable[Tuple2[K,E]] with scala.collection.mutabl } override def +=(pair : Tuple2[K,E]) : Unit = put(pair._1, pair._2); override def -(key : K) : this.type = { - remove(key); this; + removeKey(key); this; } - override def -=(key : K) : Unit = remove(key); + override def remove(p : (K,E)) = get(p._1) match { + case Some(p._2) => this -= p._1; true + case _ => false; + } + + override def -=(key : K) : Unit = removeKey(key); override def elements : MutableIterator[Tuple2[K,E]]; - trait MutableIterableProjection extends super[MutableIterable].Projection; - trait Projection extends MutableIterableProjection with super[Map].Projection { - override def filterKeys(p : K => Boolean) : jcl.Map[K,E] = new Filter(p); - override def map[B](f : ((K,E)) => B) : MutableIterable[B] = super[MutableIterableProjection].map(f); + override def projection : Map.Projection[K,E] = new Map.Projection[K,E] { + override def elements = Map.this.elements + override def size = Map.this.size + override def get(k : K) = Map.this.get(k) + override def put(k : K, e : E) = Map.this.put(k, e) } - override def projection : Projection = new Projection {} - /** */ - def lense[F](f : E => F, g : F => E) : jcl.Map[K,F] = new Lense[F](f,g); + def lense[F](f : E => F, g : F => E) : jcl.Map.Projection[K,F] = new Lense[F](f,g); - protected class Lense[F](f : E => F, g : F => E) extends jcl.Map[K,F] { + protected class Lense[F](f : E => F, g : F => E) extends jcl.Map.Projection[K,F] { override def elements = Map.this.elements.map(k => Tuple2(k._1, f(k._2))); - override def remove(key : K) = Map.this.remove(key).map(f); + override def removeKey(key : K) = Map.this.removeKey(key).map(f); override def put(key : K, elem : F) = Map.this.put(key, g(elem)).map(f); override def get(key : K) = Map.this.get(key).map(f); - - trait Projection extends super.Projection { - override def filterKeys(p : K => Boolean) : jcl.Map[K,F] = - Map.this.projection.filterKeys(p).lense(f, g); - } - override def projection = new Projection {} - - override def lense[G](f0 : F => G, g0 : G => F) : jcl.Map[K,G] = + override def lense[G](f0 : F => G, g0 : G => F) : jcl.Map.Projection[K,G] = Map.this.lense[G](x => f0(f(x)), y => g(g0(y))); override def size = size0; } - protected class Filter(p : K => Boolean) extends jcl.Map[K,E] { + protected class KeySet extends Set[K] { + override def size = Map.this.size; + override def add(k : K) = Map.this.put(k, default(k)) == None; + override def elements = Map.this.elements.map(._1); + override def has(k : K) = Map.this.contains(k); + } + override def filterKeys(p : K => Boolean) : Map.Projection[K,E] = new Filter(p); + + protected class Filter(p : K => Boolean) extends Map.Projection[K,E] { override def elements = Map.this.elements.filter(e => p(e._1)); - override def remove(key : K) = { + override def removeKey(key : K) = { if (!p(key)) throw new IllegalArgumentException; - Map.this.remove(key); + Map.this.removeKey(key); } override def contains(key : K) = p(key) && Map.this.contains(key); override def put(key : K, elem : E) = { @@ -95,17 +100,17 @@ trait Map[K,E] extends MutableIterable[Tuple2[K,E]] with scala.collection.mutabl if (!p(key)) None; else Map.this.get(key); } - class Projection extends super.Projection { - override def filterKeys(p0 : K => Boolean) : jcl.Map[K,E] = - Map.this.projection.filterKeys(e => p(e) && p0(e)); - } + override def filterKeys(p0 : K => Boolean) : Map.Projection[K,E] = + Map.this.filterKeys(e => p(e) && p0(e)); + override def size = size0; } - protected class KeySet extends Set[K] { - override def size = Map.this.size; - override def add(k : K) = Map.this.put(k, default(k)) == None; - override def elements = Map.this.elements.map(._1); - override def has(k : K) = Map.this.contains(k); - } +} +object Map { + trait MutableIterableProjection[A] extends MutableIterable.Projection[A]; + trait Projection[K,E] extends MutableIterableProjection[(K,E)] with scala.collection.Map.Projection[K,E] with Map[K,E] { + override def projection = this + override def map[B](f : ((K,E)) => B) : MutableIterable.Projection[B] = super[MutableIterableProjection].map(f); + } } diff --git a/src/library/scala/collection/jcl/MapWrapper.scala b/src/library/scala/collection/jcl/MapWrapper.scala index 5762310b66..ef45501b4d 100644 --- a/src/library/scala/collection/jcl/MapWrapper.scala +++ b/src/library/scala/collection/jcl/MapWrapper.scala @@ -15,7 +15,7 @@ package scala.collection.jcl; * @author Sean McDirmid */ trait MapWrapper[K,E] extends jcl.Map[K,E] { - protected def underlying : java.util.Map; + def underlying : java.util.Map; override def size = underlying.size; override def isEmpty = underlying.isEmpty; override def clear() = underlying.clear; @@ -33,13 +33,13 @@ trait MapWrapper[K,E] extends jcl.Map[K,E] { case that : MapWrapper[_,_] => underlying.putAll(that.underlying); case _ => super.putAll(that); } - override def remove(key : K) = { + override def removeKey(key : K) = { val ret = underlying.remove(key); if (ret == null) None else Some(ret.asInstanceOf[E]); } override def contains(key : K) = underlying.containsKey(key); - override def keySet : Set[K] = new KeySet; - override def valueSet : MutableIterable[E] = new ValueSet; + override def keySet : Set.Projection[K] = new KeySet; + override def valueSet : MutableIterable.Projection[E] = new ValueSet; override def elements : MutableIterator[Tuple2[K,E]] = new IteratorWrapper; class IteratorWrapper extends MutableIterator[Tuple2[K,E]] { val underlying = MapWrapper.this.underlying.entrySet.iterator; @@ -50,10 +50,10 @@ trait MapWrapper[K,E] extends jcl.Map[K,E] { Tuple2(next.getKey.asInstanceOf[K],next.getValue.asInstanceOf[E]); } } - class KeySet extends super.KeySet with SetWrapper[K] { - protected val underlying = MapWrapper.this.underlying.keySet; + class KeySet extends super.KeySet with SetWrapper[K] with Set.Projection[K] { + val underlying = MapWrapper.this.underlying.keySet; } - class ValueSet extends IterableWrapper[E] { + class ValueSet extends IterableWrapper[E] with MutableIterable.Projection[E] { def size = MapWrapper.this.size; val underlying = MapWrapper.this.underlying.values; override def has(e : E) = MapWrapper.this.underlying.containsValue(e); diff --git a/src/library/scala/collection/jcl/MutableIterable.scala b/src/library/scala/collection/jcl/MutableIterable.scala index 411a7ffc01..c4a8fb7dda 100644 --- a/src/library/scala/collection/jcl/MutableIterable.scala +++ b/src/library/scala/collection/jcl/MutableIterable.scala @@ -20,7 +20,8 @@ package scala.collection.jcl; trait MutableIterable[A] extends scala.Collection[A] { /** @return true if t is in the collection. **/ - def has(t : A ) : Boolean = elements.has(t); + def has(t : A ) : Boolean = elements.contains(t); + /** @return true if t was removed from this collection. **/ def remove(t : A ) : Boolean = elements.remove(t); @@ -63,16 +64,40 @@ trait MutableIterable[A] extends scala.Collection[A] { i.next; i.remove; } } - trait Projection extends super.Projection { - override def map[B](f : A => B) : MutableIterable[B] = new Map[B](f); + override def projection : MutableIterable.Projection[A] = new MutableIterable.Projection[A] { + override def elements = MutableIterable.this.elements + override def size = MutableIterable.this.size + override def remove(t : A ) : Boolean = MutableIterable.this.remove(t) + override def filter(p : A => Boolean) : MutableIterable.Projection[A] = super.filter(p) } - override def projection = new Projection {} /** The default implementation of a map over mutable iterable collections. **/ - protected class Map[B](f : A => B) extends MutableIterable[B] { - override def elements = MutableIterable.this.elements.map(f); - override def toString = elements.toList.mkString("{", ", ", "}"); - override def size = MutableIterable.this.size; - } override def elements : MutableIterator[A]; + protected class Map[B](f : A => B) extends MutableIterable.Projection[B] { + override def elements = MutableIterable.this.elements.map(f) + override def size = MutableIterable.this.size + } + trait Filter extends MutableIterable.Projection[A] { + protected def p(a : A) : Boolean + override def has(a : A) = if (!p(a)) false else MutableIterable.this.has(a); + override def remove(a : A) = { + if (!p(a)) throw new IllegalArgumentException; + MutableIterable.this.remove(a); + } + override def filter(p0 : A => Boolean) : MutableIterable.Projection[A] = + MutableIterable.this.projection.filter(a => p(a) && p0(a)); + def elements = MutableIterable.this.elements.filter(p); + def size = size0; + } } + +object MutableIterable { + trait Projection[A] extends MutableIterable[A] with Iterable.Projection[A] { + override def projection = this + override def map[B](f : A => B) : Projection[B] = new Map[B](f); + override def filter(pp : A => Boolean) : Projection[A] = new Filter { + def p(a : A) = pp(a) + } + } +} + diff --git a/src/library/scala/collection/jcl/MutableSeq.scala b/src/library/scala/collection/jcl/MutableSeq.scala index 95325b2e22..634f07b7f6 100644 --- a/src/library/scala/collection/jcl/MutableSeq.scala +++ b/src/library/scala/collection/jcl/MutableSeq.scala @@ -14,25 +14,57 @@ package scala.collection.jcl; * * @author Sean McDirmid */ -trait MutableSeq[A] extends MutableIterable[A] with Seq[A] { - override def elements : SeqIterator[Int,A]; +trait MutableSeq[A] extends Seq[A] with MutableIterable[A] { + protected class DefaultSeqIterator extends SeqIterator[Int,A] { + protected var index = 0 + override def hasNext = index < length + override def next = { + if (!hasNext) throw new NoSuchElementException("no lookahead") + index = index + 1 + MutableSeq.this.apply(index - 1) + } + override def hasPrevious = index > 0 + override def previous = { + if (!hasPrevious) throw new NoSuchElementException + index = index - 1 + MutableSeq.this.apply(index) + } + + override def nextIndex = index + override def previousIndex = { + if (index == 0) throw new NoSuchElementException + else index - 1 + } + def remove = throw new UnsupportedOperationException + } + override def elements : SeqIterator[Int,A] = new DefaultSeqIterator; override def isEmpty = super[MutableIterable].isEmpty; override def apply(idx : Int) = elements.seek(idx); - trait Projection extends super.Projection { - override def filter(p : A => Boolean) : MutableSeq[A] = new Filter(p); - override def map[B](f : A => B) : MutableSeq[B] = new Map[B](f); + override def projection : MutableSeq.Projection[A] = new MutableSeq.Projection[A] { + override def length = MutableSeq.this.length + override def elements = MutableSeq.this.elements + override def apply(idx : Int) = MutableSeq.this.apply(idx) } - override def projection = new Projection {} /** Find the index of "a" in this sequence. * @returns None if the "a" is not in this sequence. */ def indexOf(a : A) = elements.indexOf(a); - protected class Filter(p : A => Boolean) extends MutableSeq[A] { - def elements : SeqIterator[Int,A] = new FilterIterator(MutableSeq.this.elements); + override def length = { + var i = elements; + var sz = 0; + while (i.hasNext) { + sz = sz + 1; + i.next; + } + sz; + } + protected trait Filter extends MutableSeq.Projection[A] { + protected def p(a : A) : Boolean + override def elements : SeqIterator[Int,A] = new FilterIterator(MutableSeq.this.elements); class FilterIterator(underlying : SeqIterator[Int,A]) extends SeqIterator[Int,A] { private var index = 0; protected def seekNext : Option[A] = { @@ -73,19 +105,19 @@ trait MutableSeq[A] extends MutableIterable[A] with Seq[A] { def remove = underlying.remove; } } - - protected class Map[B](f : A => B) extends super.Map[B](f) with MutableSeq[B] { + protected class Map[B](f : A => B) extends super.Map[B](f) with MutableSeq.Projection[B] { override def elements = MutableSeq.this.elements.map(f); override def apply(idx : Int) = f(MutableSeq.this.apply(idx)); override def size = length; } - override def length = { - var i = elements; - var sz = 0; - while (i.hasNext) { - sz = sz + 1; - i.next; +} +object MutableSeq { + trait Projection[A] extends MutableSeq[A] with MutableIterable.Projection[A] with Seq.Projection[A] { + override def projection = this + override def filter(pp : A => Boolean) : Projection[A] = new Filter { + override def p(a : A) = pp(a) } - sz; + override def map[B](f : A => B) : Projection[B] = new Map[B](f); } } + diff --git a/src/library/scala/collection/jcl/Ranged.scala b/src/library/scala/collection/jcl/Ranged.scala index c51a15e537..94759be0d1 100644 --- a/src/library/scala/collection/jcl/Ranged.scala +++ b/src/library/scala/collection/jcl/Ranged.scala @@ -14,15 +14,9 @@ package scala.collection.jcl; * * @author Sean McDirmid */ -trait Ranged[K,A] extends MutableIterable[A] with scala.collection.Ranged[K,A] { +trait Ranged[K,A] extends scala.collection.Ranged[K,A] with MutableIterable[A] { protected type SortedSelf <: Ranged[K,A]; - /** Returns the first key of the collection. */ - def first: K; - - /** Returns the last key of the collection. */ - def last: K; - /** Comparison function that orders keys. */ def compare(k0: K, k1: K): Int; diff --git a/src/library/scala/collection/jcl/Set.scala b/src/library/scala/collection/jcl/Set.scala index c42faf4c31..604e647f52 100644 --- a/src/library/scala/collection/jcl/Set.scala +++ b/src/library/scala/collection/jcl/Set.scala @@ -14,7 +14,8 @@ package scala.collection.jcl * * @author Sean McDirmid */ -trait Set[A] extends Collection[A] with scala.collection.mutable.Set[A] { +trait Set[A] extends scala.collection.mutable.Set[A] with Collection[A] { + final def contains(a : A) = has(a) /** Add will return false if "a" already exists in the set. **/ override def add(a: A): Boolean @@ -25,7 +26,6 @@ trait Set[A] extends Collection[A] with scala.collection.mutable.Set[A] { override def -(t: A) : this.type = super[Collection].-(t) override def retain(f: A => Boolean) = super[Collection].retain(f) override def isEmpty = super[Collection].isEmpty - override final def contains(a: A) = has(a) override def clear() = super.clear() override def subsetOf(set : scala.collection.Set[A]) = set match { case set : Set[_] => set.hasAll(this) @@ -44,14 +44,26 @@ trait Set[A] extends Collection[A] with scala.collection.mutable.Set[A] { } addAll(toAdd) } - trait Projection extends super.Projection { - override def filter(p : A => Boolean) : Set[A] = new Filter(p); - } - override def projection : Projection = new Projection {} - class Filter(p : A => Boolean) extends super.Filter(p) with Set[A] { + class Filter(pp : A => Boolean) extends super.Filter with Set.Projection[A] { + override def p(a : A) = pp(a) override def retain(p0 : A => Boolean): Unit = Set.this.retain(e => !p(e) || p0(e)) - trait Projection extends super[Filter].Projection with super[Set].Projection {} - override def projection : Projection = new Projection {} + override def add(a : A) = { + if (!p(a)) throw new IllegalArgumentException + else Set.this.add(a) + } + } + override def projection : Set.Projection[A] = new Set.Projection[A] { + override def add(a: A): Boolean = Set.this.add(a) + override def elements = Set.this.elements + override def size = Set.this.size + override def has(a : A) : Boolean = Set.this.has(a) + } +} + +object Set { + trait Projection[A] extends Collection.Projection[A] with Set[A] { + override def filter(p : A => Boolean) : Projection[A] = new Filter(p); + override def projection = this } } diff --git a/src/library/scala/collection/jcl/SetWrapper.scala b/src/library/scala/collection/jcl/SetWrapper.scala index 5b1ba751e4..f60c9b5fbe 100644 --- a/src/library/scala/collection/jcl/SetWrapper.scala +++ b/src/library/scala/collection/jcl/SetWrapper.scala @@ -15,7 +15,7 @@ package scala.collection.jcl; * @author Sean McDirmid */ trait SetWrapper[A] extends Set[A] with CollectionWrapper[A] { - protected def underlying: java.util.Set; + def underlying: java.util.Set; override def isEmpty = super[CollectionWrapper].isEmpty; override def clear() = super[CollectionWrapper].clear; override def size = underlying.size; diff --git a/src/library/scala/collection/jcl/SortedMap.scala b/src/library/scala/collection/jcl/SortedMap.scala index 3188d4d6bf..223494a7a5 100644 --- a/src/library/scala/collection/jcl/SortedMap.scala +++ b/src/library/scala/collection/jcl/SortedMap.scala @@ -10,6 +10,11 @@ package scala.collection.jcl; +object SortedMap { + trait Projection[K,E] extends Map.Projection[K,E] with SortedMap[K,E] { + override def projection = this + } +} /** A map whose keys are sorted. * * @author Sean McDirmid @@ -17,59 +22,55 @@ package scala.collection.jcl; trait SortedMap[K,E] extends scala.collection.SortedMap[K,E] with Map[K,E] with Sorted[K,Tuple2[K,E]] { final protected type SortedSelf = SortedMap[K,E]; override def compare(k0 : K, k1 : K) : Int; - override def first : K = elements.next._1; - override def last : K = { + override def firstKey : K = elements.next._1; + override def lastKey : K = { val i = elements; var last : K = i.next._1; while (i.hasNext) last = i.next._1; last; } override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap[K,E] = Range(from, until); - override def keySet : SortedSet[K] = new KeySet; + override def keySet : SortedSet.Projection[K] = new KeySet; - class Projection extends super.Projection { - override def filterKeys(p : K => Boolean) : SortedMap[K,E] = new Filter(p); + override def projection : SortedMap.Projection[K,E] = new SortedMap.Projection[K,E] { + override def elements = SortedMap.this.elements + override def size = SortedMap.this.size + override def get(k : K) = SortedMap.this.get(k) + override def put(k : K, e : E) = SortedMap.this.put(k, e) + override def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0, k1) } - override def projection = new Projection; - override def lense[F](f : E => F, g : F => E) : jcl.SortedMap[K,F] = new Lense[F](f,g); + override def lense[F](f : E => F, g : F => E) : jcl.SortedMap.Projection[K,F] = new Lense[F](f,g); - protected class Lense[F](f : E => F, g : F => E) extends super.Lense[F](f,g) with SortedMap[K,F] { + protected class Lense[F](f : E => F, g : F => E) extends super.Lense[F](f,g) with SortedMap.Projection[K,F] { def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0, k1); - class Projection extends super.Projection { - override def filterKeys(p : K => Boolean) : SortedMap[K,F] = - SortedMap.this.projection.filterKeys(p).lense(f,g); - } - override def projection = new Projection; - override def lense[G](f0 : F => G, g0 : G => F) : jcl.SortedMap[K,G] = + override def filterKeys(p : K => Boolean) : SortedMap.Projection[K,F] = + SortedMap.this.projection.filterKeys(p).lense(f,g); + override def lense[G](f0 : F => G, g0 : G => F) : jcl.SortedMap.Projection[K,G] = SortedMap.this.lense[G]({x:E => f0(f(x))}, {y:G => g(g0(y))}); override def rangeImpl(from : Option[K], until : Option[K]) = SortedMap.this.rangeImpl(from,until).lense(f,g); } - protected class KeySet extends super.KeySet with SortedSet[K] { + protected class KeySet extends super.KeySet with SortedSet.Projection[K] { def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0,k1); - override def first = SortedMap.this.first; - override def last = SortedMap.this.last; + override def firstKey = SortedMap.this.firstKey; + override def lastKey = SortedMap.this.lastKey; override def rangeImpl(from : Option[K], until : Option[K]) = SortedMap.this.rangeImpl(from,until).keySet; } - protected class SuperFilter(p : K => Boolean) extends super.Filter(p); - protected class Filter(p : K => Boolean) extends SuperFilter(p) with SortedMap[K,E] { + override def filterKeys(p : K => Boolean) : SortedMap.Projection[K,E] = new Filter(p); + protected class Filter(p : K => Boolean) extends super.Filter(p) with SortedMap.Projection[K,E] { def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0,k1); - class Projection extends super.Projection { - override def filterKeys(p0 : K => Boolean) : SortedMap[K,E] = - SortedMap.this.projection.filterKeys(k => p(k) && p0(k)); - } - override def projection = new Projection; - override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap[K,E] = + override def filterKeys(p0 : K => Boolean) : SortedMap.Projection[K,E] = + SortedMap.this.filterKeys(k => p(k) && p0(k)); + override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap.Projection[K,E] = SortedMap.this.Range(from, until).projection.filterKeys(p); } - - protected def Range(from : Option[K], until : Option[K]) : SortedMap[K,E] = new Range(from,until); - protected class Range(from : Option[K], until : Option[K]) extends SuperFilter(key => { + protected def Range(from : Option[K], until : Option[K]) : SortedMap.Projection[K,E] = new Range(from,until); + protected class Range(from : Option[K], until : Option[K]) extends super.Filter(key => { ((from == None || (compare(from.get,key) <= 0)) && (until == None || (compare(key,until.get) < 0))); - }) with SortedMap[K,E] { + }) with SortedMap.Projection[K,E] { def compare(k0 : K, k1 : K) = SortedMap.this.compare(k0,k1); private def contains0(key : K) = (from == None || (compare(from.get,key) <= 0)) && @@ -88,17 +89,11 @@ trait SortedMap[K,E] extends scala.collection.SortedMap[K,E] with Map[K,E] with if (until != None && compare(this.until.get, until.get) < 0) return rangeImpl(from, this.until); SortedMap.this.Range(from, until); } - class Projection extends super.Projection { - override def filterKeys(p : K => Boolean) : SortedMap[K,E] = new Filter(p); - } - override def projection = new Projection; - protected class Filter(p : K => Boolean) extends SuperFilter(p) with SortedMap[K,E] { - def compare(k0 : K, k1 : K) = Range.this.compare(k0, k1); - class Projection extends super.Projection { - override def filterKeys(p0 : K => Boolean) = Range.this.projection.filterKeys(k => p(k) && p0(k)); - } - override def projection = new Projection; - override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap[K,E] = + override def filterKeys(p : K => Boolean) : SortedMap.Projection[K,E] = new Filter(p); + protected class Filter(p : K => Boolean) extends super.Filter(p) with SortedMap.Projection[K,E] { + //def compare(k0 : K, k1 : K) = Range.this.compare(k0, k1); + override def filterKeys(p0 : K => Boolean) = Range.this.projection.filterKeys(k => p(k) && p0(k)); + override def rangeImpl(from : Option[K], until : Option[K]) : SortedMap.Projection[K,E] = Range.this.rangeImpl(from,until).projection.filterKeys(p); } } diff --git a/src/library/scala/collection/jcl/SortedMapWrapper.scala b/src/library/scala/collection/jcl/SortedMapWrapper.scala index 62af69cfb0..a71ed832e8 100644 --- a/src/library/scala/collection/jcl/SortedMapWrapper.scala +++ b/src/library/scala/collection/jcl/SortedMapWrapper.scala @@ -15,14 +15,14 @@ package scala.collection.jcl; * @author Sean McDirmid */ trait SortedMapWrapper[K,E] extends SortedMap[K,E] with MapWrapper[K,E] { - protected override def underlying : java.util.SortedMap; + override def underlying : java.util.SortedMap; /** the comparator function of this sorted map is defined in terms * of the underlying sorted map's comparator. */ def compare(k0 : K, k1 : K) = underlying.comparator.compare(k0,k1); - override def first = underlying.firstKey.asInstanceOf[K]; - override def last = underlying.lastKey.asInstanceOf[K]; - override def keySet : SortedSet[K] = new KeySet; + override def firstKey = underlying.firstKey.asInstanceOf[K]; + override def lastKey = underlying.lastKey.asInstanceOf[K]; + override def keySet : SortedSet.Projection[K] = new KeySet; override protected def Range(from : Option[K], until : Option[K]) = new Range(from,until); protected class Range(from : Option[K], until : Option[K]) extends super.Range(from,until) with SortedMapWrapper[K,E] { val underlying = Tuple2(from,until) match { @@ -33,7 +33,7 @@ trait SortedMapWrapper[K,E] extends SortedMap[K,E] with MapWrapper[K,E] { } override def compare(k0 : K, k1 : K) = super[SortedMapWrapper].compare(k0, k1); } - protected class KeySet extends super[SortedMap].KeySet with SetWrapper[K] { - protected val underlying = SortedMapWrapper.this.underlying.keySet; + protected class KeySet extends super[SortedMap].KeySet with SetWrapper[K] with SortedSet.Projection[K] { + val underlying = SortedMapWrapper.this.underlying.keySet; } } diff --git a/src/library/scala/collection/jcl/SortedSet.scala b/src/library/scala/collection/jcl/SortedSet.scala index 0223c04a70..2bb6502f29 100644 --- a/src/library/scala/collection/jcl/SortedSet.scala +++ b/src/library/scala/collection/jcl/SortedSet.scala @@ -10,6 +10,13 @@ package scala.collection.jcl; +object SortedSet { + trait Projection[A] extends Set.Projection[A] with SortedSet[A] { + override def projection = this + override def filter(p : A => Boolean) : Projection[A] = new Filter(p); + } +} + /** Analogous to a Java sorted set. * * @author Sean McDirmid @@ -18,7 +25,7 @@ trait SortedSet[A] extends scala.collection.SortedSet[A] with jcl.Set[A] with So final protected type SortedSelf = SortedSet[A]; override def keySet = this; def compare(a0 : A, a1 : A) : Int; - override def first : A = { + override def firstKey : A = { val i = elements; if (i.hasNext) i.next; else throw new NoSuchElementException; @@ -26,7 +33,7 @@ trait SortedSet[A] extends scala.collection.SortedSet[A] with jcl.Set[A] with So override def subsetOf(that : scala.collection.Set[A]) = super[SortedSet].subsetOf(that); override def hasAll(that : Iterable[A]) = super[Sorted].hasAll(that.elements); - override def last : A = { + override def lastKey : A = { var last : A = null.asInstanceOf[A]; val i = elements; while (i.hasNext) last = i.next; @@ -34,23 +41,22 @@ trait SortedSet[A] extends scala.collection.SortedSet[A] with jcl.Set[A] with So else last; } override def rangeImpl(from : Option[A], until : Option[A]) : SortedSet[A] = new Range(from, until); - trait Projection extends super.Projection { - override def filter(p : A => Boolean) : SortedSet[A] = new Filter(p); + override def projection : SortedSet.Projection[A] = new SortedSet.Projection[A] { + override def compare(a0 : A, a1 : A) = SortedSet.this.compare(a0, a1) + override def add(a: A): Boolean = SortedSet.this.add(a) + override def elements = SortedSet.this.elements + override def size = SortedSet.this.size + override def has(a : A) : Boolean = SortedSet.this.has(a) } - override def projection : Projection = new Projection {} - protected class Filter(p : A => Boolean) extends super.Filter(p) with SortedSet[A] { + protected class Filter(p : A => Boolean) extends super.Filter(p) with SortedSet.Projection[A] { def compare(a0 : A, a1 : A) : Int = SortedSet.this.compare(a0, a1); - trait Projection extends super[Filter].Projection with super[SortedSet].Projection { - override def filter(p0 : A => Boolean) = SortedSet.this.projection.filter(k => p(k) && p0(k)); - } - override def projection : Projection = new Projection {}; + override def filter(p0 : A => Boolean) = SortedSet.this.projection.filter(k => p(k) && p0(k)); } - protected class Range(from : Option[A], until : Option[A]) extends Filter(key => { (from == None || (compare(from.get,key) <= 0)) && (until == None || (compare(key,until.get) < 0)); - }) with SortedSet[A] { + }) with SortedSet.Projection[A] { if (from == None && until == None) throw new IllegalArgumentException; if (from != None && until != None && !(SortedSet.this.compare(from.get, until.get) < 0)) throw new IllegalArgumentException; diff --git a/src/library/scala/collection/jcl/SortedSetWrapper.scala b/src/library/scala/collection/jcl/SortedSetWrapper.scala index f923a14019..0021d09031 100644 --- a/src/library/scala/collection/jcl/SortedSetWrapper.scala +++ b/src/library/scala/collection/jcl/SortedSetWrapper.scala @@ -20,11 +20,11 @@ package scala.collection.jcl; * @author Sean McDirmid */ trait SortedSetWrapper[A] extends SortedSet[A] with SetWrapper[A] { - protected def underlying : java.util.SortedSet; + def underlying : java.util.SortedSet; /** delegates to the comparator of the underlying Java sorted set */ override def compare(a0 : A, a1 : A) = underlying.comparator.compare(a0, a1); - override def first = underlying.first.asInstanceOf[A]; - override def last = underlying.last .asInstanceOf[A]; + override def firstKey = underlying.first.asInstanceOf[A]; + override def lastKey = underlying.last .asInstanceOf[A]; override def rangeImpl(from : Option[A], until : Option[A]) : SortedSet[A] = new Range(from,until); protected class Range(from : Option[A], until : Option[A]) extends super.Range(from, until) with SortedSetWrapper[A] { val underlying = Tuple2(from,until) match { diff --git a/src/library/scala/collection/jcl/Tests.scala b/src/library/scala/collection/jcl/Tests.scala index 3fab33be2f..39683323fa 100644 --- a/src/library/scala/collection/jcl/Tests.scala +++ b/src/library/scala/collection/jcl/Tests.scala @@ -33,7 +33,7 @@ private[jcl] object Tests { Console.println(fset); fset += "cd"; Console.println(set); - set.projection.map(.length).retain(x => x == 3); + //set.projection.map(.length).retain(x => x == 3); Console.println(set); Console.println(rset); Console.println(fset); @@ -66,9 +66,9 @@ private[jcl] object Tests { case e : IllegalArgumentException => case _ => throw new Error; } - val mset : MutableIterable[Int] = set.projection.map(s => s.length); - Console.println(mset); - mset.retain(n => n < 5); + //val mset : MutableIterable[Int] = set // set.projection.map(s => s.length); + //Console.println(mset); + //mset.retain(n => n < 5); Console.println(set); val set1 = new HashSet[String] + "1" + "2" + "3"; set ++ (set1); diff --git a/src/library/scala/collection/mutable/ArrayBuffer.scala b/src/library/scala/collection/mutable/ArrayBuffer.scala index e32f8aecb9..0b6077492f 100644 --- a/src/library/scala/collection/mutable/ArrayBuffer.scala +++ b/src/library/scala/collection/mutable/ArrayBuffer.scala @@ -22,7 +22,6 @@ import Predef._ */ @serializable class ArrayBuffer[A] extends Buffer[A] with ResizableArray[A] { - /** Appends a single element to this buffer and returns * the identity of the buffer. * diff --git a/src/library/scala/collection/mutable/BufferProxy.scala b/src/library/scala/collection/mutable/BufferProxy.scala index fddda07980..31b94f1ea5 100644 --- a/src/library/scala/collection/mutable/BufferProxy.scala +++ b/src/library/scala/collection/mutable/BufferProxy.scala @@ -26,7 +26,7 @@ trait BufferProxy[A] extends Buffer[A] with Proxy { def length: Int = self.length - def elements: Iterator[A] = self.elements + override def elements: Iterator[A] = self.elements def apply(n: Int): A = self.apply(n) diff --git a/src/library/scala/collection/mutable/ListBuffer.scala b/src/library/scala/collection/mutable/ListBuffer.scala index cce39bcfcc..7138fdd677 100644 --- a/src/library/scala/collection/mutable/ListBuffer.scala +++ b/src/library/scala/collection/mutable/ListBuffer.scala @@ -22,7 +22,7 @@ import Predef._ @serializable final class ListBuffer[A] extends Buffer[A] { private var start: List[A] = Nil - private var last: ::[A] = _ + private var last0: ::[A] = _ private var exported: boolean = false /** Prepends a single element to this buffer. @@ -33,7 +33,7 @@ final class ListBuffer[A] extends Buffer[A] { def +: (x: A): Buffer[A] = { if (exported) copy() val newElem = new scala.:: (x, start) - if (start.isEmpty) last = newElem + if (start.isEmpty) last0 = newElem start = newElem this } @@ -45,12 +45,12 @@ final class ListBuffer[A] extends Buffer[A] { override def += (x: A): unit = { if (exported) copy() if (start.isEmpty) { - last = new scala.:: (x, Nil) - start = last + last0 = new scala.:: (x, Nil) + start = last0 } else { - val last1 = last - last = new scala.:: (x, Nil) - last1.tl = last + val last1 = last0 + last0 = new scala.:: (x, Nil) + last1.tl = last0 } } @@ -75,8 +75,8 @@ final class ListBuffer[A] extends Buffer[A] { while (!cursor.tail.isEmpty && cursor.tail.head != x) { cursor = cursor.tail } if (!cursor.tail.isEmpty) { val z = cursor.asInstanceOf[scala.::[A]] - if(z.tl == last) - last = z + if(z.tl == last0) + last0 = z z.tl = cursor.tail.tail } } @@ -95,7 +95,7 @@ final class ListBuffer[A] extends Buffer[A] { */ def prependToList(xs: List[A]): List[A] = if (start.isEmpty) xs - else { last.tl = xs; toList } + else { last0.tl = xs; toList } /** Clears the buffer contents. */ @@ -107,7 +107,7 @@ final class ListBuffer[A] extends Buffer[A] { /** Copy contents of this buffer */ private def copy() = { var cursor = start - val limit = last.tail + val limit = last0.tail clear while (cursor ne limit) { this += cursor.head @@ -146,7 +146,7 @@ final class ListBuffer[A] extends Buffer[A] { if (exported) copy() if (n == 0) { val newElem = new scala.:: (x, start.tail); - if (last eq start) last = newElem + if (last0 eq start) last0 = newElem start = newElem } else { var cursor = start; @@ -156,7 +156,7 @@ final class ListBuffer[A] extends Buffer[A] { i = i + 1 } val newElem = new scala.:: (x, cursor.tail.tail) - if (last eq cursor.tail) last = newElem + if (last0 eq cursor.tail) last0 = newElem cursor.asInstanceOf[scala.::[A]].tl = newElem } } catch { @@ -177,7 +177,7 @@ final class ListBuffer[A] extends Buffer[A] { if (n == 0) { while (!elems.isEmpty) { val newElem = new scala.:: (elems.head, start) - if (start.isEmpty) last = newElem + if (start.isEmpty) last0 = newElem start = newElem elems = elems.tail } @@ -190,7 +190,7 @@ final class ListBuffer[A] extends Buffer[A] { } while (!elems.isEmpty) { val newElem = new scala.:: (elems.head, cursor.tail) - if (cursor.tail.isEmpty) last = newElem + if (cursor.tail.isEmpty) last0 = newElem cursor.asInstanceOf[scala.::[A]].tl = newElem elems = elems.tail } @@ -221,7 +221,7 @@ final class ListBuffer[A] extends Buffer[A] { i = i + 1 } old = cursor.tail.head - if (last eq cursor.tail) last = cursor.asInstanceOf[scala.::[A]] + if (last0 eq cursor.tail) last0 = cursor.asInstanceOf[scala.::[A]] cursor.asInstanceOf[scala.::[A]].tl = cursor.tail.tail } old @@ -244,7 +244,7 @@ final class ListBuffer[A] extends Buffer[A] { */ override def elements = new Iterator[A] { var cursor: List[A] = null - def hasNext: Boolean = !start.isEmpty && cursor != last + def hasNext: Boolean = !start.isEmpty && cursor != last0 def next(): A = if (!hasNext) { throw new NoSuchElementException("next on empty Iterator") diff --git a/src/library/scala/collection/mutable/MutableList.scala b/src/library/scala/collection/mutable/MutableList.scala index 84166c47bd..958165a095 100644 --- a/src/library/scala/collection/mutable/MutableList.scala +++ b/src/library/scala/collection/mutable/MutableList.scala @@ -23,8 +23,8 @@ package scala.collection.mutable */ trait MutableList[A] extends Seq[A] with PartialFunction[Int, A] { - protected var first: LinkedList[A] = null - protected var last: LinkedList[A] = null + protected var first0: LinkedList[A] = null + protected var last0: LinkedList[A] = null protected var len: Int = 0 /** Returns the length of this list. @@ -42,12 +42,12 @@ trait MutableList[A] extends Seq[A] with PartialFunction[Int, A] { /** Returns the <code>n</code>th element of this list or <code>None</code> * if this element does not exist. */ - def get(n: Int): Option[A] = first.get(n) + def get(n: Int): Option[A] = first0.get(n) protected def prependElem(elem: A): Unit = { - first = new LinkedList[A](elem, first) + first0 = new LinkedList[A](elem, first0) if (len == 0) - last = first + last0 = first0 len = len + 1 } @@ -55,26 +55,28 @@ trait MutableList[A] extends Seq[A] with PartialFunction[Int, A] { if (len == 0) prependElem(elem) else { - last.next = new LinkedList[A](elem, null) - last = last.next + last0.next = new LinkedList[A](elem, null) + last0 = last0.next len = len + 1 } protected def reset() { - first = null - last = null + first0 = null + last0 = null len = 0 } /** Returns an iterator over all elements of this list. */ - def elements: Iterator[A] = - if (first eq null) Nil.elements else first.elements + override def elements: Iterator[A] = + if (first0 eq null) Nil.elements else first0.elements + + override def last = last0.elem /** Returns an instance of <code>scala.List</code> containing the same * sequence of elements. */ - override def toList: List[A] = if (first eq null) Nil else first.toList + override def toList: List[A] = if (first0 eq null) Nil else first0.toList override protected def stringPrefix: String = "MutableList" } diff --git a/src/library/scala/collection/mutable/Queue.scala b/src/library/scala/collection/mutable/Queue.scala index ccb829171b..2b4138caa2 100644 --- a/src/library/scala/collection/mutable/Queue.scala +++ b/src/library/scala/collection/mutable/Queue.scala @@ -27,7 +27,7 @@ class Queue[A] extends MutableList[A] { * * @return true, iff there is no element in the queue. */ - override def isEmpty: Boolean = (first eq null) + override def isEmpty: Boolean = (first0 eq null) /** Inserts a single element at the end of the queue. * @@ -64,12 +64,12 @@ class Queue[A] extends MutableList[A] { * @return the first element of the queue. */ def dequeue(): A = - if (first eq null) + if (first0 eq null) throw new NoSuchElementException("queue empty") else { - val res = first.elem - first = first.next - if (first eq null) last = null + val res = first0.elem + first0 = first0.next + if (first0 eq null) last0 = null len = len - 1 res } @@ -81,20 +81,20 @@ class Queue[A] extends MutableList[A] { * @return the first element of the queue for which p yields true */ def dequeueFirst(p: A => Boolean): Option[A] = - if (first eq null) + if (first0 eq null) None - else if (p(first.elem)) { - val res: Option[A] = Some(first.elem) - first = first.next + else if (p(first0.elem)) { + val res: Option[A] = Some(first0.elem) + first0 = first0.next len = len - 1 - if (first eq null) { - last = null - } else if (first.next eq null) { - last = first + if (first0 eq null) { + last0 = null + } else if (first0.next eq null) { + last0 = first0 } res } else - extractFirst(first, p) match { + extractFirst(first0, p) match { case None => None case Some(cell) => Some(cell.elem) } @@ -107,21 +107,21 @@ class Queue[A] extends MutableList[A] { * p yields true. */ def dequeueAll(p: A => Boolean): Seq[A] = { - if (first eq null) + if (first0 eq null) Seq.empty else { val res = new ArrayBuffer[A] - while ((first ne null) && p(first.elem)) { - res += first.elem - first = first.next + while ((first0 ne null) && p(first0.elem)) { + res += first0.elem + first0 = first0.next len = len - 1 - if (first eq null) { - last = null - } else if (first.next eq null) { - last = first + if (first0 eq null) { + last0 = null + } else if (first0.next eq null) { + last0 = first0 } } - var cell: Option[LinkedList[A]] = extractFirst(first, p) + var cell: Option[LinkedList[A]] = extractFirst(first0, p) while (!cell.isEmpty) { res += cell.get.elem cell = extractFirst(cell.get, p) @@ -143,7 +143,7 @@ class Queue[A] extends MutableList[A] { val res: Option[LinkedList[A]] = Some(cell.next) cell.next = cell.next.next if (cell.next eq null) - last = cell + last0 = cell len = len - 1 res } @@ -155,7 +155,7 @@ class Queue[A] extends MutableList[A] { * * @return the first element. */ - def front: A = first.elem + def front: A = first0.elem /** Removes all elements from the queue. After this operation is completed, * the queue will be empty. diff --git a/src/library/scala/collection/mutable/ResizableArray.scala b/src/library/scala/collection/mutable/ResizableArray.scala index 21f8783bea..c6bd2ebeb0 100644 --- a/src/library/scala/collection/mutable/ResizableArray.scala +++ b/src/library/scala/collection/mutable/ResizableArray.scala @@ -18,11 +18,15 @@ package scala.collection.mutable * @author Matthias Zenger, Burak Emir * @version 1.0, 03/05/2004 */ -trait ResizableArray[A] extends Seq[A] { +trait ResizableArray[A] extends RandomAccessSeq[A] { protected val initialSize: Int = 16 protected var array: Array[A] = new Array[A](initialSize) - protected var size0: Int = 0 + private var size1 : Int = 0 + protected def size0 : Int = size1 + protected def size0_=(sz : Int) = { + size1 = sz + } //########################################################################## // implement/override methods of Seq[A] @@ -33,6 +37,13 @@ trait ResizableArray[A] extends Seq[A] { def apply(i: Int) = array(i) + /** remove elements of this array at indices after <code>sz</code> + */ + def reduceToSize(sz : Int) = { + if (sz > size0) throw new IllegalArgumentException + size0 = sz + } + /** Fills the given array <code>xs</code> with the elements of * this sequence starting at position <code>start</code>. * @@ -50,7 +61,7 @@ trait ResizableArray[A] extends Seq[A] { /** Returns a new iterator over all elements of this resizable array. */ - def elements: Iterator[A] = new Iterator[A] { + override def elements: Iterator[A] = new Iterator[A] { var i = 0 def hasNext: Boolean = i < size0 def next(): A = { i = i + 1; array(i - 1) } diff --git a/src/library/scala/collection/mutable/SingleLinkedList.scala b/src/library/scala/collection/mutable/SingleLinkedList.scala index 2fc51ad9a2..80b4b6efe3 100644 --- a/src/library/scala/collection/mutable/SingleLinkedList.scala +++ b/src/library/scala/collection/mutable/SingleLinkedList.scala @@ -48,7 +48,7 @@ abstract class SingleLinkedList[A, This >: Null <: SingleLinkedList[A, This]] else if (next eq null) None else next.get(n - 1) - def elements: Iterator[A] = new Iterator[A] { + override def elements: Iterator[A] = new Iterator[A] { var elems = SingleLinkedList.this def hasNext = (elems ne null) def next = { diff --git a/src/library/scala/collection/mutable/Stack.scala b/src/library/scala/collection/mutable/Stack.scala index 7f01e7e9d5..9fb44e6528 100644 --- a/src/library/scala/collection/mutable/Stack.scala +++ b/src/library/scala/collection/mutable/Stack.scala @@ -25,7 +25,7 @@ class Stack[A] extends MutableList[A] { * * @return true, iff there is no element on the stack */ - override def isEmpty: Boolean = (first eq null) + override def isEmpty: Boolean = (first0 eq null) /** Pushes a single element on top of the stack. * @@ -64,8 +64,8 @@ class Stack[A] extends MutableList[A] { * @return the top element */ def top: A = - if (first eq null) throw new NoSuchElementException("stack empty") - else first.elem + if (first0 eq null) throw new NoSuchElementException("stack empty") + else first0.elem /** Removes the top element from the stack. * @@ -73,9 +73,9 @@ class Stack[A] extends MutableList[A] { * @return the top element */ def pop(): A = - if (first ne null) { - val res = first.elem - first = first.next + if (first0 ne null) { + val res = first0.elem + first0 = first0.next len = len - 1; res } else diff --git a/src/library/scala/concurrent/Process.scala b/src/library/scala/concurrent/Process.scala index 1804c3a984..421e82e7fe 100644 --- a/src/library/scala/concurrent/Process.scala +++ b/src/library/scala/concurrent/Process.scala @@ -55,6 +55,7 @@ object Process { } +@deprecated class Process(body: => Unit) extends Actor() { private var exitReason: AnyRef = null private var links: List[Process] = Nil diff --git a/src/library/scala/runtime/BoxedArray.scala b/src/library/scala/runtime/BoxedArray.scala index c25b614882..2ce29ea5d9 100644 --- a/src/library/scala/runtime/BoxedArray.scala +++ b/src/library/scala/runtime/BoxedArray.scala @@ -43,7 +43,7 @@ abstract class BoxedArray extends Seq[Any] { override def isDefinedAt(x: Int): Boolean = 0 <= x && x < length - def elements = new Iterator[Any] { + override def elements = new Iterator[Any] { var index = 0 def hasNext: Boolean = index < length def next(): Any = { val i = index; index = i + 1; apply(i) } diff --git a/src/library/scala/runtime/RichChar.scala b/src/library/scala/runtime/RichChar.scala index f6a8fd26bc..d06aa62a57 100644 --- a/src/library/scala/runtime/RichChar.scala +++ b/src/library/scala/runtime/RichChar.scala @@ -52,23 +52,20 @@ final class RichChar(x: Char) extends Proxy with Ordered[Char] { def toLowerCase: Char = Character.toLowerCase(x) def toUpperCase: Char = Character.toUpperCase(x) - private class SequentialCharIterator(limit: Char) extends BufferedIterator[Char] { + /** Create an Iterator[Char] over the characters from 'x' to 'y' - 1 + */ + def until(limit: Char): Iterator[Char] = new Iterator[Char] { private var ch = x def hasNext: Boolean = ch < limit - def next(): Char = + def next: Char = if (hasNext) { val j = ch; ch = (ch + 1).toChar; j } else throw new NoSuchElementException("next on empty iterator") - def head: Char = - if (hasNext) ch - else throw new NoSuchElementException("head on empty iterator") } - /** Create an Iterator[Char] over the characters from 'x' to 'y' - 1 - */ - def until(y: Char): Iterator[Char] = new SequentialCharIterator(y) + //def until(y: Char): Iterator[Char] = to(y) /** Create an Iterator[Char] over the characters from 'x' to 'y' */ - def to(y: Char): Iterator[Char] = new SequentialCharIterator((y + 1).toChar) + def to(y: Char): Iterator[Char] = until((y + 1).toChar) } diff --git a/src/library/scala/runtime/RichString.scala b/src/library/scala/runtime/RichString.scala index 6786e1e692..17acf97ff1 100644 --- a/src/library/scala/runtime/RichString.scala +++ b/src/library/scala/runtime/RichString.scala @@ -21,7 +21,7 @@ final class RichString(val self: String) extends Proxy with Seq[Char] with Order // Seq[Char] def length = self.length - def elements = Iterator.fromString(self) + override def elements = Iterator.fromString(self) /** Retrieve the n-th character of the string * diff --git a/src/library/scala/xml/NodeSeq.scala b/src/library/scala/xml/NodeSeq.scala index 3bed37b5c4..d4c9d6bac4 100644 --- a/src/library/scala/xml/NodeSeq.scala +++ b/src/library/scala/xml/NodeSeq.scala @@ -35,7 +35,7 @@ abstract class NodeSeq extends Seq[Node] { import NodeSeq.view // import view magic for NodeSeq wrappers def theSeq: Seq[Node] def length = theSeq.length - def elements = theSeq.elements + override def elements = theSeq.elements def apply(i: Int): Node = theSeq.apply(i) def apply(f: Node => Boolean): NodeSeq = filter(f) |