#define SORTKEY_UNSORTABLE      0
#define SORTKEY_DIACRITIC       1
#define SORTKEY_JAPANESE        3
#define SORTKEY_JAMO            4
#define SORTKEY_EXTENSION       5
#define SORTKEY_PUNCTUATION     6
#define SORTKEY_SYMBOL_1        7
#define SORTKEY_SYMBOL_2        8
#define SORTKEY_SYMBOL_3        9
#define SORTKEY_SYMBOL_4        10
#define SORTKEY_SYMBOL_5        11
#define SORTKEY_SYMBOL_6        12

#define SORTKEY_MIN_WEIGHT 2

enum sortkey_weight_type
{
    SORTKEY_WEIGHT_TYPE_SEPARATOR,
    SORTKEY_WEIGHT_TYPE_MAIN,
    SORTKEY_WEIGHT_TYPE_DIACRITIC,
    SORTKEY_WEIGHT_TYPE_CASE,
    SORTKEY_WEIGHT_TYPE_EXTRA,
    SORTKEY_WEIGHT_TYPE_SPECIAL,
};

struct character_info
{
    BYTE weight_primary;
    BYTE script_member;
    BYTE weight_diacritic;
    BYTE weight_case;
};

struct weight_main_info
{
    BYTE script_member;
    BYTE weight_primary;
    BYTE extra;
};

struct sortkey_data
{
    int flags;
    BYTE* buffer;
    int buffer_pos;
    int buffer_len;
    enum sortkey_weight_type weight_type;
    int pos_last_weight_bigger_min;
};

static BOOL sortkey_get_char(struct sortkey_data* data, struct character_info* info, WCHAR ch)
{
    DWORD value = sort.keys[ch];

    info->weight_case = value >> 24;
    info->weight_diacritic = (value >> 16) & 0xff;
    info->script_member = (value >> 8) & 0xff;
    info->weight_primary = value & 0xff;
    return info->script_member != 0;
}

static void sortkey_data_init(struct sortkey_data* data, BYTE* buffer, int buffer_len, int flags, const WCHAR* locale, BOOL is_compare_string)
{
    data->flags = flags;
    data->buffer = buffer;
    data->buffer_pos = 0;
    data->buffer_len = buffer ? buffer_len : 0;
}

static struct weight_main_info sortkey_create_weight_main(BYTE script_member, BYTE weight_primary)
{
    struct weight_main_info ret = { 0 };
    ret.script_member = script_member;
    ret.weight_primary = weight_primary;
    return ret;
}

static void sortkey_add_weight(struct sortkey_data* data, enum sortkey_weight_type weight_type, BYTE value)
{
    if (weight_type != SORTKEY_WEIGHT_TYPE_SEPARATOR && data->weight_type != weight_type)
        return;
    if (data->buffer_pos < data->buffer_len)
        data->buffer[data->buffer_pos] = value;
    data->buffer_pos++;
}

static void sortkey_case_weights_add(struct sortkey_data* data, BYTE value)
{
    int flags = data->flags;
    if (NORM_IGNORECASE & flags)
        value = value & ~(16 + 8);
    if (NORM_IGNOREWIDTH & flags)
        value = value & ~(1);
    if (NORM_IGNOREKANATYPE & flags)
        value = value & ~(32);

    sortkey_add_weight(data, SORTKEY_WEIGHT_TYPE_CASE, value);
}

static void sortkey_main_weights_add(struct sortkey_data *data, struct weight_main_info* value)
{
    sortkey_add_weight(data, SORTKEY_WEIGHT_TYPE_MAIN, value->script_member);
    sortkey_add_weight(data, SORTKEY_WEIGHT_TYPE_MAIN, value->weight_primary);
    if (value->extra > 0)
        sortkey_add_weight(data, SORTKEY_WEIGHT_TYPE_MAIN, value->extra);
}

static void sortkey_diacritic_weights_add(struct sortkey_data* data, const struct character_info* info, BYTE value)
{
    sortkey_add_weight(data, SORTKEY_WEIGHT_TYPE_DIACRITIC, value);
    if (value > SORTKEY_MIN_WEIGHT)
        data->pos_last_weight_bigger_min = data->buffer_pos;
}

static void sortkey_handle_default_character(struct sortkey_data* data, WCHAR c)
{
    struct weight_main_info weightmain;
    struct character_info info;

    if (!sortkey_get_char(data, &info, c))
    {
        return;
    }

    weightmain = sortkey_create_weight_main(info.script_member, info.weight_primary);
    if (info.script_member >= 0xa9 && info.script_member <= 0xaf) /* Some CJK have extra value */
        weightmain.extra = info.weight_diacritic;
    else
        sortkey_diacritic_weights_add(data, &info, info.weight_diacritic);

    sortkey_main_weights_add(data, &weightmain);

    sortkey_case_weights_add(data, info.weight_case);
}

static BOOL sortkey_handle_character(struct sortkey_data* data, WCHAR c, const WCHAR* str, int i)
{
    struct weight_main_info weightmain;
    struct character_info info;
    int flags = data->flags;

    if (!sortkey_get_char(data, &info, c))
    {
        return FALSE;
    }

    switch (info.script_member)
    {
    case SORTKEY_UNSORTABLE:
        break;

    case SORTKEY_DIACRITIC:
        if (data->weight_type == SORTKEY_WEIGHT_TYPE_DIACRITIC)
        {
            int old_pos = data->buffer_pos - 1;
            if (old_pos >= 0 && old_pos < data->buffer_len)
                data->buffer[old_pos] += info.weight_diacritic; /* Overflow can happen, that's okay */
            else
                sortkey_diacritic_weights_add(data, &info, info.weight_diacritic);
        }
        break;

    case SORTKEY_JAPANESE:
        /* TODO */
        break;

    case SORTKEY_JAMO:
        weightmain = sortkey_create_weight_main(info.weight_primary, info.weight_diacritic);
        sortkey_main_weights_add(data, &weightmain);

        sortkey_diacritic_weights_add(data, &info, SORTKEY_MIN_WEIGHT);

        sortkey_case_weights_add(data, info.weight_case);
        break;

    case SORTKEY_EXTENSION:
        weightmain = sortkey_create_weight_main(253, 255);
        sortkey_main_weights_add(data, &weightmain);

        weightmain = sortkey_create_weight_main(info.weight_primary, info.weight_diacritic);
        sortkey_main_weights_add(data, &weightmain);

        sortkey_diacritic_weights_add(data, &info, SORTKEY_MIN_WEIGHT);

        sortkey_case_weights_add(data, SORTKEY_MIN_WEIGHT);
        break;

    case SORTKEY_PUNCTUATION:
        /* TODO */
        break;

    case SORTKEY_SYMBOL_1:
    case SORTKEY_SYMBOL_2:
    case SORTKEY_SYMBOL_3:
    case SORTKEY_SYMBOL_4:
    case SORTKEY_SYMBOL_5:
    case SORTKEY_SYMBOL_6:
        if (flags & NORM_IGNORESYMBOLS)
            break;

        weightmain = sortkey_create_weight_main(info.script_member, info.weight_primary);
        sortkey_main_weights_add(data, &weightmain);

        sortkey_diacritic_weights_add(data, &info, info.weight_diacritic);

        sortkey_case_weights_add(data, info.weight_case);
        break;

    default:
        sortkey_handle_default_character(data, c);
        break;
    }
    return TRUE;
}

static void sortkey_start_weight(struct sortkey_data* data, enum sortkey_weight_type weight_type)
{
    data->buffer += data->buffer_pos;
    data->buffer_len -= data->buffer_pos;
    data->buffer_pos = 0;
    data->weight_type = weight_type;
    data->pos_last_weight_bigger_min = 0;
}

static int sortkey_generate(int flags, const WCHAR* locale, const WCHAR* str, int str_len, BYTE* buffer, int buffer_len)
{
    const BYTE SORTKEY_SEPARATOR = 1;
    const BYTE SORTKEY_TERMINATOR = 0;
    int i;
    struct sortkey_data data;
    int sortkey_len = 0;

    sortkey_data_init(&data, buffer, buffer_len, flags, locale, FALSE);

    if (str_len == -1)
        str_len = wcslen(str);

    /* Main weights */
    sortkey_start_weight(&data, SORTKEY_WEIGHT_TYPE_MAIN);
    for (i = 0; i < str_len; i++)
        sortkey_handle_character(&data, str[i], str, i);
    sortkey_add_weight(&data, SORTKEY_WEIGHT_TYPE_SEPARATOR, SORTKEY_SEPARATOR);
    sortkey_len += data.buffer_pos;

    /* Diacritic weights */
    sortkey_start_weight(&data, SORTKEY_WEIGHT_TYPE_DIACRITIC);
    if ((flags & NORM_IGNORENONSPACE) == 0)
    {
        for (i = 0; i < str_len; i++)
            sortkey_handle_character(&data, str[i], str, i);
        /* Remove all weights <= SORTKEY_MIN_WEIGHT from the end */
        data.buffer_pos = data.pos_last_weight_bigger_min;
    }
    sortkey_add_weight(&data, SORTKEY_WEIGHT_TYPE_SEPARATOR, SORTKEY_SEPARATOR);
    sortkey_len += data.buffer_pos;

    /* Case weights */
    sortkey_start_weight(&data, SORTKEY_WEIGHT_TYPE_CASE);
    if ((NORM_IGNORECASE & flags) == 0 || (NORM_IGNOREWIDTH & flags) == 0)
    {
        for (i = 0; i < str_len; i++)
            sortkey_handle_character(&data, str[i], str, i);
    }
    sortkey_add_weight(&data, SORTKEY_WEIGHT_TYPE_SEPARATOR, SORTKEY_SEPARATOR);
    sortkey_len += data.buffer_pos;

    /* Extra weights */
    sortkey_start_weight(&data, SORTKEY_WEIGHT_TYPE_EXTRA);
    /* TODO */
    sortkey_add_weight(&data, SORTKEY_WEIGHT_TYPE_SEPARATOR, SORTKEY_SEPARATOR);
    sortkey_len += data.buffer_pos;

    /* Special weights */
    sortkey_start_weight(&data, SORTKEY_WEIGHT_TYPE_SPECIAL);
    /* TODO */
    sortkey_add_weight(&data, SORTKEY_WEIGHT_TYPE_SEPARATOR, SORTKEY_TERMINATOR);
    sortkey_len += data.buffer_pos;

    if (sortkey_len <= buffer_len || !buffer)
        return sortkey_len;

    return 0;
}