use crate::geometry::{Line, Rect, SpatialGrid};
use crate::utils::percent_to_pixel;

use cairo::{Context, Error};
use wmap_parser::{Component, Map};

#[derive(Debug, Clone)]
pub struct LabelPosition {
    pub x: f64,
    pub y: f64,
}

#[derive(Debug, Clone)]
pub struct PositioningDimensions {
    pub map_size: (f64, f64),
    pub vertex_size: f64,
    pub font_size: f64,
}

/// Calculate the optimal position for a vertex label with pre-cached collision data and spatial grid
pub fn calculate_optimal_label_position_cached(
    component: &Component,
    dimensions: &PositioningDimensions,
    context: &Context,
    all_lines: &[Line],
    spatial_grid: &SpatialGrid,
    note_rects: &[Rect],
) -> Result<LabelPosition, Error> {
    let map_width = dimensions.map_size.0;
    let map_height = dimensions.map_size.1;
    let vertex_pixel_x = percent_to_pixel(component.coordinates.0, map_width);
    let vertex_pixel_y = percent_to_pixel(component.coordinates.1, map_height);

    // Calculate label size
    context.set_font_size(dimensions.font_size);
    let extents = context.text_extents(&component.label)?;
    let label_width = extents.width() + 4.0;
    let label_height = extents.height() + 2.0;

    // Generate candidate positions
    let candidates = generate_candidate_positions(
        vertex_pixel_x,
        vertex_pixel_y,
        dimensions.vertex_size,
        label_width,
        label_height,
    );

    // Check if default position (right) has no collisions
    let default_position = &candidates[0];
    let default_rect = Rect::new(
        default_position.x,
        default_position.y,
        label_width,
        label_height,
    );

    if count_line_collisions_with_grid(&default_rect, all_lines, spatial_grid) == 0
        && count_note_collisions(&default_rect, note_rects) == 0
    {
        return Ok(default_position.clone());
    }

    // Score all positions and find the best
    let mut best_position = default_position.clone();
    let mut best_score = f64::INFINITY;

    for (index, position) in candidates.iter().enumerate() {
        let label_rect = Rect::new(position.x, position.y, label_width, label_height);

        let collision_count = count_line_collisions_with_grid(&label_rect, all_lines, spatial_grid);
        let note_collision_count = count_note_collisions(&label_rect, note_rects);

        // Distance from label center to vertex center
        let label_center_x = position.x + label_width / 2.0;
        let label_center_y = position.y + label_height / 2.0;
        let vertex_center_x = vertex_pixel_x + dimensions.vertex_size / 2.0;
        let vertex_center_y = vertex_pixel_y + dimensions.vertex_size / 2.0;
        let distance = ((label_center_x - vertex_center_x).powi(2)
            + (label_center_y - vertex_center_y).powi(2))
        .sqrt();

        // Calculate ownership penalty (simplified to avoid O(n²))
        let ownership_penalty = calculate_ownership_penalty_fast(
            &label_rect,
            vertex_pixel_x,
            vertex_pixel_y,
            dimensions.vertex_size,
        );

        // Score: collisions * 100 + note_collisions * 500 + distance * 0.5 + index * 0.1 + ownership
        let score = (collision_count as f64) * 100.0
            + (note_collision_count as f64) * 500.0
            + distance * 0.5
            + (index as f64) * 0.1
            + ownership_penalty;

        if score < best_score {
            best_score = score;
            best_position = position.clone();
        }
    }

    Ok(best_position)
}

/// Generate 8 candidate positions around a vertex
fn generate_candidate_positions(
    vertex_x: f64,
    vertex_y: f64,
    vertex_size: f64,
    label_width: f64,
    label_height: f64,
) -> Vec<LabelPosition> {
    let padding = 5.0;

    vec![
        // Right (default)
        LabelPosition {
            x: vertex_x + vertex_size + padding,
            y: vertex_y + (vertex_size - label_height) / 2.0,
        },
        // Left
        LabelPosition {
            x: vertex_x - label_width - padding,
            y: vertex_y + (vertex_size - label_height) / 2.0,
        },
        // Top
        LabelPosition {
            x: vertex_x + (vertex_size - label_width) / 2.0,
            y: vertex_y - label_height - padding,
        },
        // Bottom
        LabelPosition {
            x: vertex_x + (vertex_size - label_width) / 2.0,
            y: vertex_y + vertex_size + padding,
        },
        // Top-right
        LabelPosition {
            x: vertex_x + vertex_size + padding,
            y: vertex_y - label_height - padding,
        },
        // Top-left
        LabelPosition {
            x: vertex_x - label_width - padding,
            y: vertex_y - label_height - padding,
        },
        // Bottom-right
        LabelPosition {
            x: vertex_x + vertex_size + padding,
            y: vertex_y + vertex_size + padding,
        },
        // Bottom-left
        LabelPosition {
            x: vertex_x - label_width - padding,
            y: vertex_y + vertex_size + padding,
        },
    ]
}

/// Collect all lines from dependencies, evolutions, and axis lines
pub fn collect_all_lines(
    map: &Map,
    map_width: f64,
    map_height: f64,
    vertex_size: f64,
    component_map: &rustc_hash::FxHashMap<String, (f64, f64)>,
) -> Vec<Line> {
    let mut lines = Vec::new();

    // Collect dependency lines
    for dependency in &map.dependencies {
        if let (Some(&origin), Some(&destination)) = (
            component_map.get(&dependency.from.to_lowercase()),
            component_map.get(&dependency.to.to_lowercase()),
        ) {
            let slope = (destination.1 - origin.1) / (destination.0 - origin.0);
            let angle = slope.atan();
            let multiplier = if slope < 0.0 { -1.0 } else { 1.0 };

            let offset_origin_x = origin.0 + multiplier * (vertex_size / 2.0) * angle.cos();
            let offset_origin_y = origin.1 + multiplier * (vertex_size / 2.0) * angle.sin();
            let offset_dest_x = destination.0 - multiplier * (vertex_size / 2.0) * angle.cos();
            let offset_dest_y = destination.1 - multiplier * (vertex_size / 2.0) * angle.sin();

            let adjusted_origin_x = offset_origin_x + vertex_size / 2.0;
            let adjusted_origin_y = offset_origin_y + vertex_size / 2.0;
            let adjusted_dest_x = offset_dest_x + vertex_size / 2.0;
            let adjusted_dest_y = offset_dest_y + vertex_size / 2.0;

            lines.push(Line::new(
                (adjusted_origin_x, adjusted_origin_y),
                (adjusted_dest_x, adjusted_dest_y),
            ));
        }
    }

    // Collect evolution lines
    for evolution in &map.evolutions {
        if let Some(&origin) = component_map.get(&evolution.component.to_lowercase()) {
            let evolution_offset = percent_to_pixel(evolution.value, map_width);
            let destination_x = (origin.0 + evolution_offset).max(0.0).min(map_width);
            let destination_y = origin.1;

            let multiplier = if destination_x > origin.0 { 1.0 } else { -1.0 };

            let offset_origin_x = origin.0 + multiplier * (vertex_size / 2.0) + vertex_size / 2.0;
            let offset_origin_y = origin.1 + vertex_size / 2.0;
            let offset_dest_x =
                destination_x - multiplier * (vertex_size / 2.0) + vertex_size / 2.0;
            let offset_dest_y = destination_y + vertex_size / 2.0;

            lines.push(Line::new(
                (offset_origin_x, offset_origin_y),
                (offset_dest_x, offset_dest_y),
            ));
        }
    }

    // Add axis lines
    lines.push(Line::new((0.0, 0.0), (0.0, map_height))); // Y-axis
    lines.push(Line::new((0.0, map_height), (map_width, map_height))); // X-axis

    lines
}

/// Build a spatial grid from a collection of lines for fast collision detection
pub fn build_spatial_grid(lines: &[Line], map_width: f64, map_height: f64) -> SpatialGrid {
    // Use a cell size that balances grid overhead with query efficiency
    // For typical maps, 100x100 pixel cells work well
    let cell_size = 100.0;
    let mut grid = SpatialGrid::new(map_width, map_height, cell_size);

    for (idx, line) in lines.iter().enumerate() {
        grid.insert_line(idx, line);
    }

    grid
}

/// Collect rectangles for all notes
pub fn collect_note_rects(
    map: &Map,
    map_width: f64,
    map_height: f64,
    context: &Context,
    font_size: f64,
) -> Result<Vec<Rect>, Error> {
    let mut rects = Vec::new();

    context.set_font_size(font_size);

    for note in &map.notes {
        let x = percent_to_pixel(note.coordinates.0, map_width);
        let y = percent_to_pixel(note.coordinates.1, map_height);

        // Calculate note size (simplified - just use text extents)
        let extents = context.text_extents(&note.text)?;
        let width = extents.width() + 10.0; // padding
        let height = extents.height() + 10.0; // padding

        rects.push(Rect::new(x, y, width, height));
    }

    Ok(rects)
}

/// Count how many lines intersect with a label rectangle using spatial grid
fn count_line_collisions_with_grid(
    label_rect: &Rect,
    lines: &[Line],
    spatial_grid: &SpatialGrid,
) -> usize {
    spatial_grid
        .query_rect(label_rect)
        .filter(|&idx| crate::geometry::line_intersects_rect(&lines[idx], label_rect))
        .count()
}

/// Count how many note rectangles overlap with a label rectangle
fn count_note_collisions(label_rect: &Rect, note_rects: &[Rect]) -> usize {
    note_rects
        .iter()
        .filter(|note_rect| crate::geometry::rect_intersects_rect(label_rect, note_rect))
        .count()
}

/// Fast ownership penalty calculation without O(n²) iteration
fn calculate_ownership_penalty_fast(
    label_rect: &Rect,
    vertex_x: f64,
    vertex_y: f64,
    vertex_size: f64,
) -> f64 {
    let label_center_x = label_rect.x + label_rect.width / 2.0;
    let label_center_y = label_rect.y + label_rect.height / 2.0;

    let vertex_center_x = vertex_x + vertex_size / 2.0;
    let vertex_center_y = vertex_y + vertex_size / 2.0;

    let distance = ((label_center_x - vertex_center_x).powi(2)
        + (label_center_y - vertex_center_y).powi(2))
    .sqrt();

    // Apply penalty if label is too far from its vertex
    if distance > 100.0 {
        return 25.0;
    }

    0.0
}