001 // Copyright 2007, 2008 The Apache Software Foundation
002 //
003 // Licensed under the Apache License, Version 2.0 (the "License");
004 // you may not use this file except in compliance with the License.
005 // You may obtain a copy of the License at
006 //
007 // http://www.apache.org/licenses/LICENSE-2.0
008 //
009 // Unless required by applicable law or agreed to in writing, software
010 // distributed under the License is distributed on an "AS IS" BASIS,
011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
012 // See the License for the specific language governing permissions and
013 // limitations under the License.
014
015 package org.apache.tapestry5.ioc.util;
016
017 import org.apache.tapestry5.ioc.internal.util.CollectionFactory;
018
019 /**
020 * A simple, streamlined implementation of {@link java.util.Stack}. The implementation is <em>not</em> threadsafe.
021 *
022 * @param <E> the type of elements stored in the map
023 * @see CollectionFactory#newStack()
024 */
025 public class Stack<E>
026 {
027 private static final int MINIMUM_SIZE = 3;
028
029 private static final int DEFAULT_ARRAY_SIZE = 20;
030
031 private Object[] items;
032
033 private int index = -1;
034
035 /**
036 * Normal constructor supporting an initial size of 20.
037 */
038 public Stack()
039 {
040 this(DEFAULT_ARRAY_SIZE);
041 }
042
043 /**
044 * @param initialSize the initial size of the internal array (which will be expanded as necessary). For best
045 * efficiency, set this to the maximum depth of the stack.
046 */
047 public Stack(int initialSize)
048 {
049 items = new Object[Math.max(initialSize, MINIMUM_SIZE)];
050 }
051
052 /**
053 * Returns true if the stack is empty.
054 */
055 public boolean isEmpty()
056 {
057 return index < 0;
058 }
059
060 /**
061 * Returns the number of items currently in the stack.
062 */
063 public int getDepth()
064 {
065 return index + 1;
066 }
067
068 /**
069 * Clears the stack, the same as popping off all elements.
070 */
071 public void clear()
072 {
073 for (int i = 0; i <= index; i++) items[i] = null;
074
075 index = -1;
076 }
077
078 /**
079 * Pushes a new item onto the stack.
080 */
081 public void push(E item)
082 {
083 index++;
084
085 if (index == items.length)
086 {
087 int newCapacity = (items.length * 3) / 2 + 1;
088 Object[] newItems = new Object[newCapacity];
089 System.arraycopy(items, 0, newItems, 0, items.length);
090
091 items = newItems;
092 }
093
094 items[index] = item;
095 }
096
097 /**
098 * Pops the top element off the stack and returns it.
099 *
100 * @return the top element of the stack
101 * @throws IllegalStateException if the stack is empty
102 */
103 @SuppressWarnings("unchecked")
104 public E pop()
105 {
106 checkIfEmpty();
107
108 Object result = items[index];
109
110 items[index] = null;
111
112 index--;
113
114 return (E) result;
115 }
116
117 private void checkIfEmpty()
118 {
119 if (index < 0) throw new IllegalStateException(UtilMessages.stackIsEmpty());
120 }
121
122 /**
123 * Returns the top element of the stack without affecting the stack.
124 *
125 * @return top element on the stack
126 * @throws IllegalStateException if the stack is empty
127 */
128 @SuppressWarnings("unchecked")
129 public E peek()
130 {
131 checkIfEmpty();
132
133 return (E) items[index];
134 }
135
136 /**
137 * Describes the stack, listing the element in order of depth (top element first).
138 *
139 * @return string description of the stack
140 */
141 @Override
142 public String toString()
143 {
144 StringBuilder builder = new StringBuilder("Stack[");
145
146 for (int i = index; i >= 0; i--)
147 {
148 if (i != index) builder.append(", ");
149
150 builder.append(String.valueOf(items[i]));
151 }
152
153 builder.append("]");
154
155 return builder.toString();
156 }
157
158 /**
159 * Returns a snapshot of the current state of the stack as an array of objects. The first object is the deepest in
160 * the stack, the last object is the most shallowest (most recently pushed onto the stack). The returned array may
161 * be manipulated (it is a copy).
162 *
163 * @return the stack as an object array
164 */
165 public Object[] getSnapshot()
166 {
167 Object[] result = new Object[index + 1];
168
169 System.arraycopy(items, 0, result, 0, index + 1);
170
171 return result;
172 }
173 }