graph_d 1.3.2

//! Query engine for graph traversal and filtering.
//!
//! This module provides a fluent API for building and executing graph queries.
//! It supports common graph traversal patterns, filtering, aggregation, and
//! path finding operations.
//!
//! # Query Building
//!
//! The [`QueryBuilder`] provides a fluent interface for constructing complex
//! graph traversals. Queries are built by chaining operations and executed
//! lazily when results are requested.
//!
//! # Path Finding
//!
//! The [`PathFinder`] implements graph algorithms for finding paths between
//! nodes, including shortest path calculations using breadth-first search.
//!
//! # Example
//!
//! ```rust
//! use graph_d::{Graph, query::QueryBuilder};
//! use serde_json::json;
//! use std::collections::HashMap;
//!
//! # fn main() -> graph_d::Result<()> {
//! let mut graph = Graph::new()?;
//!
//! // Create nodes
//! let alice_id = graph.create_node([
//!     ("name".to_string(), json!("Alice")),
//!     ("age".to_string(), json!(30))
//! ].into())?;
//!
//! let bob_id = graph.create_node([
//!     ("name".to_string(), json!("Bob")),
//!     ("age".to_string(), json!(25))
//! ].into())?;
//!
//! // Create relationship
//! graph.create_relationship(alice_id, bob_id, "KNOWS".to_string(), HashMap::new())?;
//!
//! // Query: Find all people Alice knows who are under 30
//! let young_friends = QueryBuilder::from_node(&graph, alice_id)
//!     .outgoing("KNOWS")?
//!     .filter_by_property("age", &json!(25))?
//!     .nodes()?;
//!
//! assert_eq!(young_friends.len(), 1);
//! assert_eq!(young_friends[0].id, bob_id);
//! # Ok(())
//! # }
//! ```

pub mod aggregation;
pub mod sorting;

use crate::error::Result;
use crate::graph::{Graph, Id, Node};
use serde_json::Value;

pub use aggregation::{
    AggregateFunction, AggregateResult, Aggregator, Statistics, StatisticsResult,
};
pub use sorting::{AdvancedSorter, Pagination, SortCriteria, SortDirection, SortedPage, Sorter};

/// A fluent query builder for graph traversals.
///
/// The [`QueryBuilder`] provides a chainable API for constructing complex graph
/// queries. It maintains a current set of nodes and allows traversing relationships,
/// filtering by properties, and applying aggregation functions.
///
/// # Design Principles
///
/// - **Fluent Interface**: Method chaining for readable query construction
/// - **Lazy Evaluation**: Operations are applied when results are requested
/// - **Type Safety**: Compile-time verification of query structure
/// - **Memory Efficient**: Only stores node IDs until final materialization
///
/// # Query Operations
///
/// - **Traversal**: [`outgoing`], [`incoming`], [`either`]
/// - **Filtering**: [`filter_by_property`]
/// - **Aggregation**: [`aggregate`], [`statistics`]
/// - **Sorting**: [`sort`], [`sorted_page`]
/// - **Pagination**: [`paginate`]
/// - **Grouping**: [`group_by_sorted`]
///
/// # Performance Considerations
///
/// - Use indexed properties for filtering when possible
/// - Apply filters early to reduce intermediate result sets
/// - Consider pagination for large result sets
/// - Group operations are expensive on large datasets
///
/// # Example
///
/// ```rust
/// use graph_d::{Graph, query::QueryBuilder};
/// use serde_json::json;
/// use std::collections::HashMap;
///
/// # fn main() -> graph_d::Result<()> {
/// let mut graph = Graph::new()?;
/// let start_node = graph.create_node(HashMap::new())?;
///
/// // Multi-hop traversal with filtering
/// let result = QueryBuilder::from_node(&graph, start_node)
///     .outgoing("FOLLOWS")?
///     .outgoing("LIKES")?
///     .filter_by_property("category", &json!("music"))?
///     .nodes()?;
/// # Ok(())
/// # }
/// ```
///
/// # Future Enhancements
///
/// A production system would include:
/// - Query optimization and planning
/// - Cost-based execution strategies
/// - Support for complex predicates
/// - Join operations across multiple starting points
///
/// [`outgoing`]: QueryBuilder::outgoing
/// [`incoming`]: QueryBuilder::incoming
/// [`either`]: QueryBuilder::either
/// [`filter_by_property`]: QueryBuilder::filter_by_property
/// [`aggregate`]: QueryBuilder::aggregate
/// [`statistics`]: QueryBuilder::statistics
/// [`sort`]: QueryBuilder::sort
/// [`sorted_page`]: QueryBuilder::sorted_page
/// [`paginate`]: QueryBuilder::paginate
/// [`group_by_sorted`]: QueryBuilder::group_by_sorted
pub struct QueryBuilder<'a> {
    graph: &'a Graph,
    current_nodes: Vec<Id>,
}

impl<'a> QueryBuilder<'a> {
    /// Create a new query builder starting from the given node IDs.
    pub fn new(graph: &'a Graph, start_nodes: Vec<Id>) -> Self {
        QueryBuilder {
            graph,
            current_nodes: start_nodes,
        }
    }

    /// Start a query from a single node.
    pub fn from_node(graph: &'a Graph, node_id: Id) -> Self {
        Self::new(graph, vec![node_id])
    }

    /// Traverse outgoing relationships of the given type.
    pub fn outgoing(mut self, rel_type: &str) -> Result<Self> {
        let mut next_nodes = Vec::new();

        for &node_id in &self.current_nodes {
            let relationships = self.graph.get_relationships_for_node(node_id)?;

            for rel in relationships {
                if rel.rel_type == rel_type && rel.is_outgoing_from(node_id) {
                    next_nodes.push(rel.to_id);
                }
            }
        }

        self.current_nodes = next_nodes;
        Ok(self)
    }

    /// Traverse incoming relationships of the given type.
    pub fn incoming(mut self, rel_type: &str) -> Result<Self> {
        let mut next_nodes = Vec::new();

        for &node_id in &self.current_nodes {
            let relationships = self.graph.get_relationships_for_node(node_id)?;

            for rel in relationships {
                if rel.rel_type == rel_type && rel.is_incoming_to(node_id) {
                    next_nodes.push(rel.from_id);
                }
            }
        }

        self.current_nodes = next_nodes;
        Ok(self)
    }

    /// Traverse relationships in either direction.
    pub fn either(mut self, rel_type: &str) -> Result<Self> {
        let mut next_nodes = Vec::new();

        for &node_id in &self.current_nodes {
            let relationships = self.graph.get_relationships_for_node(node_id)?;

            for rel in relationships {
                if rel.rel_type == rel_type {
                    if rel.is_outgoing_from(node_id) {
                        next_nodes.push(rel.to_id);
                    } else if rel.is_incoming_to(node_id) {
                        next_nodes.push(rel.from_id);
                    }
                }
            }
        }

        self.current_nodes = next_nodes;
        Ok(self)
    }

    /// Filter nodes by a property condition.
    pub fn filter_by_property(mut self, key: &str, value: &Value) -> Result<Self> {
        let mut filtered_nodes = Vec::new();

        for &node_id in &self.current_nodes {
            if let Some(node) = self.graph.get_node(node_id)? {
                if node.get_property(key) == Some(value) {
                    filtered_nodes.push(node_id);
                }
            }
        }

        self.current_nodes = filtered_nodes;
        Ok(self)
    }

    /// Get the current node IDs in the query result.
    pub fn node_ids(&self) -> &[Id] {
        &self.current_nodes
    }

    /// Get the current nodes in the query result.
    pub fn nodes(&self) -> Result<Vec<Node>> {
        let mut nodes = Vec::new();

        for &node_id in &self.current_nodes {
            if let Some(node) = self.graph.get_node(node_id)? {
                nodes.push(node);
            }
        }

        Ok(nodes)
    }

    /// Count the number of nodes in the current result.
    pub fn count(&self) -> usize {
        self.current_nodes.len()
    }

    /// Check if the query result is empty.
    pub fn is_empty(&self) -> bool {
        self.current_nodes.is_empty()
    }

    /// Apply an aggregation function to the current nodes.
    pub fn aggregate(&self, function: AggregateFunction) -> Result<AggregateResult> {
        let nodes = self.nodes()?;
        Aggregator::aggregate(&nodes, &function)
    }

    /// Sort the current nodes by the given criteria.
    pub fn sort(mut self, criteria: Vec<SortCriteria>) -> Result<Self> {
        let nodes = self.nodes()?;
        let sorted_nodes = Sorter::sort_nodes(nodes, &criteria);

        self.current_nodes = sorted_nodes.into_iter().map(|node| node.id).collect();
        Ok(self)
    }

    /// Apply pagination to the current results.
    pub fn paginate(mut self, pagination: Pagination) -> Result<Self> {
        let paginated_ids = pagination.apply(self.current_nodes);
        self.current_nodes = paginated_ids;
        Ok(self)
    }

    /// Get sorted and paginated nodes.
    pub fn sorted_page(
        &self,
        criteria: Vec<SortCriteria>,
        pagination: Pagination,
    ) -> Result<SortedPage<Node>> {
        let nodes = self.nodes()?;
        Ok(AdvancedSorter::sort_nodes_paginated(
            nodes, &criteria, pagination,
        ))
    }

    /// Calculate statistics for a numeric property.
    pub fn statistics(&self, property: &str) -> Result<StatisticsResult> {
        let nodes = self.nodes()?;
        Statistics::calculate(&nodes, property)
    }

    /// Group nodes by a property and sort within groups.
    pub fn group_by_sorted(
        &self,
        group_property: &str,
        sort_criteria: Vec<SortCriteria>,
    ) -> Result<std::collections::BTreeMap<String, Vec<Node>>> {
        let nodes = self.nodes()?;
        Ok(AdvancedSorter::sort_and_group_nodes(
            nodes,
            group_property,
            &sort_criteria,
        ))
    }
}

/// Path finding algorithms for graph connectivity analysis.
///
/// The [`PathFinder`] implements various graph algorithms for finding paths
/// and analyzing connectivity between nodes. It provides efficient implementations
/// of common graph traversal algorithms.
///
/// # Algorithms
///
/// - **Shortest Path**: Breadth-first search for unweighted shortest paths
/// - **Path Existence**: Quick connectivity checks
/// - **Multi-hop Traversal**: Support for relationship type filtering
///
/// # Performance
///
/// - **Time Complexity**: O(V + E) for BFS where V=nodes, E=relationships
/// - **Space Complexity**: O(V) for visited set and queue
/// - **Memory Efficient**: Only stores necessary state during traversal
///
/// # Example
///
/// ```rust
/// use graph_d::{Graph, query::PathFinder};
/// use std::collections::HashMap;
///
/// # fn main() -> graph_d::Result<()> {
/// let mut graph = Graph::new()?;
///
/// // Create a path: A -> B -> C
/// let node_a = graph.create_node(HashMap::new())?;
/// let node_b = graph.create_node(HashMap::new())?;
/// let node_c = graph.create_node(HashMap::new())?;
///
/// graph.create_relationship(node_a, node_b, "CONNECTS".to_string(), HashMap::new())?;
/// graph.create_relationship(node_b, node_c, "CONNECTS".to_string(), HashMap::new())?;
///
/// let path_finder = PathFinder::new(&graph);
/// let path = path_finder.shortest_path(node_a, node_c)?;
///
/// assert_eq!(path, Some(vec![node_a, node_b, node_c]));
/// # Ok(())
/// # }
/// ```
///
/// # Use Cases
///
/// - **Social Networks**: Find connection paths between users
/// - **Recommendation Systems**: Discover related items through associations
/// - **Dependency Analysis**: Trace dependencies in system graphs
/// - **Network Analysis**: Analyze connectivity in infrastructure graphs
///
/// # Future Extensions
///
/// - Weighted shortest paths (Dijkstra's algorithm)
/// - All-pairs shortest paths (Floyd-Warshall)
/// - Relationship type filtering during traversal
/// - K-shortest paths algorithms
pub struct PathFinder<'a> {
    graph: &'a Graph,
}

impl<'a> PathFinder<'a> {
    /// Create a new path finder.
    pub fn new(graph: &'a Graph) -> Self {
        PathFinder { graph }
    }

    /// Find the shortest path between two nodes (BFS).
    /// Returns the sequence of node IDs in the path, or None if no path exists.
    pub fn shortest_path(&self, from_id: Id, to_id: Id) -> Result<Option<Vec<Id>>> {
        if from_id == to_id {
            return Ok(Some(vec![from_id]));
        }

        let mut queue = std::collections::VecDeque::new();
        let mut visited = std::collections::HashSet::new();
        let mut parent = std::collections::HashMap::new();

        queue.push_back(from_id);
        visited.insert(from_id);

        while let Some(current_id) = queue.pop_front() {
            let relationships = self.graph.get_relationships_for_node(current_id)?;

            for rel in relationships {
                let next_id = if rel.is_outgoing_from(current_id) {
                    rel.to_id
                } else if rel.is_incoming_to(current_id) {
                    rel.from_id
                } else {
                    continue;
                };

                if next_id == to_id {
                    // Found the target, reconstruct path
                    let mut path = vec![to_id, current_id];
                    let mut current = current_id;

                    while let Some(&prev) = parent.get(&current) {
                        path.push(prev);
                        current = prev;
                    }

                    path.reverse();
                    return Ok(Some(path));
                }

                if !visited.contains(&next_id) {
                    visited.insert(next_id);
                    parent.insert(next_id, current_id);
                    queue.push_back(next_id);
                }
            }
        }

        Ok(None)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use serde_json::json;
    use std::collections::HashMap;

    #[test]
    fn test_query_builder() {
        let mut graph = Graph::new().unwrap();

        // Create nodes
        let node1_id = graph
            .create_node([("name".to_string(), json!("Alice"))].into())
            .unwrap();
        let node2_id = graph
            .create_node([("name".to_string(), json!("Bob"))].into())
            .unwrap();
        let node3_id = graph
            .create_node([("name".to_string(), json!("Charlie"))].into())
            .unwrap();

        // Create relationships
        graph
            .create_relationship(node1_id, node2_id, "KNOWS".to_string(), HashMap::new())
            .unwrap();
        graph
            .create_relationship(node2_id, node3_id, "KNOWS".to_string(), HashMap::new())
            .unwrap();

        // Query: find all nodes that Alice knows
        let query_result = QueryBuilder::from_node(&graph, node1_id)
            .outgoing("KNOWS")
            .unwrap();
        let result = query_result.node_ids();

        assert_eq!(result.len(), 1);
        assert_eq!(result[0], node2_id);

        // Query: find all nodes that know someone named "Charlie"
        let query_result = QueryBuilder::new(&graph, vec![node1_id, node2_id, node3_id])
            .outgoing("KNOWS")
            .unwrap()
            .filter_by_property("name", &json!("Charlie"))
            .unwrap();
        let result = query_result.count();

        assert_eq!(result, 1);
    }

    #[test]
    fn test_path_finder() {
        let mut graph = Graph::new().unwrap();

        // Create a simple path: 1 -> 2 -> 3
        let node1_id = graph.create_node(HashMap::new()).unwrap();
        let node2_id = graph.create_node(HashMap::new()).unwrap();
        let node3_id = graph.create_node(HashMap::new()).unwrap();

        graph
            .create_relationship(node1_id, node2_id, "CONNECTS".to_string(), HashMap::new())
            .unwrap();
        graph
            .create_relationship(node2_id, node3_id, "CONNECTS".to_string(), HashMap::new())
            .unwrap();

        let path_finder = PathFinder::new(&graph);
        let path = path_finder.shortest_path(node1_id, node3_id).unwrap();

        assert_eq!(path, Some(vec![node1_id, node2_id, node3_id]));
    }
}