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    pub fn is_empty(&self) -> bool {
 46        self.len() == 0
 47    }
 48}
 49
 50impl Default for Locator {
 51    fn default() -> Self {
 52        Self::min()
 53    }
 54}
 55
 56impl sum_tree::Item for Locator {
 57    type Summary = Locator;
 58
 59    fn summary(&self) -> Self::Summary {
 60        self.clone()
 61    }
 62}
 63
 64impl sum_tree::KeyedItem for Locator {
 65    type Key = Locator;
 66
 67    fn key(&self) -> Self::Key {
 68        self.clone()
 69    }
 70}
 71
 72impl sum_tree::Summary for Locator {
 73    type Context = ();
 74
 75    fn add_summary(&mut self, summary: &Self, _: &()) {
 76        self.assign(summary);
 77    }
 78}
 79
 80#[cfg(test)]
 81mod tests {
 82    use super::*;
 83    use rand::prelude::*;
 84    use std::mem;
 85
 86    #[gpui::test(iterations = 100)]
 87    fn test_locators(mut rng: StdRng) {
 88        let mut lhs = Default::default();
 89        let mut rhs = Default::default();
 90        while lhs == rhs {
 91            lhs = Locator(
 92                (0..rng.gen_range(1..=5))
 93                    .map(|_| rng.gen_range(0..=100))
 94                    .collect(),
 95            );
 96            rhs = Locator(
 97                (0..rng.gen_range(1..=5))
 98                    .map(|_| rng.gen_range(0..=100))
 99                    .collect(),
100            );
101        }
102
103        if lhs > rhs {
104            mem::swap(&mut lhs, &mut rhs);
105        }
106
107        let middle = Locator::between(&lhs, &rhs);
108        assert!(middle > lhs);
109        assert!(middle < rhs);
110        for ix in 0..middle.0.len() - 1 {
111            assert!(
112                middle.0[ix] == *lhs.0.get(ix).unwrap_or(&0)
113                    || middle.0[ix] == *rhs.0.get(ix).unwrap_or(&0)
114            );
115        }
116    }
117}