Seminar1/algorithms.py

from argparse import ArgumentError
from math import log, ceil
from operator import itemgetter
from classes import *

class SolvingAlgorithm:
    def __init__(self,space,gMngr:GarageManager):
        self.space:MetricSpace = space
        self.garageManager:GarageManager = gMngr
        self.amountTraveled = 0

    def getGarageForCar(self,car:Point):
        garages:List[Garage] = list(self.garageManager.garages)
        garages = sorted(garages,key=lambda g: self.space.distancefunction.apply(car,g))

        for g in garages:
            if self.garageManager.is_full(g):
                continue
            else:
                g.cars_parked.append(g)
                self.amountTraveled += self.space.distancefunction.apply(car,g)
                return g

        return None


class MST():
    @classmethod
    def _helper_getListInPointset(self, pointesets:List[List[Point]] , point:tuple):
        for li in pointesets:
            if point in li:
                return li
        return None


    def __init__(self, points:set, distancefunction: DistanceFunction,space:MetricSpace, powerTWO = False,mst_visualize=True):
        self.points = points
        self.distancefunction = distancefunction

        all_edges = []
        for i in self.points:
            for j in self.points:
                if not i == j:
                    if not (j,i, distancefunction.apply(i,j)) in all_edges:
                        all_edges.append((i,j, distancefunction.apply(i,j)))

        all_edges = sorted(all_edges,key=itemgetter(2))

        minimal_edges =  [] # edge is represented by (i,j, distance/Weight)
        pointSets:List[List[Point]] = []
        for p in self.points:
            pointSets.append([p])

        visualisations =[]
        for edge in all_edges:
            if len(pointSets) <= 1: break
            li0 = MST._helper_getListInPointset(pointSets,edge[0])
            li1 = MST._helper_getListInPointset(pointSets,edge[1])

            if not( li0 == li1):
                minimal_edges.append(edge)

                li_new = li0 + li1
                pointSets.remove(li0)
                pointSets.remove(li1)
                pointSets.append( li_new)

                if (mst_visualize):
                    a= frameGenerator.point_to_pixel_center(space,edge[0])
                    b= frameGenerator.point_to_pixel_center(space,edge[1])
                    data = [ a[0], a[1], b[0], b [1], (23,64,96,100)]
                    visualisations.append(RenderTask(RenderTaskType.LINE,"mst",data))
                    RenderTaskStack.add_single_frame_render(RenderTaskFrame(visualisations.copy()))

        if(powerTWO):
            for x in range(len(minimal_edges)):
                c_edge = minimal_edges[x]
                c_edge = ( c_edge[0], c_edge[1], 2**ceil(log(c_edge[2],2)) )
                minimal_edges[x] = c_edge

        if (mst_visualize):
            RenderTaskStack.add_single_frame_render(RenderTaskFrame(visualisations.copy(),True))

        self.minimalEdges: List[tuple[Point,Point,float]] = minimal_edges

    def _dfs_recursive(self, tree, start, visited =[]):
        # due tue MST property,
        tour = []

        for edge in tree:# go throug all edges and recursively walk down all that lead to new places, on return add back edge
            if edge[0].get_location() == start.get_location() and edge[1].get_location() not in visited:
                tour.append(edge)
                visited.append(start.get_location()) # visited only needs to be carried in for a node downwards but not upwards, since this is a MST
                data = self._dfs_recursive(tree,edge[1],visited)
                tour+= data # add subtree
                tour.append((edge[1],edge[0],edge[2])) #append reversed edge

        return tour



    def get_dfs_eulerwalk(self,start:Point, level= 0):
        directionalEdges = []
        for min_edge in self.minimalEdges:
            i,j,dist = min_edge
            if dist > 2**level: continue
            directionalEdges.append((i,j,dist))
            directionalEdges.append((j,i,dist))

        # create walk with dfs
        walk:List[tuple[Point,Point,float]] = self._dfs_recursive(directionalEdges,start)

        return walk

class AlgorithmA(SolvingAlgorithm):
    def __init__(self, space:MetricSpace, gMngr: GarageManager):
        super().__init__(space, gMngr)
        gar_set = set(gMngr.garages)
        self.mst = MST(gar_set,space.distancefunction,space,True)

    def getGarageForCar(self, car: Car):
        garagedata= self.garageManager.get_garage_at_location(car.get_location())
        garagefound = garagedata[0]
        garage: Garage = garagedata[1]
        if(not garagefound):
            raise ArgumentError("No garage found INSIDE of ALGO A")

        if(not self.garageManager.is_full(garage)):
            car.set_walk(0)
            garage.cars_parked.append(car)
            return garage

        carParked = False
        while not carParked:
            walk = self.mst.get_dfs_eulerwalk(car,car.get_walk()) # implicite, position of car determines where it arrived!

            if len(walk) <1: continue
            if car.get_walk() >32:
                raise ArgumentError("walk got over power 32, this is likely an error and an infinite loop")

            currentGarage = self.garageManager.get_garage_at_location(car.get_location())
            for x in walk:
                currentGarage = self.garageManager.get_garage_at_location(
                    x[1].get_location())  # second argument of edge

                ##TODO Finish implementation, garage full case and proper start

                if not self.garageManager.is_full(currentGarage):
                    garage.cars_parked.append(car)
                    return garage


            car.add_to_walk(1)

        return super().getGarageForCar(car)