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