unobtanium-graph-algorithms 0.1.0

// SPDX-FileCopyrightText: 2025 Slatian 2025
//
// SPDX-License-Identifier: LGPL-3.0-only

use core::hash::Hash;
use std::marker::PhantomData;
use std::ops::Deref;

use crate::graph::Graph;
use crate::node::NodeId;

#[derive(Default, Clone, Copy)]
struct InvariantLifetime<'id>(PhantomData<*mut &'id ()>);

/// Mutable version of [Graph] which you can use inside the callback given to
/// [Graph::modify].
///
/// This is implemented using the branding mechanism from the [GhostCell Paper](https://plv.mpi-sws.org/rustbelt/ghostcell/).
pub struct MutableGraph<'id, T: Eq + Hash + Clone> {
	graph: &'id mut Graph<T>,
	_marker: InvariantLifetime<'id>,
}

/// A Node identifier that is strongly coupled to the [MutableGraph] it belongs into.
///
/// You can obtain one using [MutableGraph::fetch_id_for_data].
///
/// You can use this one to add nodes and edges to the graph.
///
/// In case you are using multiple graphs and run into liftime errors
/// check if you're mixing ids from multiple graphs.
#[derive(Clone, Copy)]
pub struct BrandedNodeId<'id> {
	inner: NodeId,
	_marker: InvariantLifetime<'id>,
}

impl PartialEq for BrandedNodeId<'_> {
	fn eq(&self, other: &Self) -> bool {
	     self.inner == other.inner
	}
}

impl Eq for BrandedNodeId<'_> { /* empty */ }

impl Hash for BrandedNodeId<'_> {
	fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
	     self.inner.hash(state);
	}
}

impl PartialOrd for BrandedNodeId<'_> {
	fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
	     Some(self.cmp(other))
	}
}

impl Ord for BrandedNodeId<'_> {
	fn cmp(&self, other: &Self) -> std::cmp::Ordering {
	    self.inner.cmp(&other.inner)
	}
}

impl<'id, T: Eq + Hash + Clone> MutableGraph<'id, T> {

	/// Creates a new MutableGraph for a given [Graph] that can be used inside the callback.
	///
	/// Prefer using the [Graph::modify] method.
	#[allow(clippy::new_ret_no_self)]
	pub fn new<F, R>(graph: &'id mut Graph<T>, callback: F) -> R
	where
		for<'new_id> F: FnOnce(MutableGraph<'new_id, T>) -> R,
	{
		callback(Self {
			graph,
			_marker: Default::default(),
		})
	}

	/// Fetch an identifier for a given data structure.
	///
	/// If this instance of `data` (as determined by the [Hash] and [Eq] traits) already exists in the graph the resulting id will refer to the same node in the graph.
	///
	/// If the argument is an instance of `data` that is not already in the graph it will automatically be added.
	pub fn fetch_id_for_data(&mut self, data: &T) -> BrandedNodeId<'id> {
		BrandedNodeId {
			inner: self.graph.fetch_id_for_data(data),
			_marker: Default::default(),
		}
	}

	/// Given a node id this returns a borrow of the data behind that node.
	pub fn get_node_data_for_id(&self, id: BrandedNodeId<'id>) -> Option<&T> {
		self.graph.get_node_data_for_id(id.inner)
	}

	/// Add a directional vertex (connection) between two nodes with a weight of `1.0`.
	#[inline(always)]
	pub fn add_edge(&mut self, from: BrandedNodeId<'id>, to: BrandedNodeId<'id>) {
		self.add_edge_weighted(from, to, 1.0);
	}

	/// Add a directional vertex (connection) between two nodes with a custom weight.
	#[inline(always)]
	pub fn add_edge_weighted(
		&mut self,
		from: BrandedNodeId<'id>,
		to: BrandedNodeId<'id>,
		weight: f32,
	) {
		self.graph.add_edge_weighted(from.inner, to.inner, weight);
	}
}

impl<'id, T: Eq + Hash + Clone> Deref for MutableGraph<'id, T> {
	type Target = Graph<T>;

	fn deref(&self) -> &Self::Target {
		self.graph
	}
}