rs-graph 0.20.0

/*
 * Copyright (c) 2018, 2020, 2021 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

use crate::vec::{Indexer, ItemVec};
use std::collections::HashMap;
use std::hash::{BuildHasher, Hash};

/// A (finite) map of items (node or edges) of a graph to some value.
pub trait ItemMap<K, V>
where
    K: Copy,
{
    /// Return `true` if this map is empty.
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Return the number of items in this map.
    fn len(&self) -> usize;

    /// Remove all items from the map.
    fn clear(&mut self);

    /// Add one item to the map.
    ///
    /// Return `true` iff `u` had not been contained in this map before. In this
    /// case the value is *not* updated.
    fn insert(&mut self, key: K, value: V) -> bool;

    /// Add one item to the map.
    ///
    /// Return `true` iff `key` had not been contained in this map before. In this
    /// case the value *is* updated.
    fn insert_or_replace(&mut self, key: K, value: V) -> bool;

    /// Remove one item from the map.
    ///
    /// Returns `true` if the item had been contained in the map, otherwise
    /// false.
    fn remove(&mut self, key: K) -> bool;

    /// Return a read-only reference to the element with the given key.
    fn get(&self, key: K) -> Option<&V>;

    /// Return a mutable reference to the element with the given key.
    fn get_mut(&mut self, key: K) -> Option<&mut V>;

    /// Return `true` iff item `u` is contained in this map.
    fn contains(&self, key: K) -> bool;
}

impl<'a, K, V, S> ItemMap<K, V> for &'a mut S
where
    K: Copy,
    S: ItemMap<K, V>,
{
    fn is_empty(&self) -> bool {
        (**self).is_empty()
    }

    fn len(&self) -> usize {
        (**self).len()
    }

    fn clear(&mut self) {
        (**self).clear()
    }

    fn insert(&mut self, key: K, value: V) -> bool {
        (**self).insert(key, value)
    }

    fn insert_or_replace(&mut self, key: K, value: V) -> bool {
        (**self).insert_or_replace(key, value)
    }

    fn remove(&mut self, key: K) -> bool {
        (**self).remove(key)
    }

    fn get(&self, key: K) -> Option<&V> {
        (**self).get(key)
    }

    fn get_mut(&mut self, key: K) -> Option<&mut V> {
        (**self).get_mut(key)
    }

    fn contains(&self, key: K) -> bool {
        (**self).contains(key)
    }
}

impl<K, V, S> ItemMap<K, V> for HashMap<K, V, S>
where
    K: Copy + Eq + Hash,
    S: BuildHasher,
{
    fn is_empty(&self) -> bool {
        HashMap::is_empty(self)
    }

    fn len(&self) -> usize {
        HashMap::len(self)
    }

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

    fn insert(&mut self, key: K, value: V) -> bool {
        let mut new = false;
        HashMap::entry(self, key).or_insert_with(|| {
            new = true;
            value
        });
        new
    }

    fn insert_or_replace(&mut self, key: K, value: V) -> bool {
        HashMap::insert(self, key, value).is_some()
    }

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

    fn get(&self, key: K) -> Option<&V> {
        HashMap::get(self, &key)
    }

    fn get_mut(&mut self, key: K) -> Option<&mut V> {
        HashMap::get_mut(self, &key)
    }

    fn contains(&self, key: K) -> bool {
        HashMap::contains_key(self, &key)
    }
}

/// A thin wrapper around a `ItemVec<_, Option<V>>`.
///
/// Such a vector can be used as `ItemMap<_, V>` with a field being `None` if
/// and only if the corresponding key is not contained in the map.
pub struct ItemVecMap<'a, I, V> {
    /// The underlying `ItemVec`.
    vec: &'a mut ItemVec<I, Option<V>>,
    /// The number of elements in this map.
    count: usize,
}

impl<'a, I, V> ItemVecMap<'a, I, V>
where
    I: Indexer,
{
    pub fn new_empty(vec: &'a mut ItemVec<I, Option<V>>) -> Self {
        for (_, v) in vec.iter_mut() {
            *v = None;
        }
        ItemVecMap { vec, count: 0 }
    }
}

impl<'a, I, V> ItemMap<I::Idx, V> for ItemVecMap<'a, I, V>
where
    I: Indexer,
    I::Idx: Copy,
{
    fn is_empty(&self) -> bool {
        self.count == 0
    }

    fn len(&self) -> usize {
        self.count
    }

    fn clear(&mut self) {
        for (_, v) in self.vec.iter_mut() {
            *v = None;
        }
    }

    fn insert(&mut self, key: I::Idx, value: V) -> bool {
        let x = &mut self.vec[key];
        if x.is_none() {
            *x = Some(value);
            self.count += 1;
            true
        } else {
            false
        }
    }

    fn insert_or_replace(&mut self, key: I::Idx, value: V) -> bool {
        if self.vec[key].replace(value).is_some() {
            true
        } else {
            self.count += 1;
            false
        }
    }

    fn remove(&mut self, key: I::Idx) -> bool {
        if self.vec[key].take().is_some() {
            self.count -= 1;
            true
        } else {
            false
        }
    }

    fn get(&self, key: I::Idx) -> Option<&V> {
        self.vec[key].as_ref()
    }

    fn get_mut(&mut self, key: I::Idx) -> Option<&mut V> {
        self.vec[key].as_mut()
    }

    fn contains(&self, key: I::Idx) -> bool {
        self.vec[key].is_some()
    }
}