1use lazy_static::lazy_static;
  2use smallvec::{smallvec, SmallVec};
  3use std::iter;
  4
  5lazy_static! {
  6    static ref MIN: Locator = Locator::min();
  7    static ref MAX: Locator = Locator::max();
  8}
  9
 10#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
 11pub struct Locator(SmallVec<[u64; 4]>);
 12
 13impl Locator {
 14    pub fn min() -> Self {
 15        Self(smallvec![u64::MIN])
 16    }
 17
 18    pub fn max() -> Self {
 19        Self(smallvec![u64::MAX])
 20    }
 21
 22    pub fn min_ref() -> &'static Self {
 23        &*MIN
 24    }
 25
 26    pub fn max_ref() -> &'static Self {
 27        &*MAX
 28    }
 29
 30    pub fn assign(&mut self, other: &Self) {
 31        self.0.resize(other.0.len(), 0);
 32        self.0.copy_from_slice(&other.0);
 33    }
 34
 35    pub fn between(lhs: &Self, rhs: &Self) -> Self {
 36        let lhs = lhs.0.iter().copied().chain(iter::repeat(u64::MIN));
 37        let rhs = rhs.0.iter().copied().chain(iter::repeat(u64::MAX));
 38        let mut location = SmallVec::new();
 39        for (lhs, rhs) in lhs.zip(rhs) {
 40            let mid = lhs + ((rhs.saturating_sub(lhs)) >> 48);
 41            location.push(mid);
 42            if mid > lhs {
 43                break;
 44            }
 45        }
 46        Self(location)
 47    }
 48
 49    pub fn len(&self) -> usize {
 50        self.0.len()
 51    }
 52
 53    pub fn is_empty(&self) -> bool {
 54        self.len() == 0
 55    }
 56}
 57
 58impl Default for Locator {
 59    fn default() -> Self {
 60        Self::min()
 61    }
 62}
 63
 64impl sum_tree::Item for Locator {
 65    type Summary = Locator;
 66
 67    fn summary(&self) -> Self::Summary {
 68        self.clone()
 69    }
 70}
 71
 72impl sum_tree::KeyedItem for Locator {
 73    type Key = Locator;
 74
 75    fn key(&self) -> Self::Key {
 76        self.clone()
 77    }
 78}
 79
 80impl sum_tree::Summary for Locator {
 81    type Context = ();
 82
 83    fn add_summary(&mut self, summary: &Self, _: &()) {
 84        self.assign(summary);
 85    }
 86}
 87
 88#[cfg(test)]
 89mod tests {
 90    use super::*;
 91    use rand::prelude::*;
 92    use std::mem;
 93
 94    #[gpui::test(iterations = 100)]
 95    fn test_locators(mut rng: StdRng) {
 96        let mut lhs = Default::default();
 97        let mut rhs = Default::default();
 98        while lhs == rhs {
 99            lhs = Locator(
100                (0..rng.gen_range(1..=5))
101                    .map(|_| rng.gen_range(0..=100))
102                    .collect(),
103            );
104            rhs = Locator(
105                (0..rng.gen_range(1..=5))
106                    .map(|_| rng.gen_range(0..=100))
107                    .collect(),
108            );
109        }
110
111        if lhs > rhs {
112            mem::swap(&mut lhs, &mut rhs);
113        }
114
115        let middle = Locator::between(&lhs, &rhs);
116        assert!(middle > lhs);
117        assert!(middle < rhs);
118        for ix in 0..middle.0.len() - 1 {
119            assert!(
120                middle.0[ix] == *lhs.0.get(ix).unwrap_or(&0)
121                    || middle.0[ix] == *rhs.0.get(ix).unwrap_or(&0)
122            );
123        }
124    }
125}