ObjectStack


1   /*
2   Copyright (c) 2000-2004, 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>Object</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 ObjectStack
45  {
46      /** Default initial array size. */
47      public static final int DEFAULT_SIZE = 8;
48  
49      /** Size of the current array. */
50      protected int m_countLimit;
51      
52      /** The number of values currently present in the stack. */
53      protected int m_countPresent;
54  
55      /** Maximum size increment for growing array. */
56      protected int m_maximumGrowth;
57  
58      /** The underlying array used for storing the data. */
59      protected Object  [] m_baseArray;
60  
61      /**
62       * Constructor with full specification.
63       *
64       * @param size number of <code>Object</code> values initially allowed in
65       * stack
66       * @param growth maximum size increment for growing stack
67       */
68  
69      public ObjectStack(int size, int growth) {
70          m_countLimit = size;
71          m_maximumGrowth = growth;
72          m_baseArray = new Object  [size];
73      }
74  
75      /**
76       * Constructor with initial size specified.
77       *
78       * @param size number of <code>Object</code> values initially allowed in
79       * stack
80       */
81  
82      public ObjectStack(int size) {
83          this(size, Integer.MAX_VALUE);
84      }
85  
86      /**
87       * Default constructor.
88       */
89  
90      public ObjectStack() {
91          this(DEFAULT_SIZE);
92      }
93  
94      /**
95       * Copy (clone) constructor.
96       *
97       * @param from instance being copied
98       */
99  
100     public ObjectStack(ObjectStack 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 strings.
109      *
110      * @param strings array of strings for initial contents
111      */
112 
113     public ObjectStack(Object  [] strings) {
114         this(strings.length);
115         System.arraycopy(strings, 0, m_baseArray, 0, strings.length);
116         m_countPresent = strings.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      * Discards values for a range of indices in the array. Checks if the
134      * values stored in the array are object references, and if so clears 
135      * them. If the values are primitives, this method does nothing.
136      * 
137      * @param from index of first value to be discarded
138      * @param to index past last value to be discarded
139      */
140     
141     private void discardValues(int from, int to) {
142         for (int i = from; i < to; i++) {
143             m_baseArray[i] = null;
144         }
145     }
146 
147     /**
148      * Increase the size of the array to at least a specified size. The array
149      * will normally be at least doubled in size, but if a maximum size
150      * increment was specified in the constructor and the value is less than
151      * the current size of the array, the maximum increment will be used
152      * instead. If the requested size requires more than the default growth, 
153      * the requested size overrides the normal growth and determines the size
154      * of the replacement array.
155      * 
156      * @param required new minimum size required
157      */
158     
159     private void growArray(int required) {
160         int size = Math.max(required,
161             m_countLimit + Math.min(m_countLimit, m_maximumGrowth));
162         Object  [] grown = new Object  [size];
163         resizeCopy(m_baseArray, grown);
164         m_countLimit = size;
165         m_baseArray = grown;
166     }
167 
168     /**
169      * Ensure that the array has the capacity for at least the specified
170      * number of values.
171      * 
172      * @param min minimum capacity to be guaranteed
173      */
174     
175     public final void ensureCapacity(int min) {
176         if (min > m_countLimit) {
177             growArray(min);
178         }
179     }
180 
181     /**
182      * Push a value on the stack.
183      *
184      * @param value value to be added
185      */
186 
187     public void push(Object   value) {
188         int index = getAddIndex();
189         m_baseArray[index] = value;
190     }
191 
192     /**
193      * Pop a value from the stack.
194      *
195      * @return value from top of stack
196      * @exception ArrayIndexOutOfBoundsException on attempt to pop empty stack
197      */
198 
199     public Object   pop() {
200         if (m_countPresent > 0) {
201             Object   value = m_baseArray[--m_countPresent];
202             m_baseArray[m_countPresent] = null;
203             return value;
204         } else {
205             throw new ArrayIndexOutOfBoundsException  
206                 ("Attempt to pop empty stack");
207         }
208     }
209 
210     /**
211      * Pop multiple values from the stack. The last value popped is the
212      * one returned.
213      *
214      * @param count number of values to pop from stack (must be strictly
215      * positive)
216      * @return value from top of stack
217      * @exception ArrayIndexOutOfBoundsException on attempt to pop past end of
218      * stack
219      */
220 
221     public Object   pop(int count) {
222         if (count < 0) {
223             throw new IllegalArgumentException  ("Count must be greater than 0");
224         } else if (m_countPresent >= count) {
225             m_countPresent -= count;
226             Object   value = m_baseArray[m_countPresent];
227             discardValues(m_countPresent, m_countPresent + count);
228             return value;
229         } else {
230             throw new ArrayIndexOutOfBoundsException  
231                 ("Attempt to pop past end of stack");
232         }
233     }
234 
235     /**
236      * Copy a value from the stack. This returns a value from within
237      * the stack without modifying the stack.
238      *
239      * @param depth depth of value to be returned
240      * @return value from stack
241      * @exception ArrayIndexOutOfBoundsException on attempt to peek past end of
242      * stack
243      */
244 
245     public Object   peek(int depth) {
246         if (m_countPresent > depth) {
247             return m_baseArray[m_countPresent - depth - 1];
248         } else {
249             throw new ArrayIndexOutOfBoundsException  
250                 ("Attempt to peek past end of stack");
251         }
252     }
253 
254     /**
255      * Copy top value from the stack. This returns the top value without
256      * removing it from the stack.
257      *
258      * @return value at top of stack
259      * @exception ArrayIndexOutOfBoundsException on attempt to peek empty stack
260      */
261 
262     public Object   peek() {
263         return peek(0);
264     }
265 
266     /**
267      * Constructs and returns a simple array containing the same data as held
268      * in this stack. Note that the items will be in reverse pop order, with
269      * the last item to be popped from the stack as the first item in the
270      * array.
271      *
272      * @return array containing a copy of the data
273      */
274 
275     public Object  [] toArray() {
276         Object  [] copy = new Object  [m_countPresent];
277         System.arraycopy(m_baseArray, 0, copy, 0, m_countPresent);
278         return copy;
279     }
280 
281     /**
282      * Duplicates the object with the generic call.
283      *
284      * @return a copy of the object
285      */
286 
287     public Object   clone() {
288         return new ObjectStack(this);
289     }
290 
291     /**
292      * Gets the array offset for appending a value to those in the stack.
293      * If the underlying array is full, it is grown by the appropriate size
294      * increment so that the index value returned is always valid for the 
295      * array in use by the time of the return.
296      * 
297      * @return index position for added element
298      */
299     
300     private int getAddIndex() {
301         int index = m_countPresent++;
302         if (m_countPresent > m_countLimit) {
303             growArray(m_countPresent);
304         }
305         return index;
306     }
307 
308     /**
309      * Get the number of values currently present in the stack.
310      * 
311      * @return count of values present
312      */
313     public int size() {
314         return m_countPresent;
315     }
316 
317     /**
318      * Check if stack is empty.
319      * 
320      * @return <code>true</code> if stack empty, <code>false</code> if not
321      */
322     
323     public boolean isEmpty() {
324         return m_countPresent == 0;
325     }
326 
327     /**
328      * Set the stack to the empty state.
329      */
330     
331     public void clear() {
332         discardValues(0, m_countPresent);
333         m_countPresent = 0;
334     }
335 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags