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