store_location

import time
import csv
import random

def sumDistance(lst, median):
    """
    Find the total distance from each building to the optimal store location
    :param lst: Given list
    :param median: Calculated median of give list
    :return: sum of distances
    """
    total = 0

    for location in range(0, len(lst) - 1):
        total += abs(median - lst[location])

    return total


def getList(filename):
    with open(filename) as csvfile:
        distances = []
        readCSV = csv.reader(csvfile, delimiter=' ')
        for line in readCSV:
            dist = line[1]
            distances.append(int(dist))

        return distances


def testComp():
    testCase(getList("large.csv"), "largeDataset")
    testCase(getList("even.csv"), "evenDataset")
    testCase(getList("odd.csv"), "oddDataset")


def testCase(lst, name):
    start = time.time()
    sumDistance(lst, quickSelect(lst, quickSelectHelper(lst)))
    end = time.time()
    print("Test case", name, ", elapsed time: ", end - start, " seconds")


def quickSelectHelper(L):
    """
    Find the index of the correct median depending on the length of the list (odd or even)
    :param L: Given list
    :return: the Median the needs to be translated (k'th element)
    """
    if len(L) % 2 == 0 and len(L) >= 2:
        idx1 = int((0.5 * len(L)) - 1)
        idx2 = (len(L) // 2)
        calculatedMedian = (L[idx1] + L[idx2]) // 2
    elif len(L) % 2 != 0 and len(L) >= 1:
        calculatedMedian = (0.5 * len(L)) - 0.5

    return calculatedMedian


def quickSelect(aList, k):
    """
    Sort the list until the k'th element is found
    :param aList: given list
    :param k: the element to find (k'th)
    :return: The median value of the given list
    """
    # print("qS at it again: ", aList, "with a length of: ", len(aList))
    if len(aList) != 0:
        pivot = aList[len(aList) // 2]
        smallerList = []
        largerList = []
        count = 0

        for dist in range(len(aList)):
            if aList[dist] > pivot:
                largerList.append(aList[dist])
            elif aList[dist] < pivot:
                smallerList.append(aList[dist])
            else:
                count += 1

        m = len(smallerList)

        if m <= k < m + count:
            return pivot
        elif m > k:
            return quickSelect(smallerList, k)
        else:
            return quickSelect(largerList, k - m - count)

    return aList[0]

def randomList(numElements, sizeRange):
    lst = []
    for num in range(numElements):
        lst.append(random.randint(0, sizeRange))
    return lst


def main():
    # testComp()
    lst = randomList(12, 100)
    print(lst)
    # print("\n", "Final return value: ", quickSelect(lst, quickSelectHelper(lst)))
    # lst = getList("large.csv")
    x = quickSelectHelper(lst)
    print("X: ", x)
    y = quickSelect(lst, x)
    print("Y: ", y)
    z = sumDistance(lst, y)
    print("Z: ", z)


main()