IntStack


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>int</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. See the base
39   * classes for other details of the implementation.
40   *
41   * @author Dennis M. Sosnoski
42   * @version 1.0
43   */
44  
45  public class IntStack
46  {
47      /** Default initial array size. */
48      public static final int DEFAULT_SIZE = 8;
49  
50      /** Size of the current array. */
51      protected int m_countLimit;
52      
53      /** The number of values currently present in the stack. */
54      protected int m_countPresent;
55  
56      /** Maximum size increment for growing array. */
57      protected int m_maximumGrowth;
58      
59      /** The underlying array used for storing the data. */
60      protected int[] m_baseArray;
61  
62      /**
63       * Constructor with full specification.
64       *
65       * @param size number of <code>int</code> values initially allowed in
66       * stack
67       * @param growth maximum size increment for growing stack
68       */
69  
70      public IntStack(int size, int growth) {
71          m_countLimit = size;
72          m_maximumGrowth = growth;
73          m_baseArray = new int[size];
74      }
75  
76      /**
77       * Constructor with initial size specified.
78       *
79       * @param size number of <code>int</code> values initially allowed in
80       * stack
81       */
82  
83      public IntStack(int size) {
84          this(size, Integer.MAX_VALUE);
85      }
86  
87      /**
88       * Default constructor.
89       */
90  
91      public IntStack() {
92          this(DEFAULT_SIZE);
93      }
94  
95      /**
96       * Copy (clone) constructor.
97       *
98       * @param base instance being copied
99       */
100 
101     public IntStack(IntStack 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 ints.
110      *
111      * @param ints array of ints for initial contents
112      */
113 
114     public IntStack(int[] ints) {
115         this(ints.length);
116         System.arraycopy(ints, 0, m_baseArray, 0, ints.length);
117         m_countPresent = ints.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      * Increase the size of the array to at least a specified size. The array
135      * will normally be at least doubled in size, but if a maximum size
136      * increment was specified in the constructor and the value is less than
137      * the current size of the array, the maximum increment will be used
138      * instead. If the requested size requires more than the default growth, 
139      * the requested size overrides the normal growth and determines the size
140      * of the replacement array.
141      * 
142      * @param required new minimum size required
143      */
144     
145     private void growArray(int required) {
146         int size = Math.max(required,
147             m_countLimit + Math.min(m_countLimit, m_maximumGrowth));
148         int[] grown = new int[size];
149         resizeCopy(m_baseArray, grown);
150         m_countLimit = size;
151         m_baseArray = grown;
152     }
153 
154     /**
155      * Ensure that the array has the capacity for at least the specified
156      * number of values.
157      * 
158      * @param min minimum capacity to be guaranteed
159      */
160     
161     public final void ensureCapacity(int min) {
162         if (min > m_countLimit) {
163             growArray(min);
164         }
165     }
166 
167     /**
168      * Push a value on the stack.
169      *
170      * @param value value to be added
171      */
172 
173     public void push(int value) {
174         int index = getAddIndex();
175         m_baseArray[index] = value;
176     }
177 
178     /**
179      * Pop a value from the stack.
180      *
181      * @return value from top of stack
182      * @exception ArrayIndexOutOfBoundsException on attempt to pop empty stack
183      */
184 
185     public int pop() {
186         if (m_countPresent > 0) {
187             return m_baseArray[--m_countPresent];
188         } else {
189             throw new ArrayIndexOutOfBoundsException  
190                 ("Attempt to pop empty stack");
191         }
192     }
193 
194     /**
195      * Pop multiple values from the stack. The last value popped is the
196      * one returned.
197      *
198      * @param count number of values to pop from stack (must be strictly
199      * positive)
200      * @return value from top of stack
201      * @exception ArrayIndexOutOfBoundsException on attempt to pop past end of
202      * stack
203      */
204 
205     public int pop(int count) {
206         if (count <= 0) {
207             throw new IllegalArgumentException  ("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 }
317
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags