1use super::Operation;
  2use crate::time;
  3use gpui::sum_tree::{Cursor, Dimension, Edit, Item, KeyedItem, SumTree, Summary};
  4use std::{fmt::Debug, ops::Add};
  5
  6#[derive(Clone, Debug)]
  7pub struct OperationQueue(SumTree<Operation>);
  8
  9#[derive(Clone, Copy, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
 10pub struct OperationKey(time::Lamport);
 11
 12#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
 13pub struct OperationSummary {
 14    pub key: OperationKey,
 15    pub len: usize,
 16}
 17
 18impl OperationKey {
 19    pub fn new(timestamp: time::Lamport) -> Self {
 20        Self(timestamp)
 21    }
 22}
 23
 24impl OperationQueue {
 25    pub fn new() -> Self {
 26        OperationQueue(SumTree::new())
 27    }
 28
 29    pub fn len(&self) -> usize {
 30        self.0.summary().len
 31    }
 32
 33    pub fn insert(&mut self, mut ops: Vec<Operation>) {
 34        ops.sort_by_key(|op| op.lamport_timestamp());
 35        ops.dedup_by_key(|op| op.lamport_timestamp());
 36        self.0
 37            .edit(ops.into_iter().map(Edit::Insert).collect(), &());
 38    }
 39
 40    pub fn drain(&mut self) -> Self {
 41        let clone = self.clone();
 42        self.0 = SumTree::new();
 43        clone
 44    }
 45
 46    pub fn cursor(&self) -> Cursor<Operation, ()> {
 47        self.0.cursor()
 48    }
 49}
 50
 51impl Summary for OperationSummary {
 52    type Context = ();
 53
 54    fn add_summary(&mut self, other: &Self, _: &()) {
 55        assert!(self.key < other.key);
 56        self.key = other.key;
 57        self.len += other.len;
 58    }
 59}
 60
 61impl<'a> Add<&'a Self> for OperationSummary {
 62    type Output = Self;
 63
 64    fn add(self, other: &Self) -> Self {
 65        assert!(self.key < other.key);
 66        OperationSummary {
 67            key: other.key,
 68            len: self.len + other.len,
 69        }
 70    }
 71}
 72
 73impl<'a> Dimension<'a, OperationSummary> for OperationKey {
 74    fn add_summary(&mut self, summary: &OperationSummary, _: &()) {
 75        assert!(*self <= summary.key);
 76        *self = summary.key;
 77    }
 78}
 79
 80impl Item for Operation {
 81    type Summary = OperationSummary;
 82
 83    fn summary(&self) -> Self::Summary {
 84        OperationSummary {
 85            key: OperationKey::new(self.lamport_timestamp()),
 86            len: 1,
 87        }
 88    }
 89}
 90
 91impl KeyedItem for Operation {
 92    type Key = OperationKey;
 93
 94    fn key(&self) -> Self::Key {
 95        OperationKey::new(self.lamport_timestamp())
 96    }
 97}
 98
 99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn test_len() {
105        let mut clock = time::Lamport::new(0);
106
107        let mut queue = OperationQueue::new();
108        assert_eq!(queue.len(), 0);
109
110        queue.insert(vec![
111            Operation::Test(clock.tick()),
112            Operation::Test(clock.tick()),
113        ]);
114        assert_eq!(queue.len(), 2);
115
116        queue.insert(vec![Operation::Test(clock.tick())]);
117        assert_eq!(queue.len(), 3);
118
119        drop(queue.drain());
120        assert_eq!(queue.len(), 0);
121
122        queue.insert(vec![Operation::Test(clock.tick())]);
123        assert_eq!(queue.len(), 1);
124    }
125
126    #[derive(Clone, Debug, Eq, PartialEq)]
127    struct TestOperation(time::Lamport);
128}