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: SuballocatedIntVector.java,v 1.3 2005/09/28 13:49:22 pvedula Exp $
22   */
23  package com.sun.org.apache.xml.internal.utils;
24  
25  /**
26   * A very simple table that stores a list of int. Very similar API to our
27   * IntVector class (same API); different internal storage.
28   *
29   * This version uses an array-of-arrays solution. Read/write access is thus
30   * a bit slower than the simple IntVector, and basic storage is a trifle
31   * higher due to the top-level array -- but appending is O(1) fast rather
32   * than O(N**2) slow, which will swamp those costs in situations where
33   * long vectors are being built up.
34   *
35   * Known issues:
36   *
37   * Some methods are private because they haven't yet been tested properly.
38   *
39   * Retrieval performance is critical, since this is used at the core
40   * of the DTM model. (Append performance is almost as important.)
41   * That's pushing me toward just letting reads from unset indices
42   * throw exceptions or return stale data; safer behavior would have
43   * performance costs.
44   * */
45  public class SuballocatedIntVector
46  {
47    /** Size of blocks to allocate          */
48    protected int m_blocksize;
49  
50    /** Bitwise addressing (much faster than div/remainder */
51    protected int m_SHIFT, m_MASK;
52  
53    /** The default number of blocks to (over)allocate by */
54    protected static final int NUMBLOCKS_DEFAULT = 32;
55  
56    /** The number of blocks to (over)allocate by */
57    protected int m_numblocks = NUMBLOCKS_DEFAULT;
58  
59    /** Array of arrays of ints          */
60    protected int m_map[][];
61  
62    /** Number of ints in array          */
63    protected int m_firstFree = 0;
64  
65    /** "Shortcut" handle to m_map[0]. Surprisingly helpful for short vectors. */
66    protected int m_map0[];
67  
68    /** "Shortcut" handle to most recently added row of m_map.
69     * Very helpful during construction.
70     * @xsl.usage internal
71     */
72    protected int m_buildCache[];
73    protected int m_buildCacheStartIndex;
74  
75  
76    /**
77     * Default constructor.  Note that the default
78     * block size is currently 2K, which may be overkill for
79     * small lists and undershootng for large ones.
80     */
81    public SuballocatedIntVector()
82    {
83      this(2048);
84    }
85  
86    /**
87     * Construct a IntVector, using the given block size and number
88     * of blocks. For efficiency, we will round the requested size
89     * off to a power of two.
90     *
91     * @param blocksize Size of block to allocate
92     * @param numblocks Number of blocks to allocate
93     * */
94    public SuballocatedIntVector(int blocksize, int numblocks)
95    {
96      //m_blocksize = blocksize;
97      for(m_SHIFT=0;0!=(blocksize>>>=1);++m_SHIFT)
98        ;
99      m_blocksize=1<<m_SHIFT;
100     m_MASK=m_blocksize-1;
101     m_numblocks = numblocks;
102 
103     m_map0=new int[m_blocksize];
104     m_map = new int[numblocks][];
105     m_map[0]=m_map0;
106     m_buildCache = m_map0;
107     m_buildCacheStartIndex = 0;
108   }
109 
110   /** Construct a IntVector, using the given block size and
111    * the default number of blocks (32).
112    *
113    * @param blocksize Size of block to allocate
114    * */
115   public SuballocatedIntVector(int blocksize)
116   {
117     this(blocksize, NUMBLOCKS_DEFAULT);
118   }
119 
120   /**
121    * Get the length of the list.
122    *
123    * @return length of the list
124    */
125   public int size()
126   {
127     return m_firstFree;
128   }
129 
130   /**
131    * Set the length of the list. This will only work to truncate the list, and
132    * even then it has not been heavily tested and may not be trustworthy.
133    *
134    * @return length of the list
135    */
136   public void setSize(int sz)
137   {
138     if(m_firstFree>sz) // Whups; had that backward!
139       m_firstFree = sz;
140   }
141 
142   /**
143    * Append a int onto the vector.
144    *
145    * @param value Int to add to the list
146    */
147   public  void addElement(int value)
148   {
149     int indexRelativeToCache = m_firstFree - m_buildCacheStartIndex;
150 
151     // Is the new index an index into the cache row of m_map?
152     if(indexRelativeToCache >= 0 && indexRelativeToCache < m_blocksize) {
153       m_buildCache[indexRelativeToCache]=value;
154       ++m_firstFree;
155     } else {
156       // Growing the outer array should be rare. We initialize to a
157       // total of m_blocksize squared elements, which at the default
158       // size is 4M integers... and we grow by at least that much each
159       // time.  However, attempts to microoptimize for this (assume
160       // long enough and catch exceptions) yield no noticable
161       // improvement.
162 
163       int index=m_firstFree>>>m_SHIFT;
164       int offset=m_firstFree&m_MASK;
165 
166       if(index>=m_map.length)
167       {
168         int newsize=index+m_numblocks;
169         int[][] newMap=new int[newsize][];
170         System.arraycopy(m_map, 0, newMap, 0, m_map.length);
171         m_map=newMap;
172       }
173       int[] block=m_map[index];
174       if(null==block)
175         block=m_map[index]=new int[m_blocksize];
176       block[offset]=value;
177 
178       // Cache the current row of m_map.  Next m_blocksize-1
179       // values added will go to this row.
180       m_buildCache = block;
181       m_buildCacheStartIndex = m_firstFree-offset;
182 
183       ++m_firstFree;
184     }
185   }
186 
187   /**
188    * Append several int values onto the vector.
189    *
190    * @param value Int to add to the list
191    */
192   private  void addElements(int value, int numberOfElements)
193   {
194     if(m_firstFree+numberOfElements<m_blocksize)
195       for (int i = 0; i < numberOfElements; i++)
196       {
197         m_map0[m_firstFree++]=value;
198       }
199     else
200     {
201       int index=m_firstFree>>>m_SHIFT;
202       int offset=m_firstFree&m_MASK;
203       m_firstFree+=numberOfElements;
204       while( numberOfElements>0)
205       {
206         if(index>=m_map.length)
207         {
208           int newsize=index+m_numblocks;
209           int[][] newMap=new int[newsize][];
210           System.arraycopy(m_map, 0, newMap, 0, m_map.length);
211           m_map=newMap;
212         }
213         int[] block=m_map[index];
214         if(null==block)
215           block=m_map[index]=new int[m_blocksize];
216         int copied=(m_blocksize-offset < numberOfElements)
217           ? m_blocksize-offset : numberOfElements;
218         numberOfElements-=copied;
219         while(copied-- > 0)
220           block[offset++]=value;
221 
222         ++index;offset=0;
223       }
224     }
225   }
226 
227   /**
228    * Append several slots onto the vector, but do not set the values.
229    * Note: "Not Set" means the value is unspecified.
230    *
231    * @param numberOfElements Int to add to the list
232    */
233   private  void addElements(int numberOfElements)
234   {
235     int newlen=m_firstFree+numberOfElements;
236     if(newlen>m_blocksize)
237     {
238       int index=m_firstFree>>>m_SHIFT;
239       int newindex=(m_firstFree+numberOfElements)>>>m_SHIFT;
240       for(int i=index+1;i<=newindex;++i)
241         m_map[i]=new int[m_blocksize];
242     }
243     m_firstFree=newlen;
244   }
245 
246   /**
247    * Inserts the specified node in this vector at the specified index.
248    * Each component in this vector with an index greater or equal to
249    * the specified index is shifted upward to have an index one greater
250    * than the value it had previously.
251    *
252    * Insertion may be an EXPENSIVE operation!
253    *
254    * @param value Int to insert
255    * @param at Index of where to insert
256    */
257   private  void insertElementAt(int value, int at)
258   {
259     if(at==m_firstFree)
260       addElement(value);
261     else if (at>m_firstFree)
262     {
263       int index=at>>>m_SHIFT;
264       if(index>=m_map.length)
265       {
266         int newsize=index+m_numblocks;
267         int[][] newMap=new int[newsize][];
268         System.arraycopy(m_map, 0, newMap, 0, m_map.length);
269         m_map=newMap;
270       }
271       int[] block=m_map[index];
272       if(null==block)
273         block=m_map[index]=new int[m_blocksize];
274       int offset=at&m_MASK;
275           block[offset]=value;
276           m_firstFree=offset+1;
277         }
278     else
279     {
280       int index=at>>>m_SHIFT;
281       int maxindex=m_firstFree>>>m_SHIFT; // %REVIEW% (m_firstFree+1?)
282       ++m_firstFree;
283       int offset=at&m_MASK;
284       int push;
285 
286       // ***** Easier to work down from top?
287       while(index<=maxindex)
288       {
289         int copylen=m_blocksize-offset-1;
290         int[] block=m_map[index];
291         if(null==block)
292         {
293           push=0;
294           block=m_map[index]=new int[m_blocksize];
295         }
296         else
297         {
298           push=block[m_blocksize-1];
299           System.arraycopy(block, offset , block, offset+1, copylen);
300         }
301         block[offset]=value;
302         value=push;
303         offset=0;
304         ++index;
305       }
306     }
307   }
308 
309   /**
310    * Wipe it out. Currently defined as equivalent to setSize(0).
311    */
312   public void removeAllElements()
313   {
314     m_firstFree = 0;
315     m_buildCache = m_map0;
316     m_buildCacheStartIndex = 0;
317   }
318 
319   /**
320    * Removes the first occurrence of the argument from this vector.
321    * If the object is found in this vector, each component in the vector
322    * with an index greater or equal to the object's index is shifted
323    * downward to have an index one smaller than the value it had
324    * previously.
325    *
326    * @param s Int to remove from array
327    *
328    * @return True if the int was removed, false if it was not found
329    */
330   private  boolean removeElement(int s)
331   {
332     int at=indexOf(s,0);
333     if(at<0)
334       return false;
335     removeElementAt(at);
336     return true;
337   }
338 
339   /**
340    * Deletes the component at the specified index. Each component in
341    * this vector with an index greater or equal to the specified
342    * index is shifted downward to have an index one smaller than
343    * the value it had previously.
344    *
345    * @param at index of where to remove and int
346    */
347   private  void removeElementAt(int at)
348   {
349         // No point in removing elements that "don't exist"...
350     if(at<m_firstFree)
351     {
352       int index=at>>>m_SHIFT;
353       int maxindex=m_firstFree>>>m_SHIFT;
354       int offset=at&m_MASK;
355 
356       while(index<=maxindex)
357       {
358         int copylen=m_blocksize-offset-1;
359         int[] block=m_map[index];
360         if(null==block)
361           block=m_map[index]=new int[m_blocksize];
362         else
363           System.arraycopy(block, offset+1, block, offset, copylen);
364         if(index<maxindex)
365         {
366           int[] next=m_map[index+1];
367           if(next!=null)
368             block[m_blocksize-1]=(next!=null) ? next[0] : 0;
369         }
370         else
371           block[m_blocksize-1]=0;
372         offset=0;
373         ++index;
374       }
375     }
376     --m_firstFree;
377   }
378 
379   /**
380    * Sets the component at the specified index of this vector to be the
381    * specified object. The previous component at that position is discarded.
382    *
383    * The index must be a value greater than or equal to 0 and less
384    * than the current size of the vector.
385    *
386    * @param value object to set
387    * @param at    Index of where to set the object
388    */
389   public void setElementAt(int value, int at)
390   {
391     if(at<m_blocksize)
392       m_map0[at]=value;
393     else
394     {
395       int index=at>>>m_SHIFT;
396       int offset=at&m_MASK;
397 
398       if(index>=m_map.length)
399       {
400         int newsize=index+m_numblocks;
401         int[][] newMap=new int[newsize][];
402         System.arraycopy(m_map, 0, newMap, 0, m_map.length);
403         m_map=newMap;
404       }
405 
406       int[] block=m_map[index];
407       if(null==block)
408         block=m_map[index]=new int[m_blocksize];
409       block[offset]=value;
410     }
411 
412     if(at>=m_firstFree)
413       m_firstFree=at+1;
414   }
415 
416 
417   /**
418    * Get the nth element. This is often at the innermost loop of an
419    * application, so performance is critical.
420    *
421    * @param i index of value to get
422    *
423    * @return value at given index. If that value wasn't previously set,
424    * the result is undefined for performance reasons. It may throw an
425    * exception (see below), may return zero, or (if setSize has previously
426    * been used) may return stale data.
427    *
428    * @throws ArrayIndexOutOfBoundsException if the index was _clearly_
429    * unreasonable (negative, or past the highest block).
430    *
431    * @throws NullPointerException if the index points to a block that could
432    * have existed (based on the highest index used) but has never had anything
433    * set into it.
434    * %REVIEW% Could add a catch to create the block in that case, or return 0.
435    * Try/Catch is _supposed_ to be nearly free when not thrown to. Do we
436    * believe that? Should we have a separate safeElementAt?
437    */
438   public int elementAt(int i)
439   {
440     // This is actually a significant optimization!
441     if(i<m_blocksize)
442       return m_map0[i];
443 
444     return m_map[i>>>m_SHIFT][i&m_MASK];
445   }
446 
447   /**
448    * Tell if the table contains the given node.
449    *
450    * @param s object to look for
451    *
452    * @return true if the object is in the list
453    */
454   private  boolean contains(int s)
455   {
456     return (indexOf(s,0) >= 0);
457   }
458 
459   /**
460    * Searches for the first occurence of the given argument,
461    * beginning the search at index, and testing for equality
462    * using the equals method.
463    *
464    * @param elem object to look for
465    * @param index Index of where to begin search
466    * @return the index of the first occurrence of the object
467    * argument in this vector at position index or later in the
468    * vector; returns -1 if the object is not found.
469    */
470   public int indexOf(int elem, int index)
471   {
472         if(index>=m_firstFree)
473                 return -1;
474 
475     int bindex=index>>>m_SHIFT;
476     int boffset=index&m_MASK;
477     int maxindex=m_firstFree>>>m_SHIFT;
478     int[] block;
479 
480     for(;bindex<maxindex;++bindex)
481     {
482       block=m_map[bindex];
483       if(block!=null)
484         for(int offset=boffset;offset<m_blocksize;++offset)
485           if(block[offset]==elem)
486             return offset+bindex*m_blocksize;
487       boffset=0; // after first
488     }
489     // Last block may need to stop before end
490     int maxoffset=m_firstFree&m_MASK;
491     block=m_map[maxindex];
492     for(int offset=boffset;offset<maxoffset;++offset)
493       if(block[offset]==elem)
494         return offset+maxindex*m_blocksize;
495 
496     return -1;
497   }
498 
499   /**
500    * Searches for the first occurence of the given argument,
501    * beginning the search at index, and testing for equality
502    * using the equals method.
503    *
504    * @param elem object to look for
505    * @return the index of the first occurrence of the object
506    * argument in this vector at position index or later in the
507    * vector; returns -1 if the object is not found.
508    */
509   public int indexOf(int elem)
510   {
511     return indexOf(elem,0);
512   }
513 
514   /**
515    * Searches for the first occurence of the given argument,
516    * beginning the search at index, and testing for equality
517    * using the equals method.
518    *
519    * @param elem Object to look for
520    * @return the index of the first occurrence of the object
521    * argument in this vector at position index or later in the
522    * vector; returns -1 if the object is not found.
523    */
524   private  int lastIndexOf(int elem)
525   {
526     int boffset=m_firstFree&m_MASK;
527     for(int index=m_firstFree>>>m_SHIFT;
528         index>=0;
529         --index)
530     {
531       int[] block=m_map[index];
532       if(block!=null)
533         for(int offset=boffset; offset>=0; --offset)
534           if(block[offset]==elem)
535             return offset+index*m_blocksize;
536       boffset=0; // after first
537     }
538     return -1;
539   }
540 
541   /**
542    * Return the internal m_map0 array
543    * @return the m_map0 array
544    */
545   public final int[] getMap0()
546   {
547     return m_map0;
548   }
549 
550   /**
551    * Return the m_map double array
552    * @return the internal map of array of arrays
553    */
554   public final int[][] getMap()
555   {
556     return m_map;
557   }
558 
559 }