001: /*
002: * Copyright 2001-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections;
017:
018: import java.util.ArrayList;
019: import java.util.EmptyStackException;
020:
021: /**
022: * An implementation of the {@link java.util.Stack} API that is based on an
023: * <code>ArrayList</code> instead of a <code>Vector</code>, so it is not
024: * synchronized to protect against multi-threaded access. The implementation
025: * is therefore operates faster in environments where you do not need to
026: * worry about multiple thread contention.
027: * <p>
028: * The removal order of an <code>ArrayStack</code> is based on insertion
029: * order: The most recently added element is removed first. The iteration
030: * order is <i>not</i> the same as the removal order. The iterator returns
031: * elements from the bottom up, whereas the {@link #remove()} method removes
032: * them from the top down.
033: * <p>
034: * Unlike <code>Stack</code>, <code>ArrayStack</code> accepts null entries.
035: *
036: * @see java.util.Stack
037: * @since Commons Collections 1.0
038: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
039: *
040: * @author Craig R. McClanahan
041: * @author Paul Jack
042: * @author Stephen Colebourne
043: */
044: public class ArrayStack extends ArrayList implements Buffer {
045:
046: /** Ensure serialization compatibility */
047: private static final long serialVersionUID = 2130079159931574599L;
048:
049: /**
050: * Constructs a new empty <code>ArrayStack</code>. The initial size
051: * is controlled by <code>ArrayList</code> and is currently 10.
052: */
053: public ArrayStack() {
054: super ();
055: }
056:
057: /**
058: * Constructs a new empty <code>ArrayStack</code> with an initial size.
059: *
060: * @param initialSize the initial size to use
061: * @throws IllegalArgumentException if the specified initial size
062: * is negative
063: */
064: public ArrayStack(int initialSize) {
065: super (initialSize);
066: }
067:
068: /**
069: * Return <code>true</code> if this stack is currently empty.
070: * <p>
071: * This method exists for compatibility with <code>java.util.Stack</code>.
072: * New users of this class should use <code>isEmpty</code> instead.
073: *
074: * @return true if the stack is currently empty
075: */
076: public boolean empty() {
077: return isEmpty();
078: }
079:
080: /**
081: * Returns the top item off of this stack without removing it.
082: *
083: * @return the top item on the stack
084: * @throws EmptyStackException if the stack is empty
085: */
086: public Object peek() throws EmptyStackException {
087: int n = size();
088: if (n <= 0) {
089: throw new EmptyStackException();
090: } else {
091: return get(n - 1);
092: }
093: }
094:
095: /**
096: * Returns the n'th item down (zero-relative) from the top of this
097: * stack without removing it.
098: *
099: * @param n the number of items down to go
100: * @return the n'th item on the stack, zero relative
101: * @throws EmptyStackException if there are not enough items on the
102: * stack to satisfy this request
103: */
104: public Object peek(int n) throws EmptyStackException {
105: int m = (size() - n) - 1;
106: if (m < 0) {
107: throw new EmptyStackException();
108: } else {
109: return get(m);
110: }
111: }
112:
113: /**
114: * Pops the top item off of this stack and return it.
115: *
116: * @return the top item on the stack
117: * @throws EmptyStackException if the stack is empty
118: */
119: public Object pop() throws EmptyStackException {
120: int n = size();
121: if (n <= 0) {
122: throw new EmptyStackException();
123: } else {
124: return remove(n - 1);
125: }
126: }
127:
128: /**
129: * Pushes a new item onto the top of this stack. The pushed item is also
130: * returned. This is equivalent to calling <code>add</code>.
131: *
132: * @param item the item to be added
133: * @return the item just pushed
134: */
135: public Object push(Object item) {
136: add(item);
137: return item;
138: }
139:
140: /**
141: * Returns the one-based position of the distance from the top that the
142: * specified object exists on this stack, where the top-most element is
143: * considered to be at distance <code>1</code>. If the object is not
144: * present on the stack, return <code>-1</code> instead. The
145: * <code>equals()</code> method is used to compare to the items
146: * in this stack.
147: *
148: * @param object the object to be searched for
149: * @return the 1-based depth into the stack of the object, or -1 if not found
150: */
151: public int search(Object object) {
152: int i = size() - 1; // Current index
153: int n = 1; // Current distance
154: while (i >= 0) {
155: Object current = get(i);
156: if ((object == null && current == null)
157: || (object != null && object.equals(current))) {
158: return n;
159: }
160: i--;
161: n++;
162: }
163: return -1;
164: }
165:
166: /**
167: * Returns the element on the top of the stack.
168: *
169: * @return the element on the top of the stack
170: * @throws BufferUnderflowException if the stack is empty
171: */
172: public Object get() {
173: int size = size();
174: if (size == 0) {
175: throw new BufferUnderflowException();
176: }
177: return get(size - 1);
178: }
179:
180: /**
181: * Removes the element on the top of the stack.
182: *
183: * @return the removed element
184: * @throws BufferUnderflowException if the stack is empty
185: */
186: public Object remove() {
187: int size = size();
188: if (size == 0) {
189: throw new BufferUnderflowException();
190: }
191: return remove(size - 1);
192: }
193:
194: }
|