import random
import time
import csv
import sys


sys.setrecursionlimit(20000)


# 1. СВЯЗНЫЙ СПИСОК
def ll_insert(head, name, phone):
    curr = head
    while curr:
        if curr['name'] == name:
            curr['phone'] = phone
            return head
        curr = curr['next']

    new_node = {'name': name, 'phone': phone, 'next': None}
    if head is None:
        return new_node

    curr = head
    while curr['next']:
        curr = curr['next']
    curr['next'] = new_node
    return head


def ll_find(head, name):
    curr = head
    while curr:
        if curr['name'] == name:
            return curr['phone']
        curr = curr['next']
    return None


def ll_delete(head, name):
    if head is None:
        return None
    if head['name'] == name:
        return head['next']

    curr = head
    while curr['next']:
        if curr['next']['name'] == name:
            curr['next'] = curr['next']['next']
            return head
        curr = curr['next']
    return head


def ll_list_all(head):
    res = []
    curr = head
    while curr:
        res.append((curr['name'], curr['phone']))
        curr = curr['next']
    res.sort(key=lambda x: x[0])
    return res



# 2. ХЕШ-ТАБЛИЦА
BUCKET_COUNT = 1024


def ht_insert(buckets, name, phone):
    idx = hash(name) % BUCKET_COUNT
    buckets[idx] = ll_insert(buckets[idx], name, phone)


def ht_find(buckets, name):
    idx = hash(name) % BUCKET_COUNT
    return ll_find(buckets[idx], name)


def ht_delete(buckets, name):
    idx = hash(name) % BUCKET_COUNT
    buckets[idx] = ll_delete(buckets[idx], name)


def ht_list_all(buckets):
    res = []
    for head in buckets:
        curr = head
        while curr:
            res.append((curr['name'], curr['phone']))
            curr = curr['next']
    res.sort(key=lambda x: x[0])
    return res



def bst_insert(root, name, phone):
    if root is None:
        return {'name': name, 'phone': phone, 'left': None, 'right': None}
    if name < root['name']:
        root['left'] = bst_insert(root['left'], name, phone)
    elif name > root['name']:
        root['right'] = bst_insert(root['right'], name, phone)
    else:
        root['phone'] = phone
    return root


def bst_find(root, name):
    if root is None:
        return None
    if name == root['name']:
        return root['phone']
    elif name < root['name']:
        return bst_find(root['left'], name)
    else:
        return bst_find(root['right'], name)


def _bst_find_min(node):
    curr = node
    while curr['left'] is not None:
        curr = curr['left']
    return curr


def bst_delete(root, name):
    if root is None:
        return None
    if name < root['name']:
        root['left'] = bst_delete(root['left'], name)
    elif name > root['name']:
        root['right'] = bst_delete(root['right'], name)
    else:
        if root['left'] is None:
            return root['right']
        elif root['right'] is None:
            return root['left']
        else:
            successor = _bst_find_min(root['right'])
            root['name'] = successor['name']
            root['phone'] = successor['phone']
            root['right'] = bst_delete(root['right'], successor['name'])
    return root


def bst_list_all(root):
    res = []

    def inorder(node):
        if node:
            inorder(node['left'])
            res.append((node['name'], node['phone']))
            inorder(node['right'])

    inorder(root)
    return res



# ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ
def run_experiments():
    N = 10000
    base_records = [(f"User_{i:05d}", f"100{i:05d}") for i in range(N)]

    records_sorted = sorted(base_records, key=lambda x: x[0])
    records_shuffled = base_records[:]
    random.shuffle(records_shuffled)

    all_names = [r[0] for r in base_records]
    find_existing = random.sample(all_names, 100)
    find_non_existing = [f"Missing_{i}" for i in range(10)]
    delete_targets = random.sample(all_names, 50)

    all_results = []
    structures = ["LinkedList", "HashTable", "BST"]
    data_modes = [("случайный", records_shuffled), ("отсортированный", records_sorted)]

    for mode_name, records in data_modes:
        print(f"\n Режим: {mode_name}")
        for run in range(1, 6):
            print(f" запуск {run}/5")


            head = None
            t = time.perf_counter()
            for n, p in records: head = ll_insert(head, n, p)
            t_ins = time.perf_counter() - t

            t = time.perf_counter()
            for n in find_existing + find_non_existing: ll_find(head, n)
            t_find = time.perf_counter() - t

            t = time.perf_counter()
            for n in delete_targets: head = ll_delete(head, n)
            t_del = time.perf_counter() - t

            all_results.append(["LinkedList", mode_name, "insert", t_ins])
            all_results.append(["LinkedList", mode_name, "find", t_find])
            all_results.append(["LinkedList", mode_name, "delete", t_del])


            buckets = [None] * BUCKET_COUNT
            t = time.perf_counter()
            for n, p in records: ht_insert(buckets, n, p)
            t_ins = time.perf_counter() - t

            t = time.perf_counter()
            for n in find_existing + find_non_existing: ht_find(buckets, n)
            t_find = time.perf_counter() - t

            t = time.perf_counter()
            for n in delete_targets: ht_delete(buckets, n)
            t_del = time.perf_counter() - t

            all_results.append(["HashTable", mode_name, "insert", t_ins])
            all_results.append(["HashTable", mode_name, "find", t_find])
            all_results.append(["HashTable", mode_name, "delete", t_del])


            root = None
            t = time.perf_counter()
            for n, p in records: root = bst_insert(root, n, p)
            t_ins = time.perf_counter() - t

            t = time.perf_counter()
            for n in find_existing + find_non_existing: bst_find(root, n)
            t_find = time.perf_counter() - t

            t = time.perf_counter()
            for n in delete_targets: root = bst_delete(root, n)
            t_del = time.perf_counter() - t

            all_results.append(["BST", mode_name, "insert", t_ins])
            all_results.append(["BST", mode_name, "find", t_find])
            all_results.append(["BST", mode_name, "delete", t_del])


    averages = []
    for struct in structures:
        for mode in ["случайный", "отсортированный"]:
            for op in ["insert", "find", "delete"]:
                times = [r[3] for r in all_results if r[0] == struct and r[1] == mode and r[2] == op]
                avg = sum(times) / len(times)
                averages.append([struct, mode, f"{op} (СРЕДНЕЕ)", avg])

    final_csv_data = [["Структура", "Режим", "Операция", "Время (сек)"]] + all_results + averages

    with open("results.csv", "w", newline="", encoding="utf-8-sig") as f:
        writer = csv.writer(f)
        writer.writerows(final_csv_data)

    return all_results, averages


if __name__ == "__main__":
    raw_data, avg_data = run_experiments()

