cranpose-core 0.18.0

//! The nodes of deactivated slots that later slots can take, and how many
//! of them stay.

use std::collections::VecDeque;

use super::SlotId;
use crate::{NodeId, collections::map::HashMap};

const DEFAULT_MAX_PER_TYPE: usize = 5;

const DEFAULT_MAX_UNTYPED: usize = 10;

// The passes a node waits in the pool before it goes. A list that scrolls
// takes the node that left last; the ones a jump left wait at the bottom.
const PASSES_KEPT: u32 = 16;

// A deactivated node and the pass it came to the pool in.
#[derive(Clone, Copy)]
struct Pooled {
    slot: SlotId,
    node: NodeId,
    pass: u32,
}

// The nodes of deactivated slots, oldest first: a queue for each content type
// and one for the slots without a type, each bounded by its limit.
pub(super) struct ReusePool {
    by_type: HashMap<u64, VecDeque<Pooled>>,
    untyped: VecDeque<Pooled>,
    max_per_type: usize,
    max_untyped: usize,
    // The running pass, counted up by `end_pass`. Every node goes within
    // `PASSES_KEPT` passes, so the count wraps without making a node look
    // younger than it is.
    pass: u32,
}

impl ReusePool {
    pub(super) fn new() -> Self {
        Self {
            by_type: HashMap::default(),
            untyped: VecDeque::new(),
            max_per_type: DEFAULT_MAX_PER_TYPE,
            max_untyped: DEFAULT_MAX_UNTYPED,
            pass: 0,
        }
    }

    pub(super) fn set_limits(&mut self, per_type: usize, untyped: usize) {
        self.max_per_type = per_type;
        self.max_untyped = untyped;
    }

    pub(super) fn type_count(&self) -> usize {
        self.by_type.len()
    }

    pub(super) fn untyped_len(&self) -> usize {
        self.untyped.len()
    }

    // Adds the nodes of `slot`, deactivated, to the queue of `content_type`.
    pub(super) fn push(
        &mut self,
        content_type: Option<u64>,
        slot: SlotId,
        nodes: impl IntoIterator<Item = NodeId>,
    ) {
        let pass = self.pass;
        let queue = match content_type {
            Some(content_type) => self.by_type.entry(content_type).or_default(),
            None => &mut self.untyped,
        };
        queue.extend(nodes.into_iter().map(|node| Pooled { slot, node, pass }));
    }

    // Takes the newest node of the queue of `content_type`, the untyped one
    // for `None`, whose slot `accepts`: the one that left last, so the older
    // ones age out.
    pub(super) fn take(
        &mut self,
        content_type: Option<u64>,
        mut accepts: impl FnMut(SlotId) -> bool,
    ) -> Option<(SlotId, NodeId)> {
        let Some(content_type) = content_type else {
            let index = self
                .untyped
                .iter()
                .rposition(|pooled| accepts(pooled.slot))?;
            return self.untyped.remove(index).map(Pooled::taken);
        };
        let queue = self.by_type.get_mut(&content_type)?;
        let index = queue.iter().rposition(|pooled| accepts(pooled.slot))?;
        let taken = queue.remove(index);
        if queue.is_empty() {
            self.by_type.remove(&content_type);
        }
        taken.map(Pooled::taken)
    }

    // Takes `node` out of whichever queue holds it, and returns its slot.
    pub(super) fn remove_node(&mut self, node: NodeId) -> Option<SlotId> {
        let typed = self.by_type.iter().find_map(|(&content_type, queue)| {
            queue
                .iter()
                .position(|pooled| pooled.node == node)
                .map(|position| (content_type, position))
        });
        if let Some((content_type, position)) = typed {
            let queue = self.by_type.get_mut(&content_type)?;
            let pooled = queue.remove(position)?;
            if queue.is_empty() {
                self.by_type.remove(&content_type);
            }
            return Some(pooled.slot);
        }
        let position = self.untyped.iter().position(|pooled| pooled.node == node)?;
        self.untyped.remove(position).map(|pooled| pooled.slot)
    }

    // Takes out the oldest nodes past each queue's limit: the typed queues'
    // first, then the untyped one's.
    pub(super) fn take_excess(&mut self) -> Vec<(SlotId, NodeId)> {
        let mut excess = Vec::new();
        for queue in self.by_type.values_mut() {
            while queue.len() > self.max_per_type {
                excess.extend(queue.pop_front().map(Pooled::taken));
            }
        }
        while self.untyped.len() > self.max_untyped {
            excess.extend(self.untyped.pop_front().map(Pooled::taken));
        }
        self.by_type.retain(|_, queue| !queue.is_empty());
        excess
    }

    // Ends a pass: takes out the nodes that waited `PASSES_KEPT` passes,
    // which no slot took back or over. Each queue holds its nodes in the
    // order they came, so they leave from its front.
    pub(super) fn end_pass(&mut self) -> Vec<(SlotId, NodeId)> {
        self.pass = self.pass.wrapping_add(1);
        let pass = self.pass;
        let expired = |pooled: &Pooled| pass.wrapping_sub(pooled.pass) > PASSES_KEPT;
        let mut expired_nodes = Vec::new();
        for queue in self.by_type.values_mut() {
            while queue.front().is_some_and(expired) {
                expired_nodes.extend(queue.pop_front().map(Pooled::taken));
            }
        }
        while self.untyped.front().is_some_and(expired) {
            expired_nodes.extend(self.untyped.pop_front().map(Pooled::taken));
        }
        self.by_type.retain(|_, queue| !queue.is_empty());
        expired_nodes
    }

    // Every node the pool holds: the typed queues' first.
    pub(super) fn nodes(&self) -> impl Iterator<Item = NodeId> + '_ {
        self.by_type
            .values()
            .flat_map(|queue| queue.iter().map(|pooled| pooled.node))
            .chain(self.untyped.iter().map(|pooled| pooled.node))
    }
}

impl Pooled {
    fn taken(self) -> (SlotId, NodeId) {
        (self.slot, self.node)
    }
}