ratio-interner 0.1.1

//! # SlotMap-based interner implementations
//!
//! ## License
//!
//! This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0.
//! If a copy of the MPL was not distributed with this file,
//! You can obtain one at <https://mozilla.org/MPL/2.0/>.
//!
//! **Code examples both in the docstrings and rendered documentation are free to use.**

use std::borrow::Cow;
use std::collections::BTreeMap;
use std::fmt::Debug;
use std::iter::once;

use slotmap::{DenseSlotMap, Key, SecondaryMap, SparseSecondaryMap};
use snafu::prelude::*;

use crate::{
    Error, FlatCollection, Interner, InvalidKeySnafu, KeyCollection, MapCollection,
    ValueAlreadyExistsSnafu,
};

/// Value interner based on a DenseSlotMap and a BTreeMap.
#[derive(Clone, Debug)]
#[cfg_attr(
    feature = "serde",
    derive(serde::Serialize, serde::Deserialize),
    serde(default, rename_all = "camelCase")
)]
pub struct DenseSlottedBTreeInterner<K, V>
where
    K: Key + Debug,
    V: Clone + Debug + Ord,
{
    /// Orderable names by slot keys.
    values_by_key: DenseSlotMap<K, V>,

    /// Slotmap keys by orderable values.
    keys_by_value: BTreeMap<V, K>,
}

impl<K, V> Default for DenseSlottedBTreeInterner<K, V>
where
    K: Key + Debug,
    V: Clone + Debug + Ord,
{
    fn default() -> Self {
        Self {
            values_by_key: Default::default(),
            keys_by_value: Default::default(),
        }
    }
}

impl<K, V> DenseSlottedBTreeInterner<K, V>
where
    K: Key + Debug,
    V: Clone + Debug + Ord,
{
    /// Create a new interner.
    pub fn new() -> Self {
        Self::default()
    }
}

impl<K: Key + Debug, V: Clone + Debug + Ord> FromIterator<V> for DenseSlottedBTreeInterner<K, V> {
    fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
        let mut new = Self::default();
        iter.into_iter().for_each(|v| {
            new.intern_owned(v);
        });
        new
    }
}

impl<'a, K: Key + Debug, V: Clone + Debug + Ord> IntoIterator
    for &'a DenseSlottedBTreeInterner<K, V>
{
    type Item = (K, &'a V);
    type IntoIter = slotmap::dense::Iter<'a, K, V>;
    fn into_iter(self) -> Self::IntoIter {
        self.values_by_key.iter()
    }
}

impl<K, V> Interner<K, V> for DenseSlottedBTreeInterner<K, V>
where
    K: Key + Debug,
    V: Clone + Debug + Ord,
{
    fn intern(&mut self, value: Cow<'_, V>) -> K {
        if let Some(key) = self.keys_by_value.get(&value) {
            *key
        } else {
            let value = value.into_owned();
            let key = self.values_by_key.insert(value.clone());
            self.keys_by_value.insert(value, key);
            key
        }
    }

    fn try_intern(&mut self, value: Cow<'_, V>) -> Result<K, Error> {
        if self.contains_value(&value) {
            ValueAlreadyExistsSnafu.fail()
        } else {
            let value = value.into_owned();
            let key = self.values_by_key.insert(value.clone());
            self.keys_by_value.insert(value, key);
            Ok(key)
        }
    }

    fn try_update(&mut self, key: K, value: Cow<'_, V>) -> Result<V, Error> {
        if self.contains_value(&value) {
            ValueAlreadyExistsSnafu.fail()
        } else {
            let value = value.into_owned();
            let old = self
                .values_by_key
                .get_mut(key)
                .map(|v| std::mem::replace(v, value.clone()))
                .context(InvalidKeySnafu)?;
            self.keys_by_value.remove(&old);
            self.keys_by_value.insert(value, key);
            Ok(old)
        }
    }

    fn remove_key(&mut self, key: K) -> Option<V> {
        let value = self.values_by_key.remove(key);
        if let Some(value) = value.as_ref() {
            self.keys_by_value.remove(value);
        }
        value
    }

    fn remove_value(&mut self, value: &V) -> Option<K> {
        let key = self.keys_by_value.remove(value);
        if let Some(key) = key {
            self.values_by_key.remove(key);
        }
        key
    }

    fn clear(&mut self) {
        self.keys_by_value.clear();
        self.values_by_key.clear();
    }

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

    fn is_empty(&self) -> bool {
        self.keys_by_value.is_empty()
    }

    fn contains_key(&self, key: K) -> bool {
        self.values_by_key.contains_key(key)
    }

    fn contains_value(&self, value: &V) -> bool {
        self.keys_by_value.contains_key(value)
    }

    fn get_key(&self, value: &V) -> Option<K> {
        self.keys_by_value.get(value).copied()
    }

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

    fn keys(&self) -> impl Iterator<Item = K> {
        self.values_by_key.keys()
    }

    fn values<'a>(&'a self) -> impl Iterator<Item = &'a V>
    where
        V: 'a,
    {
        self.keys_by_value.keys()
    }

    fn items<'a>(&'a self) -> impl Iterator<Item = (K, &'a V)>
    where
        V: 'a,
    {
        self.keys_by_value.iter().map(|(v, &k)| (k, v))
    }
}

impl<K: Key> KeyCollection<K> for K {
    fn collection_keys(&self) -> impl Iterator<Item = K> {
        once(*self)
    }

    fn collection_contains(&self, key: &K) -> bool {
        self == key
    }

    fn collection_len(&self) -> usize {
        (!self.is_null()) as usize
    }

    fn collection_is_empty(&self) -> bool {
        self.is_null()
    }
}
impl<K: Key> FlatCollection<K> for K {
    fn insert_collection_key(&mut self, key: K) -> Option<K> {
        if self == &key {
            None
        } else {
            Some(std::mem::replace(self, key))
        }
    }
    fn remove_collection_key(&mut self, key: &K) -> Option<K> {
        if self == key {
            Some(std::mem::take(self))
        } else {
            None
        }
    }
}

impl<K: Key + Debug, V: Clone + Debug + Ord> IntoIterator for DenseSlottedBTreeInterner<K, V> {
    type Item = (K, V);
    type IntoIter = slotmap::dense::IntoIter<K, V>;
    fn into_iter(self) -> Self::IntoIter {
        self.values_by_key.into_iter()
    }
}

impl<K: Key, V> KeyCollection<K> for SecondaryMap<K, V> {
    fn collection_contains(&self, key: &K) -> bool {
        self.contains_key(*key)
    }
    fn collection_is_empty(&self) -> bool {
        self.is_empty()
    }
    fn collection_keys(&self) -> impl Iterator<Item = K> {
        self.keys()
    }
    fn collection_len(&self) -> usize {
        self.len()
    }
}
impl<K: Key, V> MapCollection for SecondaryMap<K, V> {
    type Key = K;
    type Value = V;
    fn collection_value(&self, key: &K) -> Option<&V> {
        self.get(*key)
    }
    fn collection_value_mut(&mut self, key: &Self::Key) -> Option<&mut Self::Value> {
        self.get_mut(*key)
    }
    fn insert_collection_value(&mut self, key: K, value: V) -> Option<V> {
        self.insert(key, value)
    }
    fn remove_collection_value(&mut self, key: &K) -> Option<V> {
        self.remove(*key)
    }
}
impl<K: Key, V> KeyCollection<K> for SparseSecondaryMap<K, V> {
    fn collection_contains(&self, key: &K) -> bool {
        self.contains_key(*key)
    }
    fn collection_is_empty(&self) -> bool {
        self.is_empty()
    }
    fn collection_keys(&self) -> impl Iterator<Item = K> {
        self.keys()
    }
    fn collection_len(&self) -> usize {
        self.len()
    }
}
impl<K: Key, V> MapCollection for SparseSecondaryMap<K, V> {
    type Key = K;
    type Value = V;
    fn collection_value(&self, key: &K) -> Option<&V> {
        self.get(*key)
    }
    fn collection_value_mut(&mut self, key: &Self::Key) -> Option<&mut Self::Value> {
        self.get_mut(*key)
    }
    fn insert_collection_value(&mut self, key: K, value: V) -> Option<V> {
        self.insert(key, value)
    }
    fn remove_collection_value(&mut self, key: &K) -> Option<V> {
        self.remove(*key)
    }
}

#[cfg(test)]
mod tests {
    #[allow(unused_imports)]
    use pretty_assertions::{assert_eq, assert_ne, assert_str_eq};
    use slotmap::DefaultKey;

    #[allow(unused_imports)]
    use super::*;

    #[test]
    fn test_dense_slotted_btree_interner() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test interning owned values
        let key1 = interner.intern_owned("foo".to_string());
        let key2 = interner.intern_owned("bar".to_string());
        assert_ne!(key1, key2);

        // Test interning borrowed values
        let key3 = interner.intern_borrowed(&"foo".to_string());
        let key4 = interner.intern_borrowed(&"bar".to_string());
        assert_eq!(key3, key1);
        assert_eq!(key4, key2);

        // Test that the interner only stores unique values
        assert_eq!(interner.len(), 2);

        // Test value ordering from btreemap.
        assert_eq!(interner.values().collect::<Vec<_>>(), vec!["bar", "foo"]);
    }

    #[test]
    fn test_dense_slotted_btree_interner_try_intern() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test successful try_intern
        let key1 = interner.try_intern(Cow::Owned("foo".to_string())).unwrap();
        assert_eq!(interner.len(), 1);

        // Test try_intern with existing value
        let result = interner.try_intern(Cow::Owned("foo".to_string()));
        assert!(matches!(result, Err(Error::ValueAlreadyExists)));
        assert_eq!(interner.len(), 1);

        // Test try_intern with borrowed value
        let key2 = interner
            .try_intern(Cow::Borrowed(&"bar".to_string()))
            .unwrap();
        assert_eq!(interner.len(), 2);
        assert_ne!(key1, key2);
    }

    #[test]
    fn test_dense_slotted_btree_interner_try_update() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test try_update with non-existent key
        let result = interner.try_update(DefaultKey::null(), Cow::Owned("foo".to_string()));
        assert!(matches!(result, Err(Error::InvalidKey)));

        // Test successful try_update
        let key1 = interner.intern_owned("foo".to_string());
        let old_value = interner
            .try_update(key1, Cow::Owned("bar".to_string()))
            .unwrap();
        assert_eq!(old_value, "foo");
        assert_eq!(interner.get_value(key1), Some(&"bar".to_string()));

        // Test try_update with existing value
        let key2 = interner.intern_owned("baz".to_string());
        let result = interner.try_update(key2, Cow::Owned("baz".to_string()));
        assert!(matches!(result, Err(Error::ValueAlreadyExists)));
        assert_eq!(interner.get_value(key2), Some(&"baz".to_string()));
    }

    #[test]
    fn test_dense_slotted_btree_interner_remove() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test remove_key with non-existent key
        assert_eq!(interner.remove_key(DefaultKey::null()), None);

        // Test remove_key with existing key
        let key1 = interner.intern_owned("foo".to_string());
        assert_eq!(interner.remove_key(key1), Some("foo".to_string()));
        assert_eq!(interner.len(), 0);

        // Test remove_value with non-existent value
        assert_eq!(interner.remove_value(&"bar".to_string()), None);

        // Test remove_value with existing value
        let key2 = interner.intern_owned("bar".to_string());
        assert_eq!(interner.remove_value(&"bar".to_string()), Some(key2));
        assert_eq!(interner.len(), 0);
    }

    #[test]
    fn test_dense_slotted_btree_interner_try_remove() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test try_remove_key with non-existent key
        let result = interner.try_remove_key(DefaultKey::null());
        assert!(matches!(result, Err(Error::InvalidKey)));

        // Test try_remove_key with existing key
        let key1 = interner.intern_owned("foo".to_string());
        assert_eq!(interner.try_remove_key(key1).unwrap(), "foo".to_string());
        assert_eq!(interner.len(), 0);

        // Test try_remove_value with non-existent value
        let result = interner.try_remove_value(&"bar".to_string());
        assert!(matches!(result, Err(Error::ValueDoesNotExist)));

        // Test try_remove_value with existing value
        let key2 = interner.intern_owned("bar".to_string());
        assert_eq!(interner.try_remove_value(&"bar".to_string()).unwrap(), key2);
        assert_eq!(interner.len(), 0);
    }

    #[test]
    fn test_dense_slotted_btree_interner_try_get() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test try_get_key with non-existent value
        let result = interner.try_get_key(&"foo".to_string());
        assert!(matches!(result, Err(Error::ValueDoesNotExist)));

        // Test try_get_key with existing value
        let key1 = interner.intern_owned("foo".to_string());
        assert_eq!(interner.try_get_key(&"foo".to_string()).unwrap(), key1);

        // Test try_get_value with non-existent key
        let result = interner.try_get_value(DefaultKey::null());
        assert!(matches!(result, Err(Error::InvalidKey)));

        // Test try_get_value with existing key
        assert_eq!(interner.try_get_value(key1).unwrap(), &"foo".to_string());
    }

    #[test]
    fn test_dense_slotted_btree_interner_clear() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test clear on empty interner
        interner.clear();
        assert_eq!(interner.len(), 0);

        // Test clear on non-empty interner
        interner.intern_owned("foo".to_string());
        interner.intern_owned("bar".to_string());
        assert_eq!(interner.len(), 2);
        interner.clear();
        assert_eq!(interner.len(), 0);
    }
}