Closed pnevyk closed 1 year ago
An idea that I tried:
The core trait
pub trait InStorage<V, E, Ty: EdgeType> {
type Storage;
fn into_storage(self) -> Self::Storage;
}
Specific implementation for a storage, so one can use Graph<V, E, Ty, InAdjList<DefaultIndexing>>
#[derive(Debug, Clone)]
pub struct InAdjList<Ix: Indexing> {
ix: PhantomData<Ix>,
}
impl<Ix: Indexing> Default for InAdjList<Ix> {
fn default() -> Self {
Self { ix: PhantomData }
}
}
impl<V, E, Ty: EdgeType, Ix: Indexing> super::InStorage<V, E, Ty> for InAdjList<Ix> {
type Storage = AdjList<V, E, Ty, Ix>;
fn into_storage(self) -> Self::Storage {
AdjList::new()
}
}
Generic implementation as a default for custom storages and adapters such as Stable
and Frozen
#[derive(Debug, Default, Clone)]
pub struct In<S> {
inner: S,
}
impl<V, E, Ty: EdgeType, S> InStorage<V, E, Ty> for In<S> {
type Storage = S;
fn into_storage(self) -> Self::Storage {
self.inner
}
}
The Graph type
pub struct Graph<
V,
E,
Ty: EdgeType,
S: InStorage<V, E, Ty, Storage = G> = InAdjList<DefaultIndexing>,
G = <S as InStorage<V, E, Ty>>::Storage,
> {
#[graph]
storage: G,
ty: PhantomData<(V, E, Ty, S)>,
}
impl<V, E, Ty: EdgeType, G> Graph<V, E, Ty, In<G>> {
pub fn new_in(storage: G) -> Self {
Self {
storage,
ty: PhantomData,
}
}
}
impl<V, E, Ty: EdgeType, S> Default for Graph<V, E, Ty, S>
where
S: InStorage<V, E, Ty> + Default,
{
fn default() -> Self {
Self::new_impl(S::default().into_storage())
}
}
impl<V, E, Ty: EdgeType, S, G> Graph<V, E, Ty, S, G>
where
S: InStorage<V, E, Ty, Storage = G>,
{
pub fn add_vertex(&mut self, vertex: V) -> G::VertexIndex
where
G: VerticesMut<V>,
{
self.storage.add_vertex(vertex)
}
// ...
}
This ought to simplify the generics of Graph
so one does not need to type V
, E
and Ty
twice in Graph<V, E, Ty, AdjList<V, E, Ty>>
. Well, this is achieved, but the generics overall are even worse, much more complicated. This is not worthy. Even nalgebra
crate (otherwise quite magical with generic types) is fine with redundant occurrences of T
(numeric type), R
(rows dimension) and C
(columns dimension) for their storage.
I am closing this issue. If anyone comes up with a clean solution in the future, we can reopen.
Currently, the full signature for a graph type with a specific storage looks like this
This is scary and also repeating the types for vertices, edges and direction feels redundant. Of course one could use
_
placeholder, but still.Ideally, there is a mechanism that would simplify the signature to something like this:
MagicAdjList
would be a separate type that would know how to createAdjList
givenV
,E
andTy
. Or something like that. This definitely needs more thought and experiments.BuildHasher
from the standard library came to mind, but maybe it's a useless reference.