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