KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > hammurapi > inspectors > metrics > statistics > 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 JavaDoc
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 JavaDoc clone()
537     throws CloneNotSupportedException JavaDoc
538   {
539     return new IntVector(this);
540   }
541
542
543   public String JavaDoc toString(){
544     StringBuffer JavaDoc strb = new StringBuffer JavaDoc();
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
Popular Tags