jars/icu4j-4_2_1-src/src/com/ibm/richtext/styledtext/FastIntBinarySearch.java

   1 /*\r
   2 *   Copyright (C) 1996-2004, International Business Machines\r
   3 *   Corporation and others.  All Rights Reserved.\r
   4 */\r
   5 \r
   6 /*\r
   7     7/29/96\r
   8         Modified to search portions of an integer array.  Should be retested.\r
   9 */\r
  10 \r
  11 package com.ibm.richtext.styledtext;\r
  12 \r
  13 /**\r
  14  * This class searches a segment of an array of integers.  The segment\r
  15  * must be sorted in ascending order (but this class does not verify this).\r
  16  * Also, this class aliases the array;  if the array is modified later the\r
  17  * search results are undefined.\r
  18  */\r
  19 final class FastIntBinarySearch\r
  20 {\r
  21     static final String COPYRIGHT =\r
  22                 "(C) Copyright IBM Corp. 1998-1999 - All Rights Reserved";\r
  23     private int dataArray[];\r
  24     private int auxStart;\r
  25     private int power;\r
  26 \r
  27     private int fFirstIndex;\r
  28 \r
  29     private static final int exp2[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072 };\r
  30 \r
  31     public FastIntBinarySearch(int data[])\r
  32     {\r
  33         this(data, 0, data.length);\r
  34     }\r
  35 \r
  36     public FastIntBinarySearch(int data[], int firstValidIndex, int validLength)\r
  37     {\r
  38         setData(data, firstValidIndex, validLength);\r
  39     }\r
  40     \r
  41     public void setData(int data[]) {\r
  42         \r
  43         setData(data, 0, data.length);\r
  44     }\r
  45     \r
  46     public void setData(int data[], int firstValidIndex, int validLength) {\r
  47 \r
  48         if (data.length < 1) throw new IllegalArgumentException();\r
  49         if (data.length >= exp2[exp2.length-1]) throw new IllegalArgumentException();\r
  50 \r
  51         dataArray = data;\r
  52         fFirstIndex = firstValidIndex;\r
  53 \r
  54         for (power = exp2.length-1; power > 0 && validLength < exp2[power]; power--) {}\r
  55 \r
  56         // at this point, array.length >= 2^power\r
  57 \r
  58         auxStart = validLength - exp2[power];\r
  59     }\r
  60     \r
  61     /**\r
  62      * Return the index in the array of the first element which is at least\r
  63      * as large as <tt>value</tt>.  If value is larger than the largest\r
  64      * element in the array the last valid index in the array is returned.\r
  65      */\r
  66     public int findIndex(int value)\r
  67     {\r
  68         int index = exp2[power]-1 + fFirstIndex;\r
  69         if (value >= dataArray[auxStart + fFirstIndex]) {\r
  70             index += auxStart;\r
  71         }\r
  72 \r
  73         // at this point, index is the "upper limit" of the search\r
  74 \r
  75         switch (power) {\r
  76         case 17:\r
  77             if (value < dataArray[index-65536]) index -= 65536;\r
  78         case 16:\r
  79             if (value < dataArray[index-32768]) index -= 32768;\r
  80         case 15:\r
  81             if (value < dataArray[index-16384]) index -= 16384;\r
  82         case 14:\r
  83             if (value < dataArray[index-8192]) index -= 8192;\r
  84         case 13:\r
  85             if (value < dataArray[index-4096]) index -= 4096;\r
  86         case 12:\r
  87             if (value < dataArray[index-2048]) index -= 2048;\r
  88         case 11:\r
  89             if (value < dataArray[index-1024]) index -= 1024;\r
  90         case 10:\r
  91             if (value < dataArray[index-512]) index -= 512;\r
  92         case 9:\r
  93             if (value < dataArray[index-256]) index -= 256;\r
  94         case 8:\r
  95             if (value < dataArray[index-128]) index -= 128;\r
  96         case 7:\r
  97             if (value < dataArray[index-64]) index -= 64;\r
  98         case 6:\r
  99             if (value < dataArray[index-32]) index -= 32;\r
 100         case 5:\r
 101             if (value < dataArray[index-16]) index -= 16;\r
 102         case 4:\r
 103             if (value < dataArray[index-8]) index -= 8;\r
 104         case 3:\r
 105             if (value < dataArray[index-4]) index -= 4;\r
 106         case 2:\r
 107             if (value < dataArray[index-2]) index -= 2;\r
 108         case 1:\r
 109             if (value < dataArray[index-1]) index -= 1;\r
 110         case 0:\r
 111             if (value < dataArray[index]) index -= 1;\r
 112         }\r
 113         return index;\r
 114     }\r
 115 }\r