sif_itree/
sort.rs

1use std::marker::PhantomData;
2
3#[cfg(feature = "rayon")]
4use rayon::{join, slice::ParallelSliceMut};
5
6use crate::{ITree, Item, Node};
7
8impl<K, V, S> ITree<K, V, S>
9where
10    K: Ord + Clone,
11    S: AsMut<[Node<K, V>]> + FromIterator<Node<K, V>>,
12{
13    /// Construct a new tree by sorting the given `items`
14    pub fn new<I>(items: I) -> Self
15    where
16        I: IntoIterator<Item = Item<K, V>>,
17    {
18        let mut nodes = items
19            .into_iter()
20            .map(|(interval, value)| {
21                let end = interval.end.clone();
22                ((interval, value), end)
23            })
24            .collect::<S>();
25
26        {
27            let nodes = nodes.as_mut();
28
29            nodes.sort_unstable_by(|lhs, rhs| (lhs.0).0.start.cmp(&(rhs.0).0.start));
30
31            if !nodes.is_empty() {
32                update_max(nodes);
33            }
34        }
35
36        Self {
37            nodes,
38            _marker: PhantomData,
39        }
40    }
41
42    #[cfg(feature = "rayon")]
43    /// Construct a new tree by sorting the given `items`, in parallel
44    ///
45    /// Requires the `rayon` feature and dispatches tasks into the current [thread pool][rayon::ThreadPool].
46    pub fn par_new<I>(items: I) -> Self
47    where
48        I: IntoIterator<Item = Item<K, V>>,
49        K: Send,
50        V: Send,
51    {
52        let mut nodes = items
53            .into_iter()
54            .map(|(interval, value)| {
55                let end = interval.end.clone();
56                ((interval, value), end)
57            })
58            .collect::<S>();
59
60        {
61            let nodes = nodes.as_mut();
62
63            nodes.par_sort_unstable_by(|lhs, rhs| (lhs.0).0.start.cmp(&(rhs.0).0.start));
64
65            if !nodes.is_empty() {
66                par_update_max(nodes);
67            }
68        }
69
70        Self {
71            nodes,
72            _marker: PhantomData,
73        }
74    }
75}
76
77impl<K, V, S> FromIterator<Item<K, V>> for ITree<K, V, S>
78where
79    K: Ord + Clone,
80    S: AsMut<[Node<K, V>]> + FromIterator<Node<K, V>>,
81{
82    fn from_iter<I>(items: I) -> Self
83    where
84        I: IntoIterator<Item = Item<K, V>>,
85    {
86        Self::new(items)
87    }
88}
89
90fn update_max<K, V>(nodes: &mut [Node<K, V>]) -> K
91where
92    K: Ord + Clone,
93{
94    let (left, [mid, right @ ..]) = nodes.split_at_mut(nodes.len() / 2) else {
95        unreachable!()
96    };
97
98    if !left.is_empty() {
99        mid.1 = mid.1.clone().max(update_max(left));
100    }
101
102    if !right.is_empty() {
103        mid.1 = mid.1.clone().max(update_max(right));
104    }
105
106    mid.1.clone()
107}
108
109#[cfg(feature = "rayon")]
110fn par_update_max<K, V>(nodes: &mut [Node<K, V>]) -> K
111where
112    K: Ord + Clone + Send,
113    V: Send,
114{
115    let (left, [mid, right @ ..]) = nodes.split_at_mut(nodes.len() / 2) else {
116        unreachable!()
117    };
118
119    match (left.is_empty(), right.is_empty()) {
120        (true, true) => (),
121        (false, true) => {
122            mid.1 = mid.1.clone().max(update_max(left));
123        }
124        (true, false) => {
125            mid.1 = mid.1.clone().max(update_max(right));
126        }
127        (false, false) => {
128            let (left, right) = join(|| update_max(left), || update_max(right));
129
130            mid.1 = mid.1.clone().max(left.max(right));
131        }
132    }
133
134    mid.1.clone()
135}
sif_itree/sort.rs

sif_itree/
sort.rs
