"""An implementation of a fibonacci heap."""
from __future__ import annotations
from math import log2, ceil

import exceptions

class FibonacciNode():
    """A node for the fibonacci heap."""
    def __init__(self, element, value):
        self.element = element
        self.value = value
        self.children = []
        self.size = 1

    def __len__(self):
        return self.size

    def __lt__(self, other: FibonacciNode):
        return self.value < other.value

    @property
    def degree(self):
        """Return the degree (number of children) of the node."""
        return len(self.children)

    def add_child(self, child: FibonacciNode):
        """Adds a child to the node."""
        self.children.append(child)
        self.size += child.size

class FibonacciHeap():
    """The fibonacci heap."""
    def __init__(self, element, value: int):
        new_node = FibonacciNode(element, value)
        self.roots = [new_node]
        self.min = new_node
        self.size = 1

    def __len__(self):
        return self.size

    def merge(self, other: FibonacciHeap):
        """Merge two fibonacci heaps."""
        self.roots += other.roots
        self.size += other.size
        if self.min is None or other.min < self.min:
            self.min = other.min

    def insert(self, element, value: int):
        """Insert an element into the heap."""
        self.merge(FibonacciHeap(element, value))

    def extract_min(self):
        """Extract the element with the smallest value."""
        if self.min is None:
            raise exceptions.HeapEmpty()
        element = self.min.element
        value = self.min.value
        self.roots += self.min.children
        self.roots.remove(self.min)
        self.size -= 1
        if self.roots == []:
            self.min = None
        else:
            self._rearrange()
            self.min = min(self.roots)

        return element, value

    def _rearrange(self):
        heap_size = len(self)
        required_roots = (0 if heap_size == 0 else
                          1 if heap_size == 1 else
                          ceil(log2(heap_size)))

        while len(self.roots) > required_roots:
            degree_array = [None for _ in range(required_roots)]
            for root in self.roots:
                root_degree = root.degree
                if degree_array[root_degree] is None:
                    degree_array[root_degree] = root
                else:
                    if degree_array[root_degree] < root:
                        degree_array[root_degree].add_child(root)
                        self.roots.remove(root)
                    else:
                        root.add_child(degree_array[root_degree])
                        self.roots.remove(degree_array[root_degree])

                    break