"""
Regroupe une liste de clients (fournie en JSON sur stdin) en groupes geographiques
et ordonne chaque groupe pour obtenir le chemin le plus court possible (voyageur
de commerce approxime par plus-proche-voisin + amelioration 2-opt).

Les clients sans position exploitable (latitude/longitude null, vide, 0 ou -1)
sont isoles dans un groupe a part ("sans_position") et ne participent pas au
clustering / calcul de chemin.

Entree (stdin) : JSON
[
    {"id": 1, "code": "C001", "nom": "...", "prenom": "...", "latitude": 36.8, "longitude": 10.1, ...},
    ...
]

Usage:
    python3 build_tournees.py [eps_km] [min_samples] [max_clients]

    max_clients : nombre maximum de clients par groupe (0 ou absent = illimite).
    Si un groupe geographique depasse ce nombre, il est decoupe en sous-groupes
    consecutifs le long du chemin le plus court deja calcule (les sous-groupes
    restent donc geographiquement coherents).

Sortie (stdout) : JSON
{
    "groups": [
        {
            "group_id": 1,
            "color": "#aabbcc",
            "clients": [...],          # clients ordonnes selon le chemin le plus court
            "line": [[lon, lat], ...], # coordonnees ordonnees pour affichage sur une carte
            "line_length_km": 12.34
        },
        ...
    ],
    "sans_position": [ ... clients sans position valide ... ]
}
"""

import sys
import json
import random

import numpy as np
from geopy.distance import geodesic
from sklearn.cluster import DBSCAN


def generate_random_color():
    return "#{:02x}{:02x}{:02x}".format(
        random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)
    )


def to_float(value):
    try:
        if value is None or value == "":
            return None
        return float(value)
    except (TypeError, ValueError):
        return None


def has_valid_position(client):
    lat = to_float(client.get("latitude"))
    lon = to_float(client.get("longitude"))

    if lat is None or lon is None:
        return False, None, None

    # Positions invalides couramment utilisees comme "non renseignees"
    if lat in (0, -1) or lon in (0, -1):
        return False, None, None

    if not (-90 <= lat <= 90 and -180 <= lon <= 180):
        return False, None, None

    return True, lat, lon


def haversine_distance_matrix(coordinates):
    """coordinates: liste de tuples (lat, lon) -> matrice des distances en km."""
    coords = np.radians(np.array(coordinates))
    lat = coords[:, 0][:, np.newaxis]
    lon = coords[:, 1][:, np.newaxis]

    dlat = lat - lat.T
    dlon = lon - lon.T
    a = np.sin(dlat / 2) ** 2 + np.cos(lat) * np.cos(lat.T) * np.sin(dlon / 2) ** 2
    c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1 - a))
    return 6371.0 * c


def nearest_neighbor_order(distance_matrix, start=0):
    """Ordonne les indices en partant de `start` en choisissant a chaque etape
    le point non visite le plus proche (heuristique du plus proche voisin)."""
    n = distance_matrix.shape[0]
    visited = [False] * n
    order = [start]
    visited[start] = True

    for _ in range(n - 1):
        last = order[-1]
        distances = distance_matrix[last].copy()
        distances[visited] = np.inf
        next_index = int(np.argmin(distances))
        order.append(next_index)
        visited[next_index] = True

    return order


def path_length(order, distance_matrix):
    return sum(
        distance_matrix[order[i], order[i + 1]] for i in range(len(order) - 1)
    )


def two_opt(order, distance_matrix, max_iterations=200):
    """Ameliore un ordre de visite via l'heuristique 2-opt (echange de segments)
    afin de reduire la longueur totale du chemin."""
    best = order[:]
    best_length = path_length(best, distance_matrix)
    improved = True
    iterations = 0

    n = len(best)
    while improved and iterations < max_iterations and n > 3:
        improved = False
        iterations += 1
        for i in range(1, n - 2):
            for j in range(i + 1, n - 1):
                candidate = best[:i] + best[i:j + 1][::-1] + best[j + 1:]
                candidate_length = path_length(candidate, distance_matrix)
                if candidate_length < best_length:
                    best = candidate
                    best_length = candidate_length
                    improved = True

    return best, best_length


def order_clients_shortest_path(clients):
    """Retourne (clients_ordonnes, coordonnees_ordonnees[lon,lat], longueur_km)."""
    if len(clients) <= 1:
        coords = [[c["longitude"], c["latitude"]] for c in clients]
        return clients, coords, 0.0

    coordinates = [(c["latitude"], c["longitude"]) for c in clients]
    distance_matrix = haversine_distance_matrix(coordinates)

    order = nearest_neighbor_order(distance_matrix, start=0)
    order, length_km = two_opt(order, distance_matrix)

    ordered_clients = [clients[i] for i in order]
    ordered_coords = [[c["longitude"], c["latitude"]] for c in ordered_clients]

    return ordered_clients, ordered_coords, length_km


def line_length_km(coords):
    """coords: liste de [lon, lat] ordonnes -> longueur cumulee du trajet en km."""
    if len(coords) < 2:
        return 0.0
    return sum(
        geodesic((coords[i][1], coords[i][0]), (coords[i + 1][1], coords[i + 1][0])).km
        for i in range(len(coords) - 1)
    )


def split_by_max_clients(ordered_clients, ordered_coords, max_clients):
    """Decoupe une liste deja ordonnee (chemin le plus court) en sous-listes
    consecutives d'au plus `max_clients` elements, pour rester geographiquement
    coherent (contrairement a un decoupage aleatoire)."""
    chunks = []
    for i in range(0, len(ordered_clients), max_clients):
        chunk_clients = ordered_clients[i:i + max_clients]
        chunk_coords = ordered_coords[i:i + max_clients]
        chunks.append((chunk_clients, chunk_coords, line_length_km(chunk_coords)))
    return chunks


def build_groups(clients, eps_km, min_samples, max_clients=0):
    valid_clients = []
    invalid_clients = []

    for client in clients:
        is_valid, lat, lon = has_valid_position(client)
        if is_valid:
            client["latitude"] = lat
            client["longitude"] = lon
            valid_clients.append(client)
        else:
            invalid_clients.append(client)

    groups = []

    if valid_clients:
        coordinates = [(c["latitude"], c["longitude"]) for c in valid_clients]
        distance_matrix = haversine_distance_matrix(coordinates)

        dbscan = DBSCAN(eps=eps_km, min_samples=min_samples, metric="precomputed")
        labels = dbscan.fit_predict(distance_matrix)

        clusters = {}
        for label, client in zip(labels, valid_clients):
            clusters.setdefault(label, []).append(client)

        group_id = 1
        for cluster_clients in clusters.values():
            ordered_clients, line, length_km = order_clients_shortest_path(cluster_clients)

            if max_clients and max_clients > 0 and len(ordered_clients) > max_clients:
                for chunk_clients, chunk_line, chunk_length_km in split_by_max_clients(
                    ordered_clients, line, max_clients
                ):
                    groups.append({
                        "group_id": group_id,
                        "color": generate_random_color(),
                        "clients": chunk_clients,
                        "line": chunk_line,
                        "line_length_km": round(chunk_length_km, 3),
                    })
                    group_id += 1
            else:
                groups.append({
                    "group_id": group_id,
                    "color": generate_random_color(),
                    "clients": ordered_clients,
                    "line": line,
                    "line_length_km": round(length_km, 3),
                })
                group_id += 1

        # Groupes les plus fournis en premier
        groups.sort(key=lambda g: len(g["clients"]), reverse=True)

    return groups, invalid_clients


def main():
    eps_km = float(sys.argv[1]) if len(sys.argv) > 1 else 2.0
    min_samples = int(sys.argv[2]) if len(sys.argv) > 2 else 1
    max_clients = int(sys.argv[3]) if len(sys.argv) > 3 else 0

    raw_input = sys.stdin.read()
    clients = json.loads(raw_input) if raw_input.strip() else []

    groups, sans_position = build_groups(clients, eps_km, min_samples, max_clients)

    print(json.dumps({
        "groups": groups,
        "sans_position": sans_position,
    }, ensure_ascii=False))


if __name__ == "__main__":
    main()