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
22package com.sun.org.apache.xalan.internal.xsltc.util;
23
24/**
25 * @author Jacek Ambroziak
26 */
27public 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}
227