001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.lib.editor.util;
043:
044: import java.util.AbstractList;
045: import java.util.List;
046: import java.util.RandomAccess;
047:
048: /**
049: * Utility methods related to arrays.
050: *
051: * @author Miloslav Metelka
052: * @version 1.00
053: */
054:
055: public final class ArrayUtilities {
056:
057: private static boolean[] EMPTY_BOOLEAN_ARRAY;
058:
059: private static char[] EMPTY_CHAR_ARRAY;
060:
061: private static int[] EMPTY_INT_ARRAY;
062:
063: private ArrayUtilities() {
064: // no instances
065: }
066:
067: public static boolean[] booleanArray(boolean[] oldArray) {
068: return booleanArray(oldArray,
069: (oldArray != null) ? oldArray.length << 1 : 1);
070: }
071:
072: public static boolean[] booleanArray(boolean[] oldArray, int newSize) {
073: return booleanArray(oldArray, newSize,
074: (oldArray != null) ? Math.min(newSize, oldArray.length)
075: : 0, true);
076: }
077:
078: public static boolean[] booleanArray(boolean[] oldArray,
079: int newSize, int copyLen, boolean forwardFill) {
080: boolean[] newArray = new boolean[newSize];
081: if (copyLen > 0)
082: if (forwardFill)
083: System.arraycopy(oldArray, 0, newArray, 0, copyLen);
084: else
085: // backward fill
086: System.arraycopy(oldArray, oldArray.length - copyLen,
087: newArray, newSize - copyLen, copyLen);
088: return newArray;
089: }
090:
091: public static char[] charArray(char[] oldArray) {
092: return charArray(oldArray,
093: (oldArray != null) ? oldArray.length << 1 : 1);
094: }
095:
096: public static char[] charArray(char[] oldArray, int newSize) {
097: return charArray(oldArray, newSize, (oldArray != null) ? Math
098: .min(newSize, oldArray.length) : 0, true);
099: }
100:
101: public static char[] charArray(char[] oldArray, int newSize,
102: int copyLen, boolean forwardFill) {
103: char[] newArray = new char[newSize];
104: if (copyLen > 0)
105: if (forwardFill)
106: System.arraycopy(oldArray, 0, newArray, 0, copyLen);
107: else
108: // backward fill
109: System.arraycopy(oldArray, oldArray.length - copyLen,
110: newArray, newSize - copyLen, copyLen);
111: return newArray;
112: }
113:
114: public static char[] charArray(char[] oldArray, int newSize,
115: int gapStart, int gapLength) {
116: char[] newArray = new char[newSize];
117: if (gapStart > 0)
118: System.arraycopy(oldArray, 0, newArray, 0, gapStart);
119: gapStart += gapLength;
120: gapLength = oldArray.length - gapStart;
121: if (gapLength > 0)
122: System.arraycopy(oldArray, gapStart, newArray, newSize
123: - gapLength, gapLength);
124: return newArray;
125: }
126:
127: public static int[] intArray(int[] oldArray) {
128: return intArray(oldArray,
129: (oldArray != null) ? oldArray.length << 1 : 1);
130: }
131:
132: public static int[] intArray(int[] oldArray, int newSize) {
133: return intArray(oldArray, newSize, (oldArray != null) ? Math
134: .min(newSize, oldArray.length) : 0, true);
135: }
136:
137: public static int[] intArray(int[] oldArray, int newSize,
138: int copyLen, boolean forwardFill) {
139: int[] newArray = new int[newSize];
140: if (copyLen > 0)
141: if (forwardFill)
142: System.arraycopy(oldArray, 0, newArray, 0, copyLen);
143: else
144: // backward fill
145: System.arraycopy(oldArray, oldArray.length - copyLen,
146: newArray, newSize - copyLen, copyLen);
147: return newArray;
148: }
149:
150: public static int[] intArray(int[] oldArray, int newSize,
151: int gapStart, int gapLength) {
152: int[] newArray = new int[newSize];
153: if (gapStart > 0)
154: System.arraycopy(oldArray, 0, newArray, 0, gapStart);
155: gapStart += gapLength;
156: gapLength = oldArray.length - gapStart;
157: if (gapLength > 0)
158: System.arraycopy(oldArray, gapStart, newArray, newSize
159: - gapLength, gapLength);
160: return newArray;
161: }
162:
163: public static boolean[] emptyBooleanArray() {
164: if (EMPTY_BOOLEAN_ARRAY == null) { // unsynced intentionally
165: EMPTY_BOOLEAN_ARRAY = new boolean[0];
166: }
167: return EMPTY_BOOLEAN_ARRAY;
168: }
169:
170: public static char[] emptyCharArray() {
171: if (EMPTY_CHAR_ARRAY == null) { // unsynced intentionally
172: EMPTY_CHAR_ARRAY = new char[0];
173: }
174: return EMPTY_CHAR_ARRAY;
175: }
176:
177: public static int[] emptyIntArray() {
178: if (EMPTY_INT_ARRAY == null) { // unsynced intentionally
179: EMPTY_INT_ARRAY = new int[0];
180: }
181: return EMPTY_INT_ARRAY;
182: }
183:
184: public static int digitCount(int number) {
185: return String.valueOf(Math.abs(number)).length();
186: }
187:
188: public static void appendIndex(StringBuilder sb, int index,
189: int maxDigitCount) {
190: String indexStr = String.valueOf(index);
191: appendSpaces(sb, maxDigitCount - indexStr.length());
192: sb.append(indexStr);
193: }
194:
195: public static void appendIndex(StringBuffer sb, int index,
196: int maxDigitCount) {
197: String indexStr = String.valueOf(index);
198: appendSpaces(sb, maxDigitCount - indexStr.length());
199: sb.append(indexStr);
200: }
201:
202: public static void appendSpaces(StringBuilder sb, int spaceCount) {
203: while (--spaceCount >= 0) {
204: sb.append(' ');
205: }
206: }
207:
208: public static void appendSpaces(StringBuffer sb, int spaceCount) {
209: while (--spaceCount >= 0) {
210: sb.append(' ');
211: }
212: }
213:
214: public static void appendBracketedIndex(StringBuilder sb,
215: int index, int maxDigitCount) {
216: sb.append('[');
217: appendIndex(sb, index, maxDigitCount);
218: sb.append("]: ");
219: }
220:
221: public static void appendBracketedIndex(StringBuffer sb, int index,
222: int maxDigitCount) {
223: sb.append('[');
224: appendIndex(sb, index, maxDigitCount);
225: sb.append("]: ");
226: }
227:
228: /**
229: * Return unmodifiable list for the given array.
230: * <br/>
231: * Unlike <code>Collections.unmodifiableList()</code> this method
232: * does not use any extra wrappers etc.
233: *
234: * @since 1.14
235: */
236: public static <E> List<E> unmodifiableList(E[] array) {
237: return new UnmodifiableList<E>(array);
238: }
239:
240: public static String toString(Object[] array) {
241: StringBuilder sb = new StringBuilder();
242: int maxDigitCount = digitCount(array.length);
243: for (int i = 0; i < array.length; i++) {
244: appendBracketedIndex(sb, i, maxDigitCount);
245: sb.append(array[i]);
246: sb.append('\n');
247: }
248: return sb.toString();
249: }
250:
251: public static String toString(int[] array) {
252: StringBuilder sb = new StringBuilder();
253: int maxDigitCount = digitCount(array.length);
254: for (int i = 0; i < array.length; i++) {
255: appendBracketedIndex(sb, i, maxDigitCount);
256: sb.append(array[i]);
257: sb.append('\n');
258: }
259: return sb.toString();
260: }
261:
262: private static final class UnmodifiableList<E> extends
263: AbstractList<E> implements RandomAccess {
264:
265: private E[] array;
266:
267: UnmodifiableList(E[] array) {
268: this .array = array;
269: }
270:
271: public E get(int index) {
272: if (index >= 0 && index < array.length) {
273: return array[index];
274: } else {
275: throw new IndexOutOfBoundsException("index = " + index
276: + ", size = " + array.length); //NOI18N
277: }
278: }
279:
280: public int size() {
281: return array.length;
282: }
283:
284: public Object[] toArray() {
285: return array.clone();
286: }
287:
288: public <T> T[] toArray(T[] a) {
289: if (a.length < array.length) {
290: @SuppressWarnings("unchecked")
291: T[] aa = (T[]) java.lang.reflect.Array.newInstance(a
292: .getClass().getComponentType(), array.length);
293: a = aa;
294: }
295: System.arraycopy(array, 0, a, 0, array.length);
296: if (a.length > array.length)
297: a[array.length] = null;
298: return a;
299: }
300:
301: }
302:
303: /**
304: * Searches for the <code>key</code> in the <code>array</code>.
305: *
306: * @param array the array to search in
307: * @param key the number to search for
308: *
309: * @return The index of the <code>key</code> in the <code>array</code>. For
310: * details see {@link #binarySearch(int[], int, int, int)}.
311: * @since 1.18
312: */
313: public static int binarySearch(int[] array, int key) {
314: return binarySearch(array, 0, array.length - 1, key);
315: }
316:
317: /**
318: * Searches for the <code>key</code> in the <code>array</code> in the area
319: * between <code>start</code> and <code>end</code>.
320: *
321: * @param array the array to search in
322: * @param start the first index to look at
323: * @param end the last index to look at
324: * @param key the number to search for
325: *
326: * @return The index of the search key, if it is contained in the array;
327: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
328: * <i>insertion point</i> is defined as the point at which the
329: * key would be inserted into the array: the index of the first
330: * element greater than the key, or <tt>array.length</tt>, if all
331: * elements in the array are less than the specified key. Note
332: * that this guarantees that the return value will be >= 0 if
333: * and only if the key is found.
334: * @since 1.18
335: */
336: public static int binarySearch(int[] array, int start, int end,
337: int key) {
338: assert start >= 0 && start < array.length : "Invalid start index "
339: + start + " (length = " + array.length + ")"; //NOI18N
340: assert end >= start && end < array.length : "Invalid end index "
341: + end
342: + " (start = "
343: + start
344: + ", length = "
345: + array.length + ")"; //NOI18N
346:
347: int low = start;
348: int high = end;
349:
350: while (low <= high) {
351: int mid = (low + high) >> 1;
352: int midVal = array[mid];
353: int cmp = midVal - key;
354:
355: if (cmp < 0) {
356: low = mid + 1;
357: } else if (cmp > 0) {
358: high = mid - 1;
359: } else {
360: return mid; // key found
361: }
362: }
363:
364: return -(low + 1); // key not found
365: }
366: }
|