1 /* 2 * reserved comment block 3 * DO NOT REMOVE OR ALTER! 4 */ 5 /* 6 * Licensed to the Apache Software Foundation (ASF) under one or more 7 * contributor license agreements. See the NOTICE file distributed with 8 * this work for additional information regarding copyright ownership. 9 * The ASF licenses this file to You under the Apache License, Version 2.0 10 * (the "License"); you may not use this file except in compliance with 11 * the License. You may obtain a copy of the License at 12 * 13 * http://www.apache.org/licenses/LICENSE-2.0 14 * 15 * Unless required by applicable law or agreed to in writing, software 16 * distributed under the License is distributed on an "AS IS" BASIS, 17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 18 * See the License for the specific language governing permissions and 19 * limitations under the License. 20 */ 21 22 package com.sun.org.apache.xalan.internal.xsltc.util; 23 24 /** 25 * @author Jacek Ambroziak 26 */ 27 public final class IntegerArray { 28 private static final int InitialSize = 32; 29 30 private int[] _array; 31 private int _size; 32 private int _free = 0; 33 34 public IntegerArray() { 35 this(InitialSize); 36 } 37 38 public IntegerArray(int size) { 39 _array = new int[_size = size]; 40 } 41 42 public IntegerArray(int[] array) { 43 this(array.length); 44 System.arraycopy(array, 0, _array, 0, _free = _size); 45 } 46 47 public void clear() { 48 _free = 0; 49 } 50 51 public Object clone() { 52 final IntegerArray clone = new IntegerArray(_free > 0 ? _free : 1); 53 System.arraycopy(_array, 0, clone._array, 0, _free); 54 clone._free = _free; 55 return clone; 56 } 57 58 public int[] toIntArray() { 59 final int[] result = new int[cardinality()]; 60 System.arraycopy(_array, 0, result, 0, cardinality()); 61 return result; 62 } 63 64 public final int at(int index) { 65 return _array[index]; 66 } 67 68 public final void set(int index, int value) { 69 _array[index] = value; 70 } 71 72 public int indexOf(int n) { 73 for (int i = 0; i < _free; i++) { 74 if (n == _array[i]) return i; 75 } 76 return -1; 77 } 78 79 public final void add(int value) { 80 if (_free == _size) { 81 growArray(_size * 2); 82 } 83 _array[_free++] = value; 84 } 85 86 /** 87 * Adds new int at the end if not already present. 88 */ 89 public void addNew(int value) { 90 for (int i = 0; i < _free; i++) { 91 if (_array[i] == value) return; // already in array 92 } 93 add(value); 94 } 95 96 public void reverse() { 97 int left = 0; 98 int right = _free - 1; 99 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 }