cnetworks 0.7.0

/*!
A lightweight alternative to [`std::collections::HashMap`] indexed only with `usize`.
Useful in  scenarios where you simply want a [`Vec`] with arbitrary indexes - this structure
achieves that by filling non-existant indexes with `None` values. It trades space for speed by not
utilizing a hashing algorithm, as a call to [`VecMap::contains`] is roughly 8 times faster than
[`rustc_hash::FxHashMap::contains_key`].

If *i* denotes maximum index present in the map, then both iteration over items and spacial
complexity is O(*i*). Inserting at a new index `m` extends the underlying vector by (*i - m*) and
is therefore O(*i - m*). Other operations (including [`VecMap::len`]) are O(1).
*/

use crate::cn;
use std::ops::{Index, IndexMut};

/// A vector-based map, indexed by arbitrary `usize` values.
#[derive(Debug, Clone)]
pub struct VecMap<T> {
    /// Vector of actual contained data
    data: Vec<Option<T>>,
    /// Vector of valid indexes
    indexes: Vec<usize>,
}

impl<T> VecMap<T> {
    /// Create a new, empty [`VecMap`].
    pub fn new() -> Self {
        VecMap {
            data: Vec::new(),
            indexes: Vec::new(),
        }
    }

    /// Create a new [`VecMap`] with specified `capacity`.
    pub fn with_capacity(capacity: usize) -> Self {
        let mut map = VecMap {
            data: Vec::with_capacity(capacity),
            indexes: Vec::with_capacity(capacity),
        };
        for _ in 0..capacity {
            map.data.push(None);
        }
        map
    }

    /// Return the total number of non-empty entries in the map.
    pub fn len(&self) -> usize {
        self.indexes.len()
    }

    /// Return `true` if the total number of non-empty entries in the map is 0.
    pub fn is_empty(&self) -> bool {
        self.indexes.is_empty()
    }

    /// Returns immutable reference to the item at specified `index`, `None` if the entry is
    /// vacant.
    pub fn get(&self, index: usize) -> Option<&T> {
        self.data.get(index).unwrap_or(&None).as_ref()
    }

    /// Returns mutable reference to the item at specified `index`, `None` if the entry is vacant.
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        self.data
            .get_mut(index)
            .map(|opt| opt.as_mut())
            .unwrap_or(None)
    }

    /// Insert `item` at `index`. Returns the old value or `None` if the entry was vacant.
    pub fn insert(&mut self, index: usize, item: T) -> Option<T> {
        // Grow to fill the gaps
        while index >= self.data.len() {
            self.data.push(None);
        }
        let old = std::mem::replace(&mut self.data[index], Some(item));
        if old.is_none() {
            // This index now has data
            self.indexes.push(index)
        }
        old
    }

    /// Removes item at specified `index`, returning the removed value or `None` if the entry was
    /// vacant.
    pub fn remove(&mut self, index: usize) -> Option<T> {
        let mut old = None;
        if self.contains(index) {
            old = std::mem::replace(&mut self.data[index], None);
            // We know that old is "Some" now and that we have removed something
            self.indexes.retain(|&idx| idx != index);
            self.shrink();
        }
        old
    }

    /// Shrinks the map from to the maximum required size, by removing empty entries from the rear.
    pub fn shrink(&mut self) {
        while let Some(None) = self.data.last() {
            self.data.pop();
        }
    }

    /// Returns `true` if there exists a value at specified `index`.
    pub fn contains(&self, index: usize) -> bool {
        self.data.get(index).unwrap_or(&None).is_some()
    }

    /// Returns iterator of valid indexes.
    pub fn indexes(&self) -> impl cn::Iter<usize> + '_ {
        self.indexes.iter().copied()
    }

    /// Returns iterator of (index, item) pairs.
    pub fn iter(&self) -> impl cn::Iter<(usize, &T)> + '_ {
        self.data
            .iter()
            .enumerate()
            .filter_map(|(idx, item)| item.as_ref().map(|item| (idx, item)))
    }

    /// Returns immutable reference to the underlying `Vec<Option<T>>`.
    pub fn as_vec(&self) -> &Vec<Option<T>> {
        &self.data
    }

    /// Returns mutable reference to the underlying `Vec<Option<T>>`.
    pub fn as_vec_mut(&mut self) -> &mut Vec<Option<T>> {
        &mut self.data
    }
}

/// Convert [`Vec`] into a [`VecMap`].
impl<T> From<Vec<T>> for VecMap<T> {
    fn from(vec: Vec<T>) -> Self {
        let mut map = VecMap::default();
        for (index, item) in vec.into_iter().enumerate() {
            map.insert(index, item);
        }
        map
    }
}

impl<T: PartialEq> PartialEq for VecMap<T> {
    fn eq(&self, other: &Self) -> bool {
        self.data == other.data
    }
}

impl<T: Eq> Eq for VecMap<T> {}

/// Provides non-guarded immutable access to the map's contents.
impl<T> Index<usize> for VecMap<T> {
    type Output = T;

    fn index(&self, index: usize) -> &Self::Output {
        self.data[index].as_ref().unwrap()
    }
}

/// Provides non-guarded mutable access to the map's contents.
impl<T> IndexMut<usize> for VecMap<T> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        self.data[index].as_mut().unwrap()
    }
}

/// Alias for [`VecMap::new`].
impl<T> Default for VecMap<T> {
    fn default() -> Self {
        VecMap::new()
    }
}

impl<T> std::iter::FromIterator<(usize, T)> for VecMap<T> {
    fn from_iter<I: IntoIterator<Item = (usize, T)>>(iter: I) -> Self {
        let mut map = VecMap::new();
        for (idx, item) in iter {
            map.insert(idx, item);
        }
        map
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct VecSet(cn::VecMap<()>);

impl VecSet {
    /// Create a new, empty [`VecSet`].
    pub fn new() -> Self {
        VecSet(cn::VecMap::new())
    }

    /// Create a new [`VecSet`] with specified `capacity`.
    pub fn with_capacity(capacity: usize) -> Self {
        VecSet(cn::VecMap::with_capacity(capacity))
    }

    /// Return the total number of non-empty entries in the set.
    pub fn len(&self) -> usize {
        self.0.len()
    }

    /// Return `true` if the total number of non-empty entries in the set is 0.
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    /// Returns `true` if the set contains given `index`.
    pub fn contains(&self, index: usize) -> bool {
        self.0.contains(index)
    }

    /// Inserts `index` into the set. Returns `true` if the set did not have this index.
    pub fn insert(&mut self, index: usize) -> bool {
        self.0.insert(index, ()).is_none()
    }

    /// Removes `index` from the set. Returns `true` if set did have this index.
    pub fn remove(&mut self, index: usize) -> bool {
        self.0.remove(index).is_some()
    }

    /// Returns vector with contained indexes.
    pub fn indexes(&self) -> impl cn::Iter<usize> + '_ {
        self.0.indexes()
    }

    pub fn iter(&self) -> impl cn::Iter<usize> + '_ {
        self.0.iter().map(|(idx, _item)| idx)
    }
}

/// Alias for [`VecSet::new`].
impl Default for VecSet {
    fn default() -> Self {
        VecSet::new()
    }
}

impl std::iter::FromIterator<usize> for VecSet {
    fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
        let mut set = VecSet::new();
        for idx in iter {
            set.insert(idx);
        }
        set
    }
}

#[test]
fn test_remove() {
    let mut map: VecMap<usize> = VecMap::new();
    assert!(map.data.is_empty());
    for i in [3, 10, 12] {
        assert!(map.insert(i, 0).is_none());
    }
    assert_eq!(map.data.len(), 13);
    assert_eq!(map.len(), 3);

    assert!(map.remove(100).is_none());
    assert_eq!(map.data.len(), 13);
    assert_eq!(map.len(), 3);

    assert_eq!(map.remove(3), Some(0));
    assert_eq!(map.data.len(), 13);
    assert_eq!(map.len(), 2);
    assert_eq!(map.indexes, vec![10, 12]);
}

#[test]
fn test_new() {
    let map: VecMap<usize> = VecMap::new();
    assert!(map.data.is_empty());
    assert_eq!(map.len(), 0);
    let map: VecMap<i32> = [(1, 0), (10, 0), (3, 0)].iter().cloned().collect();
    for i in [1, 10, 3] {
        assert_eq!(map[i], 0);
    }
    assert_eq!(map.len(), 3);
    assert_eq!(map.indexes, vec![1, 10, 3]);
}

#[test]
fn test_insert() {
    let mut map: VecMap<usize> = VecMap::new();
    assert!(map.data.is_empty());

    assert!(map.insert(3, 0).is_none());
    assert_eq!(map.data.len(), 4);
    assert_eq!(map.indexes.len(), 1);
    assert_eq!(map.len(), map.indexes.len());
    assert_eq!(map.data[3], Some(0));

    assert!(map.insert(10, 0).is_none());
    assert_eq!(map.indexes.len(), 2);
    assert_eq!(map.data.len(), 11);
    assert_eq!(map.data[10], Some(0));

    assert_eq!(map.insert(3, 12), Some(0));
    assert_eq!(map.indexes.len(), 2);
    assert_eq!(map.len(), map.indexes.len());
    assert_eq!(map.data.len(), 11);
    assert_eq!(map.data[3], Some(12));
}