bounded_graph 0.3.0

use petgraph::{csr::IndexType, graph::DefaultIx, Direction};

/// Trait for nodes that can enforce edge count constraints.
///
/// Implementors of this trait define the logic for determining whether an edge can be added
/// to a node, based on the direction of the edge, the current number of edges, and potentially
/// the properties of the other node.
///
/// For simple cases where nodes only need to track maximum edge counts, implement the
/// [`EdgeBounds`] and [`SimpleEdgeBounds`] traits instead, which provide a blanket
/// implementation of `BoundedNode`.
///
/// # Examples
///
/// For custom logic:
/// ```
/// use petgraph::Direction;
/// use bounded_graph::BoundedNode;
/// use petgraph::graph::DefaultIx;
///
/// struct SimpleNode {}
///
/// impl BoundedNode for SimpleNode {
///     fn can_add_edge(&self, dir: Direction, existing_edge_count: usize, _other_node: &Self) -> bool {
///         // custom logic here!
///        true
///     }
/// }
/// ```
pub trait BoundedNode<Ix: IndexType = DefaultIx> {
    /// Determines if an edge can be added to this node.
    ///
    /// # Arguments
    ///
    /// * `dir` - The direction of the edge relative to this node
    /// * `existing_edge_count` - The current number of edges in this direction
    /// * `other_node` - The node at the other end of the potential edge
    ///
    /// # Returns
    ///
    /// `true` if the edge can be added, `false` otherwise.
    fn can_add_edge(&self, dir: Direction, existing_edge_count: usize, other_node: &Self) -> bool;
}

/// Trait for nodes with simple numeric edge count bounds.
///
/// This trait provides a convenient way to define nodes that have maximum
/// incoming and outgoing edge counts. Types implementing this trait and the
/// marker trait [`SimpleEdgeBounds`] automatically receive a [`BoundedNode`]
/// implementation that checks edge counts without considering properties of
/// the other node.
///
/// The bounds returned by this trait don't need to be compile-time constants,
/// but if you want mutable access to node data (via [`ImmutableEdgeBounds`]),
/// the values must never change after the node is created.
///
/// For more complex logic (e.g., constraints based on node properties),
/// implement [`BoundedNode`] directly instead.
///
/// # Examples
///
/// ```
/// use petgraph::graph::DefaultIx;
/// use bounded_graph::{EdgeBounds, SimpleEdgeBounds};
///
/// struct MyNode {
///     max_in: usize,
///     max_out: usize,
/// }
///
/// impl EdgeBounds for MyNode {
///     fn max_incoming_edges(&self) -> DefaultIx {
///         self.max_in as DefaultIx
///     }
///
///     fn max_outgoing_edges(&self) -> DefaultIx {
///         self.max_out as DefaultIx
///     }
/// }
///
/// // This marker trait enables the automatic BoundedNode implementation
/// impl SimpleEdgeBounds for MyNode {}
/// ```
pub trait EdgeBounds<Ix: IndexType = DefaultIx> {
    /// Returns the maximum number of incoming edges this node can have.
    fn max_incoming_edges(&self) -> Ix;

    /// Returns the maximum number of outgoing edges this node can have.
    fn max_outgoing_edges(&self) -> Ix;
}

/// Marker trait indicating that a node uses simple edge count logic.
///
/// Types implementing both this trait and [`EdgeBounds`] automatically get a
/// [`BoundedNode`] implementation that only checks edge counts, without considering
/// properties of the other node.
///
/// This is useful for the common case where nodes have fixed edge limits that don't
/// depend on what they're connecting to.
pub trait SimpleEdgeBounds {}

/// Marker trait indicating that a node's edge restrictions cannot be mutated after creation.
///
/// This trait is a safety marker that indicates the edge limit constraints of a node
/// are immutable and cannot be changed after construction. Only types implementing this
/// trait will have mutable access to their node weights through petgraph's [`DataMapMut`](petgraph::data::DataMapMut) trait.
///
/// # Compatibility
///
/// This trait can be implemented on any [`BoundedNode`] type, whether using [`EdgeBounds`]
/// or implementing [`BoundedNode`] directly with custom logic.
///
/// # Safety Requirements
///
/// Implementing this trait asserts that:
/// - The logic in [`BoundedNode::can_add_edge`] will never change behavior for the lifetime
///   of the node, regardless of any mutations to the node's data.
/// - For types using [`EdgeBounds`]: the return values of [`EdgeBounds::max_incoming_edges`]
///   and [`EdgeBounds::max_outgoing_edges`] will never change.
/// - The edge bounds are determined by compile-time constants, type parameters, or immutable fields.
///
/// # Examples
///
/// Safe implementation with [`EdgeBounds`] (using const generics):
/// ```
/// use bounded_graph::{EdgeBounds, ImmutableEdgeBounds, SimpleEdgeBounds};
/// use petgraph::graph::DefaultIx;
///
/// struct SafeNode<const MAX: usize> {
///     data: String,  // Mutable data is fine
/// }
///
/// impl<const MAX: usize> EdgeBounds for SafeNode<MAX> {
///     fn max_incoming_edges(&self) -> DefaultIx { MAX as DefaultIx }
///     fn max_outgoing_edges(&self) -> DefaultIx { MAX as DefaultIx }
/// }
///
/// impl<const MAX: usize> SimpleEdgeBounds for SafeNode<MAX> {}
///
/// // Safe: MAX is a const generic, cannot be mutated
/// impl<const MAX: usize> ImmutableEdgeBounds for SafeNode<MAX> {}
/// ```
///
/// Safe implementation with custom [`BoundedNode`]:
/// ```
/// use bounded_graph::{BoundedNode, ImmutableEdgeBounds};
/// use petgraph::{Direction, graph::DefaultIx};
///
/// struct CustomNode {
///     label: String,  // Mutable data
/// }
///
/// impl BoundedNode for CustomNode {
///     fn can_add_edge(&self, _dir: Direction, count: usize, _other: &Self) -> bool {
///         count < 5  // Fixed logic, doesn't depend on mutable state
///     }
/// }
///
/// // Safe: edge logic doesn't depend on mutable fields
/// impl ImmutableEdgeBounds for CustomNode {}
/// ```
///
/// Unsafe nodes cannot use DataMapMut (this will NOT compile):
/// ```compile_fail
/// # use bounded_graph::{BoundedGraph, EdgeBounds, SimpleEdgeBounds};
/// # use petgraph::graph::DefaultIx;
/// # use petgraph::data::DataMapMut;
/// struct UnsafeNode {
///     max_edges: usize,  // This can be mutated!
/// }
///
/// impl EdgeBounds for UnsafeNode {
///     fn max_incoming_edges(&self) -> DefaultIx { self.max_edges as DefaultIx }
///     fn max_outgoing_edges(&self) -> DefaultIx { self.max_edges as DefaultIx }
/// }
///
/// impl SimpleEdgeBounds for UnsafeNode {}
/// // NOTE: We do NOT implement ImmutableEdgeBounds
///
/// let mut graph = BoundedGraph::<UnsafeNode, ()>::new();
/// let n = graph.add_node(UnsafeNode { max_edges: 2 });
/// // This will NOT compile because UnsafeNode lacks ImmutableEdgeBounds:
/// DataMapMut::node_weight_mut(&mut graph, n);
/// ```
///
/// # Relation to Other Traits
///
/// This trait works with the graph's trait implementations:
/// - Types with `ImmutableEdgeBounds` get mutable access via [`DataMapMut`](petgraph::data::DataMapMut)
///   and [`IndexMut`](std::ops::IndexMut) (e.g., `graph[node_id] = new_value`).
/// - Types without it can still use [`DataMap`](petgraph::data::DataMap) and [`Index`](std::ops::Index)
///   for read-only access (e.g., `&graph[node_id]`).
pub trait ImmutableEdgeBounds {}

// Blanket implementation: types with EdgeBounds + SimpleEdgeBounds automatically get BoundedNode
impl<Ix: IndexType, T: EdgeBounds<Ix> + SimpleEdgeBounds> BoundedNode<Ix> for T {
    fn can_add_edge(&self, dir: Direction, existing_edge_count: usize, _other_node: &Self) -> bool {
        let max = match dir {
            Direction::Incoming => self.max_incoming_edges(),
            Direction::Outgoing => self.max_outgoing_edges(),
        };
        Ix::new(existing_edge_count) < max
    }
}