uuidmap 0.3.0

//! # Table
//! Implementation of a ArrayHashMap (also called MapVec or DenseStorage).
//! It has good performance characteristics for things that matter: iterating, adding, removing, finding.
//!
//! It is designed to resemble a database table, with the exception that keys are always uuids.
//! Most of the time, the keys are randomly generated.
//!
//! ### Design
//! This is meant to be a replacement for the Entity-Component-System pattern.
//! It can be used for much more, but I designed it in way to merge the architecture of component storages with resource storages.
//! This makes it much easier to reason about how things work, along with requiring significantly less code to use and build upon.
//!
//! ##### Uuid Keys
//! They were chosen because they don't need a last_index counter, they don't need O(n) to find a free slot, they won't collide and they don't cause fragmentation.
//! Also, being forced to have a single type for all keys in a program/database makes things much easier to understand than having compound keys of strings and the like.
//!
//! However, it does come at the cost of more memory usage, slightly lower performance and less opportunities for cheeky, application-specific optimizations.
//! I believe that the advantages outweight the cost here.
//!
//! ### Performance
//! Performance loss has been minimized as much as possible.
//! In my benchmarks, the results show performance similar to bitset-based entity-component-systems, which are considered extremely fast (as of writing this.)
//! However, depending on how you link tables together, you will see different performance characteristics ranging from "literally iterating a Vec<T>" to 3x slower than benchmarks.
//! See benches/benches.rs join_benchmark and ecs_like_benchmark (3x slower than join) to see the difference.
//!
//! ### Caveats
//! If you don't need iterating: Use `HashMap`.
//! If you don't need finding by key: Use `Vec`.
//! If you need elements to be sorted: Use a `BTree`.
//!
//! You may still use this in the first two cases, but do be aware that you are wasting performance and memory.
//! This can be worthwhile for consistency sometimes.
use fxhash::FxHashMap;
use rand::Rng;
use serde::{Deserialize, Serialize};
use std::io::{Read, Write};

// TODO evaluate performance degradation due to cpu cache misses when doing join_benchmark with random insertion order.
// TODO reword readme.
// TODO bump to 1.0.0 once I'm done with the other todos + have used this in other projects.
// TODO add documentation link
// TODO cargo lock

/// See crate level documentation.
#[derive(Debug, Clone)]
pub struct Table<T> {
    // Contains a map of uuid to data vector index.
    map: FxHashMap<u128, usize>,
    data: Vec<T>,
    reverse: Vec<u128>,
}

impl<T> Default for Table<T> {
    fn default() -> Self {
        Self::with_capacity(32)
    }
}

impl<T> Table<T> {
    /// Add a new value with random key.
    /// This is what you want to use 95% of the time.
    pub fn add(&mut self, value: T) -> u128 {
        let key = rand::rng().random();
        self.add_with_key(key, value);
        key
    }

    /// Add a new value with manual key. Usually used during deserialization.
    /// Might be used for performance reasons when using a Table as a Map.
    /// For example, a map KeyCode -> GameEvent.
    pub fn add_with_key(&mut self, key: u128, value: T) {
        self.remove(key);
        self.data.push(value);
        self.reverse.push(key);
        let index = self.data.len() - 1;
        self.map.insert(key, index);
    }

    /// Get a value by key.
    pub fn get(&self, key: u128) -> Option<&T> {
        self.map
            .get(&key)
            .map(|index| unsafe { self.data.get_unchecked(*index) })
    }

    /// Get a value by key.
    pub fn get_mut(&mut self, key: u128) -> Option<&mut T> {
        self.map
            .get(&key)
            .map(|index| unsafe { self.data.get_unchecked_mut(*index) })
    }

    /// Remove an element using it's key.
    pub fn remove(&mut self, key: u128) -> Option<T> {
        if let Some(index) = self.map.remove(&key) {
            // Swap-remove from both data and reverse
            let value = self.data.swap_remove(index);
            // key that got moved to index
            let pre_move_index = self.reverse[self.reverse.len() - 1];
            self.reverse.swap_remove(index);

            // if what we removed was not the last element, update the index
            if index < self.reverse.len() {
                *self.map.get_mut(&pre_move_index).unwrap() = index;
            }
            return Some(value);
        }
        None
    }

    /// Get an iterator over the contained values.
    pub fn values(&self) -> impl Iterator<Item = &T> {
        self.data.iter()
    }

    /// Get an iterator over the contained values mutably.
    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T> {
        self.data.iter_mut()
    }

    /// Return an iterator over keys.
    pub fn keys(&self) -> std::collections::hash_map::Keys<u128, usize> {
        self.map.keys()
    }

    /// Return an iterator over key-value pairs.
    pub fn iter(&self) -> impl Iterator<Item = (u128, &T)> {
        self.reverse.iter().copied().zip(self.data.iter())
    }

    /// Return an iterator over mutable key-value pairs.
    pub fn iter_mut(&mut self) -> impl Iterator<Item = (u128, &mut T)> {
        self.reverse.iter().copied().zip(self.data.iter_mut())
    }

    /// Creates a Table with a specific initial capacity.
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            map: FxHashMap::<u128, usize>::with_capacity_and_hasher(capacity, Default::default()),
            data: Vec::<T>::with_capacity(capacity),
            reverse: Vec::<u128>::with_capacity(capacity),
        }
    }

    /// Get the number of elements stored.
    pub fn count(&self) -> usize {
        self.data.len()
    }

    /// Empty out everything.
    pub fn clear(&mut self) {
        self.data.clear();
        self.reverse.clear();
        self.map.clear();
    }

    /// Serialize to JSON format (only stores key-value pairs)
    pub fn to_json(&self) -> serde_json::Result<String>
    where
        T: Serialize,
    {
        let map: FxHashMap<u128, &T> = self.iter().collect();
        serde_json::to_string(&map)
    }

    /// Deserialize from JSON format (rebuilds internal structures)
    pub fn from_json(json: &str) -> serde_json::Result<Self>
    where
        T: for<'a> Deserialize<'a>,
    {
        let map: FxHashMap<u128, T> = serde_json::from_str(json)?;
        let mut table = Table::with_capacity(map.len());
        for (key, value) in map {
            table.add_with_key(key, value);
        }
        Ok(table)
    }

    /// Serialize to CSV/TSV format
    pub fn to_csv<W: Write>(&self, writer: W, tsv: bool) -> Result<(), csv::Error>
    where
        T: Serialize,
    {
        let mut binding = csv::WriterBuilder::new();
        let mut builder = binding.has_headers(false);

        if tsv {
            builder = builder.delimiter(b'\t');
        }

        let mut wtr = builder.from_writer(writer);

        for (key, value) in self.iter() {
            wtr.serialize((key, value))?;
        }
        wtr.flush()?;
        Ok(())
    }

    /// Deserialize from CSV/TSV format
    pub fn from_csv<R: Read>(reader: R, tsv: bool) -> Result<Self, csv::Error>
    where
        T: for<'a> Deserialize<'a>,
    {
        let mut binding = csv::ReaderBuilder::new();
        let mut builder = binding.has_headers(false);

        if tsv {
            builder = builder.delimiter(b'\t');
        }

        let mut rdr = builder.from_reader(reader);
        let mut table = Table::default();
        for result in rdr.deserialize() {
            let (key, value): (u128, T) = result?;
            table.add_with_key(key, value);
        }
        Ok(table)
    }
}

impl<T: PartialEq> PartialEq for Table<T> {
    fn eq(&self, other: &Self) -> bool {
        if self.count() != other.count() {
            return false;
        }
        for (key, value) in self.iter() {
            if other.get(key) != Some(value) {
                return false;
            }
        }
        true
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::io::Cursor;

    #[derive(Serialize, Deserialize, Debug, PartialEq)]
    struct TestData {
        field1: i32,
        field2: String,
    }

    fn create_test_table() -> Table<TestData> {
        let mut table = Table::default();
        table.add_with_key(
            1,
            TestData {
                field1: 42,
                field2: "test".to_string(),
            },
        );
        table.add_with_key(
            2,
            TestData {
                field1: 24,
                field2: "example".to_string(),
            },
        );
        table
    }

    #[test]
    fn test_add_and_get() {
        let mut table: Table<i32> = Table::default();
        let key = table.add(42);
        assert_eq!(table.get(key), Some(&42));
    }

    #[test]
    fn test_add_with_key() {
        let mut table: Table<i32> = Table::default();
        let key = 123;
        table.add_with_key(key, 42);
        assert_eq!(table.get(key), Some(&42));
    }

    #[test]
    fn test_remove() {
        let mut table: Table<i32> = Table::default();
        let key = table.add(42);
        assert_eq!(table.remove(key), Some(42));
        assert_eq!(table.get(key), None);
    }

    #[test]
    fn test_count() {
        let mut table: Table<i32> = Table::default();
        assert_eq!(table.count(), 0);
        table.add(42);
        assert_eq!(table.count(), 1);

        let key = table.add(24);
        table.remove(key);
        assert_eq!(table.count(), 1);
    }

    #[test]
    fn test_values() {
        let mut table: Table<i32> = Table::default();
        table.add(42);
        table.add(24);
        let values: Vec<_> = table.values().collect();
        assert_eq!(values, vec![&42, &24]);
    }

    #[test]
    fn test_values_mut() {
        let mut table: Table<i32> = Table::default();
        let key1 = table.add(42);
        let key2 = table.add(24);

        for value in table.values_mut() {
            *value *= 2;
        }

        assert_eq!(table.get(key1), Some(&84));
        assert_eq!(table.get(key2), Some(&48));
    }

    #[test]
    fn test_edge_cases() {
        let mut table: Table<i32> = Table::default();
        let key1 = table.add(1);
        let key2 = table.add(2);
        assert_eq!(table.get(key1), Some(&1));
        assert_eq!(table.get(key2), Some(&2));
        assert_eq!(table.remove(key1), Some(1));
        assert_eq!(table.get(key1), None);
        assert_eq!(table.count(), 1);

        let key3 = 999;
        table.add_with_key(key3, 3);
        assert_eq!(table.get(key3), Some(&3));
        assert_eq!(table.remove(998), None);
        assert_eq!(table.get(998), None);

        let empty_table: Table<i32> = Table::default();
        assert_eq!(empty_table.count(), 0);
    }

    #[test]
    fn test_iter_empty() {
        let table: Table<i32> = Table::default();
        assert_eq!(table.iter().collect::<Vec<_>>(), Vec::<(u128, &i32)>::new());
    }

    #[test]
    fn test_iter() {
        let mut table: Table<i32> = Table::default();
        let key1 = table.add(10);
        let key2 = table.add(20);
        let pairs: Vec<_> = table.iter().collect();
        assert_eq!(pairs, vec![(key1, &10), (key2, &20)]);
    }

    #[test]
    fn test_iter_after_remove() {
        let mut table: Table<i32> = Table::default();
        let key1 = table.add(1);
        let key2 = table.add(2);
        assert_eq!(table.remove(key1), Some(1));
        let key3 = table.add(3);
        let pairs: Vec<_> = table.iter().collect();
        assert_eq!(pairs, vec![(key2, &2), (key3, &3)]);
    }

    #[test]
    fn test_iter_mut_empty() {
        let mut table: Table<i32> = Table::default();
        assert_eq!(
            table.iter_mut().collect::<Vec<_>>(),
            Vec::<(u128, &mut i32)>::new()
        );
    }

    #[test]
    fn test_iter_mut() {
        let mut table: Table<i32> = Table::default();
        let key1 = table.add(5);
        let key2 = table.add(6);
        for (_, v) in table.iter_mut() {
            *v *= 3;
        }
        assert_eq!(table.get(key1), Some(&15));
        assert_eq!(table.get(key2), Some(&18));
    }

    #[test]
    fn test_iter_mut_after_remove() {
        let mut table: Table<i32> = Table::default();
        let key1 = table.add(7);
        let key2 = table.add(8);
        table.remove(key1);
        let key3 = table.add(9);
        for (_, v) in table.iter_mut() {
            *v += 1;
        }
        assert_eq!(table.get(key2), Some(&9));
        assert_eq!(table.get(key3), Some(&10));
    }

    #[test]
    fn test_json_serialization() {
        let table = create_test_table();
        let json = table.to_json().unwrap();
        let deserialized = Table::from_json(&json).unwrap();
        assert_eq!(table, deserialized);
    }

    #[test]
    fn test_csv_serialization() {
        let table = create_test_table();
        let mut buffer = Vec::new();
        table.to_csv(&mut buffer, true).unwrap();
        let cursor = Cursor::new(buffer);
        let deserialized = Table::from_csv(cursor, true).unwrap();
        assert_eq!(table, deserialized);
    }
}