minerva 0.2.0

extern crate alloc;

use alloc::collections::{BTreeMap, BTreeSet};

use crate::metis::Dot;

use super::DotStore;

mod collision;
mod iter;
mod store;

pub use collision::DotCollision;
pub use iter::DotMapIter;

/// A caller-keyed composition of dot stores: per key, a nested [`DotStore`],
/// with the *pair's* context vouching for every level at once.
///
/// The composition shape of the axis: `DotMap<K, DotSet>` is an
/// observed-remove set keyed by `K` (each key alive while any of its dots
/// survives), `DotMap<K, DotMap<..>>` nests, and a caller store slots in as
/// the leaf wherever application content lives. `K` is the caller's type and
/// minerva never reads it, the same posture as an
/// [`Event`](crate::metis::Event) payload.
///
/// # Canonical form
///
/// A key whose store is bottom is absent, so "key present" and "some dot
/// survives under the key" are the same fact, equality is structural, and a
/// key vanishes from the merge exactly when every dot under it is
/// superseded. Every constructor and fold preserves this.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct DotMap<K, S> {
    /// Per key, the nested store; bottom stores are never held (canonical
    /// form).
    entries: BTreeMap<K, S>,
}

impl<K, S> Default for DotMap<K, S> {
    fn default() -> Self {
        Self {
            entries: BTreeMap::new(),
        }
    }
}

impl<K: Ord + Clone, S: DotStore> DotMap<K, S> {
    /// Creates the empty map: no keys, no dots, the lattice bottom.
    #[must_use]
    pub const fn new() -> Self {
        Self {
            entries: BTreeMap::new(),
        }
    }

    /// A one-key map, the building block of write deltas: `store` under
    /// `key`, nothing else. A bottom `store` yields the empty map (canonical
    /// form holds by construction).
    #[must_use]
    pub fn singleton(key: K, store: S) -> Self {
        let mut entries = BTreeMap::new();
        if !store.is_bottom() {
            let _ = entries.insert(key, store);
        }
        Self { entries }
    }

    /// Sets `store` under `key`, returning whether it was held.
    ///
    /// Refused as a no-op (returning `false`, the tree unchanged) in two
    /// cases. A bottom `store` is refused to keep canonical form: removal is
    /// not an insertion but a merge whose context supersedes the key's dots.
    /// And a `store` that shares any dot with the store of a *different* key
    /// is refused to keep support exactness (trait law 1): a dot names one
    /// write and cannot straddle two keys, or the survivor law and
    /// content-follows-the-dot become undefined. Replacing the *same* key is
    /// always allowed, even when the new store overlaps the old one it
    /// replaces (the old store leaves with the key), as long as the new store
    /// stays disjoint from every other key.
    ///
    /// The disjointness check scans every dot currently held under the other
    /// keys, so the cost is `O(total dots held)` (plus the incoming store's
    /// dot count); a caller building large maps by repeated insertion pays
    /// that per call. [`from_disjoint`](Self::from_disjoint) is the one-pass
    /// build for a batch known disjoint, trading the repeated scan for a single
    /// `O(total dots)` validation.
    #[must_use = "insertion is refused (returns false) on a bottom store or a cross-key dot collision, which the caller must handle to keep the disjointness invariant"]
    pub fn insert(&mut self, key: K, store: S) -> bool {
        if store.is_bottom() {
            return false;
        }
        let incoming: BTreeSet<Dot> = store.dots().collect();
        let collides = self.entries.iter().any(|(other_key, held)| {
            *other_key != key && held.dots().any(|dot| incoming.contains(&dot))
        });
        if collides {
            return false;
        }
        let _ = self.entries.insert(key, store);
        true
    }

    /// Builds a map from entries known to be pairwise dot-disjoint, validating
    /// the whole batch in one `O(total dots)` pass, or refusing with the first
    /// colliding dot as a typed witness.
    ///
    /// The batch counterpart to repeated [`insert`](Self::insert): where
    /// building an `n`-key map by insertion pays an `O(total dots)` disjointness
    /// scan *per call* (quadratic overall), this accumulates every entry's dots
    /// into one set as it goes, so each dot is touched once. A bottom store is
    /// dropped to keep canonical form (as [`singleton`](Self::singleton) does),
    /// and a later entry replacing an earlier one's key keeps the later store
    /// (last write wins for a repeated key, exactly as `insert` replaces),
    /// after checking it against every *other* key's dots.
    ///
    /// # Errors
    ///
    /// [`DotCollision`] naming the first dot two different keys' stores share,
    /// in iteration order; nothing is built, since a colliding batch has no
    /// honest map (a dot names one write and cannot straddle two keys, trait
    /// law 1).
    pub fn from_disjoint(entries: impl IntoIterator<Item = (K, S)>) -> Result<Self, DotCollision> {
        // Every dot seen so far, mapped to the key that claimed it, so a
        // collision names the dot and both keys can be found in one pass. A
        // repeated key replaces its predecessor, so its old dots leave `seen`
        // with it before the new store is charged.
        let mut seen: BTreeMap<Dot, K> = BTreeMap::new();
        let mut map: BTreeMap<K, S> = BTreeMap::new();
        for (key, store) in entries {
            if store.is_bottom() {
                continue;
            }
            // A repeated key replaces its own prior store; release the old
            // store's dots so the replacement is checked only against *other*
            // keys (matching `insert`'s same-key allowance).
            if let Some(previous) = map.remove(&key) {
                for dot in previous.dots() {
                    let _ = seen.remove(&dot);
                }
            }
            // One pass over this store's dots: a dot already claimed by a
            // different key is the collision witness; otherwise claim it. Trait
            // law 1 makes `dots()` duplicate-free, so a within-store repeat
            // cannot masquerade as a cross-key collision. On error the whole
            // build is discarded, so charging `seen` as we go is safe.
            for dot in store.dots() {
                if let Some(other_key) = seen.get(&dot)
                    && *other_key != key
                {
                    return Err(DotCollision { dot });
                }
                let _ = seen.insert(dot, key.clone());
            }
            let _ = map.insert(key, store);
        }
        Ok(Self { entries: map })
    }

    /// The store under `key`, if any dot survives there.
    #[must_use]
    pub fn get(&self, key: &K) -> Option<&S> {
        self.entries.get(key)
    }

    /// Iterates the live `(key, store)` entries in ascending key order.
    #[must_use]
    pub fn iter(&self) -> DotMapIter<'_, K, S> {
        DotMapIter::new(self.entries.iter())
    }

    /// The number of live keys.
    #[must_use]
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Whether no key is live (the bottom map).
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }
}