mapgraph/map/

mod.rs

//! Contains traits used as an interface between [`Graph`]s and their backing maps.
//!
//! # Map traits
//!
//! * [`Map`]: the base trait that should be implemented by any map to be usable with [`Graph`]s.
//! * [`MapWithCapacity`]: a trait that exposes capacity-related functionality. [`Graph`]s using maps that implement
//!   this trait as either node or edge maps allow to reserve memory capacity.
//! * [`OrderedKeyMap`]: a trait for maps that have ordered keys and provide range iterators.
//! * [`ParIterMap`]: a trait for maps that provide parallel iteration support using [`rayon`].
//!
//! ## Insertion traits
//!
//! These traits provide interfaces to insert key-value pairs into maps. Usually graphs use maps which generate their
//! keys internally and expose an opaque key type like [`SlotMap`]. However, the whole point of this library is exposing
//! the properties of the underlying maps so there is support for maps that accept external keys like [`BTreeMap`].
//!
//! * [`IntKeyMap`]: maps that generate their keys internally (e.g. [`SlotMap`]) should implement this trait.
//! * [`ExtKeyMap`]: maps that allow their users to provide keys (e.g. [`BTreeMap`]) should implement this trait.
//!
//! ## Entry API
//!
//! Entry API is provided by the [`MapWithEntry`] trait and the [`MapEntry`] type. Implementing this type is mostly
//! done on their vacant and occupied entry types using the [`VacantMapEntry`] and [`OccupiedMapEntry`] traits.
//!
//! [`Graph`]: crate::graph::Graph
//! [`BTreeMap`]: alloc::collections::BTreeMap
//! [`SlotMap`]: ::slotmap::SlotMap

#[cfg(feature = "alloc")]
mod btreemap;
#[cfg(any(feature = "std", feature = "indexmap"))]
mod hashmap;
#[cfg(feature = "slotmap")]
pub mod slotmap;

use core::{
    fmt::{self, Debug},
    ops::RangeBounds,
};
#[cfg(feature = "rayon")]
use rayon::iter::{IntoParallelIterator, Map as ParMap, ParallelIterator};

/// A trait for a generic map that can be used as a node or an edge map in a
/// [`Graph`](crate::Graph).
pub trait Map<T>: Default {
    /// The type of key used by the map.
    type Key: Copy + Eq + Debug + 'static;

    /// The type for an immutable iterator over the nodes in the map.
    type Iter<'a>: Iterator<Item = (Self::Key, &'a T)>
    where
        Self: 'a,
        T: 'a;

    /// The type for a mutable iterator over the nodes in the map.
    type IterMut<'a>: Iterator<Item = (Self::Key, &'a mut T)>
    where
        Self: 'a,
        T: 'a;

    /// Returns the amount of nodes in the map.
    fn len(&self) -> usize;

    /// Returns `true` if the map is empty.
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns `true` if a map contains the specified key.
    fn contains_key(&self, index: Self::Key) -> bool {
        self.get(index).is_some()
    }

    /// Returns an immutable reference to a value by its key or [`None`] in case the key is
    /// not present in the map.
    fn get(&self, index: Self::Key) -> Option<&T>;

    /// Returns a mutable reference to a value by its key or [`None`] in case the key is not
    /// present in the map.
    fn get_mut(&mut self, index: Self::Key) -> Option<&mut T>;

    /// Removes a value from a map by its key. Returns the removed value or [`None`] in case the
    /// key was not present in the map.
    fn remove(&mut self, index: Self::Key) -> Option<T>;

    /// Removes all the nodes from the map.
    fn clear(&mut self);

    /// Returns an immutable iterator over the nodes in a map.
    fn iter(&self) -> Self::Iter<'_>;

    /// Returns a mutable iterator over the nodes in a map.
    fn iter_mut(&mut self) -> Self::IterMut<'_>;
}

/// A trait for maps that have some preallocated capacity.
pub trait MapWithCapacity<T>: Map<T> {
    /// Allocates a new map with the specified capacity.
    fn with_capacity(capacity: usize) -> Self;

    /// Returns the currently allocated capacity of the map.
    fn capacity(&self) -> usize;

    /// Reserves space for at least `additional` nodes.
    fn reserve(&mut self, additional: usize);
}

/// An error returned by the [`ExtKeyMap::try_insert`] method when the specified key is already
/// present in the map.
#[derive(Debug)]
pub struct OccupiedError;

impl fmt::Display for OccupiedError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("map entry is occupied")
    }
}

#[cfg(feature = "std")]
impl std::error::Error for OccupiedError {}

/// A trait for maps that accept keys from the caller when adding an entry.
///
/// This is what you usually expect when you see something called a "map". Examples are `BTreeMap`,
/// `HashMap`, etc.
pub trait ExtKeyMap<T>: Map<T> {
    /// Tries to insert a key-value pair into the map.
    ///
    /// # Errors
    ///
    /// In case the key is already present, returns [`OccupiedError`].
    fn try_insert(&mut self, key: Self::Key, value: T) -> Result<(), OccupiedError>;

    /// Inserts a key-value pair into the map replacing the old value in case the key was present.
    /// The old value is returned in that case.
    fn replace(&mut self, key: Self::Key, value: T) -> Option<T>;
}

/// A trait for maps that produce keys internally when adding an entry.
///
/// This is the kind of maps usually used to back graphs in rust. Examples are `SlotMap` and `Slab`.
pub trait IntKeyMap<T>: Map<T> {
    /// Inserts a value into the map and returns the key allocated for it.
    fn insert(&mut self, value: T) -> Self::Key;

    /// Inserts a value produced by a closure into the map and returns the key allocated for it.
    ///
    /// The closure receives the allocated key as its only argument.
    fn insert_with_key<F: FnOnce(Self::Key) -> T>(&mut self, f: F) -> Self::Key;
}

/// A trait for maps that have strongly ordered keys and provide iterators over key ranges.
///
/// The most notable example of such a map is the `BTreeMap`.
pub trait OrderedKeyMap<T>: ExtKeyMap<T>
where
    Self::Key: Ord,
{
    /// The type for an immutable range iterator for the map.
    type Range<'a>: Iterator<Item = (Self::Key, &'a T)> + DoubleEndedIterator
    where
        Self: 'a,
        T: 'a;

    /// The type for a mutable range iterator for the map.
    type RangeMut<'a>: Iterator<Item = (Self::Key, &'a mut T)> + DoubleEndedIterator
    where
        Self: 'a,
        T: 'a;

    /// Returns an immutable iterator over entries corresponding to keys in the specified range.
    fn range<R: RangeBounds<Self::Key>>(&self, range: R) -> Self::Range<'_>;

    /// Returns a mutable iterator over entries corresponding to keys in the specified range.
    fn range_mut<R: RangeBounds<Self::Key>>(&mut self, range: R) -> Self::RangeMut<'_>;

    /// Returns an immutable reference to the first element in the map.
    ///
    /// # Default behavior
    ///
    /// The default implementation takes the first element returned by the range iterator on an
    /// unbounded range.
    fn first(&self) -> Option<(Self::Key, &T)> {
        self.range(..).next()
    }

    /// Returns a mutable reference to the first element in the map.
    ///
    /// # Default behavior
    ///
    /// The default implementation takes the first element returned by the range iterator on an
    /// unbounded range.
    fn first_mut(&mut self) -> Option<(Self::Key, &mut T)> {
        self.range_mut(..).next()
    }

    /// Returns an immutable reference to the last element in the map.
    ///
    /// # Default behavior
    ///
    /// The default implementation takes the last element returned by the range iterator on an
    /// unbounded range.
    fn last(&self) -> Option<(Self::Key, &T)> {
        self.range(..).last()
    }

    /// Returns a mutable reference to the last element in the map.
    ///
    /// # Default behavior
    ///
    /// The default implementation takes the last element returned by the range iterator on an
    /// unbounded range.
    fn last_mut(&mut self) -> Option<(Self::Key, &mut T)> {
        self.range_mut(..).last()
    }
}

/// A trait for maps that provide parallel iterators.
#[cfg(feature = "rayon")]
pub trait ParIterMap<T>: Map<T> {
    /// The type for the map's immutable parallel iterator.
    type ParIter<'a>: ParallelIterator<Item = (Self::Key, &'a T)>
    where
        Self: 'a,
        T: 'a;

    /// The type for the map's mutable parallel iterator.
    type ParIterMut<'a>: ParallelIterator<Item = (Self::Key, &'a mut T)>
    where
        Self: 'a,
        T: 'a;

    /// Returns an immutable parallel iterator over the key-value pairs in the map.
    fn par_iter(&self) -> Self::ParIter<'_>;

    /// Returns a mutable parallel iterator over the key-value pairs in the map.
    fn par_iter_mut(&mut self) -> Self::ParIterMut<'_>;
}

#[cfg(feature = "rayon")]
impl<M, K, T> ParIterMap<T> for M
where
    M: Map<T, Key = K>,
    K: Copy + Eq + Debug + Send + Sync + 'static,
    T: Send + Sync,
    for<'a> &'a M: IntoParallelIterator<Item = (&'a K, &'a T)>,
    for<'a> &'a mut M: IntoParallelIterator<Item = (&'a K, &'a mut T)>,
{
    type ParIter<'a> = ParMap<
        <&'a M as IntoParallelIterator>::Iter,
        fn((&'a K, &'a T)) -> (K, &'a T)
    > where Self: 'a, T: 'a;
    type ParIterMut<'a> = ParMap<
        <&'a mut M as IntoParallelIterator>::Iter,
        fn((&'a K, &'a mut T)) -> (K, &'a mut T)
    > where Self: 'a, T: 'a;

    fn par_iter(&self) -> Self::ParIter<'_> {
        IntoParallelIterator::into_par_iter(self).map(|(&k, v)| (k, v))
    }

    fn par_iter_mut(&mut self) -> Self::ParIterMut<'_> {
        IntoParallelIterator::into_par_iter(self).map(|(&k, v)| (k, v))
    }
}

/// A set of keys.
///
/// This is used to mark keys that have already been visited in algorithms.
///
/// Implementing this using a separate trait instead of relying on the [`ExtKeyMap`] trait allows to
/// use simpler set structures like bit sets with less friction.
///
/// # Auto trait implementations
///
/// All types that implement [`ExtKeyMap<()>`] automatically implement this trait.
pub trait KeySet<K: Copy + Eq + Debug + 'static> {
    /// Returns the amount of keys in the set.
    fn len(&self) -> usize;

    /// Returns `true` if the set is empty.
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns `true` if a set contains the specified key.
    fn contains(&self, index: K) -> bool;

    /// Inserts a key into the set.
    ///
    /// Returns `true` if the value was not present in the set.
    fn insert(&mut self, index: K) -> bool;

    /// Removes a key from the set.
    ///
    /// Returns `true` if the value was present in the set.
    fn remove(&mut self, index: K) -> bool;

    /// Removes all the nodes from the map.
    fn clear(&mut self);
}

impl<K: Copy + Eq + Debug + 'static, T: ExtKeyMap<(), Key = K>> KeySet<K> for T {
    fn len(&self) -> usize {
        Map::len(self)
    }

    fn is_empty(&self) -> bool {
        Map::is_empty(self)
    }

    fn contains(&self, index: K) -> bool {
        Map::contains_key(self, index)
    }

    fn insert(&mut self, index: K) -> bool {
        ExtKeyMap::replace(self, index, ()).is_some()
    }

    fn remove(&mut self, index: K) -> bool {
        Map::remove(self, index).is_some()
    }

    fn clear(&mut self) {
        Map::clear(self)
    }
}

/// A trait for vacant map entry types.
pub trait VacantMapEntry {
    /// The map's value type.
    type Value;

    /// Consumes the vacant entry and inserts a value for the corresponding key into the map.
    fn insert<'a>(self, value: Self::Value) -> &'a mut Self::Value
    where
        Self: 'a;
}

/// A trait for occupied map entry types.
pub trait OccupiedMapEntry {
    /// The map's value type.
    type Value;

    /// Gets an immutable reference to the value stored by the entry.
    fn get(&self) -> &Self::Value;

    /// Gets a mutable reference to the value stored by the entry.
    fn get_mut(&mut self) -> &mut Self::Value;

    /// Converts the map entry into a mutable reference to the stored value with a lifetime of the map itself.
    fn into_mut<'a>(self) -> &'a mut Self::Value
    where
        Self: 'a;

    /// Replaces the value stored in the entry with another value and returns the old one.
    fn replace(&mut self, value: Self::Value) -> Self::Value;

    /// Removes a value from the entry.
    fn remove(self) -> Self::Value;
}

/// An enumeration of possible map entry types.
#[derive(Clone, Debug)]
pub enum MapEntry<O, V> {
    /// A vacant map entry.
    Vacant(V),
    /// An occupied map entry.
    Occupied(O),
}

/// A trait for maps that implement entry API.
pub trait MapWithEntry<T>: ExtKeyMap<T> {
    /// The type for the vacant entry.
    type VacantEntry<'a>: VacantMapEntry<Value = T>
    where
        Self: 'a;

    /// The type for the occupied entry.
    type OccupiedEntry<'a>: OccupiedMapEntry<Value = T>
    where
        Self: 'a;

    /// Returns an entry for a key. The entry is either occupied or vacant.
    fn entry(&mut self, key: Self::Key)
        -> MapEntry<Self::OccupiedEntry<'_>, Self::VacantEntry<'_>>;
}