blob: 1c2d2f82369d8f765d89df73ff57230347b23d3d (
plain) (
blame)
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2006, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.immutable
//import Predef.NoSuchElementException
object Stack {
val Empty = new Stack[Nothing]
}
/** This class implements immutable stacks using a list-based data
* structure. Instances of <code>Stack</code> represent
* empty stacks; they can be either created by calling the constructor
* directly, or by applying the function <code>Stack.Empty</code>.
*
* @author Matthias Zenger
* @version 1.0, 10/07/2003
*/
@serializable
class Stack[+A] extends Seq[A] {
/** Checks if this stack is empty.
*
* @return true, iff there is no element on the stack.
*/
override def isEmpty: Boolean = true
/** Returns the size of this stack.
*
* @return the stack size.
*/
def length: Int = 0
/** Push an element on the stack.
*
* @deprecated Use the method <code>push</code> from now on.
*
* @param elem the element to push on the stack.
* @return the stack with the new element on top.
*/
@deprecated def +[B >: A](elem: B): Stack[B] = new Node(elem)
/** 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 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.
*
* @deprecated Use the method <code>push</code> from now on.
*
* @param elems the iterable object.
* @return the stack with the new elements on top.
*/
@deprecated def +[B >: A](elems: Iterable[B]): Stack[B] =
elems.foldLeft(this: Stack[B]){ (stack, elem) => stack + elem }
/** 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 iterable object.
* @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 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 iterable object.
* @return the stack with the new elements on top.
*/
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.
*
* @return the top element.
*/
def top: A = throw new NoSuchElementException("no element on stack")
/** Removes the top element from the stack.
*
* @return the new stack without the former top element.
*/
def pop: Stack[A] = throw new NoSuchElementException("no element on stack")
/** 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 = 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
* stack (LIFO order).
*
* @return an iterator over all stack elements.
*/
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 =
if (!hasNext) throw new NoSuchElementException("next on empty iterator")
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
* same elements in the same order.
*/
override def equals(obj: Any): Boolean = obj match {
case that: Stack[_] => this sameElements that
case _ => false
}
/** Returns the hash code for this stack.
*
* @return the hash code of the stack.
*/
override def hashCode(): Int = 0
/**
* Redefines the prefix of the string representation.
*/
override def stringPrefix: String = "Stack"
// Here comes true magic: covariant lists with implicit tail references
@serializable
protected class Node[+B >: A](elem: B) extends Stack[B] {
override def isEmpty: Boolean = false
override def length: Int = Stack.this.length + 1
override def top: B = elem
override def pop: Stack[B] = Stack.this
override def hashCode(): Int = elem.hashCode() + Stack.this.hashCode()
}
}
|
