001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: IntegerArray.java 1225434 2011-12-29 05:07:42Z mrglavas $
020 */
021
022 package org.apache.xalan.xsltc.util;
023
024 /**
025 * @author Jacek Ambroziak
026 */
027 public final class IntegerArray implements Cloneable {
028 private static final int InitialSize = 32;
029
030 private int[] _array;
031 private int _size;
032 private int _free = 0;
033
034 public IntegerArray() {
035 this(InitialSize);
036 }
037
038 public IntegerArray(int size) {
039 _array = new int[_size = size];
040 }
041
042 public IntegerArray(int[] array) {
043 this(array.length);
044 System.arraycopy(array, 0, _array, 0, _free = _size);
045 }
046
047 public void clear() {
048 _free = 0;
049 }
050
051 public Object clone() {
052 final IntegerArray clone = new IntegerArray(_free > 0 ? _free : 1);
053 System.arraycopy(_array, 0, clone._array, 0, _free);
054 clone._free = _free;
055 return clone;
056 }
057
058 public int[] toIntArray() {
059 final int[] result = new int[cardinality()];
060 System.arraycopy(_array, 0, result, 0, cardinality());
061 return result;
062 }
063
064 public final int at(int index) {
065 return _array[index];
066 }
067
068 public final void set(int index, int value) {
069 _array[index] = value;
070 }
071
072 public int indexOf(int n) {
073 for (int i = 0; i < _free; i++) {
074 if (n == _array[i]) return i;
075 }
076 return -1;
077 }
078
079 public final void add(int value) {
080 if (_free == _size) {
081 growArray(_size * 2);
082 }
083 _array[_free++] = value;
084 }
085
086 /**
087 * Adds new int at the end if not already present.
088 */
089 public void addNew(int value) {
090 for (int i = 0; i < _free; i++) {
091 if (_array[i] == value) return; // already in array
092 }
093 add(value);
094 }
095
096 public void reverse() {
097 int left = 0;
098 int right = _free - 1;
099
100 while (left < right) {
101 int temp = _array[left];
102 _array[left++] = _array[right];
103 _array[right--] = temp;
104 }
105 }
106
107 /**
108 * Merge two sorted arrays and eliminate duplicates.
109 * Elements of the other IntegerArray must not be changed.
110 */
111 public void merge(final IntegerArray other) {
112 final int newSize = _free + other._free;
113 // System.out.println("IntegerArray.merge() begin newSize = " + newSize);
114 int[] newArray = new int[newSize];
115
116 // Merge the two arrays
117 int i = 0, j = 0, k;
118 for (k = 0; i < _free && j < other._free; k++) {
119 int x = _array[i];
120 int y = other._array[j];
121
122 if (x < y) {
123 newArray[k] = x;
124 i++;
125 }
126 else if (x > y) {
127 newArray[k] = y;
128 j++;
129 }
130 else {
131 newArray[k] = x;
132 i++; j++;
133 }
134 }
135
136 // Copy the rest if of different lengths
137 if (i >= _free) {
138 while (j < other._free) {
139 newArray[k++] = other._array[j++];
140 }
141 }
142 else {
143 while (i < _free) {
144 newArray[k++] = _array[i++];
145 }
146 }
147
148 // Update reference to this array
149 _array = newArray;
150 _free = _size = newSize;
151 // System.out.println("IntegerArray.merge() end");
152 }
153
154 public void sort() {
155 quicksort(_array, 0, _free - 1);
156 }
157
158 private static void quicksort(int[] array, int p, int r) {
159 if (p < r) {
160 final int q = partition(array, p, r);
161 quicksort(array, p, q);
162 quicksort(array, q + 1, r);
163 }
164 }
165
166 private static int partition(int[] array, int p, int r) {
167 final int x = array[(p + r) >>> 1];
168 int i = p - 1; int j = r + 1;
169
170 while (true) {
171 while (x < array[--j]);
172 while (x > array[++i]);
173 if (i < j) {
174 int temp = array[i];
175 array[i] = array[j];
176 array[j] = temp;
177 }
178 else {
179 return j;
180 }
181 }
182 }
183
184 private void growArray(int size) {
185 final int[] newArray = new int[_size = size];
186 System.arraycopy(_array, 0, newArray, 0, _free);
187 _array = newArray;
188 }
189
190 public int popLast() {
191 return _array[--_free];
192 }
193
194 public int last() {
195 return _array[_free - 1];
196 }
197
198 public void setLast(int n) {
199 _array[_free - 1] = n;
200 }
201
202 public void pop() {
203 _free--;
204 }
205
206 public void pop(int n) {
207 _free -= n;
208 }
209
210 public final int cardinality() {
211 return _free;
212 }
213
214 public void print(java.io.PrintStream out) {
215 if (_free > 0) {
216 for (int i = 0; i < _free - 1; i++) {
217 out.print(_array[i]);
218 out.print(' ');
219 }
220 out.println(_array[_free - 1]);
221 }
222 else {
223 out.println("IntegerArray: empty");
224 }
225 }
226 }