StringStack


1   /*
2   Copyright (c) 2000-2005, Dennis M. Sosnoski
3   All rights reserved.
4   
5   Redistribution and use in source and binary forms, with or without modification,
6   are permitted provided that the following conditions are met:
7   
8    * Redistributions of source code must retain the above copyright notice, this
9      list of conditions and the following disclaimer.
10   * Redistributions in binary form must reproduce the above copyright notice,
11     this list of conditions and the following disclaimer in the documentation
12     and/or other materials provided with the distribution.
13   * Neither the name of JiBX nor the names of its contributors may be used
14     to endorse or promote products derived from this software without specific
15     prior written permission.
16  
17  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
18  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
21  ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
24  ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28  
29  package org.jibx.binding.util;
30  
31  import java.lang.reflect.Array  ;
32  
33  /**
34   * Growable <code>String</code> stack with type specific access methods. This
35   * implementation is unsynchronized in order to provide the best possible
36   * performance for typical usage scenarios, so explicit synchronization must
37   * be implemented by a wrapper class or directly by the application in cases
38   * where instances are modified in a multithreaded environment.
39   *
40   * @author Dennis M. Sosnoski
41   * @version 1.0
42   */
43  
44  public class StringStack
45  {
46      /** Default initial array size. */
47      public static final int DEFAULT_SIZE = 8;
48  
49      /** Size of the current array. */
50      private int m_countLimit;
51      
52      /** The number of values currently present in the stack. */
53      private int m_countPresent;
54  
55      /** Maximum size increment for growing array. */
56      private int m_maximumGrowth;
57  
58      /** The underlying array used for storing the data. */
59      private String  [] m_baseArray;
60  
61      /**
62       * Constructor with full specification.
63       *
64       * @param size number of <code>String</code> values initially allowed in
65       * stack
66       * @param growth maximum size increment for growing stack
67       */
68  
69      public StringStack(int size, int growth) {
70          String  [] array = new String  [size];
71          m_countLimit = size;
72          m_maximumGrowth = growth;
73          m_baseArray = array;
74      }
75  
76      /**
77       * Constructor with initial size specified.
78       *
79       * @param size number of <code>String</code> values initially allowed in
80       * stack
81       */
82  
83      public StringStack(int size) {
84          this(size, Integer.MAX_VALUE);
85      }
86  
87      /**
88       * Default constructor.
89       */
90  
91      public StringStack() {
92          this(DEFAULT_SIZE);
93      }
94  
95      /**
96       * Copy (clone) constructor.
97       *
98       * @param from instance being copied
99       */
100 
101     public StringStack(StringStack base) {
102         this(base.m_countLimit, base.m_maximumGrowth);
103         System.arraycopy(base.m_baseArray, 0, m_baseArray, 0, 
104             base.m_countPresent);
105         m_countPresent = base.m_countPresent;
106     }
107 
108     /**
109      * Constructor from array of strings.
110      *
111      * @param strings array of strings for initial contents
112      */
113 
114     public StringStack(String  [] strings) {
115         this(strings.length);
116         System.arraycopy(strings, 0, m_baseArray, 0, strings.length);
117         m_countPresent = strings.length;
118     }
119 
120     /**
121      * Copy data after array resize. This just copies the entire contents of the
122      * old array to the start of the new array. It should be overridden in cases
123      * where data needs to be rearranged in the array after a resize.
124      * 
125      * @param base original array containing data
126      * @param grown resized array for data
127      */
128     
129     private void resizeCopy(Object   base, Object   grown) {
130         System.arraycopy(base, 0, grown, 0, Array.getLength(base));
131     }
132 
133     /**
134      * Discards values for a range of indices in the array. Checks if the
135      * values stored in the array are object references, and if so clears 
136      * them. If the values are primitives, this method does nothing.
137      * 
138      * @param from index of first value to be discarded
139      * @param to index past last value to be discarded
140      */
141     
142     private void discardValues(int from, int to) {
143         for (int i = from; i < to; i++) {
144             m_baseArray[i] = null;
145         }
146     }
147 
148     /**
149      * Increase the size of the array to at least a specified size. The array
150      * will normally be at least doubled in size, but if a maximum size
151      * increment was specified in the constructor and the value is less than
152      * the current size of the array, the maximum increment will be used
153      * instead. If the requested size requires more than the default growth, 
154      * the requested size overrides the normal growth and determines the size
155      * of the replacement array.
156      * 
157      * @param required new minimum size required
158      */
159     
160     private void growArray(int required) {
161         int size = Math.max(required,
162             m_countLimit + Math.min(m_countLimit, m_maximumGrowth));
163         String  [] grown = new String  [size];
164         resizeCopy(m_baseArray, grown);
165         m_countLimit = size;
166         m_baseArray = grown;
167     }
168 
169     /**
170      * Ensure that the array has the capacity for at least the specified
171      * number of values.
172      * 
173      * @param min minimum capacity to be guaranteed
174      */
175     
176     public final void ensureCapacity(int min) {
177         if (min > m_countLimit) {
178             growArray(min);
179         }
180     }
181 
182     /**
183      * Push a value on the stack.
184      *
185      * @param value value to be added
186      */
187 
188     public void push(String   value) {
189         int index = getAddIndex();
190         m_baseArray[index] = value;
191     }
192 
193     /**
194      * Pop a value from the stack.
195      *
196      * @return value from top of stack
197      * @exception ArrayIndexOutOfBoundsException on attempt to pop empty stack
198      */
199 
200     public String   pop() {
201         if (m_countPresent > 0) {
202             String   value = m_baseArray[--m_countPresent];
203             m_baseArray[m_countPresent] = null;
204             return value;
205         } else {
206             throw new ArrayIndexOutOfBoundsException  
207                 ("Attempt to pop empty stack");
208         }
209     }
210 
211     /**
212      * Pop multiple values from the stack. The last value popped is the
213      * one returned.
214      *
215      * @param count number of values to pop from stack (must be strictly
216      * positive)
217      * @return value from top of stack
218      * @exception ArrayIndexOutOfBoundsException on attempt to pop past end of
219      * stack
220      */
221 
222     public String   pop(int count) {
223         if (count < 0) {
224             throw new IllegalArgumentException  ("Count must be greater than 0");
225         } else if (m_countPresent >= count) {
226             m_countPresent -= count;
227             String   value = m_baseArray[m_countPresent];
228             discardValues(m_countPresent, m_countPresent + count);
229             return value;
230         } else {
231             throw new ArrayIndexOutOfBoundsException  
232                 ("Attempt to pop past end of stack");
233         }
234     }
235 
236     /**
237      * Copy a value from the stack. This returns a value from within
238      * the stack without modifying the stack.
239      *
240      * @param depth depth of value to be returned
241      * @return value from stack
242      * @exception ArrayIndexOutOfBoundsException on attempt to peek past end of
243      * stack
244      */
245 
246     public String   peek(int depth) {
247         if (m_countPresent > depth) {
248             return m_baseArray[m_countPresent - depth - 1];
249         } else {
250             throw new ArrayIndexOutOfBoundsException  
251                 ("Attempt to peek past end of stack");
252         }
253     }
254 
255     /**
256      * Copy top value from the stack. This returns the top value without
257      * removing it from the stack.
258      *
259      * @return value at top of stack
260      * @exception ArrayIndexOutOfBoundsException on attempt to peek empty stack
261      */
262 
263     public String   peek() {
264         return peek(0);
265     }
266 
267     /**
268      * Constructs and returns a simple array containing the same data as held
269      * in this stack. Note that the items will be in reverse pop order, with
270      * the last item to be popped from the stack as the first item in the
271      * array.
272      *
273      * @return array containing a copy of the data
274      */
275 
276     public String  [] toArray() {
277         String  [] copy = new String  [m_countPresent];
278         System.arraycopy(m_baseArray, 0, copy, 0, m_countPresent);
279         return copy;
280     }
281 
282     /**
283      * Duplicates the object with the generic call.
284      *
285      * @return a copy of the object
286      */
287 
288     public Object   clone() {
289         return new StringStack(this);
290     }
291 
292     /**
293      * Gets the array offset for appending a value to those in the stack.
294      * If the underlying array is full, it is grown by the appropriate size
295      * increment so that the index value returned is always valid for the 
296      * array in use by the time of the return.
297      * 
298      * @return index position for added element
299      */
300     
301     private int getAddIndex() {
302         int index = m_countPresent++;
303         if (m_countPresent > m_countLimit) {
304             growArray(m_countPresent);
305         }
306         return index;
307     }
308 
309     /**
310      * Get the number of values currently present in the stack.
311      * 
312      * @return count of values present
313      */
314     public int size() {
315         return m_countPresent;
316     }
317 
318     /**
319      * Check if stack is empty.
320      * 
321      * @return <code>true</code> if stack empty, <code>false</code> if not
322      */
323     
324     public boolean isEmpty() {
325         return m_countPresent == 0;
326     }
327 
328     /**
329      * Set the stack to the empty state.
330      */
331     
332     public void clear() {
333         discardValues(0, m_countPresent);
334         m_countPresent = 0;
335     }
336 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags