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
119
120
121
122
123
124
125
126
127
128
129
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala.collection
package immutable
import generic._
import mutable.{ ArrayBuffer, Builder }
/** $factoryInfo
* @define Coll immutable.Stack
* @define coll immutable stack
*/
object Stack extends SeqFactory[Stack] {
/** $genericCanBuildFromInfo */
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Stack[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]
def newBuilder[A]: Builder[A, Stack[A]] = new ArrayBuffer[A] mapResult (buf => new Stack(buf.toList))
@deprecated("Use Stack.empty instead", "2.8.0")
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.
*
* @tparam A the type of the elements contained in this stack.
*
* @author Matthias Zenger
* @version 1.0, 10/07/2003
* @since 1
* @define Coll immutable.Stack
* @define coll immutable stack
* @define orderDependent
* @define orderDependentFold
* @define mayNotTerminateInf
* @define willNotTerminateInf
*/
@SerialVersionUID(1976480595012942526L)
class Stack[+A] protected (protected val elems: List[A])
extends LinearSeq[A]
with GenericTraversableTemplate[A, Stack]
with LinearSeqOptimized[A, Stack[A]]
with Serializable {
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 traversable object onto
* the stack. The last element returned by the traversable 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 `(A, Stack[A])` 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(", ", ", ")")
}
|
