diff options
Diffstat (limited to 'src/library/scala/collection/immutable')
11 files changed, 58 insertions, 19 deletions
diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala index 9b801f26cb..8fa23c3ddf 100644 --- a/src/library/scala/collection/immutable/BitSet.scala +++ b/src/library/scala/collection/immutable/BitSet.scala @@ -14,6 +14,7 @@ package immutable import generic._ import BitSetLike.{LogWL, updateArray} +import mutable.{ Builder, AddingBuilder } /** A class for immutable bitsets. * $bitsetinfo @@ -60,10 +61,12 @@ abstract class BitSet extends Set[Int] * @define coll immutable bitset */ object BitSet extends BitSetFactory[BitSet] { - /** The empty bitset */ val empty: BitSet = new BitSet1(0L) + /** An adding builder for immutable Sets. */ + def newBuilder: Builder[Int, BitSet] = new AddingBuilder[Int, BitSet](empty) + /** $bitsetCanBuildFrom */ implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom diff --git a/src/library/scala/collection/immutable/DefaultMap.scala b/src/library/scala/collection/immutable/DefaultMap.scala index 667d86d352..4f36679119 100755 --- a/src/library/scala/collection/immutable/DefaultMap.scala +++ b/src/library/scala/collection/immutable/DefaultMap.scala @@ -50,7 +50,7 @@ trait DefaultMap[A, +B] extends Map[A, B] { self => */ override def - (key: A): Map[A, B] = { val b = newBuilder - b ++= this filter (key !=) + for (kv <- this ; if kv._1 != key) b += kv b.result } } diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala index 68da0cef50..481b1c3204 100644 --- a/src/library/scala/collection/immutable/HashSet.scala +++ b/src/library/scala/collection/immutable/HashSet.scala @@ -88,7 +88,7 @@ class HashSet[A] extends Set[A] * @define mayNotTerminateInf * @define willNotTerminateInf */ -object HashSet extends SetFactory[HashSet] { +object HashSet extends ImmutableSetFactory[HashSet] { /** $setCanBuildFromInfo */ implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, HashSet[A]] = setCanBuildFrom[A] override def empty[A]: HashSet[A] = EmptyHashSet.asInstanceOf[HashSet[A]] diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala index 4ce441ca55..f9937f6925 100644 --- a/src/library/scala/collection/immutable/List.scala +++ b/src/library/scala/collection/immutable/List.scala @@ -19,9 +19,9 @@ import annotation.tailrec /** A class for immutable linked lists representing ordered collections * of elements of type. * - * This class comes with two implementing case classes `scala.Nil` - * and `scala.::` that implement the abstract members `isEmpty`, - * `head` and `tail`. + * This class comes with two implementing case classes `scala.Nil` + * and `scala.::` that implement the abstract members `isEmpty`, + * `head` and `tail`. * * @author Martin Odersky and others * @version 2.8 diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala index 2a202df9ef..979fdff552 100644 --- a/src/library/scala/collection/immutable/ListSet.scala +++ b/src/library/scala/collection/immutable/ListSet.scala @@ -19,7 +19,7 @@ import generic._ * @define coll immutable list set * @since 1 */ -object ListSet extends SetFactory[ListSet] { +object ListSet extends ImmutableSetFactory[ListSet] { /** setCanBuildFromInfo */ implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] = setCanBuildFrom[A] override def empty[A] = new ListSet[A] diff --git a/src/library/scala/collection/immutable/Queue.scala b/src/library/scala/collection/immutable/Queue.scala index 7a903cb201..7ffceb6be8 100644 --- a/src/library/scala/collection/immutable/Queue.scala +++ b/src/library/scala/collection/immutable/Queue.scala @@ -14,6 +14,7 @@ package immutable import generic._ import mutable.{ Builder, ListBuffer } +import annotation.tailrec /** `Queue` objects implement data structures that allow to * insert and retrieve elements in a first-in-first-out (FIFO) manner. @@ -29,9 +30,9 @@ import mutable.{ Builder, ListBuffer } @serializable @SerialVersionUID(-7622936493364270175L) class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) - extends Seq[A] + extends LinearSeq[A] with GenericTraversableTemplate[A, Queue] - with SeqLike[A, Queue[A]] { + with LinearSeqLike[A, Queue[A]] { override def companion: GenericCompanion[Queue] = Queue @@ -42,7 +43,7 @@ class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) * @return the element at position `n` in this queue. * @throws Predef.NoSuchElementException if the queue is too short. */ - def apply(n: Int): A = { + override def apply(n: Int): A = { val len = out.length if (n < len) out.apply(n) else { @@ -62,9 +63,19 @@ class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) */ override def isEmpty: Boolean = in.isEmpty && out.isEmpty + override def head: A = + if (out.nonEmpty) out.head + else if (in.nonEmpty) in.last + else throw new NoSuchElementException("head on empty queue") + + override def tail: Queue[A] = + if (out.nonEmpty) new Queue(in, out.tail) + else if (in.nonEmpty) new Queue(Nil, in.reverse.tail) + else throw new NoSuchElementException("tail on empty queue") + /** Returns the length of the queue. */ - def length = in.length + out.length + override def length = in.length + out.length /** Creates a new queue with element added at the end * of the old queue. @@ -101,7 +112,7 @@ class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) * @param iter an iterable object */ def enqueue[B >: A](iter: Iterable[B]) = - new Queue(iter.iterator.toList.reverse ::: in, out) + new Queue(iter.toList.reverse ::: in, out) /** Returns a tuple with the first element in the queue, * and a new queue with this element removed. @@ -121,10 +132,7 @@ class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) * @throws Predef.NoSuchElementException * @return the first element. */ - def front: A = - if (!out.isEmpty) out.head - else if (!in.isEmpty) in.last - else throw new NoSuchElementException("front on empty queue") + def front: A = head /** Returns a string representation of this queue. */ diff --git a/src/library/scala/collection/immutable/Range.scala b/src/library/scala/collection/immutable/Range.scala index 8f1f7d58a6..0f20b1ea04 100644 --- a/src/library/scala/collection/immutable/Range.scala +++ b/src/library/scala/collection/immutable/Range.scala @@ -219,6 +219,23 @@ class Range(val start: Int, val end: Int, val step: Int) extends IndexedSeq[Int] object Range { private[immutable] val MAX_PRINT = 512 // some arbitrary value + /** Calculates the number of elements in a range given start, end, step, and + * whether or not it is inclusive. Returns -1 if parameters are invalid. + */ + def count(start: Int, end: Int, step: Int): Int = count(start, end, step, false) + def count(start: Int, end: Int, step: Int, isInclusive: Boolean): Int = { + def last = + if (isInclusive && step < 0) end - 1 + else if (isInclusive && step > 0) end + 1 + else end + + if (step == 0) -1 + else if (start == end) { if (isInclusive) 1 else 0 } + else if (end > start != step > 0) -1 + else if (step == 1 || step == -1) last - start + else ((last - start - 1) / step) + 1 + } + class Inclusive(start: Int, end: Int, step: Int) extends Range(start, end, step) { override def isInclusive = true override protected def copy(start: Int, end: Int, step: Int): Range = new Inclusive(start, end, step) diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala index 769ee37f6b..745b0034e8 100644 --- a/src/library/scala/collection/immutable/Set.scala +++ b/src/library/scala/collection/immutable/Set.scala @@ -36,7 +36,7 @@ trait Set[A] extends Iterable[A] * @define Coll immutable.Set * @define coll immutable set */ -object Set extends SetFactory[Set] { +object Set extends ImmutableSetFactory[Set] { /** $setCanBuildFromInfo */ implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Set[A]] = setCanBuildFrom[A] override def empty[A]: Set[A] = EmptySet.asInstanceOf[Set[A]] diff --git a/src/library/scala/collection/immutable/Stack.scala b/src/library/scala/collection/immutable/Stack.scala index 0323db7211..c90ab379af 100644 --- a/src/library/scala/collection/immutable/Stack.scala +++ b/src/library/scala/collection/immutable/Stack.scala @@ -48,7 +48,8 @@ object Stack extends SeqFactory[Stack] { * @define willNotTerminateInf */ @serializable @SerialVersionUID(1976480595012942526L) -class Stack[+A] protected (protected val elems: List[A]) extends LinearSeq[A] +class Stack[+A] protected (protected val elems: List[A]) + extends LinearSeq[A] with GenericTraversableTemplate[A, Stack] with LinearSeqOptimized[A, Stack[A]] { override def companion: GenericCompanion[Stack] = Stack diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 50fa07c2cf..fbda0b918b 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -104,6 +104,16 @@ self => loop(this, "") } + override def length: Int = { + var len = 0 + var left = this + while (!left.isEmpty) { + len += 1 + left = left.tail + } + len + } + /** It's an imperfect world, but at least we can bottle up the * imperfection in a capsule. */ diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala index 7b1f71df5b..18c65dd373 100644 --- a/src/library/scala/collection/immutable/TreeSet.scala +++ b/src/library/scala/collection/immutable/TreeSet.scala @@ -13,7 +13,7 @@ package scala.collection package immutable import generic._ -import mutable.{Builder, AddingBuilder} +import mutable.{ Builder, AddingBuilder } /** $factoryInfo * @define Coll immutable.TreeSet |