"""Module containing some methods for finding the largest k
items in a list.
"""
from basic_priority_queue import BasicPriorityQueue
# import the following when you are ready to use it
from dheap_priority_queue import DheapPriorityQueue



def top_k_select(items, k):
    """Uses a modified max-selection sort to find the max k items of a list.
    This sort terminates once the max k values are found. Note that
    this function does not modify the list items.
        This function returns a tuple containing the following:
       1: a descending list of the top k items, and
       2: the number of item comparisons made
    That is, it returns result_list, comparisons
    """
    items = list(items)  # Makes a copy of items.
    comparisons = 0
    # ---start student section---

    out_list = []
    i = 0
    while i != k:
        holder = 0
        for index in range(0,len(items) - 1):
            comparisons += 1
            if items[index] > items[holder]:
                holder = index
        out_list.append(items[holder])
        items.pop(holder)
        i += 1
    out_tup = (out_list, comparisons)
    return out_tup
    # ===end student section===


def top_k_heap(items, k):
    """Uses a BasicPriorityQueue to find the max k items of a list. Note this
    function does not modify the list items.
    This function returns a tuple containing the following:
       1: a descending list of the top k items, and
       2: the number of item comparisons made, ie, it returns result_list, comparisons
    That is, it returns result_list, comparisons
    """
    comparisons = 0
    items = list(items)  # Makes a copy of items.
    p_queue = BasicPriorityQueue(items)
    out_list = []
    # ---start student section---
    for i in range(0, k):
        out_list.append(p_queue.pop_max())
    out_tup = (out_list, p_queue.get_comparisons())
    return out_tup
    # ===end student section===


def top_k_dheap(items, k, branch_factor):
    """Uses a DheapPriorityQueue to find the max k items of a list. Note this
    function does not modify the list items.
    This function returns a tuple containing the following:
       1: a descending list of the top k items, and
       2: the number of item comparisons made, ie, it returns result_list, comparisons
    That is, it returns result_list, comparisons

    NOTE: You can complete this function once you have your dheap working.
    """
    # ---start student section---
    pass
    # ===end student section===