/*
 *******************************************************************************
 * Copyright (C) 1998-2004, International Business Machines Corporation and    *
 * others. All Rights Reserved.                                                *
 *******************************************************************************
 *
 * Created on Dec 3, 2003
 *
 *******************************************************************************
 */
package com.ibm.icu.dev.tool.layout;


import com.ibm.icu.impl.Utility;

public class TaggedRecord
{
    private String tag;
        
    public TaggedRecord(String theTag)
    {
        tag = theTag;
    }
        
    public String getTag()
    {
        return tag;
    }
        
    //
    // Straight insertion sort from Knuth vol. III, pg. 81
    //
    public static void sort(TaggedRecord[] table, int count)
    {
        for (int j = 1; j < count; j += 1) {
            int i;
            TaggedRecord v = table[j];
            String vTag = v.getTag();

            for (i = j - 1; i >= 0; i -= 1) {
                if (vTag.compareTo(table[i].getTag()) >= 0) {
                    break;
                }

                table[i + 1] = table[i];
            }

            table[i + 1] = v;
        }
    }
    
    public static int search(TaggedRecord[] table, int count, String tag)
    {
        int log2 = Utility.highBit(count);
        int power = 1 << log2;
        int extra = count - power;
        int probe = power;
        int index = 0;

        if (table[extra].getTag().compareTo(tag) <= 0) {
            index = extra;
        }

        while (probe > (1 << 0)) {
            probe >>= 1;

            if (table[index + probe].getTag().compareTo(tag) <= 0) {
                index += probe;
            }
        }

        if (table[index].getTag().equals(tag)) {
            return index;
        }

        return -1;
    }
}