001: /*
002: * Copyright (C) 1996-2004, International Business Machines
003: * Corporation and others. All Rights Reserved.
004: */
005:
006: /*
007: 7/29/96
008: Modified to search portions of an integer array. Should be retested.
009: */
010:
011: package com.ibm.richtext.styledtext;
012:
013: /**
014: * This class searches a segment of an array of integers. The segment
015: * must be sorted in ascending order (but this class does not verify this).
016: * Also, this class aliases the array; if the array is modified later the
017: * search results are undefined.
018: */
019: final class FastIntBinarySearch {
020: static final String COPYRIGHT = "(C) Copyright IBM Corp. 1998-1999 - All Rights Reserved";
021: private int dataArray[];
022: private int auxStart;
023: private int power;
024:
025: private int fFirstIndex;
026:
027: private static final int exp2[] = { 1, 2, 4, 8, 16, 32, 64, 128,
028: 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536,
029: 131072 };
030:
031: public FastIntBinarySearch(int data[]) {
032: this (data, 0, data.length);
033: }
034:
035: public FastIntBinarySearch(int data[], int firstValidIndex,
036: int validLength) {
037: setData(data, firstValidIndex, validLength);
038: }
039:
040: public void setData(int data[]) {
041:
042: setData(data, 0, data.length);
043: }
044:
045: public void setData(int data[], int firstValidIndex, int validLength) {
046:
047: if (data.length < 1)
048: throw new IllegalArgumentException();
049: if (data.length >= exp2[exp2.length - 1])
050: throw new IllegalArgumentException();
051:
052: dataArray = data;
053: fFirstIndex = firstValidIndex;
054:
055: for (power = exp2.length - 1; power > 0
056: && validLength < exp2[power]; power--) {
057: }
058:
059: // at this point, array.length >= 2^power
060:
061: auxStart = validLength - exp2[power];
062: }
063:
064: /**
065: * Return the index in the array of the first element which is at least
066: * as large as <tt>value</tt>. If value is larger than the largest
067: * element in the array the last valid index in the array is returned.
068: */
069: public int findIndex(int value) {
070: int index = exp2[power] - 1 + fFirstIndex;
071: if (value >= dataArray[auxStart + fFirstIndex]) {
072: index += auxStart;
073: }
074:
075: // at this point, index is the "upper limit" of the search
076:
077: switch (power) {
078: case 17:
079: if (value < dataArray[index - 65536])
080: index -= 65536;
081: case 16:
082: if (value < dataArray[index - 32768])
083: index -= 32768;
084: case 15:
085: if (value < dataArray[index - 16384])
086: index -= 16384;
087: case 14:
088: if (value < dataArray[index - 8192])
089: index -= 8192;
090: case 13:
091: if (value < dataArray[index - 4096])
092: index -= 4096;
093: case 12:
094: if (value < dataArray[index - 2048])
095: index -= 2048;
096: case 11:
097: if (value < dataArray[index - 1024])
098: index -= 1024;
099: case 10:
100: if (value < dataArray[index - 512])
101: index -= 512;
102: case 9:
103: if (value < dataArray[index - 256])
104: index -= 256;
105: case 8:
106: if (value < dataArray[index - 128])
107: index -= 128;
108: case 7:
109: if (value < dataArray[index - 64])
110: index -= 64;
111: case 6:
112: if (value < dataArray[index - 32])
113: index -= 32;
114: case 5:
115: if (value < dataArray[index - 16])
116: index -= 16;
117: case 4:
118: if (value < dataArray[index - 8])
119: index -= 8;
120: case 3:
121: if (value < dataArray[index - 4])
122: index -= 4;
123: case 2:
124: if (value < dataArray[index - 2])
125: index -= 2;
126: case 1:
127: if (value < dataArray[index - 1])
128: index -= 1;
129: case 0:
130: if (value < dataArray[index])
131: index -= 1;
132: }
133: return index;
134: }
135: }
|