001: /*
002: * Copyright 1999-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: /*
017: * $Id: IntVector.java,v 1.2 2004/06/19 06:41:22 pvlasov Exp $
018: */
019: // package org.apache.xml.utils;
020: package org.hammurapi.inspectors.metrics.statistics;
021:
022: /**
023: * A very simple table that stores a list of int.
024: *
025: * This version is based on a "realloc" strategy -- a simle array is
026: * used, and when more storage is needed, a larger array is obtained
027: * and all existing data is recopied into it. As a result, read/write
028: * access to existing nodes is O(1) fast but appending may be O(N**2)
029: * slow. See also SuballocatedIntVector.
030: * @xsl.usage internal
031: */
032: public class IntVector implements Cloneable {
033:
034: /** Size of blocks to allocate */
035: protected int m_blocksize;
036:
037: /** Array of ints */
038: protected int m_map[]; // IntStack is trying to see this directly
039:
040: /** Number of ints in array */
041: protected int m_firstFree = 0;
042:
043: /** Size of array */
044: protected int m_mapSize;
045:
046: /**
047: * Default constructor. Note that the default
048: * block size is very small, for small lists.
049: */
050: public IntVector() {
051:
052: m_blocksize = 32;
053: m_mapSize = m_blocksize;
054: m_map = new int[m_blocksize];
055: }
056:
057: public IntVector(int[] intarray) {
058: m_blocksize = 32;
059: m_mapSize = m_blocksize;
060: m_map = new int[m_blocksize];
061: for (int i = 0; i < intarray.length; i++) {
062: this .addElement(intarray[i]);
063: }
064: }
065:
066: /**
067: * Construct a IntVector, using the given block size.
068: *
069: * @param blocksize Size of block to allocate
070: */
071: public IntVector(int blocksize) {
072:
073: m_blocksize = blocksize;
074: m_mapSize = blocksize;
075: m_map = new int[blocksize];
076: }
077:
078: /**
079: * Construct a IntVector, using the given block size.
080: *
081: * @param blocksize Size of block to allocate
082: */
083: public IntVector(int blocksize, int increaseSize) {
084:
085: m_blocksize = increaseSize;
086: m_mapSize = blocksize;
087: m_map = new int[blocksize];
088: }
089:
090: /**
091: * Copy constructor for IntVector
092: *
093: * @param v Existing IntVector to copy
094: */
095: public IntVector(IntVector v) {
096: m_map = new int[v.m_mapSize];
097: m_mapSize = v.m_mapSize;
098: m_firstFree = v.m_firstFree;
099: m_blocksize = v.m_blocksize;
100: System.arraycopy(v.m_map, 0, m_map, 0, m_firstFree);
101: }
102:
103: /**
104: * Get the length of the list.
105: *
106: * @return length of the list
107: */
108: public final int size() {
109: return m_firstFree;
110: }
111:
112: public boolean isEmpty() {
113: return m_firstFree == 0;
114: }
115:
116: /**
117: * Get the length of the list.
118: *
119: * @return length of the list
120: */
121: public final void setSize(int sz) {
122: m_firstFree = sz;
123: }
124:
125: /**
126: * Append a int onto the vector.
127: *
128: * @param value Int to add to the list
129: */
130: public final void addElement(int value) {
131:
132: if ((m_firstFree + 1) >= m_mapSize) {
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: if ((m_firstFree + numberOfElements) >= m_mapSize) {
155: m_mapSize += (m_blocksize + numberOfElements);
156:
157: int newMap[] = new int[m_mapSize];
158:
159: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
160:
161: m_map = newMap;
162: }
163:
164: for (int i = 0; i < numberOfElements; i++) {
165: m_map[m_firstFree] = value;
166: m_firstFree++;
167: }
168: }
169:
170: /*
171: Copyright © 1999 CERN - European Organization for Nuclear Research.
172: Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
173: is hereby granted without fee, provided that the above copyright notice appear in all copies and
174: that both that copyright notice and this permission notice appear in supporting documentation.
175: CERN makes no representations about the suitability of this software for any purpose.
176: It is provided "as is" without expressed or implied warranty.
177: */
178:
179: public void sort() {
180:
181: quickSort1(this .m_map, 0, this .m_firstFree);
182: }
183:
184: /**
185: * Sorts the specified sub-array of chars into ascending order.
186: */
187: private static void quickSort1(final int x[], int off, int len) {
188: int SMALL = 7;
189: int MEDIUM = 40;
190:
191: IntComparator comp = new IntComparator() {
192: public int compare(int a, int b) {
193: // return x[a]==x[b] ? 0 : (x[a]<x[b] ? -1 : 1);
194: return a == b ? 0 : (a < b ? -1 : 1);
195: }
196: };
197:
198: // Insertion sort on smallest arrays
199: if (len < SMALL) {
200: for (int i = off; i < len + off; i++)
201: for (int j = i; j > off
202: && comp.compare(x[j - 1], x[j]) > 0; j--)
203: swap(x, j, j - 1);
204: return;
205: }
206:
207: // Choose a partition element, v
208: int m = off + len / 2; // Small arrays, middle element
209: if (len > SMALL) {
210: int l = off;
211: int n = off + len - 1;
212: if (len > MEDIUM) { // Big arrays, pseudomedian of 9
213: int s = len / 8;
214: l = med3(x, l, l + s, l + 2 * s, comp);
215: m = med3(x, m - s, m, m + s, comp);
216: n = med3(x, n - 2 * s, n - s, n, comp);
217: }
218: m = med3(x, l, m, n, comp); // Mid-size, med of 3
219: }
220: int v = x[m];
221:
222: // Establish Invariant: v* (<v)* (>v)* v*
223: int a = off, b = a, c = off + len - 1, d = c;
224: while (true) {
225: int comparison;
226: while (b <= c && (comparison = comp.compare(x[b], v)) <= 0) {
227: if (comparison == 0)
228: swap(x, a++, b);
229: b++;
230: }
231: while (c >= b && (comparison = comp.compare(x[c], v)) >= 0) {
232: if (comparison == 0)
233: swap(x, c, d--);
234: c--;
235: }
236: if (b > c)
237: break;
238: swap(x, b++, c--);
239: }
240:
241: // Swap partition elements back to middle
242: int s, n = off + len;
243: s = Math.min(a - off, b - a);
244: vecswap(x, off, b - s, s);
245: s = Math.min(d - c, n - d - 1);
246: vecswap(x, b, n - s, s);
247:
248: // Recursively sort non-partition-elements
249: if ((s = b - a) > 1)
250: quickSort1(x, off, s);
251: if ((s = d - c) > 1)
252: quickSort1(x, n - s, s);
253: }
254:
255: /**
256: * Swaps x[a] with x[b].
257: */
258: private static void swap(int x[], int a, int b) {
259: int t = x[a];
260: x[a] = x[b];
261: x[b] = t;
262: }
263:
264: /**
265: * Returns the index of the median of the three indexed chars.
266: */
267: private static int med3(int x[], int a, int b, int c,
268: IntComparator comp) {
269: int ab = comp.compare(x[a], x[b]);
270: int ac = comp.compare(x[a], x[c]);
271: int bc = comp.compare(x[b], x[c]);
272: return (ab < 0 ? (bc < 0 ? b : ac < 0 ? c : a) : (bc > 0 ? b
273: : ac > 0 ? c : a));
274: }
275:
276: /**
277: * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
278: */
279: private static void vecswap(int x[], int a, int b, int n) {
280: for (int i = 0; i < n; i++, a++, b++)
281: swap(x, a, b);
282: }
283:
284: /**
285: * Append several slots onto the vector, but do not set the values.
286: *
287: * @param value Int to add to the list
288: */
289: public final void addElements(int numberOfElements) {
290:
291: if ((m_firstFree + numberOfElements) >= m_mapSize) {
292: m_mapSize += (m_blocksize + numberOfElements);
293:
294: int newMap[] = new int[m_mapSize];
295:
296: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
297:
298: m_map = newMap;
299: }
300:
301: m_firstFree += numberOfElements;
302: }
303:
304: /**
305: * Inserts the specified node in this vector at the specified index.
306: * Each component in this vector with an index greater or equal to
307: * the specified index is shifted upward to have an index one greater
308: * than the value it had previously.
309: *
310: * @param value Int to insert
311: * @param at Index of where to insert
312: */
313: public final void insertElementAt(int value, int at) {
314:
315: if ((m_firstFree + 1) >= m_mapSize) {
316: m_mapSize += m_blocksize;
317:
318: int newMap[] = new int[m_mapSize];
319:
320: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
321:
322: m_map = newMap;
323: }
324:
325: if (at <= (m_firstFree - 1)) {
326: System
327: .arraycopy(m_map, at, m_map, at + 1, m_firstFree
328: - at);
329: }
330:
331: m_map[at] = value;
332:
333: m_firstFree++;
334: }
335:
336: /**
337: * Inserts the specified node in this vector at the specified index.
338: * Each component in this vector with an index greater or equal to
339: * the specified index is shifted upward to have an index one greater
340: * than the value it had previously.
341: */
342: public final void removeAllElements() {
343:
344: for (int i = 0; i < m_firstFree; i++) {
345: m_map[i] = java.lang.Integer.MIN_VALUE;
346: }
347:
348: m_firstFree = 0;
349: }
350:
351: /**
352: * Removes the first occurrence of the argument from this vector.
353: * If the object is found in this vector, each component in the vector
354: * with an index greater or equal to the object's index is shifted
355: * downward to have an index one smaller than the value it had
356: * previously.
357: *
358: * @param s Int to remove from array
359: *
360: * @return True if the int was removed, false if it was not found
361: */
362: public final boolean removeElement(int s) {
363:
364: for (int i = 0; i < m_firstFree; i++) {
365: if (m_map[i] == s) {
366: if ((i + 1) < m_firstFree)
367: System.arraycopy(m_map, i + 1, m_map, i - 1,
368: m_firstFree - i);
369: else
370: m_map[i] = java.lang.Integer.MIN_VALUE;
371:
372: m_firstFree--;
373:
374: return true;
375: }
376: }
377:
378: return false;
379: }
380:
381: /**
382: * Deletes the component at the specified index. Each component in
383: * this vector with an index greater or equal to the specified
384: * index is shifted downward to have an index one smaller than
385: * the value it had previously.
386: *
387: * @param i index of where to remove and int
388: */
389: public final void removeElementAt(int i) {
390:
391: if (i > m_firstFree)
392: System.arraycopy(m_map, i + 1, m_map, i, m_firstFree);
393: else
394: m_map[i] = java.lang.Integer.MIN_VALUE;
395:
396: m_firstFree--;
397: }
398:
399: /**
400: * Sets the component at the specified index of this vector to be the
401: * specified object. The previous component at that position is discarded.
402: *
403: * The index must be a value greater than or equal to 0 and less
404: * than the current size of the vector.
405: *
406: * @param node object to set
407: * @param index Index of where to set the object
408: */
409: public final void setElementAt(int value, int index) {
410: m_map[index] = value;
411: }
412:
413: /**
414: * Get the nth element.
415: *
416: * @param i index of object to get
417: *
418: * @return object at given index
419: */
420: public final int elementAt(int i) {
421: return m_map[i];
422: }
423:
424: /**
425: * Tell if the table contains the given node.
426: *
427: * @param s object to look for
428: *
429: * @return true if the object is in the list
430: */
431: public final boolean contains(int s) {
432:
433: for (int i = 0; i < m_firstFree; i++) {
434: if (m_map[i] == s)
435: return true;
436: }
437:
438: return false;
439: }
440:
441: /**
442: * Searches for the first occurence of the given argument,
443: * beginning the search at index, and testing for equality
444: * using the equals method.
445: *
446: * @param elem object to look for
447: * @param index Index of where to begin search
448: * @return the index of the first occurrence of the object
449: * argument in this vector at position index or later in the
450: * vector; returns -1 if the object is not found.
451: */
452: public final int indexOf(int elem, int index) {
453:
454: for (int i = index; i < m_firstFree; i++) {
455: if (m_map[i] == elem)
456: return i;
457: }
458:
459: return java.lang.Integer.MIN_VALUE;
460: }
461:
462: /**
463: * Searches for the first occurence of the given argument,
464: * beginning the search at index, and testing for equality
465: * using the equals method.
466: *
467: * @param elem object to look for
468: * @return the index of the first occurrence of the object
469: * argument in this vector at position index or later in the
470: * vector; returns -1 if the object is not found.
471: */
472: public final int indexOf(int elem) {
473:
474: for (int i = 0; i < m_firstFree; i++) {
475: if (m_map[i] == elem)
476: return i;
477: }
478:
479: return java.lang.Integer.MIN_VALUE;
480: }
481:
482: /**
483: * Searches for the first occurence of the given argument,
484: * beginning the search at index, and testing for equality
485: * using the equals method.
486: *
487: * @param elem Object to look for
488: * @return the index of the first occurrence of the object
489: * argument in this vector at position index or later in the
490: * vector; returns -1 if the object is not found.
491: */
492: public final int lastIndexOf(int elem) {
493:
494: for (int i = (m_firstFree - 1); i >= 0; i--) {
495: if (m_map[i] == elem)
496: return i;
497: }
498:
499: return java.lang.Integer.MIN_VALUE;
500: }
501:
502: /**
503: * Returns clone of current IntVector
504: *
505: * @return clone of current IntVector
506: */
507: public Object clone() throws CloneNotSupportedException {
508: return new IntVector(this );
509: }
510:
511: public String toString() {
512: StringBuffer strb = new StringBuffer();
513: strb.append("[");
514: for (int i = 0; i < m_firstFree; i++) {
515: strb.append(this .elementAt(i));
516: if (i + 1 == m_firstFree) {
517: strb.append("]");
518: } else {
519: strb.append(",");
520: }
521: }
522:
523: return strb.toString();
524: }
525: }
|