1. /*
  2. * Copyright 2001-2004 The Apache Software Foundation
  3. *
  4. * Licensed under the Apache License, Version 2.0 (the "License");
  5. * you may not use this file except in compliance with the License.
  6. * You may obtain a copy of the License at
  7. *
  8. * http://www.apache.org/licenses/LICENSE-2.0
  9. *
  10. * Unless required by applicable law or agreed to in writing, software
  11. * distributed under the License is distributed on an "AS IS" BASIS,
  12. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13. * See the License for the specific language governing permissions and
  14. * limitations under the License.
  15. */
  16. package org.apache.commons.collections;
  17. import java.util.ArrayList;
  18. import java.util.EmptyStackException;
  19. /**
  20. * An implementation of the {@link java.util.Stack} API that is based on an
  21. * <code>ArrayList</code> instead of a <code>Vector</code>, so it is not
  22. * synchronized to protect against multi-threaded access. The implementation
  23. * is therefore operates faster in environments where you do not need to
  24. * worry about multiple thread contention.
  25. * <p>
  26. * The removal order of an <code>ArrayStack</code> is based on insertion
  27. * order: The most recently added element is removed first. The iteration
  28. * order is <i>not</i> the same as the removal order. The iterator returns
  29. * elements from the bottom up, whereas the {@link #remove()} method removes
  30. * them from the top down.
  31. * <p>
  32. * Unlike <code>Stack</code>, <code>ArrayStack</code> accepts null entries.
  33. *
  34. * @see java.util.Stack
  35. * @since Commons Collections 1.0
  36. * @version $Revision: 1.17 $ $Date: 2004/02/18 01:15:42 $
  37. *
  38. * @author Craig R. McClanahan
  39. * @author Paul Jack
  40. * @author Stephen Colebourne
  41. */
  42. public class ArrayStack extends ArrayList implements Buffer {
  43. /** Ensure serialization compatibility */
  44. private static final long serialVersionUID = 2130079159931574599L;
  45. /**
  46. * Constructs a new empty <code>ArrayStack</code>. The initial size
  47. * is controlled by <code>ArrayList</code> and is currently 10.
  48. */
  49. public ArrayStack() {
  50. super();
  51. }
  52. /**
  53. * Constructs a new empty <code>ArrayStack</code> with an initial size.
  54. *
  55. * @param initialSize the initial size to use
  56. * @throws IllegalArgumentException if the specified initial size
  57. * is negative
  58. */
  59. public ArrayStack(int initialSize) {
  60. super(initialSize);
  61. }
  62. /**
  63. * Return <code>true</code> if this stack is currently empty.
  64. * <p>
  65. * This method exists for compatibility with <code>java.util.Stack</code>.
  66. * New users of this class should use <code>isEmpty</code> instead.
  67. *
  68. * @return true if the stack is currently empty
  69. */
  70. public boolean empty() {
  71. return isEmpty();
  72. }
  73. /**
  74. * Returns the top item off of this stack without removing it.
  75. *
  76. * @return the top item on the stack
  77. * @throws EmptyStackException if the stack is empty
  78. */
  79. public Object peek() throws EmptyStackException {
  80. int n = size();
  81. if (n <= 0) {
  82. throw new EmptyStackException();
  83. } else {
  84. return get(n - 1);
  85. }
  86. }
  87. /**
  88. * Returns the n'th item down (zero-relative) from the top of this
  89. * stack without removing it.
  90. *
  91. * @param n the number of items down to go
  92. * @return the n'th item on the stack, zero relative
  93. * @throws EmptyStackException if there are not enough items on the
  94. * stack to satisfy this request
  95. */
  96. public Object peek(int n) throws EmptyStackException {
  97. int m = (size() - n) - 1;
  98. if (m < 0) {
  99. throw new EmptyStackException();
  100. } else {
  101. return get(m);
  102. }
  103. }
  104. /**
  105. * Pops the top item off of this stack and return it.
  106. *
  107. * @return the top item on the stack
  108. * @throws EmptyStackException if the stack is empty
  109. */
  110. public Object pop() throws EmptyStackException {
  111. int n = size();
  112. if (n <= 0) {
  113. throw new EmptyStackException();
  114. } else {
  115. return remove(n - 1);
  116. }
  117. }
  118. /**
  119. * Pushes a new item onto the top of this stack. The pushed item is also
  120. * returned. This is equivalent to calling <code>add</code>.
  121. *
  122. * @param item the item to be added
  123. * @return the item just pushed
  124. */
  125. public Object push(Object item) {
  126. add(item);
  127. return item;
  128. }
  129. /**
  130. * Returns the one-based position of the distance from the top that the
  131. * specified object exists on this stack, where the top-most element is
  132. * considered to be at distance <code>1</code>. If the object is not
  133. * present on the stack, return <code>-1</code> instead. The
  134. * <code>equals()</code> method is used to compare to the items
  135. * in this stack.
  136. *
  137. * @param object the object to be searched for
  138. * @return the 1-based depth into the stack of the object, or -1 if not found
  139. */
  140. public int search(Object object) {
  141. int i = size() - 1; // Current index
  142. int n = 1; // Current distance
  143. while (i >= 0) {
  144. Object current = get(i);
  145. if ((object == null && current == null) ||
  146. (object != null && object.equals(current))) {
  147. return n;
  148. }
  149. i--;
  150. n++;
  151. }
  152. return -1;
  153. }
  154. /**
  155. * Returns the element on the top of the stack.
  156. *
  157. * @return the element on the top of the stack
  158. * @throws BufferUnderflowException if the stack is empty
  159. */
  160. public Object get() {
  161. int size = size();
  162. if (size == 0) {
  163. throw new BufferUnderflowException();
  164. }
  165. return get(size - 1);
  166. }
  167. /**
  168. * Removes the element on the top of the stack.
  169. *
  170. * @return the removed element
  171. * @throws BufferUnderflowException if the stack is empty
  172. */
  173. public Object remove() {
  174. int size = size();
  175. if (size == 0) {
  176. throw new BufferUnderflowException();
  177. }
  178. return remove(size - 1);
  179. }
  180. }