View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   /*
6    * Copyright 1999-2004 The Apache Software Foundation.
7    *
8    * Licensed under the Apache License, Version 2.0 (the "License");
9    * you may not use this file except in compliance with the License.
10   * You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  /*
21   * $Id: IntVector.java,v 1.2.4.1 2005/09/15 08:15:45 suresh_emailid Exp $
22   */
23  package com.sun.org.apache.xml.internal.utils;
24  
25  /**
26   * A very simple table that stores a list of int.
27   *
28   * This version is based on a "realloc" strategy -- a simle array is
29   * used, and when more storage is needed, a larger array is obtained
30   * and all existing data is recopied into it. As a result, read/write
31   * access to existing nodes is O(1) fast but appending may be O(N**2)
32   * slow. See also SuballocatedIntVector.
33   * @xsl.usage internal
34   */
35  public class IntVector implements Cloneable
36  {
37  
38    /** Size of blocks to allocate          */
39    protected int m_blocksize;
40  
41    /** Array of ints          */
42    protected int m_map[]; // IntStack is trying to see this directly
43  
44    /** Number of ints in array          */
45    protected int m_firstFree = 0;
46  
47    /** Size of array          */
48    protected int m_mapSize;
49  
50    /**
51     * Default constructor.  Note that the default
52     * block size is very small, for small lists.
53     */
54    public IntVector()
55    {
56  
57      m_blocksize = 32;
58      m_mapSize = m_blocksize;
59      m_map = new int[m_blocksize];
60    }
61  
62    /**
63     * Construct a IntVector, using the given block size.
64     *
65     * @param blocksize Size of block to allocate
66     */
67    public IntVector(int blocksize)
68    {
69  
70      m_blocksize = blocksize;
71      m_mapSize = blocksize;
72      m_map = new int[blocksize];
73    }
74  
75    /**
76     * Construct a IntVector, using the given block size.
77     *
78     * @param blocksize Size of block to allocate
79     */
80    public IntVector(int blocksize, int increaseSize)
81    {
82  
83      m_blocksize = increaseSize;
84      m_mapSize = blocksize;
85      m_map = new int[blocksize];
86    }
87  
88    /**
89     * Copy constructor for IntVector
90     *
91     * @param v Existing IntVector to copy
92     */
93    public IntVector(IntVector v)
94    {
95          m_map = new int[v.m_mapSize];
96      m_mapSize = v.m_mapSize;
97      m_firstFree = v.m_firstFree;
98          m_blocksize = v.m_blocksize;
99          System.arraycopy(v.m_map, 0, m_map, 0, m_firstFree);
100   }
101 
102   /**
103    * Get the length of the list.
104    *
105    * @return length of the list
106    */
107   public final int size()
108   {
109     return m_firstFree;
110   }
111 
112   /**
113    * Get the length of the list.
114    *
115    * @return length of the list
116    */
117   public final void setSize(int sz)
118   {
119     m_firstFree = sz;
120   }
121 
122 
123   /**
124    * Append a int onto the vector.
125    *
126    * @param value Int to add to the list
127    */
128   public final void addElement(int value)
129   {
130 
131     if ((m_firstFree + 1) >= m_mapSize)
132     {
133       m_mapSize += m_blocksize;
134 
135       int newMap[] = new int[m_mapSize];
136 
137       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
138 
139       m_map = newMap;
140     }
141 
142     m_map[m_firstFree] = value;
143 
144     m_firstFree++;
145   }
146 
147   /**
148    * Append several int values onto the vector.
149    *
150    * @param value Int to add to the list
151    */
152   public final void addElements(int value, int numberOfElements)
153   {
154 
155     if ((m_firstFree + numberOfElements) >= m_mapSize)
156     {
157       m_mapSize += (m_blocksize+numberOfElements);
158 
159       int newMap[] = new int[m_mapSize];
160 
161       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
162 
163       m_map = newMap;
164     }
165 
166     for (int i = 0; i < numberOfElements; i++)
167     {
168       m_map[m_firstFree] = value;
169       m_firstFree++;
170     }
171   }
172 
173   /**
174    * Append several slots onto the vector, but do not set the values.
175    *
176    * @param numberOfElements Int to add to the list
177    */
178   public final void addElements(int numberOfElements)
179   {
180 
181     if ((m_firstFree + numberOfElements) >= m_mapSize)
182     {
183       m_mapSize += (m_blocksize+numberOfElements);
184 
185       int newMap[] = new int[m_mapSize];
186 
187       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
188 
189       m_map = newMap;
190     }
191 
192     m_firstFree += numberOfElements;
193   }
194 
195 
196   /**
197    * Inserts the specified node in this vector at the specified index.
198    * Each component in this vector with an index greater or equal to
199    * the specified index is shifted upward to have an index one greater
200    * than the value it had previously.
201    *
202    * @param value Int to insert
203    * @param at Index of where to insert
204    */
205   public final void insertElementAt(int value, int at)
206   {
207 
208     if ((m_firstFree + 1) >= m_mapSize)
209     {
210       m_mapSize += m_blocksize;
211 
212       int newMap[] = new int[m_mapSize];
213 
214       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
215 
216       m_map = newMap;
217     }
218 
219     if (at <= (m_firstFree - 1))
220     {
221       System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at);
222     }
223 
224     m_map[at] = value;
225 
226     m_firstFree++;
227   }
228 
229   /**
230    * Inserts the specified node in this vector at the specified index.
231    * Each component in this vector with an index greater or equal to
232    * the specified index is shifted upward to have an index one greater
233    * than the value it had previously.
234    */
235   public final void removeAllElements()
236   {
237 
238     for (int i = 0; i < m_firstFree; i++)
239     {
240       m_map[i] = java.lang.Integer.MIN_VALUE;
241     }
242 
243     m_firstFree = 0;
244   }
245 
246   /**
247    * Removes the first occurrence of the argument from this vector.
248    * If the object is found in this vector, each component in the vector
249    * with an index greater or equal to the object's index is shifted
250    * downward to have an index one smaller than the value it had
251    * previously.
252    *
253    * @param s Int to remove from array
254    *
255    * @return True if the int was removed, false if it was not found
256    */
257   public final boolean removeElement(int s)
258   {
259 
260     for (int i = 0; i < m_firstFree; i++)
261     {
262       if (m_map[i] == s)
263       {
264         if ((i + 1) < m_firstFree)
265           System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i);
266         else
267           m_map[i] = java.lang.Integer.MIN_VALUE;
268 
269         m_firstFree--;
270 
271         return true;
272       }
273     }
274 
275     return false;
276   }
277 
278   /**
279    * Deletes the component at the specified index. Each component in
280    * this vector with an index greater or equal to the specified
281    * index is shifted downward to have an index one smaller than
282    * the value it had previously.
283    *
284    * @param i index of where to remove and int
285    */
286   public final void removeElementAt(int i)
287   {
288 
289     if (i > m_firstFree)
290       System.arraycopy(m_map, i + 1, m_map, i, m_firstFree);
291     else
292       m_map[i] = java.lang.Integer.MIN_VALUE;
293 
294     m_firstFree--;
295   }
296 
297   /**
298    * Sets the component at the specified index of this vector to be the
299    * specified object. The previous component at that position is discarded.
300    *
301    * The index must be a value greater than or equal to 0 and less
302    * than the current size of the vector.
303    *
304    * @param value object to set
305    * @param index Index of where to set the object
306    */
307   public final void setElementAt(int value, int index)
308   {
309     m_map[index] = value;
310   }
311 
312   /**
313    * Get the nth element.
314    *
315    * @param i index of object to get
316    *
317    * @return object at given index
318    */
319   public final int elementAt(int i)
320   {
321     return m_map[i];
322   }
323 
324   /**
325    * Tell if the table contains the given node.
326    *
327    * @param s object to look for
328    *
329    * @return true if the object is in the list
330    */
331   public final boolean contains(int s)
332   {
333 
334     for (int i = 0; i < m_firstFree; i++)
335     {
336       if (m_map[i] == s)
337         return true;
338     }
339 
340     return false;
341   }
342 
343   /**
344    * Searches for the first occurence of the given argument,
345    * beginning the search at index, and testing for equality
346    * using the equals method.
347    *
348    * @param elem object to look for
349    * @param index Index of where to begin search
350    * @return the index of the first occurrence of the object
351    * argument in this vector at position index or later in the
352    * vector; returns -1 if the object is not found.
353    */
354   public final int indexOf(int elem, int index)
355   {
356 
357     for (int i = index; i < m_firstFree; i++)
358     {
359       if (m_map[i] == elem)
360         return i;
361     }
362 
363     return java.lang.Integer.MIN_VALUE;
364   }
365 
366   /**
367    * Searches for the first occurence of the given argument,
368    * beginning the search at index, and testing for equality
369    * using the equals method.
370    *
371    * @param elem object to look for
372    * @return the index of the first occurrence of the object
373    * argument in this vector at position index or later in the
374    * vector; returns -1 if the object is not found.
375    */
376   public final int indexOf(int elem)
377   {
378 
379     for (int i = 0; i < m_firstFree; i++)
380     {
381       if (m_map[i] == elem)
382         return i;
383     }
384 
385     return java.lang.Integer.MIN_VALUE;
386   }
387 
388   /**
389    * Searches for the first occurence of the given argument,
390    * beginning the search at index, and testing for equality
391    * using the equals method.
392    *
393    * @param elem Object to look for
394    * @return the index of the first occurrence of the object
395    * argument in this vector at position index or later in the
396    * vector; returns -1 if the object is not found.
397    */
398   public final int lastIndexOf(int elem)
399   {
400 
401     for (int i = (m_firstFree - 1); i >= 0; i--)
402     {
403       if (m_map[i] == elem)
404         return i;
405     }
406 
407     return java.lang.Integer.MIN_VALUE;
408   }
409 
410   /**
411    * Returns clone of current IntVector
412    *
413    * @return clone of current IntVector
414    */
415   public Object clone()
416     throws CloneNotSupportedException
417   {
418         return new IntVector(this);
419   }
420 
421 }