amazed/graph/
mod.rs

1use std::collections::HashMap;
2
3#[derive(Clone, Debug, Eq, PartialEq)]
4pub struct NodeLabel(usize);
5
6#[derive(Debug, Clone, PartialEq)]
7pub struct Neighbors<const MAX_NEIGHBORS: usize>([Option<usize>; MAX_NEIGHBORS], usize);
8
9#[derive(Debug, PartialEq)]
10pub enum AddEdgeError {
11    Overflow,
12    Exists
13}
14
15pub fn option_less_than(p: &Option<usize>,q: &Option<usize>) -> std::cmp::Ordering{
16    match (p,q) {
17        (Some(_), None) => std::cmp::Ordering::Less,
18        (None, Some(_)) => std::cmp::Ordering::Greater,
19        (None, None) => std::cmp::Ordering::Equal,
20        (Some(x), Some(y)) => x.cmp(y)
21    }
22} 
23
24impl<const MAX_NEIGHBORS: usize> Neighbors<MAX_NEIGHBORS> {
25    pub fn append(&mut self, node_id: usize) -> Result<&mut Self, AddEdgeError> {
26        if self.1 < MAX_NEIGHBORS {
27            match self.0.binary_search_by(|x| option_less_than(x,&Some(node_id))) {
28                Ok(_) => Err(AddEdgeError::Exists),
29                Err(pos) => {
30                    if pos != self.1 {
31                        self.0.copy_within(pos..self.1, pos+1);
32                    } 
33                    self.0[pos] = Some(node_id);
34                    self.1 += 1;
35
36                    Ok(self)
37                }
38            }
39        } else {
40            Err(AddEdgeError::Overflow)
41        }
42    }
43}
44
45impl<const N: usize, const MAX_NEIGHBORS: usize> From<&[usize; N]> for Neighbors<MAX_NEIGHBORS> {
46    fn from(neighbors: &[usize; N]) -> Neighbors<MAX_NEIGHBORS> {
47        let mut ns = Neighbors([None; MAX_NEIGHBORS], N);
48
49        ns.0[0..N].copy_from_slice( &neighbors.map(|x|Some(x)) );
50
51        ns
52    }
53}
54
55impl<const MAX_NEIGHBORS: usize> From<&[Option<usize>; MAX_NEIGHBORS]> for Neighbors<MAX_NEIGHBORS> {
56    fn from(neighbors: &[Option<usize>; MAX_NEIGHBORS]) -> Neighbors<MAX_NEIGHBORS> {
57        let first_null = neighbors.iter().position(|x| x.is_none()).unwrap_or(MAX_NEIGHBORS);
58
59        Neighbors::<MAX_NEIGHBORS>(*neighbors, first_null)
60    }
61}
62
63pub type GraphNodes<const MAX_NEIGHBORS: usize> = HashMap<usize, Neighbors<MAX_NEIGHBORS>>;
64
65#[derive(Clone, Debug)]
66pub struct Graph<const MAX_NEIGHBORS: usize>(GraphNodes<MAX_NEIGHBORS>);
67
68impl<const MAX_NEIGHBORS: usize> std::ops::Deref for Graph<MAX_NEIGHBORS> {
69    type Target = GraphNodes<MAX_NEIGHBORS>;
70
71    fn deref(&self) -> &GraphNodes<MAX_NEIGHBORS> {
72        &self.0
73    }
74}
75
76impl<const MAX_NEIGHBORS: usize> std::ops::DerefMut for Graph<MAX_NEIGHBORS> {
77    fn deref_mut(&mut self) -> &mut GraphNodes<MAX_NEIGHBORS> {
78        &mut self.0
79    }
80}
81
82#[derive(Debug, PartialEq)]
83pub enum InsertEdgeError {
84    FromMissing,
85    AppendEdgeError(AddEdgeError)
86}
87
88impl<const MAX_NEIGHBORS: usize> Graph<MAX_NEIGHBORS> {
89    pub fn new() -> Self {
90        Graph(GraphNodes::new())
91    }
92
93    pub fn insert<const N: usize>(&mut self, node_id: usize, neighbors: &[usize; N]) {
94        self.0.insert(node_id, Neighbors::from(neighbors));
95    }
96
97    pub fn insert_edge(&mut self, from: usize, to: usize) -> Result<&mut Self, InsertEdgeError> {
98        if let Some(from_node) = self.0.get_mut(&from) {
99            match from_node.append(to) {
100                Ok(_) => Ok(self),
101                Err(e) => Err(InsertEdgeError::AppendEdgeError(e))
102            }
103        } else {
104            Err(InsertEdgeError::FromMissing)
105        }
106    }
107}
amazed/graph/mod.rs

amazed/graph/
mod.rs
