1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#![no_std]
use smallvec::SmallVec;

pub type NodeIndex = usize;
pub type Generation = usize;
pub type NodeHandle = (NodeIndex, Generation);

pub enum GraphError {
    GenerationMismatch,
    Unexpected,
}

#[derive(Default)]
pub struct SmallGraph<T> {
    pub free: SmallVec<[NodeHandle; 128]>,
    pub nodes: SmallVec<[(Generation, Option<T>); 128]>,
    pub connections: SmallVec<[(NodeIndex, NodeIndex); 256]>,
}

impl<T> SmallGraph<T> {
    pub fn new() -> SmallGraph<T> {
        SmallGraph {
            free: SmallVec::new(),
            nodes: SmallVec::new(),
            connections: SmallVec::new(),
        }
    }

    pub fn insert(&mut self, value: T) -> NodeHandle {
        if self.free.len() == 0 {
            let index = self.nodes.len();
            let gen = 0;
            self.nodes.push((gen, Some(value)));
            (index, gen)
        } else {
            let n = self.free.remove(0);
            let index = n.0;
            let gen = n.1;
            self.nodes[index] = (gen + 1, Some(value));
            (n.0, gen + 1)
        }
    }

    pub fn directed_connect(&mut self, parent: NodeHandle, child: NodeHandle) {
        self.connections.push((parent.0, child.0));
    }

    pub fn connect(&mut self, a: NodeHandle, b: NodeHandle) {
        self.connections.push((a.0, b.0));
        self.connections.push((b.0, a.0));
    }

    pub fn disconnect(&mut self, n: NodeHandle) {
        self.connections
            .retain(|&mut connection| (connection).0 != n.0 && (connection).1 != n.0);
    }

    pub fn is_connected(&mut self, a: NodeHandle, b: NodeHandle) -> bool {
        self.connections
            .iter()
            .find(|&connection| {
                (connection.0 == a.0 && connection.1 == b.0)
                    || (connection.1 == a.0 && connection.0 == b.0)
            })
            .is_some()
    }

    pub fn is_directed_connected(&mut self, parent: NodeHandle, child: NodeHandle) -> bool {
        self.connections
            .iter()
            .find(|&connection| connection.0 == parent.0 && connection.1 == child.0)
            .is_some()
    }

    pub fn remove(&mut self, n: NodeHandle) -> Result<T, GraphError> {
        let index = n.0;
        let gen = n.1;
        if self.nodes[index].0 == gen {
            self.disconnect(n);
            let mut r = (gen + 1, None);
            core::mem::swap(&mut self.nodes[index], &mut r);
            self.free.push(n);
            Ok(r.1.unwrap())
        } else {
            Err(GraphError::GenerationMismatch)
        }
    }

    pub fn get(&self, n: NodeHandle) -> Result<&T, GraphError> {
        let index = n.0;
        let gen = n.1;
        if self.nodes[index].0 == gen {
            if let Some(value) = &self.nodes[index].1 {
                Ok(value)
            } else {
                Err(GraphError::Unexpected)
            }
        } else {
            Err(GraphError::GenerationMismatch)
        }
    }

    pub fn get_mut(&mut self, n: NodeHandle) -> Result<&mut T, GraphError> {
        let index = n.0;
        let gen = n.1;
        if self.nodes[index].0 == gen {
            if let Some(value) = &mut self.nodes[index].1 {
                Ok(value)
            } else {
                Err(GraphError::Unexpected)
            }
        } else {
            Err(GraphError::GenerationMismatch)
        }
    }
}