hojicha_rendering/

algorithms.rs

//! Core algorithms for differential rendering.
//!
//! This module contains the fundamental algorithms used in the differential
//! rendering system, with detailed documentation, complexity analysis, and
//! references to academic literature.

use ratatui::layout::Rect;
use std::collections::HashSet;

/// Rectangle intersection algorithm using the Separating Axis Theorem.
///
/// # Theory
///
/// The Separating Axis Theorem states that two convex polygons intersect
/// if and only if there is no separating axis between them. For axis-aligned
/// rectangles, we only need to check the X and Y axes.
///
/// # Algorithm
///
/// Two rectangles A and B intersect if and only if:
/// - They overlap on the X-axis AND
/// - They overlap on the Y-axis
///
/// They DON'T overlap on an axis if:
/// - A is completely to one side of B on that axis
///
/// # Complexity
///
/// - Time: O(1) - exactly 4 comparisons
/// - Space: O(1) - no additional memory
///
/// # References
///
/// - "Real-Time Collision Detection" by Christer Ericson, Chapter 4
/// - "Computational Geometry: Algorithms and Applications" by de Berg et al.
///
/// # Examples
///
/// ```rust
/// use hojicha_rendering::algorithms::rectangles_intersect;
/// use ratatui::layout::Rect;
///
/// let a = Rect::new(0, 0, 10, 10);
/// let b = Rect::new(5, 5, 10, 10);  // overlapping
/// let c = Rect::new(20, 20, 10, 10); // separate
///
/// assert!(rectangles_intersect(&a, &b));
/// assert!(!rectangles_intersect(&a, &c));
/// ```
pub fn rectangles_intersect(a: &Rect, b: &Rect) -> bool {
    debug_assert!(
        a.width > 0 && a.height > 0,
        "Rectangle A must have positive area"
    );
    debug_assert!(
        b.width > 0 && b.height > 0,
        "Rectangle B must have positive area"
    );

    // Check if rectangles are separated on X-axis
    let x_separated = a.x >= b.x.saturating_add(b.width) || b.x >= a.x.saturating_add(a.width);

    // Check if rectangles are separated on Y-axis
    let y_separated = a.y >= b.y.saturating_add(b.height) || b.y >= a.y.saturating_add(a.height);

    // Intersect if NOT separated on either axis
    !x_separated && !y_separated
}

/// Rectangle union (bounding box) calculation.
///
/// Computes the smallest rectangle that contains both input rectangles.
/// This is used in region merging to create the combined dirty area.
///
/// # Algorithm
///
/// 1. Find minimum X and Y coordinates (top-left corner)
/// 2. Find maximum X+width and Y+height coordinates (bottom-right corner)
/// 3. Compute width and height from corners
///
/// # Complexity
///
/// - Time: O(1) - arithmetic operations only
/// - Space: O(1) - no additional memory allocation
///
/// # Overflow Handling
///
/// Uses saturating arithmetic to handle coordinate overflow gracefully.
/// Large coordinates are clamped to u16::MAX rather than wrapping.
///
/// # Examples
///
/// ```rust
/// use hojicha_rendering::algorithms::rectangle_union;
/// use ratatui::layout::Rect;
///
/// let a = Rect::new(0, 0, 10, 10);
/// let b = Rect::new(5, 5, 10, 10);
/// let union = rectangle_union(&a, &b);
///
/// assert_eq!(union, Rect::new(0, 0, 15, 15));
/// ```
pub fn rectangle_union(a: &Rect, b: &Rect) -> Rect {
    debug_assert!(
        a.width > 0 && a.height > 0,
        "Rectangle A must have positive area"
    );
    debug_assert!(
        b.width > 0 && b.height > 0,
        "Rectangle B must have positive area"
    );

    let min_x = a.x.min(b.x);
    let min_y = a.y.min(b.y);

    let max_x = a.x.saturating_add(a.width).max(b.x.saturating_add(b.width));
    let max_y =
        a.y.saturating_add(a.height)
            .max(b.y.saturating_add(b.height));

    let width = max_x.saturating_sub(min_x);
    let height = max_y.saturating_sub(min_y);

    debug_assert!(width > 0 && height > 0, "Union must have positive area");

    Rect {
        x: min_x,
        y: min_y,
        width,
        height,
    }
}

/// Check if two rectangles are adjacent (touching but not overlapping).
///
/// Two rectangles are adjacent if they share a border but have no
/// overlapping area. This is used to determine if regions can be
/// merged even when they don't overlap.
///
/// # Algorithm
///
/// Checks for adjacency in both directions:
/// 1. **Horizontal adjacency**: Right edge of A touches left edge of B (or vice versa)
///    AND they overlap on the Y-axis
/// 2. **Vertical adjacency**: Bottom edge of A touches top edge of B (or vice versa)
///    AND they overlap on the X-axis
///
/// # Complexity
///
/// - Time: O(1) - up to 8 comparisons
/// - Space: O(1) - no additional memory
///
/// # Edge Cases
///
/// - Handles zero-width or zero-height rectangles gracefully
/// - Uses saturating arithmetic for overflow protection
/// - Returns false for overlapping rectangles (use intersection test instead)
///
/// # Examples
///
/// ```rust
/// use hojicha_rendering::algorithms::rectangles_adjacent;
/// use ratatui::layout::Rect;
///
/// // Horizontally adjacent
/// let a = Rect::new(0, 0, 10, 10);
/// let b = Rect::new(10, 0, 10, 10);
/// assert!(rectangles_adjacent(&a, &b));
///
/// // Vertically adjacent  
/// let c = Rect::new(0, 10, 10, 10);
/// assert!(rectangles_adjacent(&a, &c));
///
/// // Not adjacent (gap between)
/// let d = Rect::new(12, 0, 10, 10);
/// assert!(!rectangles_adjacent(&a, &d));
/// ```
pub fn rectangles_adjacent(a: &Rect, b: &Rect) -> bool {
    debug_assert!(
        a.width > 0 && a.height > 0,
        "Rectangle A must have positive area"
    );
    debug_assert!(
        b.width > 0 && b.height > 0,
        "Rectangle B must have positive area"
    );

    // Check horizontal adjacency (touching left/right edges)
    let h_adjacent = (a.x.saturating_add(a.width) == b.x ||
                     b.x.saturating_add(b.width) == a.x) &&
                     // Must overlap on Y-axis
                     !(a.y >= b.y.saturating_add(b.height) ||
                       a.y.saturating_add(a.height) <= b.y);

    // Check vertical adjacency (touching top/bottom edges)
    let v_adjacent = (a.y.saturating_add(a.height) == b.y ||
                     b.y.saturating_add(b.height) == a.y) &&
                     // Must overlap on X-axis
                     !(a.x >= b.x.saturating_add(b.width) ||
                       a.x.saturating_add(a.width) <= b.x);

    h_adjacent || v_adjacent
}

/// Greedy region coalescing algorithm.
///
/// Merges a collection of rectangles to reduce the total number while
/// maintaining coverage. This reduces the number of render operations
/// at the cost of potentially drawing slightly larger areas.
///
/// # Algorithm
///
/// Uses a greedy approach:
/// 1. For each rectangle, try to merge with all others
/// 2. If merge is beneficial (reduces total count), perform it
/// 3. Continue until no more beneficial merges are found
///
/// # Complexity
///
/// - Time: O(n²) in worst case, O(n) in best case
/// - Space: O(1) additional (modifies input in-place)
/// - n = number of input rectangles
///
/// # Merge Criteria
///
/// Two rectangles are merged if:
/// - They intersect OR are adjacent
/// - The resulting area is not significantly larger than the sum
///   (to avoid merging distant small regions)
///
/// # Trade-offs
///
/// - **Pros**: Reduces number of render calls, improves cache locality
/// - **Cons**: May render slightly more pixels than strictly necessary
/// - **Balance**: Configurable area growth threshold
///
/// # Examples
///
/// ```rust
/// use hojicha_rendering::algorithms::coalesce_regions;
/// use ratatui::layout::Rect;
///
/// let mut regions = vec![
///     Rect::new(0, 0, 10, 10),
///     Rect::new(10, 0, 10, 10),  // Adjacent to first
///     Rect::new(5, 5, 5, 5),     // Overlaps with first
/// ];
///
/// let original_count = regions.len();
/// coalesce_regions(&mut regions, 1.5); // Allow 50% area growth
///
/// assert!(regions.len() < original_count); // Should have merged some
/// ```
pub fn coalesce_regions(regions: &mut Vec<Rect>, max_area_growth: f32) -> usize {
    debug_assert!(max_area_growth >= 1.0, "Area growth factor must be >= 1.0");

    let mut merged_count = 0;
    let mut changed = true;

    // Continue until no more merges are possible
    while changed && regions.len() > 1 {
        changed = false;

        // Try to merge each pair of rectangles
        for i in 0..regions.len() {
            for j in (i + 1)..regions.len() {
                let a = regions[i];
                let b = regions[j];

                // Check if rectangles can be merged
                if rectangles_intersect(&a, &b) || rectangles_adjacent(&a, &b) {
                    let union = rectangle_union(&a, &b);

                    // Calculate area growth factor
                    let original_area =
                        (a.width as u32 * a.height as u32) + (b.width as u32 * b.height as u32);
                    let union_area = union.width as u32 * union.height as u32;
                    let growth_factor = union_area as f32 / original_area as f32;

                    // Merge if growth is acceptable
                    if growth_factor <= max_area_growth {
                        regions[i] = union;
                        regions.remove(j);
                        merged_count += 1;
                        changed = true;
                        break;
                    }
                }
            }
            if changed {
                break; // Restart from beginning after a merge
            }
        }
    }

    merged_count
}

/// Topological sort for component dependency resolution.
///
/// Sorts components based on their dependencies to ensure that dependent
/// components are updated after their dependencies. This prevents stale
/// data from being used in rendering.
///
/// # Algorithm
///
/// Uses Kahn's algorithm for topological sorting:
/// 1. Find all nodes with no incoming edges (no dependencies)
/// 2. Remove a node and all its outgoing edges
/// 3. If this creates new nodes with no incoming edges, add them to queue
/// 4. Repeat until all nodes are processed or a cycle is detected
///
/// # Complexity
///
/// - Time: O(V + E) where V is vertices (components) and E is edges (dependencies)
/// - Space: O(V + E) for auxiliary data structures
///
/// # Cycle Detection
///
/// Returns `None` if a cycle is detected in the dependency graph.
/// This indicates a configuration error where components have circular dependencies.
///
/// # Parameters
///
/// - `dependencies`: Map from component ID to set of dependency IDs
///
/// # Returns
///
/// - `Some(Vec<String>)`: Topologically sorted component IDs
/// - `None`: Cycle detected in dependency graph
///
/// # Examples
///
/// ```rust
/// use hojicha_rendering::algorithms::topological_sort;
/// use std::collections::{HashMap, HashSet};
///
/// let mut deps = HashMap::new();
/// deps.insert("C".to_string(), ["A", "B"].iter().map(|s| s.to_string()).collect());
/// deps.insert("B".to_string(), ["A"].iter().map(|s| s.to_string()).collect());
/// deps.insert("A".to_string(), HashSet::new());
///
/// let sorted = topological_sort(&deps).unwrap();
/// // A comes before B, B comes before C
/// assert_eq!(sorted, vec!["A", "B", "C"]);
/// ```
pub fn topological_sort(
    dependencies: &std::collections::HashMap<String, HashSet<String>>,
) -> Option<Vec<String>> {
    use std::collections::{HashMap, VecDeque};

    // Build reverse dependency graph (who depends on whom)
    let mut in_degree: HashMap<String, usize> = HashMap::new();
    let mut out_edges: HashMap<String, Vec<String>> = HashMap::new();

    // Initialize all components
    for component in dependencies.keys() {
        in_degree.entry(component.clone()).or_insert(0);
        out_edges.entry(component.clone()).or_default();
    }

    // Build the graph
    for (component, deps) in dependencies {
        for dep in deps {
            // Ensure dependency exists in our graph
            in_degree.entry(dep.clone()).or_insert(0);
            out_edges.entry(dep.clone()).or_default();

            // Add edge from dependency to component
            out_edges.get_mut(dep).unwrap().push(component.clone());
            *in_degree.get_mut(component).unwrap() += 1;
        }
    }

    // Find all components with no dependencies
    let mut queue: VecDeque<String> = in_degree
        .iter()
        .filter(|(_, &degree)| degree == 0)
        .map(|(component, _)| component.clone())
        .collect();

    let mut result = Vec::new();

    // Process components in dependency order
    while let Some(component) = queue.pop_front() {
        result.push(component.clone());

        // Remove this component and update dependents
        if let Some(dependents) = out_edges.get(&component) {
            for dependent in dependents {
                if let Some(degree) = in_degree.get_mut(dependent) {
                    *degree -= 1;
                    if *degree == 0 {
                        queue.push_back(dependent.clone());
                    }
                }
            }
        }
    }

    // Check if all components were processed (no cycles)
    if result.len() == dependencies.len() {
        Some(result)
    } else {
        None // Cycle detected
    }
}

/// FNV-1a hash function for fast checksumming.
///
/// Implements the FNV-1a (Fowler–Noll–Vo) hash algorithm, which provides
/// good distribution and performance for small to medium-sized inputs
/// like UI content.
///
/// # Algorithm
///
/// ```text
/// hash = FNV_offset_basis
/// for each byte in input:
///     hash = hash XOR byte
///     hash = hash * FNV_prime
/// ```
///
/// # Properties
///
/// - **Fast**: Single pass, simple operations
/// - **Good distribution**: Low collision rate for typical inputs
/// - **Deterministic**: Same input always produces same hash
/// - **Not cryptographic**: Don't use for security purposes
///
/// # Complexity
///
/// - Time: O(n) where n is input length
/// - Space: O(1) - constant memory usage
///
/// # Parameters
///
/// - `data`: Byte slice to hash
///
/// # Returns
///
/// 64-bit hash value
///
/// # References
///
/// - http://www.isthe.com/chongo/tech/comp/fnv/
/// - RFC: https://tools.ietf.org/id/draft-eastlake-fnv-16.html
///
/// # Examples
///
/// ```rust
/// use hojicha_rendering::algorithms::fnv1a_hash;
///
/// let hash1 = fnv1a_hash(b"hello");
/// let hash2 = fnv1a_hash(b"hello");
/// let hash3 = fnv1a_hash(b"world");
///
/// assert_eq!(hash1, hash2); // Same input = same hash
/// assert_ne!(hash1, hash3); // Different input = different hash (usually)
/// ```
pub fn fnv1a_hash(data: &[u8]) -> u64 {
    const FNV_OFFSET_BASIS: u64 = 0xcbf29ce484222325;
    const FNV_PRIME: u64 = 0x100000001b3;

    let mut hash = FNV_OFFSET_BASIS;

    for &byte in data {
        hash ^= byte as u64;
        hash = hash.wrapping_mul(FNV_PRIME);
    }

    hash
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::{HashMap, HashSet};

    #[test]
    fn test_rectangles_intersect() {
        let a = Rect::new(0, 0, 10, 10);

        // Overlapping
        assert!(rectangles_intersect(&a, &Rect::new(5, 5, 10, 10)));

        // Touching edges (not overlapping)
        assert!(!rectangles_intersect(&a, &Rect::new(10, 0, 10, 10)));

        // Completely separate
        assert!(!rectangles_intersect(&a, &Rect::new(20, 20, 10, 10)));

        // Contained
        assert!(rectangles_intersect(&a, &Rect::new(2, 2, 5, 5)));
    }

    #[test]
    fn test_rectangle_union() {
        let a = Rect::new(0, 0, 10, 10);
        let b = Rect::new(5, 5, 10, 10);

        let union = rectangle_union(&a, &b);
        assert_eq!(union, Rect::new(0, 0, 15, 15));

        // Union with non-overlapping
        let c = Rect::new(20, 20, 10, 10);
        let union2 = rectangle_union(&a, &c);
        assert_eq!(union2, Rect::new(0, 0, 30, 30));
    }

    #[test]
    fn test_rectangles_adjacent() {
        let a = Rect::new(0, 0, 10, 10);

        // Horizontally adjacent
        assert!(rectangles_adjacent(&a, &Rect::new(10, 0, 10, 10)));
        assert!(rectangles_adjacent(&a, &Rect::new(10, 5, 10, 5))); // Partial overlap on Y

        // Vertically adjacent
        assert!(rectangles_adjacent(&a, &Rect::new(0, 10, 10, 10)));
        assert!(rectangles_adjacent(&a, &Rect::new(5, 10, 5, 10))); // Partial overlap on X

        // Not adjacent (gap)
        assert!(!rectangles_adjacent(&a, &Rect::new(11, 0, 10, 10)));

        // Overlapping (not adjacent)
        assert!(!rectangles_adjacent(&a, &Rect::new(5, 5, 10, 10)));
    }

    #[test]
    fn test_coalesce_regions() {
        let mut regions = vec![
            Rect::new(0, 0, 10, 10),
            Rect::new(10, 0, 10, 10), // Adjacent
            Rect::new(5, 5, 5, 5),    // Overlapping with first
        ];

        let original_count = regions.len();
        let merged = coalesce_regions(&mut regions, 2.0);

        assert!(regions.len() < original_count);
        assert!(merged > 0);
    }

    #[test]
    fn test_topological_sort() {
        let mut deps = HashMap::new();
        deps.insert(
            "C".to_string(),
            ["A", "B"].iter().map(|s| s.to_string()).collect(),
        );
        deps.insert(
            "B".to_string(),
            ["A"].iter().map(|s| s.to_string()).collect(),
        );
        deps.insert("A".to_string(), HashSet::new());

        let sorted = topological_sort(&deps).unwrap();

        // A should come before B, B should come before C
        let pos_a = sorted.iter().position(|x| x == "A").unwrap();
        let pos_b = sorted.iter().position(|x| x == "B").unwrap();
        let pos_c = sorted.iter().position(|x| x == "C").unwrap();

        assert!(pos_a < pos_b);
        assert!(pos_b < pos_c);
    }

    #[test]
    fn test_topological_sort_cycle() {
        let mut deps = HashMap::new();
        deps.insert(
            "A".to_string(),
            ["B"].iter().map(|s| s.to_string()).collect(),
        );
        deps.insert(
            "B".to_string(),
            ["A"].iter().map(|s| s.to_string()).collect(),
        );

        let result = topological_sort(&deps);
        assert!(result.is_none()); // Should detect cycle
    }

    #[test]
    fn test_fnv1a_hash() {
        let hash1 = fnv1a_hash(b"hello");
        let hash2 = fnv1a_hash(b"hello");
        let hash3 = fnv1a_hash(b"world");

        assert_eq!(hash1, hash2); // Deterministic
        assert_ne!(hash1, hash3); // Different inputs (extremely likely)

        // Empty input
        let empty_hash = fnv1a_hash(b"");
        assert_ne!(empty_hash, 0); // Should not be zero
    }
}