shared-framework 0.0.18

//! Integer-range to value lookup.
//!
//! [`RangeMap<V>`] stores non-overlapping ranges keyed by their lower bound and
//! resolves an integer key to the value whose `[low, high]` interval contains it.
//! 'Low' keys ranges, so adding a range with an existing `low` replaces it.
//!
//! ```ignore
//! let mut map = RangeMap::new();
//! map.add_range(0, 9, "low").unwrap();
//! assert_eq!(map.get(5), Some(&"low"));
//! ```

use std::collections::BTreeMap;

#[derive(Debug, Clone)]
struct RangeContainer<V> {
    low: i32,
    high: i32,
    value: V,
}

/// Maps inclusive integer ranges to values of type `V`.
#[derive(Debug, Clone, Default)]
pub struct RangeMap<V> {
    tree: BTreeMap<i32, RangeContainer<V>>,
}

impl<V: Clone + PartialEq> RangeMap<V> {
    /// Creates an empty range map.
    pub fn new() -> Self {
        Self {
            tree: BTreeMap::new(),
        }
    }

    /// Inserts the inclusive range `[low, high]`. Returns an error when `low > high`;
    /// a range with an existing `low` key is replaced.
    pub fn add_range(&mut self, low: i32, high: i32, value: V) -> Result<(), String> {
        if low > high {
            return Err(format!("low {low} > high {high}"));
        }
        self.tree.insert(low, RangeContainer { low, high, value });
        Ok(())
    }

    /// Returns the value whose range contains `key`, if any.
    pub fn get(&self, key: i32) -> Option<&V> {
        let entry = self.tree.range(..=key).next_back()?;
        let rc = entry.1;
        if key <= rc.high {
            Some(&rc.value)
        } else {
            None
        }
    }

    /// Removes the first range holding `value`. Returns true when one was removed.
    pub fn remove(&mut self, value: &V) -> bool {
        let key = self
            .tree
            .iter()
            .find(|(_, rc)| &rc.value == value)
            .map(|(k, _)| *k);
        if let Some(k) = key {
            self.tree.remove(&k);
            true
        } else {
            false
        }
    }

    /// Returns the lower bound of the first range containing `key`, if any.
    pub fn lower_bound(&self, key: i32) -> Option<i32> {
        self.tree.range(..=key).next_back().map(|(_, rc)| rc.low)
    }

    /// Returns the number of stored ranges.
    pub fn len(&self) -> usize {
        self.tree.len()
    }

    /// Returns true when no ranges are stored.
    pub fn is_empty(&self) -> bool {
        self.tree.is_empty()
    }

    /// Removes all ranges.
    pub fn clear(&mut self) {
        self.tree.clear();
    }
}