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 | |
parent | c5de85e4329457b4d0b3019e0a8bb89c8132d7f1 (diff) | |
download | scala-ba0e0cdbf84df51272739b9faf91b8a5961d1989.tar.gz scala-ba0e0cdbf84df51272739b9faf91b8a5961d1989.tar.bz2 scala-ba0e0cdbf84df51272739b9faf91b8a5961d1989.zip |
unify mutable and immutable stacks behavior (#957)
-rw-r--r-- | src/compiler/scala/tools/nsc/backend/WorklistAlgorithm.scala | 4 | ||||
-rw-r--r-- | src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala | 1 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/Stack.scala | 57 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/Stack.scala | 43 | ||||
-rwxr-xr-x | test/files/jvm/serialization.check | 4 | ||||
-rw-r--r-- | test/files/run/collection-stacks.check | 14 | ||||
-rw-r--r-- | test/files/run/collection-stacks.scala | 38 |
7 files changed, 126 insertions, 35 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/WorklistAlgorithm.scala b/src/compiler/scala/tools/nsc/backend/WorklistAlgorithm.scala index 1b30e513eb..4405e7d665 100644 --- a/src/compiler/scala/tools/nsc/backend/WorklistAlgorithm.scala +++ b/src/compiler/scala/tools/nsc/backend/WorklistAlgorithm.scala @@ -8,7 +8,7 @@ package scala.tools.nsc.backend import scala.tools.nsc.ast._ -import scala.collection.mutable.MutableList +import scala.collection.mutable.Stack /** * Simple implementation of a worklist algorithm. A processing @@ -26,7 +26,7 @@ import scala.collection.mutable.MutableList */ trait WorklistAlgorithm { type Elem - type WList <: MutableList[Elem] + type WList = Stack[Elem] val worklist: WList diff --git a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala index 5a5b3ba36f..b619ff949e 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala @@ -27,7 +27,6 @@ trait Linearizers { self: ICodes => */ class NormalLinearizer extends Linearizer with WorklistAlgorithm { type Elem = BasicBlock; - type WList = Stack[Elem]; val worklist: WList = new Stack(); 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 } diff --git a/test/files/jvm/serialization.check b/test/files/jvm/serialization.check index 490be43d8a..f001f54c70 100755 --- a/test/files/jvm/serialization.check +++ b/test/files/jvm/serialization.check @@ -44,8 +44,8 @@ x = Queue(a,b,c) y = Queue(a,b,c) x equals y: true - y equals x: true -x = Stack(c, b, a) -y = Stack(c, b, a) +x = Stack(a, b, c) +y = Stack(a, b, c) x equals y: true - y equals x: true x = Map(42 -> FortyTwo) diff --git a/test/files/run/collection-stacks.check b/test/files/run/collection-stacks.check new file mode 100644 index 0000000000..fcb39c460c --- /dev/null +++ b/test/files/run/collection-stacks.check @@ -0,0 +1,14 @@ +1-2-3: true +1-2-3: true +apply +1: true +1: true +3: true +3: true +top +3: true +3: true +pop +1-2: true +3: true +1-2: true diff --git a/test/files/run/collection-stacks.scala b/test/files/run/collection-stacks.scala new file mode 100644 index 0000000000..ec557cb91d --- /dev/null +++ b/test/files/run/collection-stacks.scala @@ -0,0 +1,38 @@ +import scala.collection._ + +object Test extends Application { + def mutableStack[T](xs: T*): mutable.Stack[T] = { + val s = new mutable.Stack[T] + s.push(xs: _*) + s + } + + def immutableStack[T](xs: T*): immutable.Stack[T] = { + immutable.Stack.Empty push xs + } + + def check[T](expected: T, got: T) { + println(got + ": " + (expected == got)) + } + + // check #957 + check("1-2-3", immutableStack(1, 2, 3).elements.mkString("-")) + check("1-2-3", mutableStack(1, 2, 3).elements.mkString("-")) + + println("apply") + check(1, immutableStack(1, 2, 3).apply(0)) + check(1, mutableStack(1, 2, 3).apply(0)) + check(3, immutableStack(1, 2, 3).apply(2)) + check(3, mutableStack(1, 2, 3).apply(2)) + + println("top") + check(3, immutableStack(1, 2, 3).top) + check(3, mutableStack(1, 2, 3).top) + + println("pop") + check("1-2", immutableStack(1, 2, 3).pop.mkString("-")) + check(3, mutableStack(1, 2, 3).pop()) + check("1-2", { val s = mutableStack(1, 2, 3); s.pop(); s.toList.mkString("-") }) +} + +// vim: set ts=2 sw=2 et: |