import random
random.seed("something")

class TestGen:
    def __init__(self):
        self.test_number = 0

    def generate_samples(self):
        self.print_test(2, [1, 0], [(1, 2)])
        self.print_test(5, [5, 1, 3, 0, 1], [(1, 2), (1, 3), (3, 4), (3, 5)])    

    def generate_min_tests(self):
        self.print_test(1, [2], [])
        self.print_test(1, [0], [])
        self.print_test(1, [1], [])
        self.print_test(1, [5000], [])
        self.print_test(2, [0, 0], [(1, 2)])
        self.print_test(2, [0, 1], [(1, 2)])
        self.print_test(2, [0, 1], [(2, 1)])
        self.print_test(2, [1, 1], [(2, 1)])
        self.print_test(2, [3, 1], [(2, 1)])
        self.print_test(3, [1, 0, 5], [(1, 3), (3, 2)])
        self.print_test(3, [1, 0, 0], [(1, 3), (3, 2)])
        self.print_test(3, [0, 0, 0], [(1, 3), (3, 2)])
        self.print_test(3, [2, 3, 5], [(1, 3), (3, 2)])
        self.print_test(3, [2, 3, 10], [(1, 3), (3, 2)])
        self.print_test(3, [2, 3, 5000], [(1, 3), (3, 2)])
        self.print_test(3, [2, 3, 0], [(1, 3), (3, 2)])
        self.print_test(3, [2500, 5000, 2500], [(1, 2), (2, 3)])
        self.print_test(3, [5000, 5000, 5000], [(1, 2), (2, 3)])
                                                                    
    def generate_hand_tests(self):
        pass

    def generate_random_test(self, maxn, maxvalue):
        n = maxn
        cnt = [0 for i in range(n)]
        for i in range(n):
            if (random.randint(1, 2) == 1):
                cnt[i] = random.randint(0, n)
            else:
                cnt[i] = random.randint(0, maxvalue)
        p = [0 for i in range(n)]
        deg = [0 for i in range(n)]
        for i in range(1, n):
            p[i] = random.randint(0, i - 1)
            while (deg[p[i]] >= 2):
                p[i] = random.randint(0, i - 1)
            deg[p[i]] += 1
        edges = []
        for i in range(1, n):
            if (random.randint(1, 2) == 1):
                edges.append((i + 1, p[i] + 1))
            else:
                edges.append((p[i] + 1, i + 1))
        random.shuffle(edges)
        self.print_test(n, cnt, edges)

    def generate_bamboo(self, maxn, maxvalue):
        n = maxn
        cnt = [0 for i in range(maxn)]
        for i in range(n):
            if (random.randint(1, 2) == 1):
                cnt[i] = random.randint(0, n)
            else:
                cnt[i] = random.randint(0, maxvalue)
        p = [0 for i in range(n - 1)]
        for i in range(n - 1):
            p[i] = i + 2
        random.shuffle(p)
        edges = []
        last = 1
        for i in range(n - 1):
            if (random.randint(1, 2) == 1):
                edges.append((p[i], last))
            else:
                edges.append((last, p[i]))
            last = p[i]
        random.shuffle(edges)
        return [n, cnt, edges]

    def addTree(self, bamboo, startn, maxvalue, v, vs):
        bamboo[0] += vs
        for i in range(vs):
            if (random.randint(1, 2) == 1):
                bamboo[1].append(random.randint(0, bamboo[0]))
            else:                                    
                bamboo[1].append(random.randint(0, maxvalue))
        p = [0 for i in range(vs)]
        deg = [0 for i in range(vs)]
        for i in range(1, vs):
            p[i] = random.randint(0, i - 1)
            while (deg[p[i]] >= 2):
                p[i] = random.randint(0, i - 1)
            deg[p[i]] += 1

        for i in range(1, vs):
            if (random.randint(1, 2) == 1):
                bamboo[2].append((startn + i + 1, startn + p[i] + 1))
            else:
                bamboo[2].append((startn + p[i] + 1, startn + i + 1))
        bamboo[2].append((startn + 1, v))
        #random.shuffle(bamboo[2])

    def generate_bamboo_with_trash(self, maxn, trash, maxvalue):
        bamboo = self.generate_bamboo(maxn, maxvalue)
        startn = maxn
        was = [False for i in range(maxn)]
        while trash > 0:
            vertexNum = random.randint(1, maxn)
            while (was[vertexNum]):
                vertexNum = random.randint(1, maxn)
            was[vertexNum] = True
            vertexCnt = random.randint(1, trash)
            self.addTree(bamboo, startn, maxvalue, vertexNum, vertexCnt)
            trash -= vertexCnt
            startn += vertexCnt
        self.print_test(bamboo[0], bamboo[1], bamboo[2])

    def generate_max_tests(self, maxn, maxvalue):
        x = self.generate_bamboo(maxn, maxvalue)
        self.print_test(x[0], x[1], x[2])

        trash = random.randint(1, 100)
        self.generate_bamboo_with_trash(maxn - trash, trash, maxvalue)

    def print_test(self, n, cnt, edges):
        self.test_number += 1
        test_name = "../tests/" + "{0:0=2d}".format(self.test_number)
        test_file = open(test_name, "w")
        print(n, file=test_file)
        scnt = ""
        for i in range(len(cnt) - 1):
            scnt += str(cnt[i]) + " "
        scnt += str(cnt[-1])
        if (n > 1):
            print(scnt, file=test_file)
            for i in range(len(edges)):
                sedges = str(edges[i][0]) + " " + str(edges[i][1])
                if i < len(edges) - 1:
                    print(sedges, file=test_file)
                else:
                    print(sedges, end="", file=test_file)
            print("", file=test_file)
        else:
            print(scnt, end="", file=test_file)
            print("", file=test_file)
        test_file.close()

    def generate_all_tests(self):
        verysmalln = 10
        smalln = 30
        midn = 500
        maxn = 5000
        maxvalue = 5000

        self.generate_samples()                            #2 tests
        self.generate_min_tests()                          #18 tests
        self.generate_hand_tests()                         #0 tests

        for i in range(10):                                #10 tests
            self.generate_random_test(verysmalln, verysmalln)
        for i in range(10):                                #10 tests
            self.generate_random_test(smalln, smalln)
        for i in range(10):                                #10 tests
            self.generate_random_test(midn, midn)
        for i in range(10):                                #10 tests
            self.generate_random_test(maxn, maxvalue)
        for i in range(10):                                #20 tests
            self.generate_max_tests(maxn, maxvalue)

import os, shutil
if os.path.exists('../tests'):
    print('Directory tests is already exists')
    shutil.rmtree('../tests', ignore_errors=False, onerror=None)
try:
    os.makedirs('../tests')
except OSError:
    pass

import time
start = time.time()
writer = TestGen()
writer.generate_all_tests()
finish = time.time()
print('All tests were generated. Elapsed time: ', finish - start)