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