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