crdts/
glist.rs

1//! # GList - Grow-only List CRDT
2
3use core::convert::Infallible;
4use core::fmt;
5use core::iter::FromIterator;
6use core::ops::Bound::*;
7use std::collections::BTreeSet;
8
9use serde::{Deserialize, Serialize};
10
11use crate::{CmRDT, CvRDT, Identifier};
12
13/// Operations that can be performed on a List
14#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
15pub enum Op<T> {
16    /// Insert an element.
17    Insert {
18        /// The element identifier to insert.
19        id: Identifier<T>,
20    },
21}
22
23/// The GList is a grow-only list, that is, it allows inserts but not deletes.
24/// Elements in the list are paths through an ordered tree, the tree grows deeper
25/// when we try to insert between two elements who were inserted concurrently and
26/// whose paths happen to have the same prefix.
27#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
28pub struct GList<T: Ord> {
29    list: BTreeSet<Identifier<T>>,
30}
31
32impl<T: fmt::Display + Ord> fmt::Display for GList<T> {
33    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
34        write!(f, "GList[")?;
35        let mut iter = self.list.iter();
36        if let Some(e) = iter.next() {
37            write!(f, "{}", e)?;
38        }
39        for e in iter {
40            write!(f, "{}", e)?;
41        }
42        write!(f, "]")
43    }
44}
45
46impl<T: Ord> Default for GList<T> {
47    fn default() -> Self {
48        Self {
49            list: Default::default(),
50        }
51    }
52}
53
54impl<T: Ord + Clone> GList<T> {
55    /// Create an empty GList
56    pub fn new() -> Self {
57        Self::default()
58    }
59
60    /// Read the elements of the list into a user defined container
61    pub fn read<'a, C: FromIterator<&'a T>>(&'a self) -> C {
62        self.list.iter().map(|id| id.value()).collect()
63    }
64
65    /// Read the elements of the list into a user defined container, consuming the list in the process.
66    pub fn read_into<C: FromIterator<T>>(self) -> C {
67        self.list.into_iter().map(|id| id.into_value()).collect()
68    }
69
70    /// Iterate over the elements of the list
71    pub fn iter(&self) -> std::collections::btree_set::Iter<Identifier<T>> {
72        self.list.iter()
73    }
74
75    /// Return the element and it's marker at the specified index
76    pub fn get(&self, idx: usize) -> Option<&Identifier<T>> {
77        self.list.iter().nth(idx)
78    }
79
80    /// Generate an Op to insert the given element before the given marker
81    pub fn insert_before(&self, high_id_opt: Option<&Identifier<T>>, elem: T) -> Op<T> {
82        let low_id_opt = high_id_opt.and_then(|high_id| {
83            self.list
84                .range((Unbounded, Excluded(high_id.clone())))
85                .rev()
86                .find(|id| id < &high_id)
87        });
88        let id = Identifier::between(low_id_opt, high_id_opt, elem);
89        Op::Insert { id }
90    }
91
92    /// Generate an insert op to insert the given element after the given marker
93    pub fn insert_after(&self, low_id_opt: Option<&Identifier<T>>, elem: T) -> Op<T> {
94        let high_id_opt = low_id_opt.and_then(|low_id| {
95            self.list
96                .range((Excluded(low_id.clone()), Unbounded))
97                .find(|id| id > &low_id)
98        });
99        let id = Identifier::between(low_id_opt, high_id_opt, elem);
100        Op::Insert { id }
101    }
102
103    /// Get the length of the list.
104    pub fn len(&self) -> usize {
105        self.list.len()
106    }
107
108    /// Check if the list is empty.
109    pub fn is_empty(&self) -> bool {
110        self.list.is_empty()
111    }
112
113    /// Get first element of the sequence represented by the list.
114    pub fn first(&self) -> Option<&Identifier<T>> {
115        self.iter().next()
116    }
117
118    /// Get last element of the sequence represented by the list.
119    pub fn last(&self) -> Option<&Identifier<T>> {
120        self.iter().next_back()
121    }
122}
123
124impl<T: Ord> CmRDT for GList<T> {
125    type Op = Op<T>;
126    type Validation = Infallible;
127
128    fn validate_op(&self, _: &Self::Op) -> Result<(), Self::Validation> {
129        Ok(())
130    }
131
132    fn apply(&mut self, op: Self::Op) {
133        match op {
134            Op::Insert { id } => self.list.insert(id),
135        };
136    }
137}
138
139impl<T: Ord> CvRDT for GList<T> {
140    type Validation = Infallible;
141
142    fn validate_merge(&self, _: &Self) -> Result<(), Self::Validation> {
143        Ok(())
144    }
145
146    fn merge(&mut self, other: Self) {
147        self.list.extend(other.list)
148    }
149}
150
151#[cfg(feature = "quickcheck")]
152use quickcheck::{Arbitrary, Gen};
153
154#[cfg(feature = "quickcheck")]
155impl<T: Arbitrary> Arbitrary for Op<T> {
156    fn arbitrary(g: &mut Gen) -> Self {
157        let id = Identifier::arbitrary(g);
158        Op::Insert { id }
159    }
160}
crdts/glist.rs

crdts/
glist.rs
