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
|
/*
* This program is free software; you can redistribute it and/or modify it under the
* terms of the GNU Lesser General Public License, version 2.1 as published by the Free Software
* Foundation.
*
* You should have received a copy of the GNU Lesser General Public License along with this
* program; if not, you can obtain a copy at http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
* or from the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*
* This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU Lesser General Public License for more details.
*
* Copyright (c) 2007 - 2009 Pentaho Corporation and Contributors. All rights reserved.
*/
package org.pentaho.reporting.libraries.base.util;
import java.io.Serializable;
import java.util.Arrays;
import java.util.EmptyStackException;
/**
* A very simple unsynchronized stack. This one is faster than the java.util-Version, which is based on the
* synchronized java.util.Vector class.
*
* @author Thomas Morgner
*/
public final class FastStack implements Serializable, Cloneable
{
/**
* The contents of the stack. The array is likely to be larger than the actual size of the stack, so use
* <code>size</code> to get the last accessible item.
*/
private Object[] contents;
/**
* The current fill-level of the stack.
*/
private int size;
/**
* The initial size of the stack, but also the growth-factor.
*/
private int initialSize;
/**
* A constant for serialization support.
*/
private static final long serialVersionUID = 3111917250800511580L;
/**
* Creates a new stack with an initial size and growth of 10 items.
*/
public FastStack()
{
initialSize = 10;
}
/**
* Creates a new stack with an initial size and growth as specified.
*
* @param size the initial size and growth.
*/
public FastStack(final int size)
{
initialSize = Math.max(1, size);
}
/**
* Checks whether the stack is empty.
* @return true, if the stack is empty, false otherwise.
*/
public boolean isEmpty()
{
return size == 0;
}
/**
* Returns the number of elements in the stack.
*
* @return the stack size.
*/
public int size()
{
return size;
}
/**
* Pushes a new object on the stack. Null-references are allowed.
*
* @param o the object, maybe null.
*/
public void push(final Object o)
{
if (contents == null)
{
contents = new Object[initialSize];
contents[0] = o;
size = 1;
return;
}
final int oldSize = size;
size += 1;
if (contents.length == size)
{
// grow ..
final Object[] newContents = new Object[size + initialSize];
System.arraycopy(contents, 0, newContents, 0, size);
this.contents = newContents;
}
this.contents[oldSize] = o;
}
/**
* Loads the top-most element from the stack, without removing it from the stack.
*
* @return the top-most object.
* @throws EmptyStackException if the stack is empty.
*/
public Object peek()
{
if (size == 0)
{
throw new EmptyStackException();
}
return contents[size - 1];
}
/**
* Loads the top-most element from the stack and removes it from the stack at the same time.
*
* @return the top-most object.
* @throws EmptyStackException if the stack is empty.
*/
public Object pop()
{
if (size == 0)
{
throw new EmptyStackException();
}
size -= 1;
final Object retval = contents[size];
contents[size] = null;
return retval;
}
/**
* Creates a shallow copy of the stack.
*
* @return the cloned stack.
*/
public Object clone()
{
try
{
final FastStack stack = (FastStack) super.clone();
if (contents != null)
{
stack.contents = (Object[]) contents.clone();
}
return stack;
}
catch (final CloneNotSupportedException cne)
{
throw new IllegalStateException("Clone not supported? Why?");
}
}
/**
* Removes all contents from the stack.
*/
public void clear()
{
if (contents != null)
{
Arrays.fill(contents, 0, size, null);
}
this.size = 0;
}
/**
* Returns the element from the stack at the given index-position.
*
* @param index the element's index.
* @return the object.
* @throws IndexOutOfBoundsException if the index given is greater than the number of objects in the stack.
*/
public Object get(final int index)
{
if (index >= size)
{
throw new IndexOutOfBoundsException();
}
return contents[index];
}
}
|
