View Javadoc
1   /*
2    * reserved comment block
3    * DO NOT REMOVE OR ALTER!
4    */
5   /*
6    * Copyright 2001-2004 The Apache Software Foundation.
7    *
8    * Licensed under the Apache License, Version 2.0 (the "License");
9    * you may not use this file except in compliance with the License.
10   * You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  /*
21   * $Id: IntegerArray.java,v 1.2.4.1 2005/09/06 11:44:56 pvedula Exp $
22   */
23  
24  package com.sun.org.apache.xalan.internal.xsltc.util;
25  
26  /**
27   * @author Jacek Ambroziak
28   */
29  public final class IntegerArray {
30      private static final int InitialSize = 32;
31  
32      private int[] _array;
33      private int   _size;
34      private int   _free = 0;
35  
36      public IntegerArray() {
37          this(InitialSize);
38      }
39  
40      public IntegerArray(int size) {
41          _array = new int[_size = size];
42      }
43  
44      public IntegerArray(int[] array) {
45          this(array.length);
46          System.arraycopy(array, 0, _array, 0, _free = _size);
47      }
48  
49      public void clear() {
50          _free = 0;
51      }
52  
53      public Object clone() {
54          final IntegerArray clone = new IntegerArray(_free > 0 ? _free : 1);
55          System.arraycopy(_array, 0, clone._array, 0, _free);
56          clone._free = _free;
57          return clone;
58      }
59  
60      public int[] toIntArray() {
61          final int[] result = new int[cardinality()];
62          System.arraycopy(_array, 0, result, 0, cardinality());
63          return result;
64      }
65  
66      public final int at(int index) {
67          return _array[index];
68      }
69  
70      public final void set(int index, int value) {
71          _array[index] = value;
72      }
73  
74      public int indexOf(int n) {
75          for (int i = 0; i < _free; i++) {
76              if (n == _array[i]) return i;
77          }
78          return -1;
79      }
80  
81      public final void add(int value) {
82          if (_free == _size) {
83              growArray(_size * 2);
84          }
85          _array[_free++] = value;
86      }
87  
88      /**
89       * Adds new int at the end if not already present.
90       */
91      public void addNew(int value) {
92          for (int i = 0; i < _free; i++) {
93              if (_array[i] == value) return;  // already in array
94          }
95          add(value);
96      }
97  
98      public void reverse() {
99          int left = 0;
100         int right = _free - 1;
101 
102         while (left < right) {
103             int temp = _array[left];
104             _array[left++] = _array[right];
105             _array[right--] = temp;
106         }
107     }
108 
109     /**
110      * Merge two sorted arrays and eliminate duplicates.
111      * Elements of the other IntegerArray must not be changed.
112      */
113     public void merge(final IntegerArray other) {
114         final int newSize = _free + other._free;
115 // System.out.println("IntegerArray.merge() begin newSize = " + newSize);
116         int[] newArray = new int[newSize];
117 
118         // Merge the two arrays
119         int i = 0, j = 0, k;
120         for (k = 0; i < _free && j < other._free; k++) {
121             int x = _array[i];
122             int y = other._array[j];
123 
124             if (x < y) {
125                 newArray[k] = x;
126                 i++;
127             }
128             else if (x > y) {
129                 newArray[k] = y;
130                 j++;
131             }
132             else {
133                 newArray[k] = x;
134                 i++; j++;
135             }
136         }
137 
138         // Copy the rest if of different lengths
139         if (i >= _free) {
140             while (j < other._free) {
141                 newArray[k++] = other._array[j++];
142             }
143         }
144         else {
145             while (i < _free) {
146                 newArray[k++] = _array[i++];
147             }
148         }
149 
150         // Update reference to this array
151         _array = newArray;
152         _free = _size = newSize;
153 // System.out.println("IntegerArray.merge() end");
154     }
155 
156     public void sort() {
157         quicksort(_array, 0, _free - 1);
158     }
159 
160     private static void quicksort(int[] array, int p, int r) {
161         if (p < r) {
162             final int q = partition(array, p, r);
163             quicksort(array, p, q);
164             quicksort(array, q + 1, r);
165         }
166     }
167 
168     private static int partition(int[] array, int p, int r) {
169         final int x = array[(p + r) >>> 1];
170         int i = p - 1; int j = r + 1;
171 
172         while (true) {
173             while (x < array[--j]);
174             while (x > array[++i]);
175             if (i < j) {
176                 int temp = array[i];
177                 array[i] = array[j];
178                 array[j] = temp;
179             }
180             else {
181                 return j;
182             }
183         }
184     }
185 
186     private void growArray(int size) {
187         final int[] newArray = new int[_size = size];
188         System.arraycopy(_array, 0, newArray, 0, _free);
189         _array = newArray;
190     }
191 
192     public int popLast() {
193         return _array[--_free];
194     }
195 
196     public int last() {
197         return _array[_free - 1];
198     }
199 
200     public void setLast(int n) {
201         _array[_free - 1] = n;
202     }
203 
204     public void pop() {
205         _free--;
206     }
207 
208     public void pop(int n) {
209         _free -= n;
210     }
211 
212     public final int cardinality() {
213         return _free;
214     }
215 
216     public void print(java.io.PrintStream out) {
217         if (_free > 0) {
218             for (int i = 0; i < _free - 1; i++) {
219                 out.print(_array[i]);
220                 out.print(' ');
221             }
222             out.println(_array[_free - 1]);
223         }
224         else {
225             out.println("IntegerArray: empty");
226         }
227     }
228 }