jars/icu4j-4_4_2-src/tools/misc/src/com/ibm/icu/dev/tool/layout/TaggedRecord.java

   1 /*\r
   2  *******************************************************************************\r
   3  * Copyright (C) 1998-2004, International Business Machines Corporation and    *\r
   4  * others. All Rights Reserved.                                                *\r
   5  *******************************************************************************\r
   6  *\r
   7  * Created on Dec 3, 2003\r
   8  *\r
   9  *******************************************************************************\r
  10  */\r
  11 package com.ibm.icu.dev.tool.layout;\r
  12 \r
  13 \r
  14 import com.ibm.icu.impl.Utility;\r
  15 \r
  16 public class TaggedRecord\r
  17 {\r
  18     private String tag;\r
  19         \r
  20     public TaggedRecord(String theTag)\r
  21     {\r
  22         tag = theTag;\r
  23     }\r
  24         \r
  25     public String getTag()\r
  26     {\r
  27         return tag;\r
  28     }\r
  29         \r
  30     //\r
  31     // Straight insertion sort from Knuth vol. III, pg. 81\r
  32     //\r
  33     public static void sort(TaggedRecord[] table, int count)\r
  34     {\r
  35         for (int j = 1; j < count; j += 1) {\r
  36             int i;\r
  37             TaggedRecord v = table[j];\r
  38             String vTag = v.getTag();\r
  39 \r
  40             for (i = j - 1; i >= 0; i -= 1) {\r
  41                 if (vTag.compareTo(table[i].getTag()) >= 0) {\r
  42                     break;\r
  43                 }\r
  44 \r
  45                 table[i + 1] = table[i];\r
  46             }\r
  47 \r
  48             table[i + 1] = v;\r
  49         }\r
  50     }\r
  51     \r
  52     public static int search(TaggedRecord[] table, int count, String tag)\r
  53     {\r
  54         int log2 = Utility.highBit(count);\r
  55         int power = 1 << log2;\r
  56         int extra = count - power;\r
  57         int probe = power;\r
  58         int index = 0;\r
  59 \r
  60         if (table[extra].getTag().compareTo(tag) <= 0) {\r
  61             index = extra;\r
  62         }\r
  63 \r
  64         while (probe > (1 << 0)) {\r
  65             probe >>= 1;\r
  66 \r
  67             if (table[index + probe].getTag().compareTo(tag) <= 0) {\r
  68                 index += probe;\r
  69             }\r
  70         }\r
  71 \r
  72         if (table[index].getTag().equals(tag)) {\r
  73             return index;\r
  74         }\r
  75 \r
  76         return -1;\r
  77     }\r
  78 }\r
  79     \r