<jupyter_start><jupyter_text>Find 10 closest cities to a given latidue and longitude point on earth Use any data structure that you can get your hands on and load the cities data. Write a function that creates the data structure withthe following function signature<jupyter_code>def create_data_stucture(map_data_file):
    """Create a data structure from a data_file that allows rapid quering positions on the map

    Args:
        map_data_file (Path) csv file with the following columns:
            city,lat,lng,country,iso3,local_name,population,continent

    Returns
        data_structure that can be used with find_closest_cities

    HINT:
        BSP buildup using recursive functions
    """
# Daten einlesen, Dictionary, City zu Tupel aus Koordinaten

cities_dict = {}

with open("..\..\data\cities.csv", "r", encoding="utf8") as data:
    next(data)
    for line in data:
        if line[0] == '"':
            splitted_line = line.split(",")
            cities_dict[splitted_line[0]] = (splitted_line[2], splitted_line[3])
        else:
            splitted_line = line.split(",")
            cities_dict[splitted_line[0]] = (splitted_line[1], splitted_line[2]) 

#print(cities_dict)
# Methode um Distanz zwischen Punkt und Stadt zu berechnen (ohne Erdkrümmung)
import numpy as np

def calculate_distance(city, point):
    lat_city = cities_data[city][0]
    lng_city = cities_data[city][1]
    difference_latidue = abs(lat_city - point[0])
    difference_longitude = abs(lng_city - point[1])
    if difference_longitude > 180:
        difference_longitude = 360 - difference_longitude
    distance = np.sqrt(difference_longitude**2 + difference_latidue**2)

# Liste, welche die ersten 10 Städte speichert, eine Neue hinzufügt, und dann die 11. Stadt löscht

point = (0.000, 0.000)
print(geopy.distance.distance(cities_dict["Tokyo"], point))

distances_dict = {}

for key in cities_dict:
    distances_dict[key] = geopy.distance.distance(cities_dict[key], point)

distance_dict_sorted = {key: value for key, value in sorted(distances_dict.items(), key= lambda item: item[1])}

import itertools
nearest_dict = dict(itertools.islice(distance_dict_sorted.items(), 10))
nearest_list = list(nearest_dict.keys())

print(nearest_list)<jupyter_output>['Sekondi', 'Cape Coast', 'Winneba', 'Accra', 'Tema', 'Palé', 'Koforidua', 'Aflao', 'Lomé', 'Aboisso']<jupyter_text>Write a query function with the following signature<jupyter_code>def find_closest_cities(point, data_structure):
    """Find ten close cities to the given point on the world given the data structure
    
    Args:
        point (tuple of floats) latitude and longitude
    
        data_structure (you choose) to be queries using the point

    Returns:
        list of 10 cities that are closest to the point 
    """
    return<jupyter_output><empty_output><jupyter_text>Creating a kd-tree with the others:<jupyter_code>import csv
map_data = []
with open('..\..\data\cities.csv', encoding="utf-8") as cities_file:
    map_data_reader = csv.DictReader(cities_file, delimiter=',')
    for line in map_data_reader:
        map_data.append([line['city'], [float(line['lat']), float(line['lng'])]])

map_data[14990:15000]
# child 1 -> smaller number, child 2 -> bigger number
# orientation = 0 --> lat, orientation = 1 ---> lng
import numpy as np
def create_data_stucture(cities, orientation=0):
    
    child1 = []
    child2 = []
    median_cities= []

    if len(cities) % 2 == 0:
        median = np.median([cities[city][1][orientation] for city in range(len(cities)-1)])
    elif len(cities) % 2 == 1:
        try:
            median = np.median([cities[city][1][orientation] for city in range(len(cities))])
        except:
            print('AAAA {}'.format(cities))
    else:
        print("You idiot!")

    for city_data in cities:
        if city_data[1][orientation] < median:
            child1.append(city_data)
        elif city_data[1][orientation] > median:
            child2.append(city_data)
        elif city_data[1][orientation] == median:
            median_cities.append(city_data)
        else:
            print("No median city??")

    median_city = median_cities[0]

    if len(median_cities) >= 2:
        if len(child1)>len(child2):
            for median_to_child in median_cities[1:]:
                child2.append(median_to_child)
        elif len(child1) <= len(child2):
            for median_to_child in median_cities[1:]:
                child1.append(median_to_child)

    if orientation == 0:
        orientation = 1
    elif orientation == 1:
        orientation = 0
    else:
        print("How is it even possible?")

    if child1 == []:
        if child2 == []:
            return_tree={'city': [median_city[0], median_city[1][0], median_city[1][1]],
            'child1': None,
            'child2': None,
            'leaf': True}
        elif len(child2)==1:
            return_tree={'city': [median_city[0], median_city[1][0], median_city[1][1]],
            'child1': None,
            'child2': {'city':[child2[0][0], child2[0][1][0], child2[0][1][1]],
                        'child1':None,
                        'child2':None,
                        'leaf':True},
            'leaf': False}
        elif len(child2) >= 2:
            return_tree={'city': [median_city[0], median_city[1][0], median_city[1][1]],
            'child1': None,
            'child2':create_data_stucture(child2, orientation=orientation),
            'leaf': False}
    elif len(child1) == 1:
        if child2 == []:
            return_tree={'city': [median_city[0], median_city[1][0], median_city[1][1]],
            'child1': {'city':[child1[0][0], child1[0][1][0], child1[0][1][1]],
                        'child1':None,
                        'child2':None,
                        'leaf':True},
            'child2': None,
            'leaf': False}
        elif len(child2) == 1:
            return_tree={'city': [median_city[0], median_city[1][0], median_city[1][1]],
            'child1': {'city':[child1[0][0], child1[0][1][0], child1[0][1][1]],
                        'child1':None,
                        'child2':None,
                        'leaf':True},
            'child2': {'city':[child2[0][0], child2[0][1][0], child2[0][1][1]],
                        'child1':None,
                        'child2':None,
                        'leaf':True},
            'leaf': False}
        elif len(child2) >= 2:
            return_tree={'city': [median_city[0], median_city[1][0], median_city[1][1]],
            'child1': {'city':[child1[0][0], child1[0][1][0], child1[0][1][1]],
                        'child1':None,
                        'child2':None,
                        'leaf':True},
            'child2': create_data_stucture(child2, orientation=orientation),
            'leaf': False}
    elif len(child1) >=2:
        if child2 == []:
            return_tree={'city': [median_city[0], median_city[1][0], median_city[1][1]],
            'child1': create_data_stucture(child1, orientation=orientation),
            'child2': None,
            'leaf': False}
        elif len(child2) ==1 :
             return_tree={'city': [median_city[0], median_city[1][0], median_city[1][1]],
            'child1': create_data_stucture(child1, orientation=orientation),
            'child2': {'city':[child2[0][0], child2[0][1][0], child2[0][1][1]],
                        'child1':None,
                        'child2':None,
                        'leaf':True},
            'leaf': False}
        elif len(child2) >= 2:
            return_tree = {'city': [median_city[0], median_city[1][0], median_city[1][1]], 
                        'child1':create_data_stucture(child1, orientation=orientation), 
                        'child2':create_data_stucture(child2, orientation=orientation),
                        'leaf': False}
  
    return return_tree
map_tree = create_data_stucture(map_data)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14075471698113207, 'fraction_numerical': 0.031572327044025156, 'mean_word_length': 2.576698155645524, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '639726', 'license': 'CC0-1.0', 'n_tokens_mistral': 2604, 'n_tokens_neox': 2508, 'n_words': 553, 'path': 'exercises/day 3/03.exercise_find_the_closest_10_cities.ipynb', 'repo_name': 'LauraKaschnitz/advanced_python_2021-22_HD', 'size': '7950'}