##### On commence par importer les bibliothèques dont on aura besoin : rien à faire pour vous ####

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import scipy.spatial.distance as sd

from utils import plot_clusters, plot_edges_and_points, blobs, uniform

np.random.seed(0)



##### Génération des villes : plus d'info dans utils.py ######

num_villes = 100
villes = uniform(num_villes) # génère les positions des villes avec proba uniforme
#villes = blobs(num_villes, n_blobs=4) # le paramètre est le nombre de villes

"""
villes = np.zeros((num_villes, 2))
for i in range(1, num_villes):
	villes[i][0] = np.cos(i*2*np.pi/num_villes)
	villes[i][1] = np.sin(i*2*np.pi/num_villes)
"""
#### On calcule toute les distances pour la suite ####
distance = sd.cdist(villes,villes, 'euclidean')

# PART 3

#### Comment calculer les arrêtes ? ####

# des vecteurs utiles
u_vect = [0]*4
u_vect[1] = np.array([0,0])
u_vect[2] = np.array([0,0])
u_vect[3] = np.array([0,0])

def etre_proche(u,v):
	"""
	Parametres:
		u : vecteur normalisé
		v : vecteur normalisé
	Retourne si l'angle est de moins de 30 degré
	"""
	return True


def est_dans_cadran(centre, ville):
	"""
	Parametres:
		centre : entier, numéro de la ville que l'on étudie
		ville : entier, numéro de la ville peut-être à relier
	Retourne O si ville est dans aucun cadran, et le numéro du cadran sinon
	"""
	return 0

def proj(cadran, ville1, ville2):
	"""
	Parametres:
		cadran : entier, le cadran considéré
		ville1, ville2 : entier, numéro des villes à tester
	Retourne si on diminue la distance projective en passant de ville2 à ville1 
	selon le vecteur du cadran considéré
	"""
	return True

def calcul_voisin(ville_vue, distance):
	"""
	Parametres:
		ville_vue : entien, numéro de la ville qu'on étudie
		distance : matrice des distances entre les villes
	Retourne une liste des trois villes à relier à ville_vue
	"""
	return [0,0,0]


def calcul_graph():
	"""
	Retourne la matrice d'adjacence de graphe planaire d'étirement au plus 2
	"""
	E = np.zeros((num_villes, num_villes))

	return E


# PART 4

def plus_a_gauche(l, ville):
	"""
	Parametres:
		l     : liste d'entiers, numéro des villes à considérer
		ville : entier, ville à relier
	Retourne le premier vecteur dans le sens trigonométrique
	"""
	return l[0]

def plus_a_droite(l, ville):
	"""
	Parametres:
		l     : liste d'entiers, numéro des villes à considérer
		ville : entier, ville à relier
	Retourne le dernier vecteur dans le sens trigonométrique
	"""
	return l[0]

def plus_court(l, ville_vue):
	"""
	Parametres:
		l     : liste d'entiers, numéro des villes à considérer
		ville : entier, ville à relier
	Retourne la ville correspondant au plus court vecteur
	"""
	return l[0]


def selection_ville(ville, E, cadran):
	"""
	Parametres:
		ville : entier, numéro de la ville qu'on étudie
		E     : matrice d'adjacence du graphe construit à la partie 3
		cadran: entier, le cadran qu'on considère
	Retourne si la liste des villes est vide, 
	puis s'il est non vide les trois villes que l'on conserve
	"""
	return False, 0, 0, 0

def graphe_leger(E):
	"""
	Parametres:
		E : matrice d'adjacence du graphe de la partie 3
	Retourne la matrice d'adjacence du graphe de degré maximal 12 et d'étirement 6
	"""
	A = np.zeros((num_villes, num_villes))

	return A



if __name__ == '__main__':
	E = calcul_graph()
	plot_edges_and_points(villes, E, title="sans degré max",save=False, show=True)