/**
 * Contains support code for switch blocks using string constants.
 *
 * Copyright: Copyright Digital Mars 2004 - 2010.
 * License:   $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
 * Authors:   Walter Bright, Sean Kelly
 */

/*          Copyright Digital Mars 2004 - 2010.
 * Distributed under the Boost Software License, Version 1.0.
 *    (See accompanying file LICENSE or copy at
 *          http://www.boost.org/LICENSE_1_0.txt)
 */
module rt.switch_;

private import core.stdc.string;

/******************************************************
 * Support for switch statements switching on strings.
 * Input:
 *      table[]         sorted array of strings generated by compiler
 *      ca              string to look up in table
 * Output:
 *      result          index of match in table[]
 *                      -1 if not in table
 */

extern (C):

int _d_switch_string(char[][] table, char[] ca)
in
{
    //printf("in _d_switch_string()\n");
    assert(table.length >= 0);
    assert(ca.length >= 0);

    // Make sure table[] is sorted correctly
    for (size_t j = 1u; j < table.length; j++)
    {
        auto len1 = table[j - 1].length;
        auto len2 = table[j].length;

        assert(len1 <= len2);
        if (len1 == len2)
        {
            int ci;

            ci = memcmp(table[j - 1].ptr, table[j].ptr, len1);
            assert(ci < 0); // ci==0 means a duplicate
        }
    }
}
out (result)
{
    int cj;

    //printf("out _d_switch_string()\n");
    if (result == -1)
    {
        // Not found
        for (auto i = 0u; i < table.length; i++)
        {
            if (table[i].length == ca.length)
            {   cj = memcmp(table[i].ptr, ca.ptr, ca.length);
                assert(cj != 0);
            }
        }
    }
    else
    {
        assert(0 <= result && cast(size_t)result < table.length);
        for (auto i = 0u; 1; i++)
        {
            assert(i < table.length);
            if (table[i].length == ca.length)
            {
                cj = memcmp(table[i].ptr, ca.ptr, ca.length);
                if (cj == 0)
                {
                    assert(i == result);
                    break;
                }
            }
        }
    }
}
body
{
    //printf("body _d_switch_string(%.*s)\n", ca.length, ca.ptr);
    size_t low  = 0;
    size_t high = table.length;

    version (none)
    {
        // Print table
        printf("ca[] = '%s'\n", ca.length, ca.ptr);
        for (auto i = 0; i < high; i++)
        {
            auto pca = table[i];
            printf("table[%d] = %d, '%.*s'\n", i, pca.length, pca.length, pca.ptr);
        }
    }
    if (high &&
        ca.length >= table[0].length &&
        ca.length <= table[high - 1].length)
    {
        // Looking for 0 length string, which would only be at the beginning
        if (ca.length == 0)
            return 0;

        char c1 = ca[0];

        // Do binary search
        while (low < high)
        {
            auto mid = (low + high) >> 1;
            auto pca = table[mid];
            auto c   = cast(sizediff_t)(ca.length - pca.length);
            if (c == 0)
            {
                c = cast(ubyte)c1 - cast(ubyte)pca[0];
                if (c == 0)
                {
                    c = memcmp(ca.ptr, pca.ptr, ca.length);
                    if (c == 0)
                    {   //printf("found %d\n", mid);
                        return cast(int)mid;
                    }
                }
            }
            if (c < 0)
            {
                high = mid;
            }
            else
            {
                low = mid + 1;
            }
        }
    }

    //printf("not found\n");
    return -1; // not found
}

unittest
{
    switch (cast(char []) "c")
    {
         case "coo":
         default:
             break;
    }

    int bug5381(string s)
    {
        switch (s)
        {
            case "unittest":        return 1;
            case "D_Version2":      return 2;
            case "none":            return 3;
            case "all":             return 4;
            default:                return 5;
        }
    }
    int rc = bug5381("none");
    assert(rc == 3);
}

/**********************************
 * Same thing, but for wide chars.
 */

int _d_switch_ustring(wchar[][] table, wchar[] ca)
in
{
    //printf("in _d_switch_ustring()\n");
    assert(table.length >= 0);
    assert(ca.length >= 0);

    // Make sure table[] is sorted correctly
    for (size_t j = 1u; j < table.length; j++)
    {
        auto len1 = table[j - 1].length;
        auto len2 = table[j].length;

        assert(len1 <= len2);
        if (len1 == len2)
        {
            int c;

            c = memcmp(table[j - 1].ptr, table[j].ptr, len1 * wchar.sizeof);
            assert(c < 0);  // c==0 means a duplicate
        }
    }
}
out (result)
{
    int c;

    //printf("out _d_switch_ustring()\n");
    if (result == -1)
    {
        // Not found
        for (auto i = 0u; i < table.length; i++)
        {
            if (table[i].length == ca.length)
            {   c = memcmp(table[i].ptr, ca.ptr, ca.length * wchar.sizeof);
                assert(c != 0);
            }
        }
    }
    else
    {
        assert(0 <= result && cast(size_t)result < table.length);
        for (auto i = 0u; 1; i++)
        {
            assert(i < table.length);
            if (table[i].length == ca.length)
            {
                c = memcmp(table[i].ptr, ca.ptr, ca.length * wchar.sizeof);
                if (c == 0)
                {
                    assert(i == result);
                    break;
                }
            }
        }
    }
}
body
{
    //printf("body _d_switch_ustring()\n");
    size_t low = 0;
    auto high = table.length;

    version (none)
    {
        // Print table
        wprintf("ca[] = '%.*s'\n", ca.length, ca.ptr);
        for (auto i = 0; i < high; i++)
        {
            auto pca = table[i];
            wprintf("table[%d] = %d, '%.*s'\n", i, pca.length, pca.length, pca.ptr);
        }
    }

    // Do binary search
    while (low < high)
    {
        auto mid = (low + high) >> 1;
        auto pca = table[mid];
        auto c = cast(sizediff_t)(ca.length - pca.length);
        if (c == 0)
        {
            c = memcmp(ca.ptr, pca.ptr, ca.length * wchar.sizeof);
            if (c == 0)
            {   //printf("found %d\n", mid);
                return cast(int)mid;
            }
        }
        if (c < 0)
        {
            high = mid;
        }
        else
        {
            low = mid + 1;
        }
    }
    //printf("not found\n");
    return -1;              // not found
}


unittest
{
    switch (cast(wchar []) "c")
    {
         case "coo":
         default:
             break;
    }

    int bug5381(wstring ws)
    {
        switch (ws)
        {
            case "unittest":        return 1;
            case "D_Version2":      return 2;
            case "none":            return 3;
            case "all":             return 4;
            default:                return 5;
        }
    }
    int rc = bug5381("none"w);
    assert(rc == 3);
}

/**********************************
 * Same thing, but for wide chars.
 */

int _d_switch_dstring(dchar[][] table, dchar[] ca)
in
{
    //printf("in _d_switch_dstring()\n");
    assert(table.length >= 0);
    assert(ca.length >= 0);

    // Make sure table[] is sorted correctly
    for (auto j = 1u; j < table.length; j++)
    {
        auto len1 = table[j - 1].length;
        auto len2 = table[j].length;

        assert(len1 <= len2);
        if (len1 == len2)
        {
            auto c = memcmp(table[j - 1].ptr, table[j].ptr, len1 * dchar.sizeof);
            assert(c < 0);  // c==0 means a duplicate
        }
    }
}
out (result)
{
    //printf("out _d_switch_dstring()\n");
    if (result == -1)
    {
        // Not found
        for (auto i = 0u; i < table.length; i++)
        {
            if (table[i].length == ca.length)
            {   auto c = memcmp(table[i].ptr, ca.ptr, ca.length * dchar.sizeof);
                assert(c != 0);
            }
        }
    }
    else
    {
        assert(0 <= result && cast(size_t)result < table.length);
        for (auto i = 0u; 1; i++)
        {
            assert(i < table.length);
            if (table[i].length == ca.length)
            {
                auto c = memcmp(table[i].ptr, ca.ptr, ca.length * dchar.sizeof);
                if (c == 0)
                {
                    assert(i == result);
                    break;
                }
            }
        }
    }
}
body
{
    //printf("body _d_switch_dstring()\n");
    size_t low = 0;
    auto high = table.length;

    version (none)
    {
        // Print table
        wprintf("ca[] = '%.*s'\n", ca.length, ca.ptr);
        for (auto i = 0; i < high; i++)
        {
            auto pca = table[i];
            wprintf("table[%d] = %d, '%.*s'\n", i, pca.length, pca.length, pca.ptr);
        }
    }

    // Do binary search
    while (low < high)
    {
        auto mid = (low + high) >> 1;
        auto pca = table[mid];
        auto c = cast(sizediff_t)(ca.length - pca.length);
        if (c == 0)
        {
            c = memcmp(ca.ptr, pca.ptr, ca.length * dchar.sizeof);
            if (c == 0)
            {   //printf("found %d\n", mid);
                return cast(int)mid;
            }
        }
        if (c < 0)
        {
            high = mid;
        }
        else
        {
            low = mid + 1;
        }
    }
    //printf("not found\n");
    return -1; // not found
}


unittest
{
    switch (cast(dchar []) "c")
    {
         case "coo":
         default:
             break;
    }

    int bug5381(dstring ds)
    {
        switch (ds)
        {
            case "unittest":        return 1;
            case "D_Version2":      return 2;
            case "none":            return 3;
            case "all":             return 4;
            default:                return 5;
        }
    }
    int rc = bug5381("none"d);
    assert(rc == 3);
}