1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#![forbid(unsafe_code)]
#![deny(missing_docs, missing_debug_implementations)]

//! A simple library implementing an immutable, flat representation of an [augmented interval tree](https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree)
//!
//! Supports querying for overlapping intervals without temporary allocations and uses a flat memory layout that can be backed by memory maps.

mod query;
mod sort;

use std::marker::PhantomData;
use std::ops::{Deref, Range};

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

/// The items stored in the tree consisting of an interval and an associated value
pub type Item<K, V> = (Range<K>, V);

/// The nodes of which the tree is built consisting of an item and the maximum of the interval upper bounds in the subtree
pub type Node<K, V> = (Item<K, V>, K);

/// Interval tree mapping half-open intervals with boundaries of type `K` to values of type `V`
#[derive(Debug, Default, Clone)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(feature = "serde", serde(transparent))]
pub struct ITree<K, V, S = Box<[Node<K, V>]>> {
    nodes: S,
    _marker: PhantomData<(K, V)>,
}

impl<K, V, S> Deref for ITree<K, V, S>
where
    S: AsRef<[Node<K, V>]>,
{
    type Target = [Node<K, V>];

    fn deref(&self) -> &Self::Target {
        self.nodes.as_ref()
    }
}

impl<K, V, S> AsRef<[Node<K, V>]> for ITree<K, V, S>
where
    S: AsRef<[Node<K, V>]>,
{
    fn as_ref(&self) -> &[Node<K, V>] {
        self.nodes.as_ref()
    }
}

impl<K, V, S> ITree<K, V, S>
where
    S: AsRef<[Node<K, V>]>,
{
    /// Interprets the given `nodes` as a tree
    ///
    /// Supplying `nodes` which are not actually organized as an interval tree is safe but will lead to incorrect results.
    pub fn new_unchecked(nodes: S) -> Self {
        Self {
            nodes,
            _marker: PhantomData,
        }
    }

    /// Iterate over all intervals
    pub fn iter(&self) -> impl ExactSizeIterator<Item = &Item<K, V>> {
        self.nodes.as_ref().iter().map(|node| &node.0)
    }
}