use std::collections::{BTreeMap, BTreeSet, VecDeque};
use thiserror::Error;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct DeviceId(pub [u8; 8]);
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct LinkHealth {
pub rssi_dbm: i16,
pub reliability: f32,
pub age_seconds: u32,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct NodeState {
pub id: DeviceId,
pub nickname: u16,
pub active: bool,
}
#[derive(Debug, Clone, Default)]
pub struct MeshGraph {
nodes: BTreeMap<DeviceId, NodeState>,
links: BTreeMap<(DeviceId, DeviceId), LinkHealth>,
adjacency: BTreeMap<DeviceId, BTreeSet<DeviceId>>,
}
impl MeshGraph {
pub fn upsert_node(&mut self, node: NodeState) -> Option<NodeState> {
self.adjacency.entry(node.id).or_default();
self.nodes.insert(node.id, node)
}
pub fn remove_node(&mut self, id: DeviceId) -> Option<NodeState> {
if let Some(neighbors) = self.adjacency.remove(&id) {
for neighbor in neighbors {
if let Some(entries) = self.adjacency.get_mut(&neighbor) {
entries.remove(&id);
}
}
}
self.links
.retain(|(left, right), _| *left != id && *right != id);
self.nodes.remove(&id)
}
pub fn update_link(&mut self, left: DeviceId, right: DeviceId, health: LinkHealth) -> bool {
if left == right
|| !health.reliability.is_finite()
|| !(0.0..=1.0).contains(&health.reliability)
|| !self.nodes.contains_key(&left)
|| !self.nodes.contains_key(&right)
{
return false;
}
self.links.insert(ordered_pair(left, right), health);
self.adjacency.entry(left).or_default().insert(right);
self.adjacency.entry(right).or_default().insert(left);
true
}
pub fn route(
&self,
source: DeviceId,
destination: DeviceId,
minimum_reliability: f32,
) -> Option<Route> {
if !minimum_reliability.is_finite() || !(0.0..=1.0).contains(&minimum_reliability) {
return None;
}
if !self.nodes.get(&source).is_some_and(|node| node.active)
|| !self.nodes.get(&destination).is_some_and(|node| node.active)
{
return None;
}
if source == destination {
return Some(Route { hops: vec![source] });
}
let mut queue = VecDeque::from([source]);
let mut previous = BTreeMap::new();
let mut visited = BTreeSet::from([source]);
while let Some(current) = queue.pop_front() {
for neighbor in self.neighbors(current, minimum_reliability) {
if !visited.insert(neighbor) {
continue;
}
previous.insert(neighbor, current);
if neighbor == destination {
return reconstruct_route(source, destination, &previous);
}
queue.push_back(neighbor);
}
}
None
}
pub fn node_count(&self) -> usize {
self.nodes.len()
}
pub fn link_count(&self) -> usize {
self.links.len()
}
pub fn node(&self, id: DeviceId) -> Option<&NodeState> {
self.nodes.get(&id)
}
fn neighbors(
&self,
id: DeviceId,
minimum_reliability: f32,
) -> impl Iterator<Item = DeviceId> + '_ {
self.adjacency
.get(&id)
.into_iter()
.flatten()
.copied()
.filter(move |candidate| {
self.links
.get(&ordered_pair(id, *candidate))
.is_some_and(|health| health.reliability >= minimum_reliability)
&& self.nodes.get(candidate).is_some_and(|node| node.active)
})
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Route {
pub hops: Vec<DeviceId>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CellDirection {
Transmit,
Receive,
Shared,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Cell {
pub timeslot: u16,
pub channel_offset: u8,
pub source: DeviceId,
pub destination: DeviceId,
pub direction: CellDirection,
}
#[derive(Debug, Clone, Default)]
pub struct Schedule {
superframe_size: u16,
cells: Vec<Cell>,
}
impl Schedule {
pub fn new(superframe_size: u16) -> Result<Self, ScheduleError> {
if superframe_size == 0 {
return Err(ScheduleError::EmptySuperframe);
}
Ok(Self {
superframe_size,
cells: Vec::new(),
})
}
pub fn insert(&mut self, cell: Cell) -> Result<(), ScheduleError> {
if cell.timeslot >= self.superframe_size {
return Err(ScheduleError::Timeslot(cell.timeslot));
}
if cell.channel_offset > 15 {
return Err(ScheduleError::Channel(cell.channel_offset));
}
if cell.source == cell.destination {
return Err(ScheduleError::Loopback);
}
if self.cells.iter().any(|existing| {
existing.timeslot == cell.timeslot
&& (existing.source == cell.source
|| existing.source == cell.destination
|| existing.destination == cell.source
|| existing.destination == cell.destination)
}) {
return Err(ScheduleError::Conflict(cell.timeslot));
}
if self.cells.iter().any(|existing| {
existing.timeslot == cell.timeslot && existing.channel_offset == cell.channel_offset
}) {
return Err(ScheduleError::RadioConflict {
timeslot: cell.timeslot,
channel: cell.channel_offset,
});
}
let key = (cell.timeslot, cell.channel_offset);
let index = self
.cells
.binary_search_by_key(&key, |value| (value.timeslot, value.channel_offset))
.unwrap_or_else(|index| index);
self.cells.insert(index, cell);
Ok(())
}
pub fn remove_device(&mut self, device: DeviceId) -> usize {
let previous = self.cells.len();
self.cells
.retain(|cell| cell.source != device && cell.destination != device);
previous.saturating_sub(self.cells.len())
}
pub fn cells(&self) -> &[Cell] {
&self.cells
}
pub const fn superframe_size(&self) -> u16 {
self.superframe_size
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
pub enum ScheduleError {
#[error("superframe length cannot be zero")]
EmptySuperframe,
#[error("timeslot {0} lies outside the superframe")]
Timeslot(u16),
#[error("channel offset {0} is outside 0..=15")]
Channel(u8),
#[error("a cell cannot connect a device to itself")]
Loopback,
#[error("device conflict in timeslot {0}")]
Conflict(u16),
#[error("radio conflict in timeslot {timeslot}, channel offset {channel}")]
RadioConflict {
timeslot: u16,
channel: u8,
},
}
fn ordered_pair(left: DeviceId, right: DeviceId) -> (DeviceId, DeviceId) {
if left <= right {
(left, right)
} else {
(right, left)
}
}
fn reconstruct_route(
source: DeviceId,
destination: DeviceId,
previous: &BTreeMap<DeviceId, DeviceId>,
) -> Option<Route> {
let mut hops = vec![destination];
let mut current = destination;
while current != source {
current = *previous.get(¤t)?;
hops.push(current);
}
hops.reverse();
Some(Route { hops })
}