#include "pfc-lite.h"
#include "unicode-normalize.h"
#include "string_base.h"
#include <map>



static constexpr uint16_t modifiers[] =
{0x0300, 0x0301, 0x0302, 0x0303, 0x0304, 0x0306, 0x0307, 0x0308, 0x0309, 0x030A, 0x030B, 0x030C, 0x030F, 0x0311, 0x0313, 0x0314, 0x031B, 0x0323, 0x0324, 0x0325, 0x0326, 0x0327, 0x0328, 0x032D, 0x032E, 0x0330, 0x0331, 0x0338, 0x0342, 0x0345, 0x05B4, 0x05B7, 0x05B8, 0x05B9, 0x05BC, 0x05BF, 0x05C1, 0x05C2, 0x0653, 0x0654, 0x0655, 0x093C, 0x09BC, 0x09BE, 0x09D7, 0x0A3C, 0x0B3C, 0x0B3E, 0x0B56, 0x0B57, 0x0BBE, 0x0BD7, 0x0C56, 0x0CC2, 0x0CD5, 0x0CD6, 0x0D3E, 0x0D57, 0x0DCA, 0x0DCF, 0x0DDF, 0x0F72, 0x0F74, 0x0F80, 0x0FB5, 0x0FB7, 0x102E, 0x1161, 0x1162, 0x1163, 0x1164, 0x1165, 0x1166, 0x1167, 0x1168, 0x1169, 0x116A, 0x116B, 0x116C, 0x116D, 0x116E, 0x116F, 0x1170, 0x1171, 0x1172, 0x1173, 0x1174, 0x1175, 0x11A8, 0x11A9, 0x11AA, 0x11AB, 0x11AC, 0x11AD, 0x11AE, 0x11AF, 0x11B0, 0x11B1, 0x11B2, 0x11B3, 0x11B4, 0x11B5, 0x11B6, 0x11B7, 0x11B8, 0x11B9, 0x11BA, 0x11BB, 0x11BC, 0x11BD, 0x11BE, 0x11BF, 0x11C0, 0x11C1, 0x11C2, 0x1B35, 0x3099, 0x309A};

static bool is_modifier( unsigned c ) {
    if (c < modifiers[0]) return false; // common case, bail early
    unsigned lo = 0, hi = (unsigned) std::size(modifiers);
    do {
        unsigned mid = (lo+hi)/2;
        unsigned hit = modifiers[mid];
        if ( c < hit ) hi = mid;
        else if ( c > hit ) lo = mid + 1;
        else return true;
    } while(lo < hi);
    return false;
}

static constexpr struct {
    uint16_t form1;
    uint16_t form2[2];
} normtable[] = {
    {0x00C0, {0x0041,0x0300}},
    {0x00C1, {0x0041,0x0301}},
    {0x00C2, {0x0041,0x0302}},
    {0x00C3, {0x0041,0x0303}},
    {0x00C4, {0x0041,0x0308}},
    {0x00C5, {0x0041,0x030A}},
    {0x00C7, {0x0043,0x0327}},
    {0x00C8, {0x0045,0x0300}},
    {0x00C9, {0x0045,0x0301}},
    {0x00CA, {0x0045,0x0302}},
    {0x00CB, {0x0045,0x0308}},
    {0x00CC, {0x0049,0x0300}},
    {0x00CD, {0x0049,0x0301}},
    {0x00CE, {0x0049,0x0302}},
    {0x00CF, {0x0049,0x0308}},
    {0x00D1, {0x004E,0x0303}},
    {0x00D2, {0x004F,0x0300}},
    {0x00D3, {0x004F,0x0301}},
    {0x00D4, {0x004F,0x0302}},
    {0x00D5, {0x004F,0x0303}},
    {0x00D6, {0x004F,0x0308}},
    {0x00D9, {0x0055,0x0300}},
    {0x00DA, {0x0055,0x0301}},
    {0x00DB, {0x0055,0x0302}},
    {0x00DC, {0x0055,0x0308}},
    {0x00DD, {0x0059,0x0301}},
    {0x00E0, {0x0061,0x0300}},
    {0x00E1, {0x0061,0x0301}},
    {0x00E2, {0x0061,0x0302}},
    {0x00E3, {0x0061,0x0303}},
    {0x00E4, {0x0061,0x0308}},
    {0x00E5, {0x0061,0x030A}},
    {0x00E7, {0x0063,0x0327}},
    {0x00E8, {0x0065,0x0300}},
    {0x00E9, {0x0065,0x0301}},
    {0x00EA, {0x0065,0x0302}},
    {0x00EB, {0x0065,0x0308}},
    {0x00EC, {0x0069,0x0300}},
    {0x00ED, {0x0069,0x0301}},
    {0x00EE, {0x0069,0x0302}},
    {0x00EF, {0x0069,0x0308}},
    {0x00F1, {0x006E,0x0303}},
    {0x00F2, {0x006F,0x0300}},
    {0x00F3, {0x006F,0x0301}},
    {0x00F4, {0x006F,0x0302}},
    {0x00F5, {0x006F,0x0303}},
    {0x00F6, {0x006F,0x0308}},
    {0x00F9, {0x0075,0x0300}},
    {0x00FA, {0x0075,0x0301}},
    {0x00FB, {0x0075,0x0302}},
    {0x00FC, {0x0075,0x0308}},
    {0x00FD, {0x0079,0x0301}},
    {0x00FF, {0x0079,0x0308}},
    {0x0100, {0x0041,0x0304}},
    {0x0101, {0x0061,0x0304}},
    {0x0102, {0x0041,0x0306}},
    {0x0103, {0x0061,0x0306}},
    {0x0104, {0x0041,0x0328}},
    {0x0105, {0x0061,0x0328}},
    {0x0106, {0x0043,0x0301}},
    {0x0107, {0x0063,0x0301}},
    {0x0108, {0x0043,0x0302}},
    {0x0109, {0x0063,0x0302}},
    {0x010A, {0x0043,0x0307}},
    {0x010B, {0x0063,0x0307}},
    {0x010C, {0x0043,0x030C}},
    {0x010D, {0x0063,0x030C}},
    {0x010E, {0x0044,0x030C}},
    {0x010F, {0x0064,0x030C}},
    {0x0112, {0x0045,0x0304}},
    {0x0113, {0x0065,0x0304}},
    {0x0114, {0x0045,0x0306}},
    {0x0115, {0x0065,0x0306}},
    {0x0116, {0x0045,0x0307}},
    {0x0117, {0x0065,0x0307}},
    {0x0118, {0x0045,0x0328}},
    {0x0119, {0x0065,0x0328}},
    {0x011A, {0x0045,0x030C}},
    {0x011B, {0x0065,0x030C}},
    {0x011C, {0x0047,0x0302}},
    {0x011D, {0x0067,0x0302}},
    {0x011E, {0x0047,0x0306}},
    {0x011F, {0x0067,0x0306}},
    {0x0120, {0x0047,0x0307}},
    {0x0121, {0x0067,0x0307}},
    {0x0122, {0x0047,0x0327}},
    {0x0123, {0x0067,0x0327}},
    {0x0124, {0x0048,0x0302}},
    {0x0125, {0x0068,0x0302}},
    {0x0128, {0x0049,0x0303}},
    {0x0129, {0x0069,0x0303}},
    {0x012A, {0x0049,0x0304}},
    {0x012B, {0x0069,0x0304}},
    {0x012C, {0x0049,0x0306}},
    {0x012D, {0x0069,0x0306}},
    {0x012E, {0x0049,0x0328}},
    {0x012F, {0x0069,0x0328}},
    {0x0130, {0x0049,0x0307}},
    {0x0134, {0x004A,0x0302}},
    {0x0135, {0x006A,0x0302}},
    {0x0136, {0x004B,0x0327}},
    {0x0137, {0x006B,0x0327}},
    {0x0139, {0x004C,0x0301}},
    {0x013A, {0x006C,0x0301}},
    {0x013B, {0x004C,0x0327}},
    {0x013C, {0x006C,0x0327}},
    {0x013D, {0x004C,0x030C}},
    {0x013E, {0x006C,0x030C}},
    {0x0143, {0x004E,0x0301}},
    {0x0144, {0x006E,0x0301}},
    {0x0145, {0x004E,0x0327}},
    {0x0146, {0x006E,0x0327}},
    {0x0147, {0x004E,0x030C}},
    {0x0148, {0x006E,0x030C}},
    {0x014C, {0x004F,0x0304}},
    {0x014D, {0x006F,0x0304}},
    {0x014E, {0x004F,0x0306}},
    {0x014F, {0x006F,0x0306}},
    {0x0150, {0x004F,0x030B}},
    {0x0151, {0x006F,0x030B}},
    {0x0154, {0x0052,0x0301}},
    {0x0155, {0x0072,0x0301}},
    {0x0156, {0x0052,0x0327}},
    {0x0157, {0x0072,0x0327}},
    {0x0158, {0x0052,0x030C}},
    {0x0159, {0x0072,0x030C}},
    {0x015A, {0x0053,0x0301}},
    {0x015B, {0x0073,0x0301}},
    {0x015C, {0x0053,0x0302}},
    {0x015D, {0x0073,0x0302}},
    {0x015E, {0x0053,0x0327}},
    {0x015F, {0x0073,0x0327}},
    {0x0160, {0x0053,0x030C}},
    {0x0161, {0x0073,0x030C}},
    {0x0162, {0x0054,0x0327}},
    {0x0163, {0x0074,0x0327}},
    {0x0164, {0x0054,0x030C}},
    {0x0165, {0x0074,0x030C}},
    {0x0168, {0x0055,0x0303}},
    {0x0169, {0x0075,0x0303}},
    {0x016A, {0x0055,0x0304}},
    {0x016B, {0x0075,0x0304}},
    {0x016C, {0x0055,0x0306}},
    {0x016D, {0x0075,0x0306}},
    {0x016E, {0x0055,0x030A}},
    {0x016F, {0x0075,0x030A}},
    {0x0170, {0x0055,0x030B}},
    {0x0171, {0x0075,0x030B}},
    {0x0172, {0x0055,0x0328}},
    {0x0173, {0x0075,0x0328}},
    {0x0174, {0x0057,0x0302}},
    {0x0175, {0x0077,0x0302}},
    {0x0176, {0x0059,0x0302}},
    {0x0177, {0x0079,0x0302}},
    {0x0178, {0x0059,0x0308}},
    {0x0179, {0x005A,0x0301}},
    {0x017A, {0x007A,0x0301}},
    {0x017B, {0x005A,0x0307}},
    {0x017C, {0x007A,0x0307}},
    {0x017D, {0x005A,0x030C}},
    {0x017E, {0x007A,0x030C}},
    {0x01A0, {0x004F,0x031B}},
    {0x01A1, {0x006F,0x031B}},
    {0x01AF, {0x0055,0x031B}},
    {0x01B0, {0x0075,0x031B}},
    {0x01CD, {0x0041,0x030C}},
    {0x01CE, {0x0061,0x030C}},
    {0x01CF, {0x0049,0x030C}},
    {0x01D0, {0x0069,0x030C}},
    {0x01D1, {0x004F,0x030C}},
    {0x01D2, {0x006F,0x030C}},
    {0x01D3, {0x0055,0x030C}},
    {0x01D4, {0x0075,0x030C}},
    {0x01E2, {0x00C6,0x0304}},
    {0x01E3, {0x00E6,0x0304}},
    {0x01E6, {0x0047,0x030C}},
    {0x01E7, {0x0067,0x030C}},
    {0x01E8, {0x004B,0x030C}},
    {0x01E9, {0x006B,0x030C}},
    {0x01EA, {0x004F,0x0328}},
    {0x01EB, {0x006F,0x0328}},
    {0x01EE, {0x01B7,0x030C}},
    {0x01EF, {0x0292,0x030C}},
    {0x01F0, {0x006A,0x030C}},
    {0x01F4, {0x0047,0x0301}},
    {0x01F5, {0x0067,0x0301}},
    {0x01F8, {0x004E,0x0300}},
    {0x01F9, {0x006E,0x0300}},
    {0x01FC, {0x00C6,0x0301}},
    {0x01FD, {0x00E6,0x0301}},
    {0x01FE, {0x00D8,0x0301}},
    {0x01FF, {0x00F8,0x0301}},
    {0x0200, {0x0041,0x030F}},
    {0x0201, {0x0061,0x030F}},
    {0x0202, {0x0041,0x0311}},
    {0x0203, {0x0061,0x0311}},
    {0x0204, {0x0045,0x030F}},
    {0x0205, {0x0065,0x030F}},
    {0x0206, {0x0045,0x0311}},
    {0x0207, {0x0065,0x0311}},
    {0x0208, {0x0049,0x030F}},
    {0x0209, {0x0069,0x030F}},
    {0x020A, {0x0049,0x0311}},
    {0x020B, {0x0069,0x0311}},
    {0x020C, {0x004F,0x030F}},
    {0x020D, {0x006F,0x030F}},
    {0x020E, {0x004F,0x0311}},
    {0x020F, {0x006F,0x0311}},
    {0x0210, {0x0052,0x030F}},
    {0x0211, {0x0072,0x030F}},
    {0x0212, {0x0052,0x0311}},
    {0x0213, {0x0072,0x0311}},
    {0x0214, {0x0055,0x030F}},
    {0x0215, {0x0075,0x030F}},
    {0x0216, {0x0055,0x0311}},
    {0x0217, {0x0075,0x0311}},
    {0x0218, {0x0053,0x0326}},
    {0x0219, {0x0073,0x0326}},
    {0x021A, {0x0054,0x0326}},
    {0x021B, {0x0074,0x0326}},
    {0x021E, {0x0048,0x030C}},
    {0x021F, {0x0068,0x030C}},
    {0x0226, {0x0041,0x0307}},
    {0x0227, {0x0061,0x0307}},
    {0x0228, {0x0045,0x0327}},
    {0x0229, {0x0065,0x0327}},
    {0x022E, {0x004F,0x0307}},
    {0x022F, {0x006F,0x0307}},
    {0x0232, {0x0059,0x0304}},
    {0x0233, {0x0079,0x0304}},
    {0x0344, {0x0308,0x0301}},
    {0x0385, {0x00A8,0x0301}},
    {0x0386, {0x0391,0x0301}},
    {0x0388, {0x0395,0x0301}},
    {0x0389, {0x0397,0x0301}},
    {0x038A, {0x0399,0x0301}},
    {0x038C, {0x039F,0x0301}},
    {0x038E, {0x03A5,0x0301}},
    {0x038F, {0x03A9,0x0301}},
    {0x03AA, {0x0399,0x0308}},
    {0x03AB, {0x03A5,0x0308}},
    {0x03AC, {0x03B1,0x0301}},
    {0x03AD, {0x03B5,0x0301}},
    {0x03AE, {0x03B7,0x0301}},
    {0x03AF, {0x03B9,0x0301}},
    {0x03CA, {0x03B9,0x0308}},
    {0x03CB, {0x03C5,0x0308}},
    {0x03CC, {0x03BF,0x0301}},
    {0x03CD, {0x03C5,0x0301}},
    {0x03CE, {0x03C9,0x0301}},
    {0x03D3, {0x03D2,0x0301}},
    {0x03D4, {0x03D2,0x0308}},
    {0x0400, {0x0415,0x0300}},
    {0x0401, {0x0415,0x0308}},
    {0x0403, {0x0413,0x0301}},
    {0x0407, {0x0406,0x0308}},
    {0x040C, {0x041A,0x0301}},
    {0x040D, {0x0418,0x0300}},
    {0x040E, {0x0423,0x0306}},
    {0x0419, {0x0418,0x0306}},
    {0x0439, {0x0438,0x0306}},
    {0x0450, {0x0435,0x0300}},
    {0x0451, {0x0435,0x0308}},
    {0x0453, {0x0433,0x0301}},
    {0x0457, {0x0456,0x0308}},
    {0x045C, {0x043A,0x0301}},
    {0x045D, {0x0438,0x0300}},
    {0x045E, {0x0443,0x0306}},
    {0x0476, {0x0474,0x030F}},
    {0x0477, {0x0475,0x030F}},
    {0x04C1, {0x0416,0x0306}},
    {0x04C2, {0x0436,0x0306}},
    {0x04D0, {0x0410,0x0306}},
    {0x04D1, {0x0430,0x0306}},
    {0x04D2, {0x0410,0x0308}},
    {0x04D3, {0x0430,0x0308}},
    {0x04D6, {0x0415,0x0306}},
    {0x04D7, {0x0435,0x0306}},
    {0x04DA, {0x04D8,0x0308}},
    {0x04DB, {0x04D9,0x0308}},
    {0x04DC, {0x0416,0x0308}},
    {0x04DD, {0x0436,0x0308}},
    {0x04DE, {0x0417,0x0308}},
    {0x04DF, {0x0437,0x0308}},
    {0x04E2, {0x0418,0x0304}},
    {0x04E3, {0x0438,0x0304}},
    {0x04E4, {0x0418,0x0308}},
    {0x04E5, {0x0438,0x0308}},
    {0x04E6, {0x041E,0x0308}},
    {0x04E7, {0x043E,0x0308}},
    {0x04EA, {0x04E8,0x0308}},
    {0x04EB, {0x04E9,0x0308}},
    {0x04EC, {0x042D,0x0308}},
    {0x04ED, {0x044D,0x0308}},
    {0x04EE, {0x0423,0x0304}},
    {0x04EF, {0x0443,0x0304}},
    {0x04F0, {0x0423,0x0308}},
    {0x04F1, {0x0443,0x0308}},
    {0x04F2, {0x0423,0x030B}},
    {0x04F3, {0x0443,0x030B}},
    {0x04F4, {0x0427,0x0308}},
    {0x04F5, {0x0447,0x0308}},
    {0x04F8, {0x042B,0x0308}},
    {0x04F9, {0x044B,0x0308}},
};


static const uint16_t * match( uint16_t c ) {
    size_t lo = 0, hi = std::size(normtable);
    do {
        size_t mid = (lo+hi)/2;
        auto & rec = normtable[mid];
        if ( rec.form1 < c ) lo = mid + 1;
        else if ( rec.form1 > c ) hi = mid;
        else return rec.form2;
    } while( lo < hi );
    return nullptr;
}
namespace {
    class shortener {
    public:
        shortener() {
            for (auto& walk : normtable) {
                m_data[walk.form2[0]][walk.form2[1]] = walk.form1;
            }
        }

        std::map< uint16_t, std::map<uint16_t, uint16_t> > m_data;
    };
}

namespace pfc {
    pfc::string8 unicodeNormalizeD_Lite(const char* in) {
        pfc::string8 ret; ret.prealloc(1024);
        for (;; ) {
            unsigned c;
            auto d = utf8_decode_char(in, c);
            if (d == 0) break;
            in += d;
            const uint16_t* m = nullptr;
            if (c < 0x10000) {
                m = match((uint16_t)c);
            }
            if (m != nullptr) {
                ret.add_char(m[0]);
                ret.add_char(m[1]);
            } else {
                ret.add_char(c);
            }
        }

        return ret;
    }
    pfc::string8 unicodeNormalizeC_Lite(const char* in) {
        static shortener g_shortener; auto& data = g_shortener.m_data;
        pfc::string8 ret; ret.prealloc(strlen(in));
        for (;; ) {
            unsigned c;
            auto d = pfc::utf8_decode_char(in, c);
            if (d == 0) break; 
            in += d;
            if ( c < 0x10000 ) {
                auto iter1 = data.find((uint16_t)c);
                if (iter1 != data.end()) {
                    unsigned next;
                    auto d2 = pfc::utf8_decode_char(in, next);
                    if (d2 != 0) {
                        auto& data2 = iter1->second;
                        auto iter2 = data2.find(next);
                        if (iter2 != data2.end()) {
                            in += d2;
                            ret.add_char(iter2->second); continue;
                        }
                    }
                }
            }
            ret.add_char(c);
        }
        return ret;
    }
    bool stringContainsFormD(const char* in) {
        for (;; ) {
            unsigned c;
            auto d = pfc::utf8_decode_char(in, c);
            if (d == 0) return false;
            if (is_modifier(c)) return true;
            in += d;
        }
    }
}
#if ! defined(__APPLE__) && !defined(_WIN32)
namespace pfc {
    pfc::string8 unicodeNormalizeD(const char* in) {
        return unicodeNormalizeD_Lite(in);
    }
    pfc::string8 unicodeNormalizeC(const char* in) {
        return unicodeNormalizeC_Lite(in);
    }
}

#endif // #if ! defined(__APPLE__) && !defined(_WIN32)