//////////////////////////////////////////////////////////////////////////////
// Testy
//////////////////////////////////////////////////////////////////////////////

/*
 * If you did not implement ListMap::const_iterator::operator--() set
 * TEST_REVERSE_ITERATORS and SPEED_RITER_ITERATIONS to 0.
 */

/* Do not touch this part */
#if defined DO_TEST && ! defined DO_SPEED_TEST
# define DO_SPEED_TEST           (!DO_TEST)
#endif
#if defined DO_SPEED_TEST && ! defined DO_TEST
# define DO_TEST                 (!DO_SPEED_TEST)
#endif

/* Here you can configure if you like */
#ifndef DO_TEST
# define DO_TEST                 1
#endif
#ifndef DO_SPEED_TEST
# define DO_SPEED_TEST           0
#endif

#if DO_TEST
# define TEST_REVERSE_ITERATORS  1
# define KEY_MAX                 4096
# define INS_ITERATIONS          (KEY_MAX / 2)
# define SET_ITERATIONS          (KEY_MAX / 2)
# define ERASE_ITERATIONS        (INS_ITERATIONS / 4)
# define ERASE_BY_KEY_ITERATIONS ERASE_ITERATIONS
# define ERASE_RANGE_ITERATIONS  (ERASE_ITERATIONS / 2)
# define ERASE_RANGE_MAX         4
# define FIND_ITERATIONS         KEY_MAX

# define MAPS_COUNT              4
# define SRAND_RANDOMIZE         0
# define SRAND_SEED              0
#endif

#if DO_SPEED_TEST
# define SPEED_KEY_MAX           0
# define SPEED_INS_ITERATIONS    16384
# define SPEED_FIND_ITERATIONS   16384
# define SPEED_ERASE_ITERATIONS  16384
# define SPEED_ITER_ITERATIONS   16384
# define SPEED_RITER_INS         1024
# define SPEED_RITER_ITERATIONS  1024

# define SPEED_SRAND_RANDOMIZE   0
# define SPEED_SRAND_SEED        0
#endif



#include <map>
#include <limits.h>
#include <stdlib.h>
#if SRAND_RANDOMIZE || SPEED_SRAND_RANDOMIZE
# include <time.h>
#endif
#if DO_SPEED_TEST
# include "timer.h"
#endif


typedef std::map<ListMap::Key, ListMap::Val> StdMap;
typedef std::pair<ListMap, StdMap> MapPair;
typedef std::pair<ListMap::iterator, bool> ListInsRet;
typedef std::pair<StdMap::iterator, bool> StdInsRet;


#if DO_TEST
std::ostream &operator<<(std::ostream &os, const ListMap::P &entry) {
    os << '(';
    os.width(5);
    return os << entry.first << ", " << entry.second << ')';
}



/* Finds elements in maps */
static std::pair<ListMap::iterator, StdMap::iterator>
find(ListMap &m, StdMap &sm, const ListMap::Key &k) {
    /* Find key */
    ListMap::iterator it =  m.find(k);
    if (it!=m.end() && it->first!=k) {
        std::cerr << "searched for " << k << " but got " << *it << "\n";
    }

    /* If found test with [] */
    if (it!=m.end() && it->second!=m[k]) {
        std::cerr << "value of find(" << k << ") (" << it->first
                  << ") differs from m[" << k << "] (" << m[k] << ")\n";
    }

    /* Compare with StdMap */
    StdMap::iterator sit = sm.find(k);
    if (sit==sm.end()) {
        if (it!=m.end()) {
            std::cerr << "key " << k
                      << " does not exist in StdMap but exists in ListMap; "
                      << *it << "\n";
        }
    } else if (it==m.end()) {
        std::cerr << "key " << k
                  << " exists in StdMap but does not exist in ListMap; "
                  << *sit << "\n";
    } else if (it->first!=sit->first || it->second!=sit->second) {
        std::cerr << "StdMap contains " << *sit << " but ListMap contains "
                  << *it << "\n";
    }

    return std::make_pair(it, sit);
}



/* Checks number of elements */
static void elements(ListMap &m, StdMap &sm, bool print = true) {
    if (m.size()!=sm.size()) {
        std::cerr << "Number of elements " << m.size()
                  << " should be " << sm.size() << "\n";
    } else if (print){
        std::cout << "Number of elements " << m.size() << "\n";
    }
    std::cout << '\n';
}



/* Checks elements count */
static void count_changed(size_t from, size_t to, size_t expected) {
    if (to==expected) {
        return;
    }
    if (from==to) {
        std::cerr << "elements count stayed at " << from
                  << " where should change to " << expected << '\n';
        return;
    }

    std::cerr << "elements count changed from " << from << " to " << to;
    if (from==expected) {
        std::cerr << "where should stayed at " << expected << '\n';
    } else {
        std::cerr << "where should change to " << expected << '\n';
    }
}



/* Inserts entry */
static void insert(ListMap &m, StdMap &sm, const ListMap::Key &k,
                   const ListMap::Val &v) {
    const ListMap::P entry = std::make_pair(k, v);
    std::cout << ":: inserting " << entry << "\n";
    ListMap::iterator it = find(m, sm, k).first;

    size_t num = m.size();
    ListInsRet ret = m.insert(entry);
    sm.insert(entry);

    if ((it==m.end()) != ret.second) {
        std::cerr << "insertion of " << entry
                  << (ret.second ?  "succeed\n" : " failed\n");
    }
    if (ret.first->first!=k) {
        std::cerr << "inserted " << k << " but got " << *ret.first << "\n";
    }
    if (it==m.end() && ret.first->second!=v) {
        std::cerr << "inserted " << v << " but got " << *ret.first << "\n";
    }
    if (it!=m.end() && *ret.first!=*it) {
        std::cerr << "value has changed but it shouldn't\n";
    }

    count_changed(num, m.size(), num + (it==m.end()));
}



/* Sets entry */
static void set(ListMap &m, StdMap &sm, const ListMap::Key &k,
                const ListMap::Val &v) {
    std::cout << ":: setting " << std::make_pair(k, v) << "\n";
    bool found = find(m, sm, k).first != m.end();;

    size_t num = m.size();
    m [k] = v;
    sm[k] = v;
    ListMap::iterator it = find(m, sm, k).first;

    if (it==m.end()) {
        std::cerr << "set " << k << " but find() returns {end}\n";
    } else {
        if (it->first!=k) {
            std::cerr << "set " << k << " but got " << *it << "\n";
        }
        if (it->second!=v) {
            std::cerr << "set " << v << " but got " << *it << "\n";
        }
    }

    count_changed(num, m.size(), num + !found);
}



/* Erases entry */
static void erase(ListMap &m, StdMap &sm, const ListMap::Key &k) {
    std::cout << ":: erasing " << k << "\n";
    const std::pair<ListMap::iterator, StdMap::iterator> p = find(m, sm, k);
    ListMap::iterator it = p.first;
    StdMap::iterator sit = p.second;

    size_t num = m.size();
    if (it!=m.end()) {
        ListMap::iterator i2 = m.erase(it);
        sm.erase(sit);
    }

    count_changed(num, m.size(), num - (it!=m.end()));
}



/* Erases entry by key */
static void erase_by_key(ListMap &m, StdMap &sm, const ListMap::Key &k) {
    std::cout << ":: erasing (by key) " << k << "\n";
    const std::pair<ListMap::iterator, StdMap::iterator> p = find(m, sm, k);
    ListMap::iterator it = p.first;
    StdMap::iterator sit = p.second;
    bool found = it!=m.end();

    size_t num = m.size();
    int removed = m.erase(k);
    sm.erase(k);

    if (found && !removed) {
        std::cerr << "erase removed nothing but element was found\n";
    } else if (!found && removed) {
        std::cerr << "erase removed something but nothing was found\n";
    }

    count_changed(num, m.size(), num - (it!=m.end()));
}



/* Erases number of entries */
static void erase_range(ListMap &m, StdMap &sm, const ListMap::Key &k,
                        size_t range) {
    std::cout << ":: erasing " << range << " key(s) from " << k << "\n";
    const std::pair<ListMap::iterator, StdMap::iterator> p = find(m, sm, k);
    ListMap::iterator it = p.first;
    StdMap::iterator sit = p.second;

    ListMap::iterator end = it;
    StdMap::iterator send = sit;
    size_t rem = 0;
    for (size_t i = range; i; --i) {
        if (end!=m.end()) {
            ++end;
            ++rem;
        }
        if (send!=sm.end()) ++send;
    }

    size_t num = m.size();
    ListMap::iterator ret = m.erase(it, end);
    sm.erase(sit, send);

    if (ret!=end) {
        std::cerr << "erase returned ";
        if (ret==m.end()) {
            std::cerr << "{end}";
        } else {
            std::cerr << '{' << *ret << '}';
        }
        std::cerr << " where ";
        if (end==m.end()) {
            std::cerr << "{end}";
        } else {
            std::cerr << '{' << *end << '}';
        }
        std::cerr << " expected\n";
    }

    count_changed(num, m.size(), num - rem);
}



/* Tests iterators */
static void iterators(ListMap &m, StdMap sm) {
    ListMap::size_type size = m.size(), num = 0;
    ListMap::iterator it = m.begin(), end = m.end();

    while (it!=end) {
        const ListMap::P &entry = *it;
        const StdMap::iterator sit = sm.find(entry.first);

        std::cout << ":: iterating through " << entry << "\n";
        if (sit==sm.end()) {
            std::cerr << "We were in " << entry << " already!\n";
        } else {
            sm.erase(sit);
        }

        ++it;
        ++num;
    }

    if (num!=size) {
        std::cerr << "Map contains " << size << " elements but we where in "
                  << num;
    }
}


/* Test reverse iterators */
static void reverse_iterators(ListMap &m, StdMap sm) {
    ListMap::size_type size = m.size(), num = 0;
    ListMap::iterator it = m.end(), begin = m.begin();

    while (it!=begin) {
        --it;
        ++num;

        const ListMap::P &entry = *it;
        const StdMap::iterator sit = sm.find(entry.first);

        std::cout << ":: iterating in reverse through " << entry << "\n";
        if (sit==sm.end()) {
            std::cerr << "We were in " << entry << " already!\n";
        } else {
            sm.erase(sit);
        }
    }

    if (num!=size) {
        std::cerr << "Map contains " << size << " elements but we where in "
                  << num;
    }
}



/* Compare two maps */
#if MAPS_COUNT > 1
static void compare(unsigned id1, unsigned id2, ListMap &m1, ListMap &m2,
                    bool result) {
    bool equal = m1.struct_eq(m2);
    bool identical = m1.info_eq(m2);

    if (equal!=m2.info_eq(m1)) {
        std::cerr << '#' << id1 << (equal ? " == " : " != ") << '#' << id2
                  << " but #" << id2 << (equal ? " != " : " == ") << '#' << id1
                  << '\n';
    }

    if (identical!=m2.struct_eq(m1)) {
        std::cerr << '#' << id1 << (identical ? " === " : " !== ") << '#' << id2
                  << " but #" << id2 << (identical ? " !== " : " === ") << '#'
                  << id1 << '\n';
    }

    if (identical && !equal) {
        std::cerr << "#" << id1 << " === #" << id2 << " but #" << id1 << " != #"
                  << id2 << '\n';
    }

    if (equal && m1.size() != m2.size()) {
        std::cerr << "#" << id1 << " == #" << id2 << " but size(#" << id1
                  << ") == " << m1.size() << " != " << m2.size()
                  << " == size(#" << id2 << ")\n";
    }

    if (equal!=result) {
        std::cerr << '#' << id1 << (equal ? " == " : " != ") << '#' << id2
                  << " but expected otherwise\n";
    }
}
#endif


#undef RAND_KEY
#if KEY_MAX
# define RAND_KEY (rand() % KEY_MAX - KEY_MAX/2)
#else
# define RAND_KEY (rand() - RAND_MAX/2)
#endif


/* Test function */
static void test(void) {
    /* Init */
    MapPair m[MAPS_COUNT];
    unsigned i, j, k;

#if SRAND_RANDOMIZE
    srand(time(0));
#else
    srand(SRAND_SEED);
#endif


    /* All should compare equal */
#if MAPS_COUNT > 1
    for (i = 0; i<(sizeof(m)/sizeof(*m)); ++i) {
        for (j = 0; j<(sizeof(m)/sizeof(*m)); ++j) {
            compare(i, j, m[i].first, m[j].first, true);
        }
    }
    std::cout << '\n';
#endif


    /* Main test */
    for (k = 0; k<(sizeof(m)/sizeof(*m)); ++k) {
        std::cout << "=== Operates on map #" << k << " ===\n\n";

        /* Insert */
        for (i = 0; i<INS_ITERATIONS; ++i) {
            char str[9];
            for (j = 0; j<8; ++j) str[j] = 'A' + rand() % 26;
            str[j] = 0;
            insert(m[k].first, m[k].second, RAND_KEY, str);
        }
        elements(m[k].first, m[k].second);

        /* Set */
        for (i = 0; i<INS_ITERATIONS; ++i) {
            char str[9];
            for (j = 0; j<8; ++j) str[j] = 'A' + rand() % 26;
            str[j] = 0;
            set(m[k].first, m[k].second, RAND_KEY, str);
        }
        elements(m[k].first, m[k].second);

        /* Erase */
        for (i = 0; i<ERASE_ITERATIONS; ++i) {
            erase(m[k].first, m[k].second, RAND_KEY);
        }
        elements(m[k].first, m[k].second);

        /* Erase by key */
        for (i = 0; i<ERASE_BY_KEY_ITERATIONS; ++i) {
            erase_by_key(m[k].first, m[k].second, RAND_KEY);
        }
        elements(m[k].first, m[k].second);

        /* Erase range */
        for (i = 0; i<ERASE_BY_KEY_ITERATIONS; ++i) {
            erase_range(m[k].first, m[k].second, RAND_KEY,
                        rand() % ERASE_RANGE_MAX);
        }
        elements(m[k].first, m[k].second);

        /* Find */
#if FIND_ITERATIONS >= KEY_MAX
        for (i = 0; i < KEY_MAX; ++i) {
            find(m[k].first, m[k].second, i);
        }
#else
        for (i = 0; i < FIND_ITERATIONS; ++i) {
            find(m[k].first, m[k].second, RAND_KEY);
        }
#endif

        /* Iterators */
        iterators(m[k].first, m[k].second);
#if TEST_REVERSE_ITERATORS
        reverse_iterators(m[k].first, m[k].second);
#endif
    }


#if MAPS_COUNT > 1
    /* Compare */
    for (i = 0; i<(sizeof(m)/sizeof(*m)); ++i) {
        for (j = 0; j<(sizeof(m)/sizeof(*m)); ++j) {
            compare(i, j, m[i].first, m[j].first, i==j || m[i].second==m[j].second);
        }
    }
    std::cout << '\n';


    /* Create two equal maps */
    std::cout << "=== Creating two equal maps ===\n\n";
    m[0].first.clear(); m[0].second.clear();
    m[1].first.clear(); m[1].second.clear();

    compare(0, 0, m[0].first, m[0].first, true);
    compare(0, 1, m[0].first, m[1].first, true);
    compare(1, 0, m[1].first, m[0].first, true);
    compare(1, 1, m[1].first, m[1].first, true);

    /* Insert */
    for (i = 0; i<INS_ITERATIONS; ++i) {
        ListMap::Key key = RAND_KEY;
        char str[9];
        for (j = 0; j<8; ++j) str[j] = 'A' + rand() % 26;
        str[j] = 0;
        insert(m[0].first, m[0].second, key, str);
        insert(m[1].first, m[1].second, key, str);
    }
    elements(m[0].first, m[0].second);
    elements(m[1].first, m[1].second);

    /* Set */
    for (i = 0; i<INS_ITERATIONS; ++i) {
        ListMap::Key key = RAND_KEY;
        char str[9];
        for (j = 0; j<8; ++j) str[j] = 'A' + rand() % 26;
        str[j] = 0;
        set(m[0].first, m[0].second, key, str);
        set(m[1].first, m[1].second, key, str);
    }
    elements(m[0].first, m[0].second);
    elements(m[1].first, m[1].second);

    /* Compare */
    compare(0, 0, m[0].first, m[0].first, true);
    compare(0, 1, m[0].first, m[1].first, true);
    compare(1, 0, m[1].first, m[0].first, true);
    compare(1, 1, m[1].first, m[1].first, true);
#endif

    /* Copy constructor test */
    std::cout << "=== Cloning #0 to #666 ===\n";
    ListMap *clone = new ListMap(m[0].first);
    compare(0, 666, m[0].first, *clone, true);
    compare(0, 666, *clone, m[0].first, true);
    delete clone;
}
#endif /* DO_TEST */



/* Speed test */
#if DO_SPEED_TEST


#undef RAND_KEY
#if SPEED_KEY_MAX
# define RAND_KEY (rand() % SPEED_KEY_MAX - SPEED_KEY_MAX/2)
#else
# define RAND_KEY (rand() - RAND_MAX/2)
#endif


#define PRINT_TIME(str) do {                            \
        double _time = timer_stop(timer);               \
        std::cout.width(20);                            \
        std::cout << std::left << (str) << ": ";        \
        std::cout.precision(8);                         \
        std::cout << std::showpoint <<_time << " s\n";  \
    } while (0)


static void speed_test() {
    /* Init */
    ListMap m;
    unsigned i;
    struct time_m timer;

#if SPEED_SRAND_RANDOMIZE
    srand(time(0));
#else
    srand(SPEED_SRAND_SEED);
#endif

    /* Insert */
    timer = timer_start();
    for (i = 0; i<SPEED_INS_ITERATIONS; ++i) {
        m.insert(std::make_pair(RAND_KEY, ""));
    }
    PRINT_TIME("Insert");

    /* Find */
    timer = timer_start();
    for (i = 0; i<SPEED_FIND_ITERATIONS; ++i) {
        m.find(RAND_KEY);
    }
    PRINT_TIME("Find");

    /* Erase */
    timer = timer_start();
    for (i = 0; i<SPEED_ERASE_ITERATIONS; ++i) {
        m.erase(RAND_KEY);
    }
    PRINT_TIME("Erase");

    /* Clear */
    timer = timer_start();
    m.clear();
    PRINT_TIME("Clear");

    /* Insert */
    timer = timer_start();
    for (i = 0; i<SPEED_INS_ITERATIONS; ++i) {
        m.insert(std::make_pair(RAND_KEY, ""));
    }
    PRINT_TIME("Insert");

    /* Iterators */
    timer = timer_start();
    for (i = 0; i<SPEED_ITER_ITERATIONS; ++i) {
        const ListMap::const_iterator end = m.end();
        ListMap::const_iterator it = m.begin();
        for (; it!=end; ++it);
    }
    PRINT_TIME("Iterators");

    /* Find + Erase */
    timer = timer_start();
    for (i = 0; i<SPEED_ERASE_ITERATIONS; ++i) {
        m.erase(m.find(RAND_KEY));
    }
    PRINT_TIME("Find + erase");

    /* Reverse iterators */
#if SPEED_RITER_ITERATIONS
    timer = timer_start();
    m.clear();
    PRINT_TIME("Clear");

    /* Insert */
    timer = timer_start();
    for (i = 0; i<SPEED_RITER_INS; ++i) {
        m.insert(std::make_pair(RAND_KEY, ""));
    }
    PRINT_TIME("Insert (riter)");

    timer = timer_start();
    for (i = 0; i<SPEED_RITER_ITERATIONS; ++i) {
        const ListMap::const_iterator begin = m.begin();
        ListMap::const_iterator it = m.end();
        for (; it!=begin; --it);
    }
    PRINT_TIME("Reverse iterators");
#endif

}
#endif /* DO_SPEED_TEST */



/* Main */
int main(void) {
#if DO_TEST
    test();
    if (CCount::getCount()) {
        std::cerr << "count = " << CCount::getCount()
                  << "; should be 0; memory leak\n";
    } else {
        std::cout << "count = " << CCount::getCount() << "\n";
    }
#endif

#if DO_SPEED_TEST
    speed_test();
#endif

    return 0;
}