1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2010, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection
package immutable
import generic._
import mutable.{ ArrayBuffer, Builder }
object Stack extends SeqFactory[Stack] {
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Stack[A]] = new GenericCanBuildFrom[A]
def newBuilder[A]: Builder[A, Stack[A]] = new ArrayBuffer[A] mapResult (buf => new Stack(buf.toList))
@deprecated("Use Stack.empty instead")
val Empty: Stack[Nothing] = Stack()
}
/** This class implements immutable stacks using a list-based data
* structure.
*
* @note This class exists only for historical reason and as an
* analogue of mutable stacks
* Instead of an immutable stack you can just use a list.
*
* @author Matthias Zenger
* @version 1.0, 10/07/2003
* @since 1
*/
@serializable @SerialVersionUID(1976480595012942526L)
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
def this() = this(Nil)
/** Checks if this stack is empty.
*
* @return true, iff there is no element on the stack.
*/
override def isEmpty: Boolean = elems.isEmpty
override def head = elems.head
override def tail = new Stack(elems.tail)
/** Push an element on the stack.
*
* @param elem the element to push on the stack.
* @return the stack with the new element on top.
*/
def push[B >: A](elem: B): Stack[B] = new Stack(elem :: elems)
/** 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](elem1: B, elem2: B, elems: B*): Stack[B] =
this.push(elem1).push(elem2).pushAll(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.
*/
def pushAll[B >: A](xs: TraversableOnce[B]): Stack[B] =
((this: Stack[B]) /: xs.toIterator)(_ push _)
/** Returns the top element of the stack. An error is signaled if
* there is no element on the stack.
*
* @throws Predef.NoSuchElementException
* @return the top element.
*/
def top: A =
if (!isEmpty) elems.head
else throw new NoSuchElementException("top of empty stack")
/** Removes the top element from the stack.
* Note: should return <code>(A, Stack[A])</code> as for queues (mics)
*
* @throws Predef.NoSuchElementException
* @return the new stack without the former top element.
*/
def pop: Stack[A] =
if (!isEmpty) new Stack(elems.tail)
else throw new NoSuchElementException("pop of empty stack")
def pop2: (A, Stack[A]) =
if (!isEmpty) (elems.head, new Stack(elems.tail))
else throw new NoSuchElementException("pop of empty stack")
override def reverse: Stack[A] = new Stack(elems.reverse)
/** Returns an iterator over all elements on the stack. The iterator
* issues elements in the reversed order they were inserted into the
* stack (LIFO order).
*
* @return an iterator over all stack elements.
*/
override def iterator: Iterator[A] = elems.iterator
/** Returns a string representation of this stack.
*/
override def toString() = elems.mkString("Stack(", ", ", ")")
}
|