001: /*
002: Copyright (c) 2000-2004, Dennis M. Sosnoski
003: All rights reserved.
004:
005: Redistribution and use in source and binary forms, with or without modification,
006: are permitted provided that the following conditions are met:
007:
008: * Redistributions of source code must retain the above copyright notice, this
009: list of conditions and the following disclaimer.
010: * Redistributions in binary form must reproduce the above copyright notice,
011: this list of conditions and the following disclaimer in the documentation
012: and/or other materials provided with the distribution.
013: * Neither the name of JiBX nor the names of its contributors may be used
014: to endorse or promote products derived from this software without specific
015: prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
018: ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
019: WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
020: DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
021: ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
022: (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
023: LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
024: ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
026: SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028:
029: package org.jibx.runtime;
030:
031: import java.lang.reflect.Array;
032:
033: /**
034: * Growable <code>int</code> stack with type specific access methods. This
035: * implementation is unsynchronized in order to provide the best possible
036: * performance for typical usage scenarios, so explicit synchronization must
037: * be implemented by a wrapper class or directly by the application in cases
038: * where instances are modified in a multithreaded environment. See the base
039: * classes for other details of the implementation.
040: *
041: * @author Dennis M. Sosnoski
042: * @version 1.0
043: */
044:
045: public class IntStack {
046: /** Default initial array size. */
047: public static final int DEFAULT_SIZE = 8;
048:
049: /** Size of the current array. */
050: protected int m_countLimit;
051:
052: /** The number of values currently present in the stack. */
053: protected int m_countPresent;
054:
055: /** Maximum size increment for growing array. */
056: protected int m_maximumGrowth;
057:
058: /** The underlying array used for storing the data. */
059: protected int[] m_baseArray;
060:
061: /**
062: * Constructor with full specification.
063: *
064: * @param size number of <code>int</code> values initially allowed in
065: * stack
066: * @param growth maximum size increment for growing stack
067: */
068:
069: public IntStack(int size, int growth) {
070: m_countLimit = size;
071: m_maximumGrowth = growth;
072: m_baseArray = new int[size];
073: }
074:
075: /**
076: * Constructor with initial size specified.
077: *
078: * @param size number of <code>int</code> values initially allowed in
079: * stack
080: */
081:
082: public IntStack(int size) {
083: this (size, Integer.MAX_VALUE);
084: }
085:
086: /**
087: * Default constructor.
088: */
089:
090: public IntStack() {
091: this (DEFAULT_SIZE);
092: }
093:
094: /**
095: * Copy (clone) constructor.
096: *
097: * @param base instance being copied
098: */
099:
100: public IntStack(IntStack base) {
101: this (base.m_countLimit, base.m_maximumGrowth);
102: System.arraycopy(base.m_baseArray, 0, m_baseArray, 0,
103: base.m_countPresent);
104: m_countPresent = base.m_countPresent;
105: }
106:
107: /**
108: * Constructor from array of ints.
109: *
110: * @param ints array of ints for initial contents
111: */
112:
113: public IntStack(int[] ints) {
114: this (ints.length);
115: System.arraycopy(ints, 0, m_baseArray, 0, ints.length);
116: m_countPresent = ints.length;
117: }
118:
119: /**
120: * Copy data after array resize. This just copies the entire contents of the
121: * old array to the start of the new array. It should be overridden in cases
122: * where data needs to be rearranged in the array after a resize.
123: *
124: * @param base original array containing data
125: * @param grown resized array for data
126: */
127:
128: private void resizeCopy(Object base, Object grown) {
129: System.arraycopy(base, 0, grown, 0, Array.getLength(base));
130: }
131:
132: /**
133: * Increase the size of the array to at least a specified size. The array
134: * will normally be at least doubled in size, but if a maximum size
135: * increment was specified in the constructor and the value is less than
136: * the current size of the array, the maximum increment will be used
137: * instead. If the requested size requires more than the default growth,
138: * the requested size overrides the normal growth and determines the size
139: * of the replacement array.
140: *
141: * @param required new minimum size required
142: */
143:
144: private void growArray(int required) {
145: int size = Math.max(required, m_countLimit
146: + Math.min(m_countLimit, m_maximumGrowth));
147: int[] grown = new int[size];
148: resizeCopy(m_baseArray, grown);
149: m_countLimit = size;
150: m_baseArray = grown;
151: }
152:
153: /**
154: * Ensure that the array has the capacity for at least the specified
155: * number of values.
156: *
157: * @param min minimum capacity to be guaranteed
158: */
159:
160: public final void ensureCapacity(int min) {
161: if (min > m_countLimit) {
162: growArray(min);
163: }
164: }
165:
166: /**
167: * Push a value on the stack.
168: *
169: * @param value value to be added
170: */
171:
172: public void push(int value) {
173: int index = getAddIndex();
174: m_baseArray[index] = value;
175: }
176:
177: /**
178: * Pop a value from the stack.
179: *
180: * @return value from top of stack
181: * @exception ArrayIndexOutOfBoundsException on attempt to pop empty stack
182: */
183:
184: public int pop() {
185: if (m_countPresent > 0) {
186: return m_baseArray[--m_countPresent];
187: } else {
188: throw new ArrayIndexOutOfBoundsException(
189: "Attempt to pop empty stack");
190: }
191: }
192:
193: /**
194: * Pop multiple values from the stack. The last value popped is the
195: * one returned.
196: *
197: * @param count number of values to pop from stack (must be strictly
198: * positive)
199: * @return value from top of stack
200: * @exception ArrayIndexOutOfBoundsException on attempt to pop past end of
201: * stack
202: */
203:
204: public int pop(int count) {
205: if (count <= 0) {
206: throw new IllegalArgumentException(
207: "Count must be greater than 0");
208: } else if (m_countPresent >= count) {
209: m_countPresent -= count;
210: return m_baseArray[m_countPresent];
211: } else {
212: throw new ArrayIndexOutOfBoundsException(
213: "Attempt to pop past end of stack");
214: }
215: }
216:
217: /**
218: * Copy a value from the stack. This returns a value from within
219: * the stack without modifying the stack.
220: *
221: * @param depth depth of value to be returned
222: * @return value from stack
223: * @exception ArrayIndexOutOfBoundsException on attempt to peek past end of
224: * stack
225: */
226:
227: public int peek(int depth) {
228: if (m_countPresent > depth) {
229: return m_baseArray[m_countPresent - depth - 1];
230: } else {
231: throw new ArrayIndexOutOfBoundsException(
232: "Attempt to peek past end of stack");
233: }
234: }
235:
236: /**
237: * Copy top value from the stack. This returns the top value without
238: * removing it from the stack.
239: *
240: * @return value at top of stack
241: * @exception ArrayIndexOutOfBoundsException on attempt to peek empty stack
242: */
243:
244: public int peek() {
245: return peek(0);
246: }
247:
248: /**
249: * Constructs and returns a simple array containing the same data as held
250: * in this stack. Note that the items will be in reverse pop order, with
251: * the last item to be popped from the stack as the first item in the
252: * array.
253: *
254: * @return array containing a copy of the data
255: */
256:
257: public int[] toArray() {
258: int[] copy = new int[m_countPresent];
259: System.arraycopy(m_baseArray, 0, copy, 0, m_countPresent);
260: return copy;
261: }
262:
263: /**
264: * Duplicates the object with the generic call.
265: *
266: * @return a copy of the object
267: */
268:
269: public Object clone() {
270: return new IntStack(this );
271: }
272:
273: /**
274: * Gets the array offset for appending a value to those in the stack.
275: * If the underlying array is full, it is grown by the appropriate size
276: * increment so that the index value returned is always valid for the
277: * array in use by the time of the return.
278: *
279: * @return index position for added element
280: */
281:
282: private int getAddIndex() {
283: int index = m_countPresent++;
284: if (m_countPresent > m_countLimit) {
285: growArray(m_countPresent);
286: }
287: return index;
288: }
289:
290: /**
291: * Get the number of values currently present in the stack.
292: *
293: * @return count of values present
294: */
295: public int size() {
296: return m_countPresent;
297: }
298:
299: /**
300: * Check if stack is empty.
301: *
302: * @return <code>true</code> if stack empty, <code>false</code> if not
303: */
304:
305: public boolean isEmpty() {
306: return m_countPresent == 0;
307: }
308:
309: /**
310: * Set the stack to the empty state.
311: */
312:
313: public void clear() {
314: m_countPresent = 0;
315: }
316: }
|