diff options
author | Paul Phillips <paulp@improving.org> | 2010-04-20 18:07:43 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2010-04-20 18:07:43 +0000 |
commit | 22b66d601b790894827051bfe40fa5f0d119456a (patch) | |
tree | ee15a2da766ce83e494569918bc5c94d2d280e48 /src | |
parent | c5441dcc98a7c91d398cb43a35fcad9d07ad0da6 (diff) | |
download | scala-22b66d601b790894827051bfe40fa5f0d119456a.tar.gz scala-22b66d601b790894827051bfe40fa5f0d119456a.tar.bz2 scala-22b66d601b790894827051bfe40fa5f0d119456a.zip |
More fully integrate immutable.Queue into colle...
More fully integrate immutable.Queue into collections. Fixes issue with
return type of methods being Seq. Closes #3297, no review.
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/immutable/Queue.scala | 26 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/Stack.scala | 3 |
2 files changed, 19 insertions, 10 deletions
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/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 |