GrowableBase


1   /*
2    * Copyright (c) 2000-2001 Sosnoski Software Solutions, Inc.
3    *
4    * Permission is hereby granted, free of charge, to any person obtaining a copy
5    * of this software and associated documentation files (the "Software"), to deal
6    * in the Software without restriction, including without limitation the rights 
7    * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 
8    * copies of the Software, and to permit persons to whom the Software is 
9    * furnished to do so, subject to the following conditions:
10   *
11   * The above copyright notice and this permission notice shall be included in 
12   * all copies or substantial portions of the Software.
13   *
14   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
15   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
16   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
17   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
18   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
19   * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 
20   * IN THE SOFTWARE.
21   */
22  
23  package com.sosnoski.util;
24  
25  import java.lang.reflect.Array  ;
26  
27  /**
28   * Base class for various types of collections based on type-specific 
29   * growable arrays. The underlying array used for storage of items doubles
30   * in size each time more space is required, up to an optional maximum
31   * growth increment specified by the user.
32   * 
33   * @author Dennis M. Sosnoski
34   * @version 1.0
35   * @see com.sosnoski.util.array.ArrayBase
36   * @see com.sosnoski.util.queue.QueueBase
37   * @see com.sosnoski.util.stack.StackBase
38   */
39  
40  public abstract class GrowableBase
41  {
42      /** Default initial array size. */
43      public static final int DEFAULT_SIZE = 8;
44  
45      /** Size of the current array. */
46      protected int m_countLimit;
47  
48      /** Maximum size increment for growing array. */
49      protected int m_maximumGrowth;
50  
51      /**
52       * Constructor with full specification.
53       * 
54       * @param size number of elements in initial array
55       * @param growth maximum size increment for growing array
56       * @param type array element type
57       */
58      
59      public GrowableBase(int size, int growth, Class   type) {
60          Object   array = Array.newInstance(type, size);
61          m_countLimit = size;
62          m_maximumGrowth = growth;
63          setArray(array);
64      }
65  
66      /**
67       * Constructor with partial specification.
68       * 
69       * @param size number of elements initially allowed in array
70       * @param type array element type
71       */
72      
73      public GrowableBase(int size, Class   type) {
74          this(size, Integer.MAX_VALUE, type);
75      }
76  
77      /**
78       * Copy (clone) constructor.
79       * 
80       * @param base instance being copied
81       */
82      
83      public GrowableBase(GrowableBase base) {
84          this(base.m_countLimit, base.m_maximumGrowth,
85              base.getArray().getClass().getComponentType());
86      }
87  
88      /**
89       * Get the backing array. This method is used by the type-agnostic base
90       * class code to access the array used for type-specific storage by the
91       * child class.
92       * 
93       * @return backing array object
94       */
95      
96      protected abstract Object   getArray();
97  
98      /**
99       * Set the backing array. This method is used by the type-agnostic base
100      * class code to set the array used for type-specific storage by the
101      * child class.
102      * 
103      * @param backing array object
104      */
105     
106     protected abstract void setArray(Object   array);
107 
108     /**
109      * Copy data after array resize. This default implementation just copies
110      * the entire contents of the old array to the start of the new array. It
111      * should be overridden in cases where data needs to be rearranged in the
112      * array after a resize.
113      * 
114      * @param base original array containing data
115      * @param grown resized array for data
116      */
117     
118     protected void resizeCopy(Object   base, Object   grown) {
119         System.arraycopy(base, 0, grown, 0, Array.getLength(base));
120     }
121 
122     /**
123      * Discards values for a range of indices in the array. Checks if the
124      * values stored in the array are object references, and if so clears 
125      * them. If the values are primitives, this method does nothing.
126      * 
127      * @param from index of first value to be discarded
128      * @param to index past last value to be discarded
129      */
130     
131     protected void discardValues(int from, int to) {
132         Object   values = getArray();
133         if (!values.getClass().getComponentType().isPrimitive()) {
134             Object  [] objects = (Object  [])values;
135             for (int i = from; i < to; i++) {
136                 objects[i] = null;
137             }
138         }
139     }
140 
141     /**
142      * Increase the size of the array to at least a specified size. The array
143      * will normally be at least doubled in size, but if a maximum size
144      * increment was specified in the constructor and the value is less than
145      * the current size of the array, the maximum increment will be used
146      * instead. If the requested size requires more than the default growth, 
147      * the requested size overrides the normal growth and determines the size
148      * of the replacement array.
149      * 
150      * @param required new minimum size required
151      */
152     
153     protected void growArray(int required) {
154         Object   base = getArray();
155         int size = Math.max(required,
156             m_countLimit + Math.min(m_countLimit, m_maximumGrowth));
157         Class   type = base.getClass().getComponentType();
158         Object   grown = Array.newInstance(type, size);
159         resizeCopy(base, grown);
160         m_countLimit = size;
161         setArray(grown);
162     }
163 
164     /**
165      * Ensure that the array has the capacity for at least the specified
166      * number of values.
167      * 
168      * @param min minimum capacity to be guaranteed
169      */
170     
171     public final void ensureCapacity(int min) {
172         if (min > m_countLimit) {
173             growArray(min);
174         }
175     }
176 
177     /**
178      * Constructs and returns a simple array containing the same data as held 
179      * in a portion of this growable array.
180      * 
181      * @param type element type for constructed array
182      * @param offset start offset in array
183      * @param length number of characters to use
184      * @return array containing a copy of the data
185      */
186     
187     protected Object   buildArray(Class   type, int offset, int length) {
188         Object   copy = Array.newInstance(type, length);
189         System.arraycopy(getArray(), offset, copy, 0, length);
190         return copy;
191     }
192 }
193
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags