/*
 * Copyright (C) 2011-2020 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1.  Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer. 
 * 2.  Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution. 
 * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
 *     its contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission. 
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

// This is based on WebKit's TestWebkitAPI test for WTF's RedBlackTree.

#include "TestHarness.h"
#include <algorithm>
#include "pas_cartesian_tree.h"
#include "pas_heap_lock.h"
#include "pas_utility_heap.h"
#include <sstream>
#include <vector>

using namespace std;

namespace {

static constexpr bool verbose = false;

struct TestNode : public pas_cartesian_tree_node {
    TestNode(char xKey, char yKey, unsigned value)
        : xKey(xKey)
        , yKey(yKey)
        , value(value)
    {
    }
    
    char xKey;
    char yKey;
    unsigned value;

    static int compare(void* aRaw, void* bRaw)
    {
        char a = static_cast<char>(reinterpret_cast<uintptr_t>(aRaw));
        char b = static_cast<char>(reinterpret_cast<uintptr_t>(bRaw));
        
        if (a < b)
            return -1;
        if (a == b)
            return 0;
        return 1;
    }

    static void* getXKey(pas_cartesian_tree_node* node)
    {
        return reinterpret_cast<void*>(
            static_cast<uintptr_t>(reinterpret_cast<TestNode*>(node)->xKey));
    }

    static void* getYKey(pas_cartesian_tree_node* node)
    {
        return reinterpret_cast<void*>(
            static_cast<uintptr_t>(reinterpret_cast<TestNode*>(node)->yKey));
    }
};

static pas_cartesian_tree_config config = {
    .get_x_key = TestNode::getXKey,
    .get_y_key = TestNode::getYKey,
    .x_compare = TestNode::compare,
    .y_compare = TestNode::compare
};

static unsigned counter;

struct Pair {
    Pair() = default;
    
    Pair(char xKey, char yKey, unsigned value)
        : xKey(xKey)
        , yKey(yKey)
        , value(value)
    {
    }
    
    bool operator==(const Pair& other) const
    {
        return xKey == other.xKey;
    }
    
    bool operator<(const Pair& other) const
    {
        return xKey < other.xKey;
    }
    
    char xKey;
    char yKey;
    unsigned value;
};

typedef vector<Pair> PairVector;

PairVector findExact(PairVector& asVector, char xKey)
{
    PairVector result;
    
    for (size_t index = 0; index < asVector.size(); ++index) {
        if (asVector[index].xKey == xKey)
            result.push_back(asVector[index]);
    }
    
    sort(result.begin(), result.end());
    
    return result;
}

void remove(PairVector& asVector, size_t index)
{
    asVector[index] = asVector.back();
    asVector.pop_back();
}

PairVector findLeastGreaterThanOrEqual(PairVector& asVector, char xKey)
{
    char bestKey = 0; // assignment to make gcc happy
    bool foundKey = false;
    
    for (size_t index = 0; index < asVector.size(); ++index) {
        if (asVector[index].xKey >= xKey) {
            if (asVector[index].xKey < bestKey || !foundKey) {
                foundKey = true;
                bestKey = asVector[index].xKey;
            }
        }
    }
    
    PairVector result;
    
    if (!foundKey)
        return result;
    
    return findExact(asVector, bestKey);
}

void assertFoundAndRemove(PairVector& asVector, char xKey, char yKey, unsigned value)
{
    bool found = false;
    size_t foundIndex = 0; // make compilers happy
    
    for (size_t index = 0; index < asVector.size(); ++index) {
        if (asVector[index].xKey == xKey
            && asVector[index].yKey == yKey
            && asVector[index].value == value) {
            CHECK(!found);
            
            found = true;
            foundIndex = index;
        }
    }
    
    CHECK(found);
    
    remove(asVector, foundIndex);
}

// This deliberately passes a copy of the vector.
void assertEqual(pas_cartesian_tree& asCartesianTree, PairVector asVector)
{
    for (TestNode* current = reinterpret_cast<TestNode*>(
             pas_cartesian_tree_minimum(&asCartesianTree));
         current;
         current = reinterpret_cast<TestNode*>(pas_cartesian_tree_node_successor(current)))
        assertFoundAndRemove(asVector, current->xKey, current->yKey, current->value);
    CHECK(asVector.empty());
}

void assertSameValuesForKey(pas_cartesian_tree& asCartesianTree, TestNode* node,
                            PairVector foundValues, char xKey)
{
    if (node) {
        CHECK_EQUAL(node->xKey, xKey);
        
        TestNode* prevNode = node;
        do {
            node = prevNode;
            prevNode = reinterpret_cast<TestNode*>(pas_cartesian_tree_node_predecessor(prevNode));
        } while (prevNode && prevNode->xKey == xKey);
        
        if (verbose)
            printf("in assertSameValuesForKey, starting the search: node = %p\n", node);
        
        CHECK_EQUAL(node->xKey, xKey);
        CHECK(!prevNode || prevNode->xKey < xKey);
        
        do {
            if (verbose)
                printf("node = %p\n", node);
            
            assertFoundAndRemove(foundValues, node->xKey, node->yKey, node->value);
            
            node = reinterpret_cast<TestNode*>(pas_cartesian_tree_node_successor(node));
            CHECK(!node || node->xKey >= xKey);
        } while (node && node->xKey == xKey);
    }
    
    CHECK(foundValues.empty());
}

static constexpr unsigned nodeDumpWidth = 2;

unsigned cartesianTreePrintWidth(pas_cartesian_tree_node* node)
{
    if (!node)
        return 0;
    return nodeDumpWidth
        + cartesianTreePrintWidth(pas_compact_cartesian_tree_node_ptr_load(&node->left))
        + cartesianTreePrintWidth(pas_compact_cartesian_tree_node_ptr_load(&node->right));
}

void printSpaces(unsigned count)
{
    while (count--)
        cout << " ";
}

void dumpCartesianTree(pas_cartesian_tree& asCartesianTree, const char* prefix)
{
    struct WorkItem {
        WorkItem() = default;
        
        explicit WorkItem(pas_cartesian_tree_node* node)
            : node(node)
            , spaces(0)
        {
        }

        explicit WorkItem(unsigned spaces)
            : node(nullptr)
            , spaces(spaces)
        {
        }

        pas_cartesian_tree_node* node;
        unsigned spaces;
    };

    vector<WorkItem> workItems;
    bool hasRealWork = false;

    if (pas_cartesian_tree_node* node = pas_compact_cartesian_tree_node_ptr_load(
            &asCartesianTree.root)) {
        workItems.push_back(WorkItem(node));
        hasRealWork = true;
    }

    while (hasRealWork) {
        vector<WorkItem> currentWorkItems;
        swap(workItems, currentWorkItems);
        hasRealWork = false;

        cout << prefix;

        for (WorkItem workItem : currentWorkItems) {
            if (workItem.spaces) {
                PAS_ASSERT(!workItem.node);
                printSpaces(workItem.spaces);
                workItems.push_back(workItem);
                continue;
            }
            auto handleChild =
                [&] (pas_cartesian_tree_node* child) {
                    if (!child)
                        return;
                    printSpaces(cartesianTreePrintWidth(child));
                    workItems.push_back(WorkItem(child));
                    hasRealWork = true;
                };
            handleChild(pas_compact_cartesian_tree_node_ptr_load(&workItem.node->left));
            TestNode* node = static_cast<TestNode*>(workItem.node);
            cout << node->xKey;
            cout << node->yKey;
            workItems.push_back(WorkItem(nodeDumpWidth));
            handleChild(pas_compact_cartesian_tree_node_ptr_load(&workItem.node->right));
        }

        cout << "\n";
    }
}

void dumpVector(PairVector vector)
{
    bool first = true;
    for (const Pair& pair : vector) {
        if (first)
            first = false;
        else
            cout << " ";
        cout << pair.xKey << pair.yKey;
    }
}

// The control string is a null-terminated list of commands. Each
// command is two characters, with the first identifying the operation
// and the second giving a key. The commands are:
//  +x  Add x
//  *x  Find all elements equal to x
//  @x  Find all elements that have the smallest key that is greater than or equal to x
//  !x  Remove all elements equal to x
void testDriver(const char* controlString)
{
    PairVector asVector;
    pas_cartesian_tree asCartesianTree;
    
    pas_cartesian_tree_construct(&asCartesianTree);
    
    for (const char* current = controlString; *current;) {
        char command = *current++;
        char xKey = *current++;
        char yKey = 0;
        if (command == '+')
            yKey = *current++;
        unsigned value = ++counter;
            
        PAS_ASSERT(command);
        PAS_ASSERT(xKey);
        if (command == '+')
            PAS_ASSERT(yKey);
        
        if (verbose) {
            printf("Running command: %c%c", command, xKey);
            if (command == '+')
                printf("%c", yKey);
            printf(" with current = %p (%zu)\n", current, current - controlString);
        }
            
        switch (command) {
        case '+': {
            pas_heap_lock_lock();
            TestNode* node = static_cast<TestNode*>(
                pas_utility_heap_allocate(sizeof(TestNode), "TestNode"));
            if (verbose)
                cout << "Adding node = " << node << "\n";
            pas_heap_lock_unlock();
            new (node) TestNode(xKey, yKey, value);
            pas_cartesian_tree_insert(
                &asCartesianTree,
                reinterpret_cast<void*>(static_cast<uintptr_t>(xKey)),
                reinterpret_cast<void*>(static_cast<uintptr_t>(yKey)),
                node,
                &config);
            asVector.push_back(Pair(xKey, yKey, value));
            break;
        }
                
        case '*': {
            TestNode* node = reinterpret_cast<TestNode*>(
                pas_cartesian_tree_find_exact(
                    &asCartesianTree,
                    reinterpret_cast<void*>(static_cast<uintptr_t>(xKey)),
                    &config));
            if (verbose)
                printf("Found node = %p\n", node);
            if (node)
                CHECK_EQUAL(node->xKey, xKey);
            assertSameValuesForKey(asCartesianTree, node, findExact(asVector, xKey), xKey);
            break;
        }

        case '@': {
            TestNode* node = reinterpret_cast<TestNode*>(
                pas_cartesian_tree_find_least_greater_than_or_equal(
                    &asCartesianTree,
                    reinterpret_cast<void*>(static_cast<uintptr_t>(xKey)),
                    &config));
            if (verbose) {
                cout << "CartesianTree:\n";
                dumpCartesianTree(asCartesianTree, "    ");
                cout << "Vector: ";
                dumpVector(asVector);
                cout << "\n";
            }
            if (verbose)
                printf("Found node = %p\n", node);
            if (node) {
                CHECK_GREATER_EQUAL(node->xKey, xKey);
                assertSameValuesForKey(asCartesianTree, node, findLeastGreaterThanOrEqual(asVector, xKey), node->xKey);
            } else
                CHECK(findLeastGreaterThanOrEqual(asVector, xKey).empty());
            break;
        }
                
        case '!': {
            while (true) {
                TestNode* node = static_cast<TestNode*>(
                    pas_cartesian_tree_find_exact(
                        &asCartesianTree,
                        reinterpret_cast<void*>(static_cast<uintptr_t>(xKey)),
                        &config));
                if (verbose) {
                    cout << "Found node = " << node;
                    if (node)
                        cout <<" (" << node->xKey << node->yKey << ")";
                    cout << " and removing it.\n";
                }
                if (node) {
                    pas_cartesian_tree_remove(&asCartesianTree, node, &config);
                    CHECK_EQUAL(node->xKey, xKey);
                    assertFoundAndRemove(asVector, node->xKey, node->yKey, node->value);
                    
                    if (verbose) {
                        cout << "Validating cartesian tree right after removal:\n";
                        dumpCartesianTree(asCartesianTree, "    ");
                    }
                    pas_cartesian_tree_validate(&asCartesianTree, &config);
                } else {
                    CHECK(findExact(asVector, xKey).empty());
                    break;
                }
            }
            break;
        }
                
        default:
            CHECK(!"bad command");
            break;
        }

        if (verbose) {
            cout << "Validating cartesian tree:\n";
            dumpCartesianTree(asCartesianTree, "    ");
        }
        pas_cartesian_tree_validate(&asCartesianTree, &config);
        CHECK_EQUAL(pas_cartesian_tree_size(&asCartesianTree), asVector.size());
        assertEqual(asCartesianTree, asVector);
    }
}

void randomTestDriver(unsigned numAddOperations, unsigned numOperations)
{
    ostringstream out;
    const char* things = "abcdefghijklmnopqrstuvwxyzQWERTYUIOPASDFGHJKLZXCVBNM1234567890";
    const char* operations = "+*@!";
    auto randomChar =
        [] (const char* things) -> char {
            return things[deterministicRandomNumber(static_cast<unsigned>(strlen(things)))];
        };
    for (unsigned index = numAddOperations; index--;) {
        out << "+" << randomChar(things) << randomChar(things);
    }
    for (unsigned index = numOperations; index--;) {
        char operation = randomChar(operations);
        out << operation << randomChar(things);
        if (operation == '+')
            out << randomChar(things);
    }
    string str = out.str();
    if (verbose)
        cout << "    Operation string: " << str << "\n";
    testDriver(str.c_str());
}

} // anonymous namespace

void addCartesianTreeTests()
{
    ADD_TEST(testDriver(""));
    ADD_TEST(testDriver("*x@y!z"));
    ADD_TEST(testDriver("+aa"));
    ADD_TEST(testDriver("+aa*x@y!z"));
    ADD_TEST(testDriver("+aa*a@a!a"));
    ADD_TEST(testDriver("+aa+ba"));
    ADD_TEST(testDriver("+ab+ba"));
    ADD_TEST(testDriver("+aa+bb"));
    ADD_TEST(testDriver("+ab+bb"));
    ADD_TEST(testDriver("+aa+bb+cc"));
    ADD_TEST(testDriver("+ab+bc+ca"));
    ADD_TEST(testDriver("+ab+ba+cc"));
    ADD_TEST(testDriver("+ac+bb+ca"));
    ADD_TEST(testDriver("+az+by+cx+dw"));
    ADD_TEST(testDriver("+az+by+cx+dw!a"));
    ADD_TEST(testDriver("+aw+by+cx+dz"));
    ADD_TEST(testDriver("+aw+by+cx+dz!d"));
    ADD_TEST(testDriver("+az+by+dx+cw"));
    ADD_TEST(testDriver("+az+by+dx+cw!b"));
    ADD_TEST(testDriver("+az+bx+dy+cw"));
    ADD_TEST(testDriver("+az+bx+dy+cw!c"));
    ADD_TEST(testDriver("+az+dy+cx+bw"));
    ADD_TEST(testDriver("+az+dy+cx+bw!b"));
    ADD_TEST(testDriver("+ay+dz+cx+bw"));
    ADD_TEST(testDriver("+ay+dz+cx+bw!d"));
    ADD_TEST(testDriver("+az+dy+bx+cw"));
    ADD_TEST(testDriver("+az+dy+bx+cw!a"));
    ADD_TEST(testDriver("+ax+dy+bz+cw"));
    ADD_TEST(testDriver("+ax+dy+bz+cw!c"));
    ADD_TEST(testDriver("+dz+by+cx+aw"));
    ADD_TEST(testDriver("+dz+by+cx+aw!a"));
    ADD_TEST(testDriver("+dz+bw+cx+ay"));
    ADD_TEST(testDriver("+dz+bw+cx+ay!b"));
    ADD_TEST(testDriver("+dz+by+ax+cw"));
    ADD_TEST(testDriver("+dz+by+ax+cw!c"));
    ADD_TEST(testDriver("+dz+by+aw+cx"));
    ADD_TEST(testDriver("+dz+by+aw+cx!d"));
    ADD_TEST(testDriver("+dz+ay+cx+bw"));
    ADD_TEST(testDriver("+dz+ay+cx+bw!b"));
    ADD_TEST(testDriver("+dw+ax+cy+bz"));
    ADD_TEST(testDriver("+dw+ax+cy+bz!c"));
    ADD_TEST(testDriver("+dz+ay+bx+cw"));
    ADD_TEST(testDriver("+dz+ay+bx+cw!a"));
    ADD_TEST(testDriver("+dz+aw+by+cx"));
    ADD_TEST(testDriver("+dz+aw+by+cx!d"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!a!b!c!d"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!a!b!d!c"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!a!c!d!b"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!a!c!b!d"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!a!d!b!c"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!a!d!c!b"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!b!d!c!a"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!b!d!a!c"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!d!b!a!c"));
    ADD_TEST(testDriver("+ax+by+cz+dx+ay+bz+cx+dy+az+bx+cy+dz+ax+by+cz+dx+ay+bz+cm+dn+ao+bp+cq+dr+am+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq+ar+bn+co+dp+aq+br+cs+dm+an+bo+cp+dq!c!b!a!d"));
    ADD_TEST(testDriver("+az+by+cx+dw+av+bu+ct+ds+ar+bq+cp+do+an+bm+cl+dk+aj+bi+ch+dg+af+be+cd+dc+ab+ba+ca+db+ac+bd+ce+df+ag+bh+ci+dj+ak+bl+cm+dn+ax+by+cz+dz+ay+bx+cf+dg+eh+fi+gf+hg+ih+ji+ka+lb+mc+nd+oe+pf+qg+rh+si+tj+uk+vl+xm+yn+zo"));
    ADD_TEST(testDriver("+az+by+cx+dw+av+bu+ct+ds+ar+bq+cp+do+an+bm+cl+dk+aj+bi+ch+dg+af+be+cd+dc+ab+ba+ca+db+ac+bd+ce+df+ag+bh+ci+dj+ak+bl+cm+dn+ax+by+cz+dz+ay+bx+cf+dg+eh+fi+gf+hg+ih+ji+ka+lb+mc+nd+oe+pf+qg+rh+si+tj+uk+vl+xm+yn+zo!p!i!a!l!z!m"));
    ADD_TEST(testDriver("+az+by+cx+dw+av+bu+ct+ds+ar+bq+cp+do+an+bm+cl+dk+aj+bi+ch+dg+af+be+cd+dc+ab+ba+ca+db+ac+bd+ce+df+ag+bh+ci+dj+ak+bl+cm+dn+ax+by+cz+dz+ay+bx+cf+dg+eh+fi+gf+hg+ih+ji+ka+lb+mc+nd+oe+pf+qg+rh+si+tj+uk+vl+xm+yn+zo!k!i!b!s!r!g"));
    ADD_TEST(testDriver("+zg+yh+xq+wi+vn+ud+tp+sy+rf+qg+pq+oh+na+mg+ld+kc+jd+ie+hj+gh+fe+en+ds+cf+br+ad*a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z!a!b!c!d!e!f!g!h!i!j!k!l!m!n!o!p!q!r!s!t!u!v!w!x!y!z"));
    ADD_TEST(testDriver("+zj+yd+xb+ew+fv+us+ty+sf+rw+qf+pg+oe+nd+mq+ld+kg+jd+iq+hd+ge+fd+ef+dw+cf+bv+aw*a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z!z!y!x!w!v!u!t!s!r!q!p!o!n!m!l!k!j!i!h!g!f!e!d!c!b!a"));
    ADD_TEST(testDriver("+aj+bf+cb+dr+af+bh+cw+dd+ah+br+cd+dq+ag+bc+cr+df+aq+bh+cr+ds+an+br+cj+dq+aj+bq+cf+dr+af+bv+cc+ds+ab+br+cn+df+aq+bn+cc+dh+aw+bc+ch+de+ar+bb+cq+dn+er+fn+gc+ht+iw+jg+kd+lv+mr+nq+og+pr+qw+rb+st+tj+uu+vn+xd+yv+zt*a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z!a!b!c!d!e!f!g!h!i!j!k!l!m!n!o!p!q!r!s!t!u!v!w!x!y!z"));
    ADD_TEST(testDriver("+dj+ds+mt+wn@d@m@w@a@g@q"));
    ADD_TEST(testDriver("+da+da+da+da+da+da+da+da+da+da+fa+fa+fa+fa+fa+fa+fa+ha+ha+ia+ja+ka+la+ma+oa+pa+qa+ra+za@a@b@c@d@e@f@g@h@i@j@k@l@m@n@o@p@q@r@s@t@u@v@w@x@y@z"));
    ADD_TEST(randomTestDriver(10, 1000));
    ADD_TEST(randomTestDriver(20, 1000));
    ADD_TEST(randomTestDriver(30, 1000));
    ADD_TEST(randomTestDriver(40, 1000));
    ADD_TEST(randomTestDriver(50, 1000));
    ADD_TEST(randomTestDriver(100, 1000));
    ADD_TEST(randomTestDriver(1000, 1000));
    ADD_TEST(randomTestDriver(10, 10000));
    ADD_TEST(randomTestDriver(20, 10000));
    ADD_TEST(randomTestDriver(100, 10000));
    ADD_TEST(randomTestDriver(1000, 10000));
}