#####################################################################################################################################################
######################################################################## INFO #######################################################################
#####################################################################################################################################################

"""
    This file contains a class that implements a min-heap.
    It is made to be used as a library in other files.
"""
#####################################################################################################################################################
###################################################################### IMPORTS ######################################################################
#####################################################################################################################################################

# Imports
from typing import *
from typing_extensions import *
from numbers import *

#####################################################################################################################################################
###################################################################### CLASSES ######################################################################
#####################################################################################################################################################

class ListBasedMinHeap ():

    """
        This class implements a min-heap.
        It is a naive implementation based on a list.
        The heap is a list of tuples (key, value).
        The key is used to identify the elements and the value is used to order them.
    """

    #############################################################################################################################################
    #                                                                CONSTRUCTOR                                                                #
    #############################################################################################################################################

    def __init__ ( self: Self,
                 ) ->    Self:

        """
            This function is the constructor of the class.
            When an object is instantiated, this method is called to initialize the object.
            This is where you should define the attributes of the object and set their initial values.
            In:
                * self: Reference to the current object.
            Out:
                * A new instance of the class.
        """

        # We create an attribute to store the elements
        self.elements = []
       
    #############################################################################################################################################
    #                                                                  METHODS                                                                  #
    #############################################################################################################################################

    def add_or_replace ( self:  Self,
                         key:   Any,
                         value: Number
                       ) ->     None:
        
        """
            This method adds a new element to the heap or replaces an existing one if the new value is lower.
            In:
                * self:  Reference to the current object.
                * key:   Key of the element to add.
                * value: Value of the element to add.
            Out:
                * None.
        """
        
        # We check if the key is already in the heap
        index = None
        for i in range(len(self.elements)):
            if self.elements[i][0] == key:
                index = i
                break
        
        # If the key is already in the heap, we remove the previous element if the new value is lower
        add_new_element = True
        if index is not None:
            if value < self.elements[index][1]:
                del self.elements[index]
            else:
                add_new_element = False

        # We add the new element
        if add_new_element:
            self.elements.append((key, value))

    #############################################################################################################################################

    def remove ( self: Self
               ) ->    Tuple[Any, Number]:

        """
            This method removes the element with the smallest value from the heap.
            It will update the list of elements and return the key and value of the element removed.
            In:
                * self: Reference to the current object.
            Out:
                * key:   Key of the element removed.
                * value: Value of the element removed.
        """

        # We find the element with the smallest value
        min_index = 0
        for i in range(1, len(self.elements)):
            if self.elements[i][1] < self.elements[min_index][1]:
                min_index = i

        # We remove the element with the smallest value
        key, value = self.elements[min_index]
        del self.elements[min_index]

        # We return the key and value of the element removed
        return key, value

#####################################################################################################################################################
#####################################################################################################################################################