diff options
author | stepancheg <stepancheg@epfl.ch> | 2008-06-06 19:28:49 +0000 |
---|---|---|
committer | stepancheg <stepancheg@epfl.ch> | 2008-06-06 19:28:49 +0000 |
commit | ba0e0cdbf84df51272739b9faf91b8a5961d1989 (patch) | |
tree | 0cf4ec902c26024df1452ce5bd34e2215b87d0af /src/library | |
parent | c5de85e4329457b4d0b3019e0a8bb89c8132d7f1 (diff) | |
download | scala-ba0e0cdbf84df51272739b9faf91b8a5961d1989.tar.gz scala-ba0e0cdbf84df51272739b9faf91b8a5961d1989.tar.bz2 scala-ba0e0cdbf84df51272739b9faf91b8a5961d1989.zip |
unify mutable and immutable stacks behavior (#957)
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/immutable/Stack.scala | 57 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/Stack.scala | 43 |
2 files changed, 70 insertions, 30 deletions
diff --git a/src/library/scala/collection/immutable/Stack.scala b/src/library/scala/collection/immutable/Stack.scala index dfcb3823df..1c2d2f8236 100644 --- a/src/library/scala/collection/immutable/Stack.scala +++ b/src/library/scala/collection/immutable/Stack.scala @@ -57,6 +57,14 @@ class Stack[+A] extends Seq[A] { */ def push[B >: A](elem: B): Stack[B] = new Node(elem) + /** Push a sequence of elements onto the stack. The last element + * of the sequence will be on top of the new stack. + * + * @param elems the element sequence. + * @return the stack with the new elements on top. + */ + def push[B >: A](elems: B*): Stack[B] = this + elems + /** Push all elements provided by the given iterable object onto * the stack. The last element returned by the iterable object * will be on top of the new stack. @@ -77,15 +85,28 @@ class Stack[+A] extends Seq[A] { * @return the stack with the new elements on top. */ def push[B >: A](elems: Iterable[B]): Stack[B] = + this ++ elems + + /** Push all elements provided by the given iterator object onto + * the stack. The last element returned by the iterable object + * will be on top of the new stack. + * + * @param elems the iterator object. + * @return the stack with the new elements on top. + * @deprecated + */ + def ++[B >: A](elems: Iterator[B]): Stack[B] = elems.foldLeft(this: Stack[B]){ (stack, elem) => stack + elem } - /** Push a sequence of elements onto the stack. The last element - * of the sequence will be on top of the new stack. + /** Push all elements provided by the given iterable object onto + * the stack. The last element returned by the iterable object + * will be on top of the new stack. * - * @param elems the element sequence. + * @param elems the iterable object. * @return the stack with the new elements on top. */ - def push[B >: A](elems: B*): Stack[B] = this + elems + override def ++[B >: A](elems: Iterable[B]): Stack[B] = + this ++ elems.elements /** Returns the top element of the stack. An error is signaled if * there is no element on the stack. @@ -100,13 +121,17 @@ class Stack[+A] extends Seq[A] { */ def pop: Stack[A] = throw new NoSuchElementException("no element on stack") - /** Returns the n-th element of this stack. The top element has index - * 0, elements below are indexed with increasing numbers. + /** Returns the n-th element of this stack. The bottom element has index + * 0, elements above are indexed with increasing numbers. * * @param n the index number. * @return the n-th element on the stack. */ - def apply(n: Int): A = throw new NoSuchElementException("no element on stack") + def apply(n: Int): A = reverse.reverseApply(n) + + private def reverseApply(n: Int): A = + if (n > 0) pop.reverseApply(n - 1) + else top /** Returns an iterator over all elements on the stack. The iterator * issues elements in the reversed order they were inserted into the @@ -114,7 +139,9 @@ class Stack[+A] extends Seq[A] { * * @return an iterator over all stack elements. */ - override def elements: Iterator[A] = new Iterator[A] { + override def elements: Iterator[A] = reverse.reverseElements + + private def reverseElements: Iterator[A] = new Iterator[A] { var that: Stack[A] = Stack.this; def hasNext = !that.isEmpty; def next = @@ -122,6 +149,19 @@ class Stack[+A] extends Seq[A] { else { val res = that.top; that = that.pop; res } } + /** A stack consisting of all elements of this stack in reverse order. + */ + override def reverse: Stack[A] = { + // copy-paste from List.reverse + var result: Stack[A] = Stack.Empty + var these = this + while (!these.isEmpty) { + result = result push List(these.top) // see #978 + these = these.pop + } + result + } + /** Compares this stack with the given object. * * @return true, iff the two stacks are equal; i.e. they contain the @@ -150,7 +190,6 @@ class Stack[+A] extends Seq[A] { override def length: Int = Stack.this.length + 1 override def top: B = elem override def pop: Stack[B] = Stack.this - override def apply(n: Int): B = if (n > 0) Stack.this(n - 1) else elem override def hashCode(): Int = elem.hashCode() + Stack.this.hashCode() } diff --git a/src/library/scala/collection/mutable/Stack.scala b/src/library/scala/collection/mutable/Stack.scala index 8aa2f27115..b61a3659f8 100644 --- a/src/library/scala/collection/mutable/Stack.scala +++ b/src/library/scala/collection/mutable/Stack.scala @@ -19,19 +19,26 @@ package scala.collection.mutable * @version 1.1, 03/05/2004 */ @serializable @cloneable -class Stack[A] extends MutableList[A] with CloneableCollection { +class Stack[A] extends Seq[A] with CloneableCollection { + private var stack: immutable.Stack[A] = immutable.Stack.Empty /** Checks if the stack is empty. * * @return true, iff there is no element on the stack */ - override def isEmpty: Boolean = (first0 eq null) + override def isEmpty: Boolean = stack.isEmpty + + override def length = stack.length + + override def apply(index: Int) = stack(index) /** Pushes a single element on top of the stack. * * @param elem the element to push onto the stack */ - def +=(elem: A): Unit = prependElem(elem) + def +=(elem: A) { + this push elem + } /** Pushes all elements provided by an <code>Iterable</code> object * on top of the stack. The elements are pushed in the order they @@ -39,7 +46,7 @@ class Stack[A] extends MutableList[A] with CloneableCollection { * * @param iter an iterable object */ - def ++=(iter: Iterable[A]): Unit = this ++= iter.elements + def ++=(iter: Iterable[A]): Unit = stack = stack ++ iter /** Pushes all elements provided by an iterator * on top of the stack. The elements are pushed in the order they @@ -47,7 +54,7 @@ class Stack[A] extends MutableList[A] with CloneableCollection { * * @param iter an iterator */ - def ++=(it: Iterator[A]): Unit = it foreach { e => prependElem(e) } + def ++=(it: Iterator[A]): Unit = stack = stack ++ it /** Pushes a sequence of elements on top of the stack. The first element * is pushed first, etc. @@ -64,28 +71,24 @@ class Stack[A] extends MutableList[A] with CloneableCollection { * @return the top element */ def top: A = - if (first0 eq null) throw new NoSuchElementException("stack empty") - else first0.elem + stack.top /** Removes the top element from the stack. * * @throws Predef.NoSuchElementException * @return the top element */ - def pop(): A = - if (first0 ne null) { - val res = first0.elem - first0 = first0.next - len = len - 1; - res - } else - throw new NoSuchElementException("stack empty") + def pop(): A = { + val res = stack.top + stack = stack.pop + res + } /** * Removes all elements from the stack. After this operation completed, * the stack will be empty. */ - def clear(): Unit = reset + def clear(): Unit = stack = immutable.Stack.Empty /** Returns an iterator over all elements on the stack. This iterator * is stable with respect to state changes in the stack object; i.e. @@ -95,13 +98,13 @@ class Stack[A] extends MutableList[A] with CloneableCollection { * * @return an iterator over all stack elements. */ - override def elements: Iterator[A] = toList.elements + override def elements: Iterator[A] = stack.elements /** Creates a list of all stack elements in FIFO order. * * @return the created list. */ - override def toList: List[A] = super[MutableList].toList.reverse + override def toList: List[A] = stack.toList /** Checks if two stacks are structurally identical. * @@ -109,9 +112,7 @@ class Stack[A] extends MutableList[A] with CloneableCollection { */ override def equals(obj: Any): Boolean = obj match { case that: Stack[_] => - (this.elements zip that.elements) forall { - case (thiselem, thatelem) => thiselem == thatelem - } + this.stack == that.stack case _ => false } |