001: /*
002: Copyright (c) 2000-2006, 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.binding.util;
030:
031: import java.lang.reflect.Array;
032:
033: /**
034: * Growable <code>Object</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.
039: *
040: * @author Dennis M. Sosnoski
041: */
042: public class ObjectStack {
043: /** Default initial array size. */
044: public static final int DEFAULT_SIZE = 8;
045:
046: /** Size of the current array. */
047: protected int m_countLimit;
048:
049: /** The number of values currently present in the stack. */
050: protected int m_countPresent;
051:
052: /** Maximum size increment for growing array. */
053: protected int m_maximumGrowth;
054:
055: /** The underlying array used for storing the data. */
056: protected Object[] m_baseArray;
057:
058: /**
059: * Constructor with full specification.
060: *
061: * @param size number of <code>Object</code> values initially allowed in
062: * stack
063: * @param growth maximum size increment for growing stack
064: */
065: public ObjectStack(int size, int growth) {
066: m_countLimit = size;
067: m_maximumGrowth = growth;
068: m_baseArray = new Object[size];
069: }
070:
071: /**
072: * Constructor with initial size specified.
073: *
074: * @param size number of <code>Object</code> values initially allowed in
075: * stack
076: */
077: public ObjectStack(int size) {
078: this (size, Integer.MAX_VALUE);
079: }
080:
081: /**
082: * Default constructor.
083: */
084: public ObjectStack() {
085: this (DEFAULT_SIZE);
086: }
087:
088: /**
089: * Copy (clone) constructor.
090: *
091: * @param base instance being copied
092: */
093: public ObjectStack(ObjectStack base) {
094: this (base.m_countLimit, base.m_maximumGrowth);
095: System.arraycopy(base.m_baseArray, 0, m_baseArray, 0,
096: base.m_countPresent);
097: m_countPresent = base.m_countPresent;
098: }
099:
100: /**
101: * Constructor from array of strings.
102: *
103: * @param strings array of strings for initial contents
104: */
105: public ObjectStack(Object[] strings) {
106: this (strings.length);
107: System.arraycopy(strings, 0, m_baseArray, 0, strings.length);
108: m_countPresent = strings.length;
109: }
110:
111: /**
112: * Copy data after array resize. This just copies the entire contents of the
113: * old array to the start of the new array. It should be overridden in cases
114: * where data needs to be rearranged in the array after a resize.
115: *
116: * @param base original array containing data
117: * @param grown resized array for data
118: */
119: private void resizeCopy(Object base, Object grown) {
120: System.arraycopy(base, 0, grown, 0, Array.getLength(base));
121: }
122:
123: /**
124: * Discards values for a range of indices in the array. Checks if the
125: * values stored in the array are object references, and if so clears
126: * them. If the values are primitives, this method does nothing.
127: *
128: * @param from index of first value to be discarded
129: * @param to index past last value to be discarded
130: */
131: private void discardValues(int from, int to) {
132: for (int i = from; i < to; i++) {
133: m_baseArray[i] = null;
134: }
135: }
136:
137: /**
138: * Increase the size of the array to at least a specified size. The array
139: * will normally be at least doubled in size, but if a maximum size
140: * increment was specified in the constructor and the value is less than
141: * the current size of the array, the maximum increment will be used
142: * instead. If the requested size requires more than the default growth,
143: * the requested size overrides the normal growth and determines the size
144: * of the replacement array.
145: *
146: * @param required new minimum size required
147: */
148: private void growArray(int required) {
149: int size = Math.max(required, m_countLimit
150: + Math.min(m_countLimit, m_maximumGrowth));
151: Object[] grown = new Object[size];
152: resizeCopy(m_baseArray, grown);
153: m_countLimit = size;
154: m_baseArray = grown;
155: }
156:
157: /**
158: * Ensure that the array has the capacity for at least the specified
159: * number of values.
160: *
161: * @param min minimum capacity to be guaranteed
162: */
163: public final void ensureCapacity(int min) {
164: if (min > m_countLimit) {
165: growArray(min);
166: }
167: }
168:
169: /**
170: * Push a value on the stack.
171: *
172: * @param value value to be added
173: */
174: public void push(Object value) {
175: int index = getAddIndex();
176: m_baseArray[index] = value;
177: }
178:
179: /**
180: * Pop a value from the stack.
181: *
182: * @return value from top of stack
183: * @exception ArrayIndexOutOfBoundsException on attempt to pop empty stack
184: */
185: public Object pop() {
186: if (m_countPresent > 0) {
187: Object value = m_baseArray[--m_countPresent];
188: m_baseArray[m_countPresent] = null;
189: return value;
190: } else {
191: throw new ArrayIndexOutOfBoundsException(
192: "Attempt to pop empty stack");
193: }
194: }
195:
196: /**
197: * Pop multiple values from the stack. The last value popped is the
198: * one returned.
199: *
200: * @param count number of values to pop from stack (must be strictly
201: * positive)
202: * @return value from top of stack
203: * @exception ArrayIndexOutOfBoundsException on attempt to pop past end of
204: * stack
205: */
206: public Object pop(int count) {
207: if (count < 0) {
208: throw new IllegalArgumentException(
209: "Count must be greater than 0");
210: } else if (m_countPresent >= count) {
211: m_countPresent -= count;
212: Object value = m_baseArray[m_countPresent];
213: discardValues(m_countPresent, m_countPresent + count);
214: return value;
215: } else {
216: throw new ArrayIndexOutOfBoundsException(
217: "Attempt to pop past end of stack");
218: }
219: }
220:
221: /**
222: * Copy a value from the stack. This returns a value from within
223: * the stack without modifying the stack.
224: *
225: * @param depth depth of value to be returned
226: * @return value from stack
227: * @exception ArrayIndexOutOfBoundsException on attempt to peek past end of
228: * stack
229: */
230: public Object peek(int depth) {
231: if (m_countPresent > depth) {
232: return m_baseArray[m_countPresent - depth - 1];
233: } else {
234: throw new ArrayIndexOutOfBoundsException(
235: "Attempt to peek past end of stack");
236: }
237: }
238:
239: /**
240: * Copy top value from the stack. This returns the top value without
241: * removing it from the stack.
242: *
243: * @return value at top of stack
244: * @exception ArrayIndexOutOfBoundsException on attempt to peek empty stack
245: */
246: public Object peek() {
247: return peek(0);
248: }
249:
250: /**
251: * Constructs and returns a simple array containing the same data as held
252: * in this stack. Note that the items will be in reverse pop order, with
253: * the last item to be popped from the stack as the first item in the
254: * array.
255: *
256: * @return array containing a copy of the data
257: */
258: public Object[] toArray() {
259: Object[] copy = new Object[m_countPresent];
260: System.arraycopy(m_baseArray, 0, copy, 0, m_countPresent);
261: return copy;
262: }
263:
264: /**
265: * Duplicates the object with the generic call.
266: *
267: * @return a copy of the object
268: */
269: public Object clone() {
270: return new ObjectStack(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: private int getAddIndex() {
282: int index = m_countPresent++;
283: if (m_countPresent > m_countLimit) {
284: growArray(m_countPresent);
285: }
286: return index;
287: }
288:
289: /**
290: * Get the number of values currently present in the stack.
291: *
292: * @return count of values present
293: */
294: public int size() {
295: return m_countPresent;
296: }
297:
298: /**
299: * Check if stack is empty.
300: *
301: * @return <code>true</code> if stack empty, <code>false</code> if not
302: */
303: public boolean isEmpty() {
304: return m_countPresent == 0;
305: }
306:
307: /**
308: * Set the stack to the empty state.
309: */
310: public void clear() {
311: discardValues(0, m_countPresent);
312: m_countPresent = 0;
313: }
314: }
|