- /*
- * Copyright 2001-2004 The Apache Software Foundation.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- /*
- * $Id: IntegerArray.java,v 1.8 2004/02/16 22:58:24 minchau Exp $
- */
-
- package com.sun.org.apache.xalan.internal.xsltc.util;
-
- /**
- * @author Jacek Ambroziak
- */
- public final class IntegerArray {
- private static final int InitialSize = 32;
-
- private int[] _array;
- private int _size;
- private int _free = 0;
-
- public IntegerArray() {
- this(InitialSize);
- }
-
- public IntegerArray(int size) {
- _array = new int[_size = size];
- }
-
- public IntegerArray(int[] array) {
- this(array.length);
- System.arraycopy(array, 0, _array, 0, _free = _size);
- }
-
- public void clear() {
- _free = 0;
- }
-
- public Object clone() {
- final IntegerArray clone = new IntegerArray(_free > 0 ? _free : 1);
- System.arraycopy(_array, 0, clone._array, 0, _free);
- clone._free = _free;
- return clone;
- }
-
- public int[] toIntArray() {
- final int[] result = new int[cardinality()];
- System.arraycopy(_array, 0, result, 0, cardinality());
- return result;
- }
-
- public final int at(int index) {
- return _array[index];
- }
-
- public final void set(int index, int value) {
- _array[index] = value;
- }
-
- public int indexOf(int n) {
- for (int i = 0; i < _free; i++) {
- if (n == _array[i]) return i;
- }
- return -1;
- }
-
- public final void add(int value) {
- if (_free == _size) {
- growArray(_size * 2);
- }
- _array[_free++] = value;
- }
-
- /**
- * Adds new int at the end if not already present.
- */
- public void addNew(int value) {
- for (int i = 0; i < _free; i++) {
- if (_array[i] == value) return; // already in array
- }
- add(value);
- }
-
- public void reverse() {
- int left = 0;
- int right = _free - 1;
-
- while (left < right) {
- int temp = _array[left];
- _array[left++] = _array[right];
- _array[right--] = temp;
- }
- }
-
- /**
- * Merge two sorted arrays and eliminate duplicates.
- */
- public void merge(IntegerArray other) {
- final int newSize = _free + other._free;
- // System.out.println("IntegerArray.merge() begin newSize = " + newSize);
- int[] newArray = new int[newSize];
-
- // Merge the two arrays
- int i = 0, j = 0, k;
- for (k = 0; i < _free && j < other._free; k++) {
- int x = _array[i];
- int y = other._array[j];
-
- if (x < y) {
- newArray[k] = x;
- i++;
- }
- else if (x > y) {
- newArray[k] = y;
- j++;
- }
- else {
- newArray[k] = x;
- i++; j++;
- }
- }
-
- // Copy the rest if of different lengths
- if (i >= _free) {
- while (j < other._free) {
- newArray[k++] = other._array[j++];
- }
- }
- else {
- while (i < _free) {
- newArray[k++] = _array[i++];
- }
- }
-
- // Update reference to this array
- _array = newArray;
- _free = _size = newSize;
- // System.out.println("IntegerArray.merge() end");
- }
-
- public void sort() {
- quicksort(_array, 0, _free - 1);
- }
-
- private static void quicksort(int[] array, int p, int r) {
- if (p < r) {
- final int q = partition(array, p, r);
- quicksort(array, p, q);
- quicksort(array, q + 1, r);
- }
- }
-
- private static int partition(int[] array, int p, int r) {
- final int x = array[(p + r) >>> 1];
- int i = p - 1; int j = r + 1;
-
- while (true) {
- while (x < array[--j]);
- while (x > array[++i]);
- if (i < j) {
- int temp = array[i];
- array[i] = array[j];
- array[j] = temp;
- }
- else {
- return j;
- }
- }
- }
-
- private void growArray(int size) {
- final int[] newArray = new int[_size = size];
- System.arraycopy(_array, 0, newArray, 0, _free);
- _array = newArray;
- }
-
- public int popLast() {
- return _array[--_free];
- }
-
- public int last() {
- return _array[_free - 1];
- }
-
- public void setLast(int n) {
- _array[_free - 1] = n;
- }
-
- public void pop() {
- _free--;
- }
-
- public void pop(int n) {
- _free -= n;
- }
-
- public final int cardinality() {
- return _free;
- }
-
- public void print(java.io.PrintStream out) {
- if (_free > 0) {
- for (int i = 0; i < _free - 1; i++) {
- out.print(_array[i]);
- out.print(' ');
- }
- out.println(_array[_free - 1]);
- }
- else {
- out.println("IntegerArray: empty");
- }
- }
- }