indexset/core/
node.rs

1use ::core::ops::Deref;
2use alloc::vec::Vec;
3use core::borrow::Borrow;
4
5pub trait NodeLike<T: Ord> {
6    #[allow(dead_code)]
7    fn with_capacity(capacity: usize) -> Self;
8    #[allow(dead_code)]
9    fn get_ith(&self, index: usize) -> Option<&T>;
10    #[allow(dead_code)]
11    fn halve(&mut self) -> Self;
12    #[allow(dead_code)]
13    fn need_to_split(&self, border: usize, value: &T) -> bool;
14    #[allow(dead_code)]
15    fn len(&self) -> usize;
16    #[allow(dead_code)]
17    fn is_empty(&self) -> bool {
18        self.len() == 0
19    }
20    #[allow(dead_code)]
21    fn capacity(&self) -> usize;
22    #[allow(dead_code)]
23    fn insert(&mut self, value: T) -> (bool, usize);
24    #[allow(dead_code)]
25    fn contains<Q: Ord + ?Sized>(&self, value: &Q) -> bool
26    where
27        T: Borrow<Q>;
28    #[allow(dead_code)]
29    /// Must return `Some(i)` exactly when [`Self::contains`] is true, with
30    /// `get_ith(i)` equal to the requested value.
31    fn try_select<Q: Ord + ?Sized>(&self, value: &Q) -> Option<usize>
32    where
33        T: Borrow<Q>;
34    #[allow(dead_code)]
35    fn rank<Q: Ord + ?Sized>(&self, bound: ::core::ops::Bound<&Q>, from_start: bool) -> Option<usize>
36    where
37        T: Borrow<Q>;
38    #[allow(dead_code)]
39    fn delete<Q: Ord + ?Sized>(&mut self, value: &Q) -> Option<(T, usize)>
40    where
41        T: Borrow<Q>;
42    // Positional deletion is only used by the multimap concurrent-removal
43    // recovery path. Gate it so enabling this trait method is not an
44    // unconditional source-compatibility break for custom NodeLike impls that
45    // do not use multimap.
46    #[cfg(feature = "multimap")]
47    #[allow(dead_code)]
48    fn delete_at(&mut self, index: usize) -> Option<T>;
49    #[allow(dead_code)]
50    fn replace(&mut self, idx: usize, value: T) -> Option<T>;
51    #[allow(dead_code)]
52    fn max(&self) -> Option<&T>;
53    #[allow(dead_code)]
54    fn min(&self) -> Option<&T>;
55    #[allow(dead_code)]
56    fn iter<'a>(&'a self) -> ::core::slice::Iter<'a, T>
57    where
58        T: 'a;
59}
60
61#[cfg(all(feature = "std-binary-search", not(feature = "custom-binary-search")))]
62mod search_backend {
63    use core::borrow::Borrow;
64
65    #[cfg(test)]
66    pub(super) const NAME: &str = "std";
67
68    #[inline]
69    pub(super) fn search<Q, T>(haystack: &[T], needle: &Q) -> Result<usize, usize>
70    where
71        T: Borrow<Q> + Ord,
72        Q: Ord + ?Sized,
73    {
74        haystack.binary_search_by(|candidate| candidate.borrow().cmp(needle))
75    }
76}
77
78#[cfg(all(
79    feature = "superslice-binary-search",
80    not(any(
81        feature = "custom-binary-search",
82        feature = "std-binary-search",
83        feature = "wt-slice-binary-search"
84    ))
85))]
86mod search_backend {
87    use core::borrow::Borrow;
88    use superslice::Ext;
89
90    #[cfg(test)]
91    pub(super) const NAME: &str = "superslice";
92
93    #[inline]
94    pub(super) fn search<Q, T>(haystack: &[T], needle: &Q) -> Result<usize, usize>
95    where
96        T: Borrow<Q> + Ord,
97        Q: Ord + ?Sized,
98    {
99        let index = haystack.lower_bound_by(|candidate| candidate.borrow().cmp(needle));
100        match haystack.get(index) {
101            Some(candidate) if candidate.borrow().cmp(needle).is_eq() => Ok(index),
102            _ => Err(index),
103        }
104    }
105}
106
107#[cfg(all(
108    feature = "wt-slice-binary-search",
109    not(any(feature = "custom-binary-search", feature = "std-binary-search"))
110))]
111mod search_backend {
112    use core::borrow::Borrow;
113    use wt_slice::ExactSearch;
114
115    #[cfg(test)]
116    pub(super) const NAME: &str = "wt-slice";
117
118    #[inline]
119    pub(super) fn search<Q, T>(haystack: &[T], needle: &Q) -> Result<usize, usize>
120    where
121        T: Borrow<Q> + Ord,
122        Q: Ord + ?Sized,
123    {
124        haystack.exact_search_by(|candidate| candidate.borrow().cmp(needle))
125    }
126}
127
128#[cfg(any(
129    feature = "custom-binary-search",
130    not(any(
131        feature = "std-binary-search",
132        feature = "superslice-binary-search",
133        feature = "wt-slice-binary-search"
134    ))
135))]
136mod search_backend {
137    use core::borrow::Borrow;
138    use core::cmp::Ordering;
139
140    #[cfg(test)]
141    pub(super) const NAME: &str = "custom";
142
143    #[inline]
144    pub(super) fn search<Q, T>(haystack: &[T], needle: &Q) -> Result<usize, usize>
145    where
146        T: Borrow<Q> + Ord,
147        Q: Ord + ?Sized,
148    {
149        let mut j = haystack.len();
150        let mut i = 0;
151        let mut m = j >> 1;
152
153        while i != j {
154            debug_assert!(i <= m && m < j && j <= haystack.len());
155            // SAFETY: initialization establishes `i <= m < j <= haystack.len()`
156            // for a non-empty range, and both branches preserve that invariant.
157            let candidate = unsafe { haystack.get_unchecked(m) };
158            match candidate.borrow().cmp(needle) {
159                Ordering::Equal => return Ok(m),
160                Ordering::Less => {
161                    i = m + 1;
162                    m = (i + j) >> 1;
163                }
164                Ordering::Greater => {
165                    j = m;
166                    m = (i + j) >> 1;
167                }
168            }
169        }
170
171        Err(i)
172    }
173}
174
175// Search backend precedence is deterministic when features are composed:
176// custom > std > wt-slice > superslice. With no search feature selected, the
177// custom implementation is the compatibility fallback. Each backend's cfg
178// selects its implementation and test name together, preventing drift.
179use search_backend::search;
180
181/// Returns the first comparator-equal entry, or its insertion position.
182///
183/// This helper deliberately has one implementation across configured search
184/// backends: callers that compare only a prefix (such as map key without
185/// value) must not observe backend-dependent positions among duplicates.
186#[inline]
187pub(crate) fn search_by<T>(haystack: &[T], mut compare: impl FnMut(&T) -> core::cmp::Ordering) -> Result<usize, usize> {
188    let index = haystack.partition_point(|candidate| compare(candidate).is_lt());
189    match haystack.get(index) {
190        Some(candidate) if compare(candidate).is_eq() => Ok(index),
191        _ => Err(index),
192    }
193}
194
195#[inline]
196fn compute_positions_to_skip<Q, T: Ord>(haystack: &[T], bound: ::core::ops::Bound<&Q>, forward: bool) -> Option<usize>
197where
198    T: Borrow<Q> + Ord,
199    Q: Ord + ?Sized,
200{
201    let skipped = match (bound, forward) {
202        // A forward iterator skips values before the start bound.
203        (::core::ops::Bound::Included(value), true) => {
204            haystack.partition_point(|item| item.borrow().cmp(value).is_lt())
205        }
206        (::core::ops::Bound::Excluded(value), true) => {
207            haystack.partition_point(|item| item.borrow().cmp(value).is_le())
208        }
209
210        // A backward iterator skips values after the end bound.
211        (::core::ops::Bound::Included(value), false) => {
212            let first_greater = haystack.partition_point(|item| item.borrow().cmp(value).is_le());
213            haystack.len() - first_greater
214        }
215        (::core::ops::Bound::Excluded(value), false) => {
216            let first_equal = haystack.partition_point(|item| item.borrow().cmp(value).is_lt());
217            haystack.len() - first_equal
218        }
219        (::core::ops::Bound::Unbounded, _) => return None,
220    };
221
222    // Callers use this as the index of the last value to skip. No skipped
223    // values is represented by `None`.
224    skipped.checked_sub(1)
225}
226
227impl<T: Ord> NodeLike<T> for Vec<T> {
228    #[inline]
229    fn with_capacity(capacity: usize) -> Self {
230        Vec::with_capacity(capacity)
231    }
232    #[inline]
233    fn get_ith(&self, index: usize) -> Option<&T> {
234        self.get(index)
235    }
236    #[inline]
237    fn halve(&mut self) -> Self {
238        self.split_off(self.len() / 2)
239    }
240    #[inline]
241    fn need_to_split(&self, border: usize, _: &T) -> bool {
242        self.len() >= border
243    }
244    #[inline]
245    fn len(&self) -> usize {
246        self.len()
247    }
248    #[inline]
249    fn capacity(&self) -> usize {
250        self.capacity()
251    }
252    #[inline]
253    fn insert(&mut self, value: T) -> (bool, usize) {
254        match search(self, &value) {
255            Ok(idx) => (false, idx),
256            Err(idx) => {
257                self.insert(idx, value);
258                (true, idx)
259            }
260        }
261    }
262    #[inline]
263    fn contains<Q>(&self, value: &Q) -> bool
264    where
265        T: Borrow<Q> + Ord,
266        Q: Ord + ?Sized,
267    {
268        search(self, value).is_ok()
269    }
270    #[inline]
271    fn try_select<Q>(&self, value: &Q) -> Option<usize>
272    where
273        T: Borrow<Q> + Ord,
274        Q: Ord + ?Sized,
275    {
276        search(self, value).ok()
277    }
278    #[inline]
279    fn rank<Q>(&self, bound: ::core::ops::Bound<&Q>, from_start: bool) -> Option<usize>
280    where
281        T: Borrow<Q> + Ord,
282        Q: Ord + ?Sized,
283    {
284        compute_positions_to_skip(self, bound, from_start)
285    }
286    #[inline]
287    fn delete<Q>(&mut self, value: &Q) -> Option<(T, usize)>
288    where
289        T: Borrow<Q> + Ord,
290        Q: Ord + ?Sized,
291    {
292        match search(self, value) {
293            Ok(idx) => Some((self.remove(idx), idx)),
294            Err(_) => None,
295        }
296    }
297    #[cfg(feature = "multimap")]
298    #[inline]
299    fn delete_at(&mut self, index: usize) -> Option<T> {
300        if index < self.len() {
301            Some(self.remove(index))
302        } else {
303            None
304        }
305    }
306    #[inline]
307    fn replace(&mut self, idx: usize, value: T) -> Option<T> {
308        if let Some(old) = self.get_mut(idx) {
309            let old = ::core::mem::replace(old, value);
310            return Some(old);
311        }
312
313        None
314    }
315    #[inline]
316    fn max(&self) -> Option<&T> {
317        self.last()
318    }
319    #[inline]
320    fn min(&self) -> Option<&T> {
321        self.first()
322    }
323    #[inline]
324    fn iter<'a>(&'a self) -> ::core::slice::Iter<'a, T>
325    where
326        T: 'a,
327    {
328        self.deref().iter()
329    }
330}
331
332#[cfg(test)]
333mod tests {
334    use super::*;
335
336    #[derive(Eq, Ord, PartialEq, PartialOrd)]
337    struct KeyThenValue(usize, &'static str);
338
339    impl Borrow<usize> for KeyThenValue {
340        fn borrow(&self) -> &usize {
341            &self.0
342        }
343    }
344
345    #[test]
346    fn configured_search_implementation_matches_precedence() {
347        #[cfg(feature = "custom-binary-search")]
348        assert_eq!(search_backend::NAME, "custom");
349
350        #[cfg(all(feature = "std-binary-search", not(feature = "custom-binary-search")))]
351        assert_eq!(search_backend::NAME, "std");
352
353        #[cfg(all(
354            feature = "wt-slice-binary-search",
355            not(any(feature = "custom-binary-search", feature = "std-binary-search"))
356        ))]
357        assert_eq!(search_backend::NAME, "wt-slice");
358
359        #[cfg(all(
360            feature = "superslice-binary-search",
361            not(any(
362                feature = "custom-binary-search",
363                feature = "std-binary-search",
364                feature = "wt-slice-binary-search"
365            ))
366        ))]
367        assert_eq!(search_backend::NAME, "superslice");
368
369        #[cfg(not(any(
370            feature = "custom-binary-search",
371            feature = "std-binary-search",
372            feature = "superslice-binary-search",
373            feature = "wt-slice-binary-search"
374        )))]
375        assert_eq!(search_backend::NAME, "custom");
376    }
377
378    #[test]
379    fn comparator_search_returns_first_duplicate() {
380        let values = [(1, "a"), (1, "b"), (1, "c"), (2, "d")];
381        assert_eq!(search_by(&values, |candidate| candidate.0.cmp(&1)), Ok(0));
382        assert_eq!(search_by(&values, |candidate| candidate.0.cmp(&2)), Ok(3));
383        assert_eq!(search_by(&values, |candidate| candidate.0.cmp(&0)), Err(0));
384    }
385
386    #[test]
387    fn point_search_returns_match_or_insertion_position() {
388        for values in [vec![], vec![2], vec![2, 4, 8, 16, 32]] {
389            for needle in 0..=34 {
390                let insertion = values.partition_point(|candidate| candidate < &needle);
391                let expected = match values.get(insertion) {
392                    Some(candidate) if candidate == &needle => Ok(insertion),
393                    _ => Err(insertion),
394                };
395
396                assert_eq!(search(&values, &needle), expected, "values={values:?}, needle={needle}");
397            }
398        }
399    }
400
401    #[test]
402    fn test_search_bound() {
403        let vec = vec![1, 3, 5, 7, 9];
404
405        assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Unbounded, true), None);
406        assert_eq!(compute_positions_to_skip(&vec, std::ops::Bound::Unbounded, false), None);
407
408        assert_eq!(
409            compute_positions_to_skip(&vec, std::ops::Bound::Included(&1), true),
410            None
411        );
412        assert_eq!(
413            compute_positions_to_skip(&vec, std::ops::Bound::Included(&5), true),
414            Some(1)
415        );
416        assert_eq!(
417            compute_positions_to_skip(&vec, std::ops::Bound::Included(&9), true),
418            Some(3)
419        );
420        assert_eq!(
421            compute_positions_to_skip(&vec, std::ops::Bound::Included(&0), true),
422            None
423        );
424        assert_eq!(
425            compute_positions_to_skip(&vec, std::ops::Bound::Included(&10), true),
426            Some(4)
427        );
428
429        assert_eq!(
430            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&1), true),
431            Some(0)
432        );
433        assert_eq!(
434            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&5), true),
435            Some(2)
436        );
437        assert_eq!(
438            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&9), true),
439            Some(4)
440        );
441        assert_eq!(
442            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&0), true),
443            None
444        );
445        assert_eq!(
446            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&10), true),
447            Some(4)
448        );
449
450        assert_eq!(
451            compute_positions_to_skip(&vec, std::ops::Bound::Included(&1), false),
452            Some(3)
453        );
454        assert_eq!(
455            compute_positions_to_skip(&vec, std::ops::Bound::Included(&5), false),
456            Some(1)
457        );
458        assert_eq!(
459            compute_positions_to_skip(&vec, std::ops::Bound::Included(&9), false),
460            None
461        );
462        assert_eq!(
463            compute_positions_to_skip(&vec, std::ops::Bound::Included(&0), false),
464            Some(4)
465        );
466        assert_eq!(
467            compute_positions_to_skip(&vec, std::ops::Bound::Included(&10), false),
468            None
469        );
470
471        assert_eq!(
472            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&1), false),
473            Some(4)
474        );
475        assert_eq!(
476            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&5), false),
477            Some(2)
478        );
479        assert_eq!(
480            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&9), false),
481            Some(0)
482        );
483        assert_eq!(
484            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&0), false),
485            Some(4)
486        );
487        assert_eq!(
488            compute_positions_to_skip(&vec, std::ops::Bound::Excluded(&10), false),
489            None
490        );
491
492        let empty: Vec<i32> = vec![];
493        assert_eq!(
494            compute_positions_to_skip(&empty, std::ops::Bound::Included(&1), true),
495            None
496        );
497        assert_eq!(
498            compute_positions_to_skip(&empty, std::ops::Bound::Excluded(&1), false),
499            None
500        );
501    }
502    #[test]
503    fn excluded_borrowed_bound_skips_all_equal_keys() {
504        let node = vec![KeyThenValue(1, "a"), KeyThenValue(1, "b"), KeyThenValue(2, "a")];
505
506        assert_eq!(
507            compute_positions_to_skip(&node, std::ops::Bound::Excluded(&1), true),
508            Some(1),
509        );
510    }
511
512    #[test]
513    fn excluded_borrowed_end_bound_skips_all_equal_keys() {
514        let node = vec![
515            KeyThenValue(1, "a"),
516            KeyThenValue(2, "a"),
517            KeyThenValue(2, "b"),
518            KeyThenValue(3, "a"),
519        ];
520
521        assert_eq!(
522            compute_positions_to_skip(&node, std::ops::Bound::Excluded(&2), false),
523            Some(2),
524        );
525    }
526
527    #[test]
528    fn binary_bound_search_matches_linear_bound_semantics() {
529        fn expected(values: &[i32], bound: std::ops::Bound<&i32>, forward: bool) -> Option<usize> {
530            let skipped = match (bound, forward) {
531                (std::ops::Bound::Included(value), true) => values.iter().take_while(|item| *item < value).count(),
532                (std::ops::Bound::Excluded(value), true) => values.iter().take_while(|item| *item <= value).count(),
533                (std::ops::Bound::Included(value), false) => {
534                    values.iter().rev().take_while(|item| *item > value).count()
535                }
536                (std::ops::Bound::Excluded(value), false) => {
537                    values.iter().rev().take_while(|item| *item >= value).count()
538                }
539                (std::ops::Bound::Unbounded, _) => return None,
540            };
541
542            skipped.checked_sub(1)
543        }
544
545        let cases = [vec![], vec![1], vec![1, 3, 5, 7, 9], vec![1, 1, 1, 2, 2, 4, 7, 7, 9]];
546
547        for values in cases {
548            for probe in 0..=10 {
549                for forward in [true, false] {
550                    for bound in [std::ops::Bound::Included(&probe), std::ops::Bound::Excluded(&probe)] {
551                        assert_eq!(
552                            compute_positions_to_skip(&values, bound, forward),
553                            expected(&values, bound, forward),
554                            "values={values:?}, probe={probe}, forward={forward}, bound={bound:?}",
555                        );
556                    }
557                }
558            }
559        }
560    }
561}
indexset/core/node.rs

indexset/core/
node.rs
