| /* |
| * @(#)$RCSfile: FastIntBinarySearch.java,v $ $Revision: 1.1 $ $Date: 2000/04/20 17:45:10 $ |
| * |
| * (C) Copyright IBM Corp. 1998-1999. All Rights Reserved. |
| * |
| * The program is provided "as is" without any warranty express or |
| * implied, including the warranty of non-infringement and the implied |
| * warranties of merchantibility and fitness for a particular purpose. |
| * IBM will not be liable for any damages suffered by you as a result |
| * of using the Program. In no event will IBM be liable for any |
| * special, indirect or consequential damages or lost profits even if |
| * IBM has been advised of the possibility of their occurrence. IBM |
| * will not be liable for any third party claims against you. |
| */ |
| /* |
| (C) Copyright Taligent, Inc. 1996 - All Rights Reserved |
| (C) Copyright IBM Corp. 1996 - All Rights Reserved |
| |
| The original version of this source code and documentation is copyrighted and |
| owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These materials are |
| provided under terms of a License Agreement between Taligent and Sun. This |
| technology is protected by multiple US and International patents. This notice and |
| attribution to Taligent may not be removed. |
| Taligent is a registered trademark of Taligent, Inc. |
| */ |
| |
| /* |
| 7/29/96 |
| Modified to search portions of an integer array. Should be retested. |
| */ |
| |
| package com.ibm.richtext.styledtext; |
| |
| /** |
| * This class searches a segment of an array of integers. The segment |
| * must be sorted in ascending order (but this class does not verify this). |
| * Also, this class aliases the array; if the array is modified later the |
| * search results are undefined. |
| */ |
| final class FastIntBinarySearch |
| { |
| static final String COPYRIGHT = |
| "(C) Copyright IBM Corp. 1998-1999 - All Rights Reserved"; |
| private int dataArray[]; |
| private int auxStart; |
| private int power; |
| |
| private int fFirstIndex; |
| |
| private static final int exp2[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072 }; |
| |
| public FastIntBinarySearch(int data[]) |
| { |
| this(data, 0, data.length); |
| } |
| |
| public FastIntBinarySearch(int data[], int firstValidIndex, int validLength) |
| { |
| setData(data, firstValidIndex, validLength); |
| } |
| |
| public void setData(int data[]) { |
| |
| setData(data, 0, data.length); |
| } |
| |
| public void setData(int data[], int firstValidIndex, int validLength) { |
| |
| if (data.length < 1) throw new IllegalArgumentException(); |
| if (data.length >= exp2[exp2.length-1]) throw new IllegalArgumentException(); |
| |
| dataArray = data; |
| fFirstIndex = firstValidIndex; |
| |
| for (power = exp2.length-1; power > 0 && validLength < exp2[power]; power--) {} |
| |
| // at this point, array.length >= 2^power |
| |
| auxStart = validLength - exp2[power]; |
| } |
| |
| /** |
| * Return the index in the array of the first element which is at least |
| * as large as <tt>value</tt>. If value is larger than the largest |
| * element in the array the last valid index in the array is returned. |
| */ |
| public int findIndex(int value) |
| { |
| int index = exp2[power]-1 + fFirstIndex; |
| if (value >= dataArray[auxStart + fFirstIndex]) { |
| index += auxStart; |
| } |
| |
| // at this point, index is the "upper limit" of the search |
| |
| switch (power) { |
| case 17: |
| if (value < dataArray[index-65536]) index -= 65536; |
| case 16: |
| if (value < dataArray[index-32768]) index -= 32768; |
| case 15: |
| if (value < dataArray[index-16384]) index -= 16384; |
| case 14: |
| if (value < dataArray[index-8192]) index -= 8192; |
| case 13: |
| if (value < dataArray[index-4096]) index -= 4096; |
| case 12: |
| if (value < dataArray[index-2048]) index -= 2048; |
| case 11: |
| if (value < dataArray[index-1024]) index -= 1024; |
| case 10: |
| if (value < dataArray[index-512]) index -= 512; |
| case 9: |
| if (value < dataArray[index-256]) index -= 256; |
| case 8: |
| if (value < dataArray[index-128]) index -= 128; |
| case 7: |
| if (value < dataArray[index-64]) index -= 64; |
| case 6: |
| if (value < dataArray[index-32]) index -= 32; |
| case 5: |
| if (value < dataArray[index-16]) index -= 16; |
| case 4: |
| if (value < dataArray[index-8]) index -= 8; |
| case 3: |
| if (value < dataArray[index-4]) index -= 4; |
| case 2: |
| if (value < dataArray[index-2]) index -= 2; |
| case 1: |
| if (value < dataArray[index-1]) index -= 1; |
| case 0: |
| if (value < dataArray[index]) index -= 1; |
| } |
| return index; |
| } |
| } |