#!/usr/bin/python3

from shutil import rmtree, copy
from os import mkdir, chdir, listdir, remove, rename
from os.path import isdir

import subprocess
import sys
import random

seed = "YOU'RE MY HEART, YOU'RE MY SOUL " + ' '.join(sys.argv[1:])
rnd = random.Random(seed)

test_num = 1

vx = [1, 0, -1, 0]
vy = [0, 1, 0, -1]

class Test:
    
    # A is set of all original and added cells, n is the number
    # of cells that will be original among them
    def __init__(self, w, h, n, A):
        global test_num
        print("Creating test", test_num)
        
        self.w = w
        self.h = h
        self.n = n
        self.U = []
        self.cells = set()
        self.mxr = -1
        self.mnr = self.h + 1
        self.mxc = -1
        self.mnc = self.w + 1
        self.row_mx = [0] * (self.h + 2)
        self.row_mn = [self.w + 1] * (self.h + 2)
        self.col_mx = [0] * (self.w + 2)
        self.col_mn = [self.h + 1] * (self.w + 2)
        self.A = []
        for r, c in A:
            self.add_cell((r, c))
   
    def add_cell(self, cell):
        r, c = cell
        self.mxr = max(self.mxr, r)
        self.mnr = min(self.mnr, r)
        self.mxc = max(self.mxc, c)
        self.mnc = min(self.mnc, c)
        self.row_mx[r] = max(self.row_mx[r], c)
        self.row_mn[r] = min(self.row_mn[r], c)
        self.col_mx[c] = max(self.col_mx[c], r)
        self.col_mn[c] = min(self.col_mn[c], r)
        self.A.append((r, c))
        self.cells.add((r, c))
        for v in range(4):
            nr = r + vy[v]
            nc = c + vx[v]
            if nr >= 1 and nr <= self.h and nc >= 1 and nc <= self.w and not (nr, nc) in self.cells:
                self.U.append((nr, nc))

    def add_conv(self):
        r, c = -1, -1
        while r == -1 and c == -1:
            assert len(self.U) != 0
            q = rnd.randint(0, len(self.U) - 1)
            if not self.U[q] in self.cells:
                r, c = self.U[q]

            if not ((r > self.mxr or r < self.mnr or self.row_mx[r] + 1 == c or self.row_mn[r] - 1 == c) and 
                    (c > self.mxc or c < self.mnc or self.col_mx[c] + 1 == r or self.col_mn[c] - 1 == r)):
                r = -1
                c = -1
                continue

            self.U[q], self.U[-1] = self.U[-1], self.U[q]
            self.U.pop()
        
        assert r != -1 and c != -1
        self.add_cell((r, c))

    def add_random(self): 
        r, c = -1, -1
        while r == -1 and c == -1:
            assert len(self.U) != 0
            q = rnd.randint(0, len(self.U) - 1)
            if not self.U[q] in self.cells:
                r, c = self.U[q]

            self.U[q], self.U[-1] = self.U[-1], self.U[q]
            self.U.pop()
        
        assert r != -1 and c != -1
        self.add_cell((r, c))
        
    def fix(self):
        for i in range(len(self.U)):
            r, c = self.U[i]
            if (r, c) in self.cells:
                continue
            if not (self.row_mn[r] <= c and c <= self.row_mx[r]) and not (self.col_mn[c] <= r and r <= self.col_mx[c]):
                continue
            self.add_cell((r, c))
            
    def debug(self):
        S = [[0] * (self.mxc - self.mnc + 1) for i in range(self.mnr, self.mxr + 1)]
        for r, c in self.cells:
            S[r - self.mnr][c - self.mnc] = 1
        for s in S:
            print(''.join(".#"[x] for x in s))
        print('')
               
    def write(self):
        global test_num
        assert self.n <= len(self.A)
        file_name = "../tests/%02d" % (test_num,)
        print("Writing test " + file_name + '.')
        with open(file_name, 'w') as test:
            print(self.h, self.w, file=test)
            print(self.n, file=test)
            for r, c in self.A[:self.n]:
                print(r, c, file=test)
            print(len(self.A) - self.n, file=test)
            for r, c in self.A[self.n:]:
                print(r, c, file=test)

        test_num += 1

# random set of n non-negative integers of sum s
def random_set_nonneg(s, n):
    Q = sorted([0, s] + [rnd.randint(0, s) for i in range(n - 1)])
    return [Q[i + 1] - Q[i] for i in range(n)]

# random set of n positive integers of sum s
def random_set_pos(s, n):
    assert s >= n
    return [x + 1 for x in random_set_nonneg(s - n, n)]

def gen_longline(a, b, c, d, e):
    w = 100000
    h = 100000
    sx = w // 2
    sy = h // 2
    tx = w // 2
    ty = h // 2
    n = max(1, a + b + c + d + e + 2 - 100000)
    test = Test(w, h, n, [(sx, sy)])
    for i in range(c):
        if (rnd.randint(0, 1) == 1):
            if (rnd.randint(0, 1) == 1):
                sx -= 1
            else:
                sy -= 1
            test.add_cell((sy, sx))
        else:
            if (rnd.randint(0, 1) == 1):
                tx += 1
            else:
                ty += 1
            test.add_cell((ty, tx))

    for i in range(a):
        if (sy - i - 1 > 0):
            test.add_cell((sy - i - 1, sx))
    for i in range(b):
        if (sx - i - 1 > 0):
            test.add_cell((sy, sx - i - 1))
    for i in range(d):
        if (ty + i + 1 <= h):
            test.add_cell((ty + i + 1, tx))
    for i in range(e):
        if (tx + i + 1 <= w):
            test.add_cell((ty, tx + i + 1))
    test.add_random()
    return test
    

def gen_random(w, h, n, total):
    test = Test(w, h, n, [(rnd.randint(1, h), rnd.randint(1, w))])
    for i in range(total - 1):
        if i > 0 and i % 10000 == 0:
            print("i =", i, "(from " + str(total) + " )")
        test.add_random()
    return test

def gen_only_yes(w, h, n, total):
    test = Test(w, h, n, [(rnd.randint(1, h), rnd.randint(1, w))])
    for i in range(total - 1):
        if i > 0 and i % 10000 == 0:
            print("i =", i, "(from " + str(total) + " )")
        test.add_conv()
    return test

# add random cell, add conv or fix everything with
# specific probabilities
def gen_cool_test(w, h, n, total, a, b, c):
    test = Test(w, h, n, [(rnd.randint(1, h), rnd.randint(1, w))])
    while len(test.A) < total:
        q = rnd.randint(0, 10000) / 10000
        if len(test.A) % 10000 == 0:
            print("i =", len(test.A), "(from " + str(total) + " )")
        if q < a:
            test.add_random()
        elif q < a + b:
            test.add_conv()
        else:
            test.fix()
    test.A = test.A[:total]
    return test

def gen_alternating():
    test = Test(3, 100000, 100000, [(i, 1) for i in range(1, 100001)])
    cur = 1
    while len(test.A) + 6 <= 200000:
        test.add_cell((cur, 2))
        test.add_cell((cur, 3))
        test.add_cell((cur + 1, 3))
        test.add_cell((cur + 2, 3))
        test.add_cell((cur + 2, 2))
        test.add_cell((cur + 1, 2))
        cur += 3
    return test

def gen_alternating2():
    test = Test(100000, 2, 100000, [(1, i) for i in range(1, 100001)])
    for i in range(2, 100001, 2):
        test.add_cell((2, i))
        test.add_cell((2, i - 1))
    return test

def gen_square():
    S = []
    for i in range(1, 300):
        S.append((i, 1))
        S.append((300, i))
        S.append((301 - i, 300))
        S.append((1, 301 - i))

    test = Test(300, 300, 4 * 299, S)
    for i in range(90000 - 4 * 299):
        test.add_random()
    return test

def gen_antikun():
    n = 100000
    s = 2**16
    w = s
    h = s
    test = Test(w, h, n, [])
    for i in range(1, s + 1):
        test.add_cell((1, i))
    for i in range(2, s + 1):
        test.add_cell((i, s))
    for i in range(s - 1, 0, -1):
        test.add_cell((s, i))
    test.add_cell((s - 1, s - 9))
    for i in range(2, 5):
        test.add_cell((i, 1))
    return test

def generate_tests():
    if isdir('../tests'):
        rmtree('../tests')
    mkdir('../tests')
    
    # ====== SAMPLES =================================
    Test(
        10, 5, 8,
        [
            (1, 4),
            (2, 4),
            (2, 5),
            (2, 6),
            (1, 6),
            (3, 5),
            (3, 4),
            (4, 4),
            (1, 5),
            (2, 7),
            (3, 7),
            (3, 6)
        ]).write()

    Test(
        3, 3, 5,
        [
            (1, 1),
            (1, 2),
            (1, 3),
            (2, 3),
            (3, 3),
            (2, 1),
            (3, 2),
            (3, 1),
            (2, 2)
        ]).write()

    # ====== TESTS ============================ 

    # several small random tests
    gen_random(10, 10, 1, 10).write()
    gen_random(10, 10, 3, 10).write()
    gen_random(20, 20, 5, 40).write()
    gen_random(20, 20, 10, 100).write()
    
    # w, h corner cases
    gen_random(1, 1, 1, 1).write()
    gen_random(1, 100000, 42, 4242).write()
    gen_random(100000, 1, 42, 4242).write()
    gen_random(100000, 100000, 1, 1).write()
    
    # large only-yes tests
    gen_only_yes(990, 1110, 100, 3000).write()
    gen_only_yes(99990, 100000, 100000, 200000).write()

    # large random tests
    gen_random(990, 942, 1000, 2000).write()
    gen_random(99990, 99492, 100000, 200000).write()
    
    # two tests filling the whole square
    # most no
    gen_random(300, 300, 1, 90000).write()
    # all yes
    gen_only_yes(300, 300, 1, 90000).write()

    # tests with interesting different output
    gen_cool_test(980, 942, 20, 100, 0.4, 0.4, 0.2).write()
    gen_cool_test(2020, 3032, 1000, 10000, 0.49, 0.49, 0.02).write()
    gen_cool_test(2020, 3032, 1000, 10000, 0.3, 0.3, 0.4).write()
    gen_cool_test(100000, 100000, 10000, 100000, 0.49, 0.49, 0.02).write()
    gen_cool_test(100000, 100000, 10000, 100000, 0.45, 0.45, 0.1).write()

    # vertical test of fixed structure with YYYNNNYYYNNN... answer alternation
    gen_alternating().write()
    # horizontal test of fixed structure with YYNYNYNYN... answer alternation
    gen_alternating2().write()

    # square boundary filled till the end
    gen_square().write()

    # long line
    gen_longline(0, 0, 180000, 0, 0).write()
    gen_longline(40000, 40000, 39900, 40000, 40000).write()
    gen_longline(49999, 49999, 1, 49999, 49999).write()
    # long line with n = 1
    gen_longline(0, 0, 100000, 0, 0).write()
    gen_longline(20000, 20000, 19900, 20000, 20000).write()
    gen_longline(24999, 24999, 1, 24999, 24999).write()

    # anti-kunyavsky
    gen_antikun().write()


if __name__ == "__main__":
    generate_tests()
