IntVector


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: IntVector.java,v 1.2 2004/06/19 06:41:22 pvlasov Exp $
18   */
19  // package org.apache.xml.utils;
20  
21  package org.hammurapi.inspectors.metrics.statistics;
22  
23  /**
24   * A very simple table that stores a list of int.
25   *
26   * This version is based on a "realloc" strategy -- a simle array is
27   * used, and when more storage is needed, a larger array is obtained
28   * and all existing data is recopied into it. As a result, read/write
29   * access to existing nodes is O(1) fast but appending may be O(N**2)
30   * slow. See also SuballocatedIntVector.
31   * @xsl.usage internal
32   */
33  public class IntVector implements Cloneable  
34  {
35  
36    /** Size of blocks to allocate          */
37    protected int m_blocksize;
38  
39    /** Array of ints          */
40    protected int m_map[]; // IntStack is trying to see this directly
41  
42    /** Number of ints in array          */
43    protected int m_firstFree = 0;
44  
45    /** Size of array          */
46    protected int m_mapSize;
47  
48    /**
49     * Default constructor.  Note that the default
50     * block size is very small, for small lists.
51     */
52    public IntVector()
53    {
54  
55      m_blocksize = 32;
56      m_mapSize = m_blocksize;
57      m_map = new int[m_blocksize];
58    }
59  
60    public IntVector(int[] intarray )
61    {
62      m_blocksize = 32;
63      m_mapSize = m_blocksize;
64      m_map = new int[m_blocksize];
65      for( int i=0; i< intarray.length; i++){
66           this.addElement(intarray[i]);
67           }
68    }
69  
70    /**
71     * Construct a IntVector, using the given block size.
72     *
73     * @param blocksize Size of block to allocate
74     */
75    public IntVector(int blocksize)
76    {
77  
78      m_blocksize = blocksize;
79      m_mapSize = blocksize;
80      m_map = new int[blocksize];
81    }
82  
83    /**
84     * Construct a IntVector, using the given block size.
85     *
86     * @param blocksize Size of block to allocate
87     */
88    public IntVector(int blocksize, int increaseSize)
89    {
90  
91      m_blocksize = increaseSize;
92      m_mapSize = blocksize;
93      m_map = new int[blocksize];
94    }
95  
96    /**
97     * Copy constructor for IntVector
98     *
99     * @param v Existing IntVector to copy
100    */
101   public IntVector(IntVector v)
102   {
103     m_map = new int[v.m_mapSize];
104     m_mapSize = v.m_mapSize;
105     m_firstFree = v.m_firstFree;
106     m_blocksize = v.m_blocksize;
107     System.arraycopy(v.m_map, 0, m_map, 0, m_firstFree);
108   }
109 
110   /**
111    * Get the length of the list.
112    *
113    * @return length of the list
114    */
115   public final int size()
116   {
117     return m_firstFree;
118   }
119 
120   public boolean isEmpty(){
121     return m_firstFree == 0;
122   }
123 
124   /**
125    * Get the length of the list.
126    *
127    * @return length of the list
128    */
129   public final void setSize(int sz)
130   {
131     m_firstFree = sz;
132   }
133 
134 
135   /**
136    * Append a int onto the vector.
137    *
138    * @param value Int to add to the list
139    */
140   public final void addElement(int value)
141   {
142 
143     if ((m_firstFree + 1) >= m_mapSize)
144     {
145       m_mapSize += m_blocksize;
146 
147       int newMap[] = new int[m_mapSize];
148 
149       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
150 
151       m_map = newMap;
152     }
153 
154     m_map[m_firstFree] = value;
155 
156     m_firstFree++;
157   }
158 
159   /**
160    * Append several int values onto the vector.
161    *
162    * @param value Int to add to the list
163    */
164   public final void addElements(int value, int numberOfElements)
165   {
166 
167     if ((m_firstFree + numberOfElements) >= m_mapSize)
168     {
169       m_mapSize += (m_blocksize+numberOfElements);
170 
171       int newMap[] = new int[m_mapSize];
172 
173       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
174 
175       m_map = newMap;
176     }
177 
178     for (int i = 0; i < numberOfElements; i++)
179     {
180       m_map[m_firstFree] = value;
181       m_firstFree++;
182     }
183   }
184 
185   /*
186   Copyright � 1999 CERN - European Organization for Nuclear Research.
187   Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
188   is hereby granted without fee, provided that the above copyright notice appear in all copies and
189   that both that copyright notice and this permission notice appear in supporting documentation.
190   CERN makes no representations about the suitability of this software for any purpose.
191   It is provided "as is" without expressed or implied warranty.
192   */
193 
194   public void sort(){
195 
196      quickSort1( this.m_map, 0, this.m_firstFree);
197   }
198 
199   /**
200    * Sorts the specified sub-array of chars into ascending order.
201    */
202   private static void quickSort1( final int x[], int off, int len) {
203     int SMALL = 7;
204     int MEDIUM = 40;
205 
206     IntComparator comp = new IntComparator() {
207         public int compare(int a, int b) {
208             // return x[a]==x[b] ? 0 : (x[a]<x[b] ? -1 : 1);
209             return a==b ? 0 : (a<b ? -1 : 1);
210         }
211     };
212 
213     // Insertion sort on smallest arrays
214     if (len < SMALL) {
215         for (int i=off; i<len+off; i++)
216         for (int j=i; j>off && comp.compare(x[j-1],x[j])>0; j--)
217             swap(x, j, j-1);
218         return;
219     }
220 
221     // Choose a partition element, v
222     int m = off + len/2;       // Small arrays, middle element
223     if (len > SMALL) {
224         int l = off;
225         int n = off + len - 1;
226         if (len > MEDIUM) {        // Big arrays, pseudomedian of 9
227         int s = len/8;
228         l = med3(x, l,     l+s, l+2*s, comp);
229         m = med3(x, m-s,   m,   m+s, comp);
230         n = med3(x, n-2*s, n-s, n, comp);
231         }
232         m = med3(x, l, m, n, comp); // Mid-size, med of 3
233     }
234     int v = x[m];
235 
236     // Establish Invariant: v* (<v)* (>v)* v*
237     int a = off, b = a, c = off + len - 1, d = c;
238     while(true) {
239         int comparison;
240         while (b <= c && (comparison=comp.compare(x[b],v))<=0) {
241         if (comparison == 0)
242             swap(x, a++, b);
243         b++;
244         }
245         while (c >= b && (comparison=comp.compare(x[c],v))>=0) {
246         if (comparison == 0)
247             swap(x, c, d--);
248         c--;
249         }
250         if (b > c)
251         break;
252         swap(x, b++, c--);
253     }
254 
255     // Swap partition elements back to middle
256     int s, n = off + len;
257     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
258     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
259 
260     // Recursively sort non-partition-elements
261     if ((s = b-a) > 1)
262         quickSort1(x, off, s);
263     if ((s = d-c) > 1)
264         quickSort1(x, n-s, s);
265   }
266 
267   /**
268    * Swaps x[a] with x[b].
269    */
270   private static void swap(int x[], int a, int b) {
271     int t = x[a];
272     x[a] = x[b];
273     x[b] = t;
274   }
275 
276   /**
277      * Returns the index of the median of the three indexed chars.
278      */
279     private static int med3(int x[], int a, int b, int c, IntComparator comp) {
280         int ab = comp.compare(x[a],x[b]);
281         int ac = comp.compare(x[a],x[c]);
282         int bc = comp.compare(x[b],x[c]);
283         return (ab<0 ?
284         (bc<0 ? b : ac<0 ? c : a) :
285         (bc>0 ? b : ac>0 ? c : a));
286     }
287     /**
288      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
289      */
290     private static void vecswap(int x[], int a, int b, int n) {
291     for (int i=0; i<n; i++, a++, b++)
292         swap(x, a, b);
293     }
294   /**
295    * Append several slots onto the vector, but do not set the values.
296    *
297    * @param value Int to add to the list
298    */
299   public final void addElements(int numberOfElements)
300   {
301 
302     if ((m_firstFree + numberOfElements) >= m_mapSize)
303     {
304       m_mapSize += (m_blocksize+numberOfElements);
305 
306       int newMap[] = new int[m_mapSize];
307 
308       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
309 
310       m_map = newMap;
311     }
312 
313     m_firstFree += numberOfElements;
314   }
315 
316 
317   /**
318    * Inserts the specified node in this vector at the specified index.
319    * Each component in this vector with an index greater or equal to
320    * the specified index is shifted upward to have an index one greater
321    * than the value it had previously.
322    *
323    * @param value Int to insert
324    * @param at Index of where to insert
325    */
326   public final void insertElementAt(int value, int at)
327   {
328 
329     if ((m_firstFree + 1) >= m_mapSize)
330     {
331       m_mapSize += m_blocksize;
332 
333       int newMap[] = new int[m_mapSize];
334 
335       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
336 
337       m_map = newMap;
338     }
339 
340     if (at <= (m_firstFree - 1))
341     {
342       System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at);
343     }
344 
345     m_map[at] = value;
346 
347     m_firstFree++;
348   }
349 
350   /**
351    * Inserts the specified node in this vector at the specified index.
352    * Each component in this vector with an index greater or equal to
353    * the specified index is shifted upward to have an index one greater
354    * than the value it had previously.
355    */
356   public final void removeAllElements()
357   {
358 
359     for (int i = 0; i < m_firstFree; i++)
360     {
361       m_map[i] = java.lang.Integer.MIN_VALUE;
362     }
363 
364     m_firstFree = 0;
365   }
366 
367   /**
368    * Removes the first occurrence of the argument from this vector.
369    * If the object is found in this vector, each component in the vector
370    * with an index greater or equal to the object's index is shifted
371    * downward to have an index one smaller than the value it had
372    * previously.
373    *
374    * @param s Int to remove from array
375    *
376    * @return True if the int was removed, false if it was not found
377    */
378   public final boolean removeElement(int s)
379   {
380 
381     for (int i = 0; i < m_firstFree; i++)
382     {
383       if (m_map[i] == s)
384       {
385         if ((i + 1) < m_firstFree)
386           System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i);
387         else
388           m_map[i] = java.lang.Integer.MIN_VALUE;
389 
390         m_firstFree--;
391 
392         return true;
393       }
394     }
395 
396     return false;
397   }
398 
399   /**
400    * Deletes the component at the specified index. Each component in
401    * this vector with an index greater or equal to the specified
402    * index is shifted downward to have an index one smaller than
403    * the value it had previously.
404    *
405    * @param i index of where to remove and int
406    */
407   public final void removeElementAt(int i)
408   {
409 
410     if (i > m_firstFree)
411       System.arraycopy(m_map, i + 1, m_map, i, m_firstFree);
412     else
413       m_map[i] = java.lang.Integer.MIN_VALUE;
414 
415     m_firstFree--;
416   }
417 
418   /**
419    * Sets the component at the specified index of this vector to be the
420    * specified object. The previous component at that position is discarded.
421    *
422    * The index must be a value greater than or equal to 0 and less
423    * than the current size of the vector.
424    *
425    * @param node object to set
426    * @param index Index of where to set the object
427    */
428   public final void setElementAt(int value, int index)
429   {
430     m_map[index] = value;
431   }
432 
433   /**
434    * Get the nth element.
435    *
436    * @param i index of object to get
437    *
438    * @return object at given index
439    */
440   public final int elementAt(int i)
441   {
442     return m_map[i];
443   }
444 
445   /**
446    * Tell if the table contains the given node.
447    *
448    * @param s object to look for
449    *
450    * @return true if the object is in the list
451    */
452   public final boolean contains(int s)
453   {
454 
455     for (int i = 0; i < m_firstFree; i++)
456     {
457       if (m_map[i] == s)
458         return true;
459     }
460 
461     return false;
462   }
463 
464   /**
465    * Searches for the first occurence of the given argument,
466    * beginning the search at index, and testing for equality
467    * using the equals method.
468    *
469    * @param elem object to look for
470    * @param index Index of where to begin search
471    * @return the index of the first occurrence of the object
472    * argument in this vector at position index or later in the
473    * vector; returns -1 if the object is not found.
474    */
475   public final int indexOf(int elem, int index)
476   {
477 
478     for (int i = index; i < m_firstFree; i++)
479     {
480       if (m_map[i] == elem)
481         return i;
482     }
483 
484     return java.lang.Integer.MIN_VALUE;
485   }
486 
487   /**
488    * Searches for the first occurence of the given argument,
489    * beginning the search at index, and testing for equality
490    * using the equals method.
491    *
492    * @param elem object to look for
493    * @return the index of the first occurrence of the object
494    * argument in this vector at position index or later in the
495    * vector; returns -1 if the object is not found.
496    */
497   public final int indexOf(int elem)
498   {
499 
500     for (int i = 0; i < m_firstFree; i++)
501     {
502       if (m_map[i] == elem)
503         return i;
504     }
505 
506     return java.lang.Integer.MIN_VALUE;
507   }
508 
509   /**
510    * Searches for the first occurence of the given argument,
511    * beginning the search at index, and testing for equality
512    * using the equals method.
513    *
514    * @param elem Object to look for
515    * @return the index of the first occurrence of the object
516    * argument in this vector at position index or later in the
517    * vector; returns -1 if the object is not found.
518    */
519   public final int lastIndexOf(int elem)
520   {
521 
522     for (int i = (m_firstFree - 1); i >= 0; i--)
523     {
524       if (m_map[i] == elem)
525         return i;
526     }
527 
528     return java.lang.Integer.MIN_VALUE;
529   }
530 
531   /**
532    * Returns clone of current IntVector
533    *
534    * @return clone of current IntVector
535    */
536   public Object   clone()
537     throws CloneNotSupportedException  
538   {
539     return new IntVector(this);
540   }
541 
542 
543   public String   toString(){
544     StringBuffer   strb = new StringBuffer  ();
545     strb.append ( "[");
546     for ( int i= 0; i< m_firstFree; i++){
547         strb.append ( this.elementAt(i) );
548         if( i+1 == m_firstFree){
549             strb.append ( "]");
550         }else{
551             strb.append ( "," );
552         }
553   }
554 
555     return strb.toString();
556     }
557 }
558
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags