cargo-perspective 0.1.0

//! Squarified TreeMap layout algorithm.
//!
//! Based on "Squarified Treemaps" by Mark Bruls, Kees Huizing, and Jarke J. van Wijk.
//! The algorithm tries to create rectangles with aspect ratios as close to 1 as possible.

use crate::types::{TreeMapNode, TreeMapRect};

/// Layout nodes in a TreeMap using the squarified algorithm.
pub fn layout_treemap(nodes: &mut [TreeMapNode], bounds: TreeMapRect) {
    if nodes.is_empty() {
        return;
    }

    // Sort nodes by value descending for better squarification
    let mut sorted_nodes: Vec<&mut TreeMapNode> = nodes.iter_mut().collect();
    sorted_nodes.sort_by(|a, b| b.value.cmp(&a.value));

    let total_value: usize = sorted_nodes.iter().map(|n| n.value).sum();
    if total_value == 0 {
        return;
    }

    squarify(&mut sorted_nodes, total_value, bounds);
}

/// Squarified TreeMap layout algorithm.
fn squarify(nodes: &mut [&mut TreeMapNode], total_value: usize, bounds: TreeMapRect) {
    if nodes.is_empty() {
        return;
    }

    let mut remaining_nodes = nodes;
    let mut current_bounds = bounds;

    while !remaining_nodes.is_empty() {
        // Find the best row to add
        let row_size = find_best_row(remaining_nodes, total_value, &current_bounds);

        if row_size == 0 {
            // Fallback: just use all remaining nodes
            layout_row(remaining_nodes, total_value, &current_bounds);
            break;
        }

        // Split nodes into current row and remaining
        let (row, rest) = remaining_nodes.split_at_mut(row_size);

        // Calculate total value for this row
        let row_value: usize = row.iter().map(|n| n.value).sum();

        // Layout this row
        layout_row(row, row_value, &current_bounds);

        // Update bounds for remaining nodes
        if !rest.is_empty() {
            current_bounds = remaining_bounds(&current_bounds, row_value, total_value);
        }

        remaining_nodes = rest;
    }
}

/// Find the optimal number of nodes to include in the next row.
fn find_best_row(nodes: &[&mut TreeMapNode], total_value: usize, bounds: &TreeMapRect) -> usize {
    if nodes.is_empty() {
        return 0;
    }

    let mut best_size = 1;
    let mut best_ratio = f64::INFINITY;

    for i in 1..=nodes.len() {
        let row_value: usize = nodes[..i].iter().map(|n| n.value).sum();
        let ratio = worst_aspect_ratio(&nodes[..i], row_value, total_value, bounds);

        if ratio < best_ratio {
            best_ratio = ratio;
            best_size = i;
        } else {
            // Aspect ratio getting worse, stop here
            break;
        }
    }

    best_size
}

/// Calculate the worst aspect ratio in a row.
fn worst_aspect_ratio(
    row: &[&mut TreeMapNode],
    row_value: usize,
    total_value: usize,
    bounds: &TreeMapRect,
) -> f64 {
    if row.is_empty() || row_value == 0 || total_value == 0 {
        return f64::INFINITY;
    }

    let area = bounds.area();
    let row_area = area * (row_value as f64 / total_value as f64);

    let short_side = if bounds.width < bounds.height {
        bounds.width
    } else {
        bounds.height
    };

    if short_side == 0.0 {
        return f64::INFINITY;
    }

    let mut max_ratio: f64 = 0.0;

    for node in row {
        let node_area = row_area * (node.value as f64 / row_value as f64);
        let side = node_area / short_side;

        if side == 0.0 {
            continue;
        }

        let ratio = if short_side > side {
            short_side / side
        } else {
            side / short_side
        };

        max_ratio = max_ratio.max(ratio);
    }

    max_ratio
}

/// Layout a row of nodes within the given bounds.
fn layout_row(row: &mut [&mut TreeMapNode], row_value: usize, bounds: &TreeMapRect) {
    if row.is_empty() || row_value == 0 {
        return;
    }

    let area = bounds.area();
    let row_area = area * (row_value as f64 / row_value as f64); // This is always the full area for the row

    // Determine if we're laying out horizontally or vertically
    let horizontal = bounds.width >= bounds.height;

    let short_side = if horizontal { bounds.height } else { bounds.width };
    let long_side = if horizontal { bounds.width } else { bounds.height };

    let mut offset = 0.0;

    for node in row {
        let node_area = row_area * (node.value as f64 / row_value as f64);
        let length = if short_side > 0.0 {
            node_area / short_side
        } else {
            0.0
        };

        let rect = if horizontal {
            TreeMapRect::new(
                bounds.x + offset,
                bounds.y,
                length.min(long_side - offset),
                short_side,
            )
        } else {
            TreeMapRect::new(
                bounds.x,
                bounds.y + offset,
                short_side,
                length.min(long_side - offset),
            )
        };

        node.rect = Some(rect);
        offset += length;
    }
}

/// Calculate the remaining bounds after laying out a row.
fn remaining_bounds(bounds: &TreeMapRect, row_value: usize, total_value: usize) -> TreeMapRect {
    if total_value == 0 {
        return bounds.clone();
    }

    let ratio = row_value as f64 / total_value as f64;
    let horizontal = bounds.width >= bounds.height;

    if horizontal {
        let used_width = bounds.width * ratio;
        TreeMapRect::new(
            bounds.x + used_width,
            bounds.y,
            bounds.width - used_width,
            bounds.height,
        )
    } else {
        let used_height = bounds.height * ratio;
        TreeMapRect::new(
            bounds.x,
            bounds.y + used_height,
            bounds.width,
            bounds.height - used_height,
        )
    }
}

/// Layout a hierarchical TreeMap (crates containing methods).
pub fn layout_hierarchical(nodes: &mut [TreeMapNode], bounds: TreeMapRect, padding: f64) {
    if nodes.is_empty() {
        return;
    }

    // First, layout the top-level nodes (crates)
    layout_treemap(nodes, bounds);

    // Then, recursively layout children (methods) within each crate
    for node in nodes.iter_mut() {
        if let Some(rect) = &node.rect {
            if !node.children.is_empty() && rect.width > padding * 2.0 && rect.height > padding * 2.0
            {
                // Create inner bounds with padding
                let inner_bounds = TreeMapRect::new(
                    rect.x + padding,
                    rect.y + padding,
                    rect.width - 2.0 * padding,
                    rect.height - 2.0 * padding,
                );

                layout_treemap(&mut node.children, inner_bounds);
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_simple_layout() {
        let mut nodes = vec![
            TreeMapNode::new_method("method1".to_string(), 100, None),
            TreeMapNode::new_method("method2".to_string(), 50, None),
            TreeMapNode::new_method("method3".to_string(), 25, None),
        ];

        let bounds = TreeMapRect::new(0.0, 0.0, 100.0, 100.0);
        layout_treemap(&mut nodes, bounds);

        // Check that all nodes have been assigned rectangles
        for node in &nodes {
            assert!(node.rect.is_some());
        }

        // Check that total area is approximately preserved
        let total_area: f64 = nodes.iter().filter_map(|n| n.rect.as_ref()).map(|r| r.area()).sum();
        assert!((total_area - 10000.0).abs() < 1.0); // bounds area = 100 * 100 = 10000
    }

    #[test]
    fn test_hierarchical_layout() {
        let children = vec![
            TreeMapNode::new_method("method1".to_string(), 10, None),
            TreeMapNode::new_method("method2".to_string(), 5, None),
        ];

        let mut nodes = vec![TreeMapNode::new_crate("crate1".to_string(), 15, children)];

        let bounds = TreeMapRect::new(0.0, 0.0, 100.0, 100.0);
        layout_hierarchical(&mut nodes, bounds, 2.0);

        // Check that parent has a rect
        assert!(nodes[0].rect.is_some());

        // Check that children have rects
        for child in &nodes[0].children {
            assert!(child.rect.is_some());
        }
    }
}