# LInkedList (Node = List = {'name': 'Имя', 'phone': '123', 'next': None}) имена уникальные (id)


def ll_insert(head, name, phone):

    """ проходит до конца (или сразу добавляет в конец) и возвращает новую голову
      (если вставка в начало) или изменяет список по ссылке. Удобнее возвращать новую
        голову, если вставка может быть в начало """
    
    new_node = {'name': name, 'phone': phone, 'next': None}

    # если списка не было
    if head is None:
        return new_node
    
    # # вставка в начало O(1)
    # new_node = {'name': name, 'phone': phone, 'next': head}
    # return new_node

    # вставка в конец O(n)
    current = head
    while current['next'] is not None:
        # проверка существования данного идентификатора (обновляем запись)
        if current['name'] == name:
            current['phone'] = phone
            return head
        current = current['next']
    
    # проверка на id
    if current['name'] == name:
        current['phone'] = phone
    else:   current['next'] = new_node
    return head


def ll_find(head, name):

    """  ищет узел, возвращает телефон или None """

    current = head
    while current is not None:
        if current['name'] == name:
            return current['phone']
        current = current['next']
    
    return None
    

def ll_delete(head, name):
    
    """  удаляет узел, возвращает новую голову """

    if head is None:
        return None

    # Удаление первого 
    if head['name'] == name:
        new_head = head['next']
        head['next'] = None 
        return new_head

    # Если не первый
    current = head
    while current['next'] is not None:
        if current['next']['name'] == name:
            target = current['next']
            current['next'] = target['next']
            target['next'] = None
            return head
        current = current['next']
    
    return head
    

def ll_list_all(head):
    
    """ собирает все записи в список и сортирует (сортировка вынесена отдельно) """

    length = ll_Lenght(head)
    new_list = [None]*length
    current = head
    for i in range(length):
        new_list[i] = (current['name'], current['phone'])
        current = current['next']
    sorten(new_list)
    return new_list
        

# вспомогательные функции--------------------------------
def ll_Lenght(head):
    # длина связного списка
    counter = 0
    curr = head
    while curr:
        counter += 1
        curr = curr['next']
    return counter


def sorten(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j][0] > arr[j + 1][0]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
# -----------------------------------------------------------

# HashTable (Хранится как список buckets фиксированной длины, каждый элемент — голова связного списка (или None))

def hash_table(size):
    return [None]*size


def hash_func(name, buckets_count):
    h = 0
    for char in name:
        h += ord(char)
    return h % buckets_count


def ht_insert(buckets, name, phone):

    """ вычисляет индекс, вызывает ll_insert для соответствующего бакета """

    if buckets is None:
        return 

    index = hash_func(name, len(buckets))
    buckets[index] = ll_insert(buckets[index], name, phone)


def ht_find(buckets, name):
    """  """
    idx = hash_func(name, len(buckets))
    return ll_find(buckets[idx], name)


def ht_delete(buckets, name):
    idx = hash_func(name, len(buckets))
    buckets[idx] = ll_delete(buckets[idx], name)


def ht_list_all(buckets):

    """ собирает все записи из всех бакетов и сортирует """
    total_count = 0
    for head in buckets:
        total_count += ll_Lenght(head)

    full_data = [None]*total_count

    k = 0
    for head in buckets:
        curr = head
        while curr:
            full_data[k] = (curr['name'], curr['phone'])
            k += 1
            curr = curr['next']
        
    sorten(full_data)
    return full_data


# Двоичное дерево поиска : Узел — словарь: {'name': 'Имя', 'phone': '123', 'left': None, 'right': None}

def bst_insert(root, name, phone):

    """ рекурсивно или итеративно вставляет, возвращает новый корень (если корень меняется) """

    new_node = {'name': name, 'phone': phone, 'left': None, 'right': None}

    # если дерева нет
    if root is None:
        return new_node
    
    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 root['name'] == name:
        return root['phone']

    elif name < root['name']:
        return bst_find(root['left'], name)

    elif name > root['name']:
        return bst_find(root['right'], name)


def bst_delete(root, name):

    """ удаление, возвращает новый корень """

    if root is None:
        return None
    
    # спускаемся к нужному узлу (аналогично поиску)
    elif name < root['name']:
        root['left'] = bst_delete(root['left'], name)

    elif name > root['name']:
        root['right'] = bst_delete(root['right'], name)

    # стоим в нужном узле
    else:
        # узла слева нет (вернет правого ребенка или None)
        if root['left'] is None:
            return root['right']
            
        # узла справа нет (вернет левого ребенка)
        if root['right'] is None:
            return root['left']
        
        # два наследника (поиск минимального поддерева в правой ветке)

        successor = root['right']
        while successor['left'] is not None:
            successor = successor['left']

        root['name'] = successor['name']
        root['phone'] = successor['phone']
        # Удаляем дубликат преемника в правом поддереве
        root['right'] = bst_delete(root['right'], successor['name'])

        
    return root
    

def bst_list_all(root, result=None): 
    """ центрированный обход (рекурсивно собирает записи в отсортированном порядке) """
    if result is None:
        result = []
    # сначала спускаемся по левой стороне вниз, затем идем вверх и вправо 
    if root is not None:
        bst_list_all(root['left'], result)
        result.append((root['name'], root['phone']))
        bst_list_all(root['right'], result)
    return result
