SuballocatedIntVector


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