sif_itree/
lib.rs

1#![forbid(unsafe_code)]
2#![deny(missing_docs, missing_debug_implementations)]
3
4//! A simple library implementing an immutable, flat representation of an [augmented interval tree](https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree)
5//!
6//! Supports querying for overlapping intervals without temporary allocations and uses a flat memory layout that can be backed by memory maps.
7
8mod query;
9mod sort;
10
11use std::marker::PhantomData;
12use std::ops::{Deref, Range};
13
14#[cfg(feature = "serde")]
15use serde::{Deserialize, Serialize};
16
17/// The items stored in the tree consisting of an interval and an associated value
18pub type Item<K, V> = (Range<K>, V);
19
20/// The nodes of which the tree is built consisting of an item and the maximum of the interval upper bounds in the subtree
21pub type Node<K, V> = (Item<K, V>, K);
22
23/// Interval tree mapping half-open or closed intervals with boundaries of type `K` to values of type `V`
24#[derive(Debug, Default, Clone)]
25#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
26#[cfg_attr(feature = "serde", serde(transparent))]
27pub struct ITree<K, V, S = Box<[Node<K, V>]>> {
28    nodes: S,
29    _marker: PhantomData<(K, V)>,
30}
31
32impl<K, V, S> Deref for ITree<K, V, S>
33where
34    S: AsRef<[Node<K, V>]>,
35{
36    type Target = [Node<K, V>];
37
38    fn deref(&self) -> &Self::Target {
39        self.nodes.as_ref()
40    }
41}
42
43impl<K, V, S> AsRef<[Node<K, V>]> for ITree<K, V, S>
44where
45    S: AsRef<[Node<K, V>]>,
46{
47    fn as_ref(&self) -> &[Node<K, V>] {
48        self.nodes.as_ref()
49    }
50}
51
52impl<K, V, S> ITree<K, V, S>
53where
54    S: AsRef<[Node<K, V>]>,
55{
56    /// Interprets the given `nodes` as a tree
57    ///
58    /// Supplying `nodes` which are not actually organized as an interval tree is safe but will lead to incorrect results.
59    pub fn new_unchecked(nodes: S) -> Self {
60        Self {
61            nodes,
62            _marker: PhantomData,
63        }
64    }
65
66    /// Iterate over all intervals
67    pub fn iter(&self) -> impl ExactSizeIterator<Item = &Item<K, V>> {
68        self.nodes.as_ref().iter().map(|node| &node.0)
69    }
70}
sif_itree/lib.rs

sif_itree/
lib.rs
