woot/
lib.rs

1// (C) Sebastian Köln <sebk@rynx.org> 2016
2
3//! Algorith from the following research paper:
4//!
5//! [Gérald Oster, Pascal Urso, Pascal Molli, Abdessamad Imine.
6//! Real time group editors without Operational transformation.
7//! [Research Report] RR-5580, INRIA. 2005, pp.24. <inria-00071240>](https://hal.inria.fr/inria-00071240)
8
9extern crate itertools;
10extern crate rand;
11extern crate num_traits;
12
13pub mod stamp;
14pub use stamp::IncrementalStamper;
15
16use std::clone::Clone;
17use std::fmt::Debug;
18use std::fmt::{Formatter, Error};
19use std::collections::{HashMap, LinkedList};
20use std::iter::Iterator;
21use std::hash::Hash;
22
23pub trait Key : Eq + Ord + Copy + Hash {}
24impl<S, C> Key for (S, C) where
25    S: Eq + Ord + Copy + Hash,
26    C: Eq + Ord + Copy + Hash {}
27    
28#[derive(Eq, PartialEq, Ord, PartialOrd, Copy, Clone)]
29pub enum Index<I> where I: Key {
30    Start,
31    Ident(I),
32    End
33}
34impl<I> Debug for Index<I> where I: Key + Debug {
35    fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
36        match self {
37            &Index::Start => write!(fmt, "Start"),
38            &Index::Ident(ref id) => id.fmt(fmt),
39            &Index::End => write!(fmt, "End")
40        }
41    }
42}
43
44
45#[derive(PartialEq, Copy, Clone, Debug)]
46enum ListIndex {
47    Start,
48    Mid(usize),
49    End
50}
51
52/// The symbol type of the string.
53// W-charcter
54// except the visible attribute was integrated with the value as an Option.
55// Represents one character and can be almost anything.
56#[derive(Clone)]
57pub struct Character<S, I: Key> {
58    id:         I,
59    value:      Option<S>,   // Some -> visible, None -> invisible
60    prev:       Index<I>,    // id_cp
61    next:       Index<I>     // id_cn
62}
63impl<S, I> Debug for Character<S, I> where S: Debug, I: Key + Debug {
64    fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
65        match &self.value {
66            &Some(ref v) => write!(fmt,
67                "C({:?} < {:?} @ {:?} < {:?})", self.prev, v, self.id, self.next
68            ),
69            &None => write!(fmt,
70                "C({:?} < Del @ {:?} < {:?})", self.prev, self.id, self.next
71            )
72        }
73    }
74}
75impl<S, I: Key> Character<S, I> {
76    /// Create a new Charater.
77    // 
78    /// Only use when deserialising a existing character.
79    pub fn new(id: I, value: S, prev: Index<I>, next: Index<I>) -> Character<S, I> {
80        Character {
81            id:     id,
82            value:  Some(value),
83            prev:   prev,
84            next:   next
85        }
86    }
87}
88
89/// Represents an Operation on the WString.
90#[derive(Clone)]
91pub enum Operation<S, I: Key> {
92    /// insert a new Charater
93    Ins(Character<S, I>),
94    
95    /// delete character with the given Key
96    Del(I)
97}
98impl<S: Debug, P: Key + Debug> Debug for Operation<S, P> {
99    fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
100        match self {
101            &Operation::Ins(ref c) => write!(fmt, "Ins({:?})", c),
102            &Operation::Del(k) => write!(fmt, "Del({:?})", k)
103        }
104    }
105}
106
107pub struct WStringIter<'a, S: 'a, P: Key + 'a> {
108    data:   &'a [Character<S, P>],
109    pos:    usize,
110    size:   usize
111}
112impl<'a, S, P: Key> Iterator for WStringIter<'a, S, P> {
113    type Item = &'a S;
114    fn next(&mut self) -> Option<&'a S> {
115        for pos in self.pos .. self.data.len() {
116            if let Some(ref v) = self.data[pos].value {
117                self.pos = pos + 1;
118                return Some(v);
119            }
120        }
121        None
122    }
123    
124    fn size_hint(&self) -> (usize, Option<usize>) {
125        (self.size, Some(self.size))
126    }
127}
128
129/// The actual String type
130pub struct WString<S, P: Key> {
131    data:       Vec<Character<S, P>>,
132    buf:        HashMap<P, LinkedList<Operation<S, P>>>,
133    size:       usize
134}
135impl<S, P> Debug for WString<S, P> where S: Debug, P: Key + Debug {
136    fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
137        try!(writeln!(fmt, "WString"));
138        for (stamp, items) in &self.buf {
139            try!(writeln!(fmt, "  queue for {:?}", stamp));
140            for item in items.iter() {
141                try!(writeln!(fmt, "    {:?}", item));
142            }
143        }
144        for (i, item) in self.data.iter().enumerate() {
145            try!(writeln!(fmt, "  data[{:4}]: {:?}", i, item));
146        }
147        Ok(())
148    }
149}
150
151impl<S, P> WString<S, P> where S: Clone, P: Key {
152    pub fn new() -> WString<S, P> {
153        WString {
154            data:       vec![],
155            buf:        HashMap::new(),
156            size:       0
157        }
158    }
159
160    /// Length of visible data.
161    pub fn len(&self) -> usize {
162        self.size
163    }
164    
165    /// Visible data
166    pub fn contents(&self) -> Vec<S> {
167        self.data.iter().filter_map(|c| c.value.clone()).collect()
168    }
169    
170    /// Visible data as an iterator
171    pub fn iter(&self) -> WStringIter<S, P> {
172        WStringIter::<S, P> {
173            data:   &self.data,
174            pos:    0,
175            size:   self.size
176        }
177    }
178    
179    fn pos_ident(&self, id: P, start: usize) -> Option<usize> {
180        self.data.iter().skip(start).position(|c| c.id == id).map(|i| i + start)
181    }
182    
183    // pos(S, c)
184    fn pos(&self, idx: Index<P>, start: usize) -> Option<ListIndex> {
185        match idx {
186            Index::Ident(id) => 
187                self.pos_ident(id, start).map(|i| ListIndex::Mid(i)),
188            Index::Start => Some(ListIndex::Start),
189            Index::End => Some(ListIndex::End)
190        }
191    }
192    
193    // insert(S, c, p)
194    // insert Character c at position p
195    fn insert(&mut self, c: Character<S, P>, p: usize) {
196        self.data.insert(p, c);
197        self.size += 1;
198    }
199    
200    // integrate between prev and next
201    fn integrate_ins(&mut self, c: Character<S, P>, mut prev: ListIndex, mut next: ListIndex) {
202        use std::cmp::Ordering;
203        use itertools::Itertools;
204        use std::iter::once;
205        
206        loop {
207            // i_0 is the first element to access
208            let i_0 = match prev {
209                ListIndex::Start => 0,
210                ListIndex::Mid(n) => n + 1,
211                ListIndex::End => panic!("got End as prev id")
212            };
213            
214            // i_(n-1) is the last element to access
215            // i_n is forbidden and may be 0
216            let i_n = match next {
217                ListIndex::Start => panic!("got Start as next id"),
218                ListIndex::Mid(n) => n,
219                ListIndex::End => self.data.len()
220            };
221            
222            //println!("i_0={}, i_n={}", i_0, i_n);
223            if i_0 == i_n {
224                self.insert(c, i_n);
225                return;
226            }
227            
228            // characters that do not fullfill this filter are ignored
229            let outside = |d: &[Character<S, P>], c: &Character<S, P>| {
230                d.iter()
231                .map(|c| Index::Ident(c.id))
232                .all(|idx| idx != c.prev && idx != c.next)
233            };
234            
235            let it = self.data[i_0 .. i_n].iter()
236            .enumerate() // we have to track the indices!
237            .filter(|&(_, c)| outside(&self.data[i_0 .. i_n], c)) // ignore any inner characters
238            .map(|(id, c_i)| (ListIndex::Mid(i_0 + id), c_i.id.cmp(&c.id)));
239            
240            let it2 = once((prev, Ordering::Less))
241            .chain(it).chain(once((next, Ordering::Greater)))
242            .peekable()
243            .batching(|mut it| match (it.next(), it.peek()) {
244                (Some(a), Some(&b)) => Some((a, b)),
245                _ => None
246            })
247            .peekable();
248            
249            let mut c_p = prev;
250            let mut c_n = next;
251            for ((p_idx, _), (n_idx, n_cmp)) in it2 {
252                c_p = p_idx;
253                c_n = n_idx;
254                
255                if n_cmp != Ordering::Less {
256                    break;
257                }
258            }
259            
260            assert!(c_p != prev || c_n != next, "no progress!");
261            prev = c_p;
262            next = c_n;
263        }
264    }
265    
266    fn enqueue(&mut self, id: P, op: Operation<S, P>) {
267        self.buf.entry(id).or_insert_with(LinkedList::new).push_front(op)
268    }
269    
270    fn delete(&mut self, p: usize) {
271        match self.data[p].value.take() {
272            Some(_) => {
273                self.size -= 1;
274            },
275            None => {
276                println!("already deleted");
277            }
278        }
279    }
280    
281    /// Applies Operation op.
282    pub fn apply(&mut self, op: Operation<S, P>) {
283        // remove reference when borrowck allows so
284        match op {
285            Operation::Ins(c) => {
286                if let Some(prev) = self.pos(c.prev, 0) {
287                    if let Some(next) = self.pos(c.next, 0) { // set start to prev
288                        /*
289                        println!("integrate {:?} between {:?} < {:?}", c, prev, next);
290                        for (j, d) in self.data.iter().enumerate() {
291                            println!("{:2} {:?}", j, d);
292                        }
293                        */
294                        let id = c.id;
295                        self.integrate_ins(c, prev, next);
296                        /*
297                        println!("now:");
298                        for (j, d) in self.data.iter().enumerate() {
299                            println!("{:2} {:?}", j, d);
300                        }
301                        */
302                        // remove the entry. The id is now known.
303                        match self.buf.remove(&id) {
304                            Some(list) => {
305                                for op in list.into_iter() {
306                                    self.apply(op);
307                                }
308                            },
309                            None => {}
310                        }
311                    } else { // next node missing
312                        match c.next {
313                            Index::Ident(next) => self.enqueue(next, Operation::Ins(c)),
314                            _ => unreachable!()
315                        }
316                    }
317                } else { // prev is missing
318                    match c.prev {
319                        Index::Ident(prev) => self.enqueue(prev, Operation::Ins(c)),
320                        _ => unreachable!()
321                    }
322                }
323            },
324            Operation::Del(id) => {
325                if let Some(i) = self.pos_ident(id, 0) {
326                    self.data[i].value = None;
327                } else {
328                    self.enqueue(id, Operation::Del(id));
329                }
330            }
331        }
332    }
333    
334    /// Insert v at position n.
335    /// This will panic if n > len()
336    pub fn ins(&mut self, n: usize, v: S, stamp: P) -> Operation<S, P> {
337        let (c, prev, next) = {
338            let mut it = self.data.iter()
339            .enumerate()
340            .filter(|&(_, c)| c.value.is_some());
341            
342            let (prev_idx, prev) = match n {
343                0 => (ListIndex::Start, Index::Start), 
344                _ => {
345                    let (idx, c) = it.by_ref().skip(n-1)
346                    .next().expect("out of bounds");
347                    (ListIndex::Mid(idx), Index::Ident(c.id))
348                }
349            };
350            let (next_idx, next) = match it.next() {
351                Some((idx, c)) => (ListIndex::Mid(idx), Index::Ident(c.id)),
352                None           => (ListIndex::End, Index::End)
353            };
354            
355            let c = Character {
356                id:         stamp,
357                value:      Some(v),
358                prev:       prev,
359                next:       next
360            };
361            
362            (c, prev_idx, next_idx)
363        };
364        // WRONG !! that would be integrate between S[idx] and S[idx+1]
365        // we need nthVisible(n-1) and nthVisible(n)
366        // self.insert(&c, idx+1);
367        
368        // double check
369        // pos returns indices offset by +1
370        //assert_eq!(self.pos(c.prev, 0), Some(prev));
371        //assert_eq!(self.pos(c.next, 0), Some(next));
372        // println!("send integrate {:?} between {:?} < {:?}", c, prev, next);
373        self.integrate_ins(c.clone(), prev, next);
374        
375        Operation::Ins(c)
376    }
377    
378    /// delete charater at position n
379    /// panics if n >= len()
380    pub fn del(&mut self, n: usize) -> Operation<S, P> {
381        let (p, id) = self.data.iter()
382        .enumerate()
383        .filter(|&(_, c)| c.value.is_some())
384        .map(|(i, c)| (i, c.id))
385        .skip(n)
386        .next().expect("out of bounds");
387        
388        self.delete(p);
389        
390        Operation::Del(id)
391    }
392}
393
394
woot/lib.rs

woot/
lib.rs
