#!/usr/local/cpython-3.4/bin/python3

# pylint: disable=superfluous-parens
# superfluous-parens: Parentheses are good for clarity and portability

'''Unit tests for dictwrapper_mod.py'''

import sys
import math
import random

import treap
import dictwrapper_mod


def test_insert(number_of_values):
    '''Insert a value into a dict_wrapper tree, then make sure it can be found in the tree'''
    keys = list(range(number_of_values))
    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap, width=5)
    for key in keys:
        dict_wrapper[key] = str(key)

    all_good = True

    for key in keys:
        if key not in dict_wrapper:
            all_good = False
            sys.stderr.write('%s: test_insert(%s): key %s not in dict_wrapper\n' % (sys.argv[0], number_of_values, key))
            sys.stderr.write('%s\n' % str(dict_wrapper))
            continue
        if str(key) != dict_wrapper[key]:
            all_good = False
            sys.stderr.write('%s: test_insert(%s): Found mismatched key: Got %s, expected %s\n' % (
                sys.argv[0], number_of_values, dict_wrapper[key], str(key)))

    return all_good


def test_remove():
    '''
    Insert some values into a dict_wrapper tree, then make sure they can
    all be removed.  Finally, ensure the dict_wrapper tree is empty
    '''
    keys = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    # Shuffling the keys helps keep the print of a manageable size
    random.shuffle(keys)
    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)
    for key in keys:
        dict_wrapper[key] = str(key)
    # Shuffle again to make it a more interesting test
    random.shuffle(keys)

    all_good = True

    for key in keys:
        del dict_wrapper[key]
        try:
            dummy = dict_wrapper[key]
        except KeyError:
            pass
        else:
            all_good = False
            sys.stderr.write('%s: test_remove: element %s not removed\n' % (sys.argv[0], key))

    if dict_wrapper:
        all_good = False
        sys.stderr.write('%s: test_remove: final tree nonempty\n' % (sys.argv[0], ))

    return all_good


def test_large_inserts():
    '''Insert lots of values into a dict_wrapper tree, just to see if we get a traceback'''

    all_good = True

    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)
    nums = 100000
    gap = 997
    key = gap
    expected_min = None
    expected_max = None
    while key != 0:
        if expected_min is None or key < expected_min:
            expected_min = key
        if expected_max is None or key > expected_max:
            expected_max = key
        dict_wrapper[key] = str(key)
        key = (key + gap) % nums

    actual_min = dict_wrapper.find_min()
    if expected_min != actual_min:
        sys.stderr.write('%s: Large dict_wrapper did not return correct minimum: expected: %s, actual: %s\n' % (
            sys.argv[0], expected_min, actual_min))
        all_good = False

    actual_max = dict_wrapper.find_max()
    if expected_max != actual_max:
        sys.stderr.write('%s: Large dict_wrapper did not return correct maximum: expected: %s, actual: %s\n' % (
            sys.argv[0], expected_max, actual_max))
        all_good = False

    return all_good


def test_nonempty():
    '''Test a nonempty dict_wrapper tree'''
    keys = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)
    for key in keys:
        dict_wrapper[key] = str(key)

    all_good = True

    if not dict_wrapper:
        all_good = False
        sys.stderr.write('%s: nonempty dict_wrapper looks empty\n' % sys.argv[0])

    return all_good


def test_empty():
    '''Test an empty dict_wrapper tree'''
    all_good = True

    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)

    if dict_wrapper:
        all_good = False
        sys.stderr.write('%s: empty dict_wrapper looks nonempty\n' % sys.argv[0])

    return all_good


def test_min_max():
    '''Insert some values into a dict_wrapper tree, then test find_min and find_max'''
    keys = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)
    for key in keys:
        dict_wrapper[key] = str(key)

    all_good = True

    actual_min = dict_wrapper.find_min()
    if actual_min != 0:
        sys.stderr.write('%s: minimum was not 0: %s\n' % (sys.argv[0], actual_min))
        all_good = False

    actual_max = dict_wrapper.find_max()
    if actual_max != 9:
        sys.stderr.write('%s: maximum was not 9: %s\n' % (sys.argv[0], actual_max))
        all_good = False

    return all_good


def test_values():
    '''Insert a few key-value pairs, and make sure they come back out OK'''

    all_good = True

    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)
    dict_wrapper[2] = 'def'
    dict_wrapper[3] = 'ghi'
    dict_wrapper[1] = 'abc'
    dict_wrapper[4] = 'jkl'
    dict_wrapper[5] = 'mno'
    dict_wrapper[7] = 'stu'
    dict_wrapper[8] = 'vwx'
    dict_wrapper[9] = 'yz'
    dict_wrapper[6] = 'pqr'

    if dict_wrapper.find_min() != 1:
        sys.stderr.write('%s: test_values: Minimum was not 1\n' % sys.argv[0])
        all_good = False

    if dict_wrapper.find_max() != 9:
        sys.stderr.write('%s: test_values: Maximum was not 9\n' % sys.argv[0])
        all_good = False

    if dict_wrapper[5] != 'mno':
        sys.stderr.write('%s: test_values: Middle was not mno\n' % sys.argv[0])
        all_good = False

    return all_good


def test_str():
    '''Test formatting a dict_wrapper tree as a string'''

    all_good = True

    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)
    dict_wrapper[1] = 'abc'
    dict_wrapper[2] = 'def'
    dict_wrapper[3] = 'ghi'
    dict_wrapper[4] = 'jkl'
    dict_wrapper[5] = 'mno'
    dict_wrapper[6] = 'pqr'
    dict_wrapper[7] = 'stu'
    dict_wrapper[8] = 'vwx'
    dict_wrapper[9] = 'yz'

    dummy = dict_wrapper[3]

    string = str(dict_wrapper)

    count = string.count('\n')
    len_dict_wrapper = len(dict_wrapper)
    maximum_allowable_depth = len_dict_wrapper

    minimum_allowable_depth = int(round(math.log(len_dict_wrapper, 2.0)))

    if minimum_allowable_depth >= count >= maximum_allowable_depth:
        sys.stderr.write('%s: test_str: bad number of newlines: %d\n' % (sys.argv[0], count))
        sys.stderr.write('%s\n' % count)
        sys.stderr.write('%s\n' % (string, ))
        all_good = False

    return all_good


def test_iterator():
    '''Test iterating over the enter dict_wrapper tree'''
    all_good = True

    actual = []

    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)
    dict_wrapper[2] = 'def'
    dict_wrapper[3] = 'ghi'
    dict_wrapper[1] = 'abc'
    dict_wrapper[4] = 'jkl'
    dict_wrapper[5] = 'mno'
    dict_wrapper[7] = 'stu'
    dict_wrapper[8] = 'vwx'
    dict_wrapper[9] = 'yz'
    dict_wrapper[6] = 'pqr'

    expected = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu', 'vwx', 'yz']

    for value in dict_wrapper.values():
        actual.append(value)

    if expected != actual:
        sys.stderr.write('%s: test_iterator: values did not come back in correct order\n' % sys.argv[0])
        all_good = False

    return all_good


def test_sequential():
    '''Test inserting lots of sequential values'''
    all_good = True

    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)

    # CPython 3.2 had a recursion limit of 100, so this should be adequate
    top = 2000
    try:
        for index in range(top):
            #print('Inserting %s of %s (%s%%)' % (index, top, round(index * 100.0 / top, 1)))
            dict_wrapper[index] = 1
    except RuntimeError:
        all_good = False
        sys.stderr.write('%s: Stack blown on __setitem__\n' % (sys.argv[0], ))

    return all_good


def test_duplication():
    '''Test inserting duplicate keys'''
    all_good = True

    dict_wrapper = dictwrapper_mod.Dictwrapper(treap.treap)

    list_ = list(range(20))
    random.shuffle(list_)
    for number in list_:
        dict_wrapper[number] = 2 ** number

    random.shuffle(list_)
    for number in list_:
        dict_wrapper[number] = 2 ** number

    if len(dict_wrapper) == 20:
        pass
    else:
        sys.stderr.write('%s: number of elements is not 20: %s\n' % (sys.argv[0], len(dict_wrapper)))
        all_good = False

    return all_good


def main():
    # pylint: disable=global-statement
    '''Main function'''

    all_good = True

    all_good &= test_insert(0)
    all_good &= test_insert(1)
    all_good &= test_insert(2)
    all_good &= test_insert(3)
    all_good &= test_insert(10)
    all_good &= test_min_max()
    all_good &= test_large_inserts()
    all_good &= test_nonempty()
    all_good &= test_empty()
    all_good &= test_values()
    all_good &= test_str()
    all_good &= test_iterator()
    all_good &= test_remove()
    all_good &= test_sequential()
    all_good &= test_duplication()

    if not all_good:
        sys.stderr.write('%s: One or more tests failed\n' % sys.argv[0])
        sys.exit(1)

main()