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 }