KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > org > apache > xalan > internal > xsltc > util > IntegerArray


1 /*
2  * Copyright 2001-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: IntegerArray.java,v 1.8 2004/02/16 22:58:24 minchau Exp $
18  */
19
20 package com.sun.org.apache.xalan.internal.xsltc.util;
21
22 /**
23  * @author Jacek Ambroziak
24  */
25 public final class IntegerArray {
26     private static final int InitialSize = 32;
27     
28     private int[] _array;
29     private int _size;
30     private int _free = 0;
31   
32     public IntegerArray() {
33     this(InitialSize);
34     }
35   
36     public IntegerArray(int size) {
37     _array = new int[_size = size];
38     }
39
40     public IntegerArray(int[] array) {
41     this(array.length);
42     System.arraycopy(array, 0, _array, 0, _free = _size);
43     }
44
45     public void clear() {
46     _free = 0;
47     }
48
49     public Object JavaDoc clone() {
50     final IntegerArray clone = new IntegerArray(_free > 0 ? _free : 1);
51     System.arraycopy(_array, 0, clone._array, 0, _free);
52     clone._free = _free;
53     return clone;
54     }
55
56     public int[] toIntArray() {
57     final int[] result = new int[cardinality()];
58     System.arraycopy(_array, 0, result, 0, cardinality());
59     return result;
60     }
61
62     public final int at(int index) {
63     return _array[index];
64     }
65
66     public final void set(int index, int value) {
67     _array[index] = value;
68     }
69
70     public int indexOf(int n) {
71     for (int i = 0; i < _free; i++) {
72         if (n == _array[i]) return i;
73     }
74     return -1;
75     }
76
77     public final void add(int value) {
78     if (_free == _size) {
79         growArray(_size * 2);
80     }
81     _array[_free++] = value;
82     }
83   
84     /**
85      * Adds new int at the end if not already present.
86      */
87     public void addNew(int value) {
88     for (int i = 0; i < _free; i++) {
89         if (_array[i] == value) return; // already in array
90 }
91     add(value);
92     }
93
94     public void reverse() {
95     int left = 0;
96     int right = _free - 1;
97
98     while (left < right) {
99         int temp = _array[left];
100         _array[left++] = _array[right];
101         _array[right--] = temp;
102     }
103     }
104
105     /**
106      * Merge two sorted arrays and eliminate duplicates.
107      */
108     public void merge(IntegerArray other) {
109     final int newSize = _free + other._free;
110 // System.out.println("IntegerArray.merge() begin newSize = " + newSize);
111 int[] newArray = new int[newSize];
112
113     // Merge the two arrays
114 int i = 0, j = 0, k;
115     for (k = 0; i < _free && j < other._free; k++) {
116         int x = _array[i];
117         int y = other._array[j];
118
119         if (x < y) {
120         newArray[k] = x;
121         i++;
122         }
123         else if (x > y) {
124         newArray[k] = y;
125         j++;
126         }
127         else {
128         newArray[k] = x;
129         i++; j++;
130         }
131     }
132
133     // Copy the rest if of different lengths
134 if (i >= _free) {
135         while (j < other._free) {
136         newArray[k++] = other._array[j++];
137         }
138     }
139     else {
140         while (i < _free) {
141         newArray[k++] = _array[i++];
142         }
143     }
144
145     // Update reference to this array
146 _array = newArray;
147     _free = _size = newSize;
148 // System.out.println("IntegerArray.merge() end");
149 }
150
151     public void sort() {
152     quicksort(_array, 0, _free - 1);
153     }
154
155     private static void quicksort(int[] array, int p, int r) {
156     if (p < r) {
157         final int q = partition(array, p, r);
158         quicksort(array, p, q);
159         quicksort(array, q + 1, r);
160     }
161     }
162     
163     private static int partition(int[] array, int p, int r) {
164     final int x = array[(p + r) >>> 1];
165     int i = p - 1; int j = r + 1;
166
167     while (true) {
168         while (x < array[--j]);
169         while (x > array[++i]);
170         if (i < j) {
171         int temp = array[i];
172         array[i] = array[j];
173         array[j] = temp;
174         }
175         else {
176         return j;
177         }
178     }
179     }
180
181     private void growArray(int size) {
182     final int[] newArray = new int[_size = size];
183     System.arraycopy(_array, 0, newArray, 0, _free);
184     _array = newArray;
185     }
186
187     public int popLast() {
188     return _array[--_free];
189     }
190
191     public int last() {
192     return _array[_free - 1];
193     }
194
195     public void setLast(int n) {
196     _array[_free - 1] = n;
197     }
198
199     public void pop() {
200     _free--;
201     }
202
203     public void pop(int n) {
204     _free -= n;
205     }
206   
207     public final int cardinality() {
208     return _free;
209     }
210
211     public void print(java.io.PrintStream JavaDoc out) {
212     if (_free > 0) {
213         for (int i = 0; i < _free - 1; i++) {
214         out.print(_array[i]);
215         out.print(' ');
216         }
217         out.println(_array[_free - 1]);
218     }
219     else {
220         out.println("IntegerArray: empty");
221     }
222     }
223 }
224
Popular Tags