delta_btree_map/
lib.rs

1// Copyright 2025 RisingWave Labs
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![feature(btree_cursors)]
16
17use std::cmp::Ordering;
18use std::collections::{BTreeMap, btree_map};
19use std::ops::Bound;
20
21use educe::Educe;
22use enum_as_inner::EnumAsInner;
23
24/// [`DeltaBTreeMap`] wraps two [`BTreeMap`] references respectively as snapshot and delta,
25/// providing cursor that can iterate over the updated version of the snapshot.
26#[derive(Debug, Educe)]
27#[educe(Clone, Copy)]
28pub struct DeltaBTreeMap<'a, K: Ord, V> {
29    snapshot: &'a BTreeMap<K, V>,
30    delta: &'a BTreeMap<K, Change<V>>,
31
32    first_key: Option<&'a K>,
33    last_key: Option<&'a K>,
34}
35
36#[derive(Debug, Clone, Copy, PartialEq, Eq, EnumAsInner)]
37pub enum Change<V> {
38    Insert(V),
39    Delete,
40}
41
42impl<'a, K: Ord, V> DeltaBTreeMap<'a, K, V> {
43    /// Create a new [`DeltaBTreeMap`] from the given snapshot and delta.
44    /// Best case time complexity: O(1), worst case time complexity: O(m), where m is `delta.len()`.
45    pub fn new(snapshot: &'a BTreeMap<K, V>, delta: &'a BTreeMap<K, Change<V>>) -> Self {
46        let first_key = {
47            let cursor = CursorWithDelta {
48                ss_cursor: snapshot.lower_bound(Bound::Unbounded),
49                dt_cursor: delta.lower_bound(Bound::Unbounded),
50            };
51            cursor.peek_next().map(|(key, _)| key)
52        };
53        let last_key = {
54            let cursor = CursorWithDelta {
55                ss_cursor: snapshot.upper_bound(Bound::Unbounded),
56                dt_cursor: delta.upper_bound(Bound::Unbounded),
57            };
58            cursor.peek_prev().map(|(key, _)| key)
59        };
60        Self {
61            snapshot,
62            delta,
63            first_key,
64            last_key,
65        }
66    }
67
68    /// Get a reference to the snapshot.
69    pub fn snapshot(&self) -> &'a BTreeMap<K, V> {
70        self.snapshot
71    }
72
73    /// Get a reference to the delta.
74    pub fn delta(&self) -> &'a BTreeMap<K, Change<V>> {
75        self.delta
76    }
77
78    /// Get the first key in the updated version of the snapshot. Complexity: O(1).
79    pub fn first_key(&self) -> Option<&'a K> {
80        self.first_key
81    }
82
83    /// Get the last key in the updated version of the snapshot. Complexity: O(1).
84    pub fn last_key(&self) -> Option<&'a K> {
85        self.last_key
86    }
87
88    /// Get a [`CursorWithDelta`] pointing at the gap before the given given key.
89    /// If the given key is not found in either the snapshot or the delta, `None` is returned.
90    pub fn before(&self, key: &K) -> Option<CursorWithDelta<'a, K, V>> {
91        let cursor = self.lower_bound(Bound::Included(key));
92        if cursor.peek_next().map(|(k, _)| k) != Some(key) {
93            return None;
94        }
95        Some(cursor)
96    }
97
98    /// Get a [`CursorWithDelta`] pointing at the gap after the given given key.
99    /// If the given key is not found in either the snapshot or the delta, `None` is returned.
100    pub fn after(&self, key: &K) -> Option<CursorWithDelta<'a, K, V>> {
101        let cursor = self.upper_bound(Bound::Included(key));
102        if cursor.peek_prev().map(|(k, _)| k) != Some(key) {
103            return None;
104        }
105        Some(cursor)
106    }
107
108    /// Get a [`CursorWithDelta`] pointing at the gap before the smallest key greater than the given bound.
109    pub fn lower_bound(&self, bound: Bound<&K>) -> CursorWithDelta<'a, K, V> {
110        let ss_cursor = self.snapshot.lower_bound(bound);
111        let dt_cursor = self.delta.lower_bound(bound);
112        CursorWithDelta {
113            ss_cursor,
114            dt_cursor,
115        }
116    }
117
118    /// Get a [`CursorWithDelta`] pointing at the gap after the greatest key smaller than the given bound.
119    pub fn upper_bound(&self, bound: Bound<&K>) -> CursorWithDelta<'a, K, V> {
120        let ss_cursor = self.snapshot.upper_bound(bound);
121        let dt_cursor = self.delta.upper_bound(bound);
122        CursorWithDelta {
123            ss_cursor,
124            dt_cursor,
125        }
126    }
127}
128
129/// Cursor that can iterate back and forth over the updated version of the snapshot.
130///
131/// A cursor always points at the gap of items in the map. For example:
132///
133/// ```text
134/// | Foo | Bar |
135/// ^     ^     ^
136/// 1     2     3
137/// ```
138///
139/// The cursor can be at position 1, 2, or 3.
140/// If it's at position 1, `peek_prev` will return `None`, and `peek_next` will return `Foo`.
141/// If it's at position 3, `peek_prev` will return `Bar`, and `peek_next` will return `None`.
142#[derive(Debug, Clone)]
143pub struct CursorWithDelta<'a, K: Ord, V> {
144    ss_cursor: btree_map::Cursor<'a, K, V>,
145    dt_cursor: btree_map::Cursor<'a, K, Change<V>>,
146}
147
148impl<'a, K: Ord, V> CursorWithDelta<'a, K, V> {
149    pub fn peek_prev(&self) -> Option<(&'a K, &'a V)> {
150        self.peek::<false /* PREV */>()
151    }
152
153    pub fn peek_next(&self) -> Option<(&'a K, &'a V)> {
154        self.peek::<true /* NEXT */>()
155    }
156
157    pub fn prev(&mut self) -> Option<(&'a K, &'a V)> {
158        self.r#move::<false /* PREV */>()
159    }
160
161    #[allow(clippy::should_implement_trait)]
162    pub fn next(&mut self) -> Option<(&'a K, &'a V)> {
163        self.r#move::<true /* NEXT */>()
164    }
165
166    fn peek<const NEXT: bool>(&self) -> Option<(&'a K, &'a V)> {
167        let mut ss_cursor = self.ss_cursor.clone();
168        let mut dt_cursor = self.dt_cursor.clone();
169        Self::move_impl::<NEXT>(&mut ss_cursor, &mut dt_cursor)
170    }
171
172    fn r#move<const NEXT: bool>(&mut self) -> Option<(&'a K, &'a V)> {
173        let mut ss_cursor = self.ss_cursor.clone();
174        let mut dt_cursor = self.dt_cursor.clone();
175        let res = Self::move_impl::<NEXT>(&mut ss_cursor, &mut dt_cursor);
176        self.ss_cursor = ss_cursor;
177        self.dt_cursor = dt_cursor;
178        res
179    }
180
181    fn move_impl<const NEXT: bool>(
182        ss_cursor: &mut btree_map::Cursor<'a, K, V>,
183        dt_cursor: &mut btree_map::Cursor<'a, K, Change<V>>,
184    ) -> Option<(&'a K, &'a V)> {
185        loop {
186            let ss_peek = if NEXT {
187                ss_cursor.peek_next()
188            } else {
189                ss_cursor.peek_prev()
190            };
191            let dt_peek = if NEXT {
192                dt_cursor.peek_next()
193            } else {
194                dt_cursor.peek_prev()
195            };
196
197            let in_delta = match (ss_peek, dt_peek) {
198                (None, None) => return None,
199                (None, Some(_)) => true,
200                (Some(_), None) => false,
201                (Some((ss_key, _)), Some((dt_key, dt_change))) => match ss_key.cmp(dt_key) {
202                    Ordering::Less => !NEXT,   // if NEXT { in snapshot } else { in delta }
203                    Ordering::Greater => NEXT, // if NEXT { in delta } else { in snapshot }
204                    Ordering::Equal => {
205                        if NEXT {
206                            ss_cursor.next().unwrap();
207                        } else {
208                            ss_cursor.prev().unwrap();
209                        }
210                        match dt_change {
211                            Change::Insert(_) => true, // in delta
212                            Change::Delete => {
213                                if NEXT {
214                                    dt_cursor.next().unwrap();
215                                } else {
216                                    dt_cursor.prev().unwrap();
217                                }
218                                continue;
219                            }
220                        }
221                    }
222                },
223            };
224
225            if in_delta {
226                let (key, change) = if NEXT {
227                    dt_cursor.next().unwrap()
228                } else {
229                    dt_cursor.prev().unwrap()
230                };
231                return Some((key, change.as_insert().unwrap()));
232            } else {
233                return if NEXT {
234                    ss_cursor.next()
235                } else {
236                    ss_cursor.prev()
237                };
238            }
239        }
240    }
241}
242
243#[cfg(test)]
244mod tests {
245    use super::*;
246
247    #[test]
248    fn test_empty() {
249        let map: BTreeMap<i32, &str> = BTreeMap::new();
250        let delta = BTreeMap::new();
251        let delta_map = DeltaBTreeMap::new(&map, &delta);
252
253        assert_eq!(delta_map.first_key(), None);
254        assert_eq!(delta_map.last_key(), None);
255        assert!(delta_map.before(&1).is_none());
256        assert!(delta_map.after(&1).is_none());
257        assert_eq!(delta_map.lower_bound(Bound::Included(&1)).peek_next(), None);
258        assert_eq!(delta_map.upper_bound(Bound::Included(&1)).peek_prev(), None);
259
260        let mut map = BTreeMap::new();
261        map.insert(1, "1");
262        map.insert(2, "2");
263        let mut delta = BTreeMap::new();
264        delta.insert(1, Change::Delete);
265        delta.insert(2, Change::Delete);
266        let delta_map = DeltaBTreeMap::new(&map, &delta);
267        assert_eq!(delta_map.first_key(), None);
268        assert_eq!(delta_map.last_key(), None);
269        assert!(delta_map.before(&1).is_none());
270        assert!(delta_map.before(&2).is_none());
271        assert!(delta_map.before(&3).is_none());
272    }
273
274    #[test]
275    fn test_empty_delta() {
276        let mut map = BTreeMap::new();
277        map.insert(1, "1");
278        map.insert(2, "2");
279        map.insert(5, "5");
280        let delta = BTreeMap::new();
281        let delta_map = DeltaBTreeMap::new(&map, &delta);
282
283        assert_eq!(delta_map.first_key(), Some(&1));
284        assert_eq!(delta_map.last_key(), Some(&5));
285        assert!(delta_map.before(&100).is_none());
286        assert_eq!(
287            delta_map.lower_bound(Bound::Included(&1)).peek_next(),
288            Some((&1, &"1"))
289        );
290        assert_eq!(
291            delta_map.lower_bound(Bound::Excluded(&3)).peek_next(),
292            Some((&5, &"5"))
293        );
294        assert_eq!(
295            delta_map.upper_bound(Bound::Included(&1)).peek_prev(),
296            Some((&1, &"1"))
297        );
298        assert_eq!(
299            delta_map.upper_bound(Bound::Excluded(&3)).peek_prev(),
300            Some((&2, &"2"))
301        );
302
303        let mut cursor = delta_map.before(&2).unwrap();
304        assert_eq!(cursor.peek_next(), Some((&2, &"2")));
305        assert_eq!(cursor.peek_prev(), Some((&1, &"1")));
306        let (key, value) = cursor.next().unwrap();
307        assert_eq!(key, &2);
308        assert_eq!(value, &"2");
309        assert_eq!(cursor.peek_next(), Some((&5, &"5")));
310        assert_eq!(cursor.peek_prev(), Some((&2, &"2")));
311        cursor.next();
312        assert_eq!(cursor.peek_next(), None);
313        cursor.next();
314        assert_eq!(cursor.peek_next(), None);
315        assert_eq!(cursor.peek_prev(), Some((&5, &"5")));
316        cursor.prev();
317        assert_eq!(cursor.peek_next(), Some((&5, &"5")));
318        cursor.prev();
319        cursor.prev();
320        assert_eq!(cursor.peek_next(), Some((&1, &"1")));
321        assert_eq!(cursor.peek_prev(), None);
322        cursor.prev();
323        assert_eq!(cursor.peek_next(), Some((&1, &"1")));
324        assert_eq!(cursor.peek_prev(), None);
325    }
326
327    #[test]
328    fn test_empty_snapshot() {
329        let map: BTreeMap<i32, &str> = BTreeMap::new();
330        let mut delta = BTreeMap::new();
331        delta.insert(1, Change::Insert("1"));
332        delta.insert(2, Change::Insert("2"));
333        let delta_map = DeltaBTreeMap::new(&map, &delta);
334
335        assert_eq!(delta_map.first_key(), Some(&1));
336        assert_eq!(delta_map.last_key(), Some(&2));
337        assert!(delta_map.before(&100).is_none());
338        assert_eq!(
339            delta_map.lower_bound(Bound::Included(&1)).peek_next(),
340            Some((&1, &"1"))
341        );
342        assert_eq!(
343            delta_map.lower_bound(Bound::Excluded(&1)).peek_next(),
344            Some((&2, &"2"))
345        );
346        assert_eq!(
347            delta_map.upper_bound(Bound::Included(&1)).peek_prev(),
348            Some((&1, &"1"))
349        );
350        assert_eq!(
351            delta_map.upper_bound(Bound::Excluded(&10)).peek_prev(),
352            Some((&2, &"2"))
353        );
354
355        let mut cursor = delta_map.before(&2).unwrap();
356        assert_eq!(cursor.peek_next(), Some((&2, &"2")));
357        assert_eq!(cursor.peek_prev(), Some((&1, &"1")));
358        cursor.next();
359        assert_eq!(cursor.peek_next(), None);
360        assert_eq!(cursor.peek_prev(), Some((&2, &"2")));
361        cursor.next();
362        assert_eq!(cursor.peek_next(), None);
363        assert_eq!(cursor.peek_prev(), Some((&2, &"2")));
364        cursor.prev();
365        assert_eq!(cursor.peek_next(), Some((&2, &"2")));
366        assert_eq!(cursor.peek_prev(), Some((&1, &"1")));
367        cursor.prev();
368        assert_eq!(cursor.peek_next(), Some((&1, &"1")));
369        assert_eq!(cursor.peek_prev(), None);
370        cursor.prev();
371        assert_eq!(cursor.peek_next(), Some((&1, &"1")));
372        assert_eq!(cursor.peek_prev(), None);
373    }
374
375    #[test]
376    fn test_delete_first() {
377        let mut map = BTreeMap::new();
378        map.insert(1, "1");
379        map.insert(3, "3");
380        let mut delta = BTreeMap::new();
381        delta.insert(1, Change::Delete);
382        let delta_map = DeltaBTreeMap::new(&map, &delta);
383
384        assert_eq!(delta_map.first_key(), Some(&3));
385        assert_eq!(delta_map.last_key(), Some(&3));
386        assert!(delta_map.before(&1).is_none());
387        assert!(delta_map.before(&2).is_none());
388        assert_eq!(
389            delta_map.lower_bound(Bound::Included(&1)).peek_next(),
390            Some((&3, &"3"))
391        );
392        assert_eq!(
393            delta_map.lower_bound(Bound::Excluded(&0)).peek_next(),
394            Some((&3, &"3"))
395        );
396        assert_eq!(delta_map.upper_bound(Bound::Included(&1)).peek_prev(), None);
397        assert_eq!(
398            delta_map.upper_bound(Bound::Excluded(&10)).peek_prev(),
399            Some((&3, &"3"))
400        );
401
402        let mut cursor = delta_map.before(&3).unwrap();
403        assert_eq!(cursor.peek_next(), Some((&3, &"3")));
404        assert_eq!(cursor.peek_prev(), None);
405        cursor.next();
406        assert_eq!(cursor.peek_next(), None);
407        assert_eq!(cursor.peek_prev(), Some((&3, &"3")));
408        cursor.prev();
409        assert_eq!(cursor.peek_next(), Some((&3, &"3")));
410        assert_eq!(cursor.peek_prev(), None);
411        cursor.prev();
412        assert_eq!(cursor.peek_next(), Some((&3, &"3")));
413        assert_eq!(cursor.peek_prev(), None);
414        cursor.next();
415        assert_eq!(cursor.peek_next(), None);
416        assert_eq!(cursor.peek_prev(), Some((&3, &"3")));
417    }
418
419    #[test]
420    fn test_delete_last() {
421        let mut map = BTreeMap::new();
422        map.insert(1, "1");
423        map.insert(3, "3");
424        let mut delta = BTreeMap::new();
425        delta.insert(3, Change::Delete);
426        let delta_map = DeltaBTreeMap::new(&map, &delta);
427
428        assert_eq!(delta_map.first_key(), Some(&1));
429        assert_eq!(delta_map.last_key(), Some(&1));
430        assert!(delta_map.before(&2).is_none());
431        assert!(delta_map.before(&3).is_none());
432        assert_eq!(
433            delta_map.lower_bound(Bound::Included(&1)).peek_next(),
434            Some((&1, &"1"))
435        );
436        assert_eq!(delta_map.lower_bound(Bound::Excluded(&1)).peek_next(), None);
437        assert_eq!(
438            delta_map.upper_bound(Bound::Included(&3)).peek_prev(),
439            Some((&1, &"1"))
440        );
441        assert_eq!(
442            delta_map.upper_bound(Bound::Excluded(&3)).peek_prev(),
443            Some((&1, &"1"))
444        );
445
446        let mut cursor = delta_map.before(&1).unwrap();
447        assert_eq!(cursor.peek_next(), Some((&1, &"1")));
448        cursor.next();
449        assert_eq!(cursor.peek_next(), None);
450        assert_eq!(cursor.peek_prev(), Some((&1, &"1")));
451        cursor.prev();
452        assert_eq!(cursor.peek_next(), Some((&1, &"1")));
453        assert_eq!(cursor.peek_prev(), None);
454    }
455
456    #[test]
457    fn test_delete_all() {
458        let mut map = BTreeMap::new();
459        map.insert(1, "1");
460        map.insert(3, "3");
461        let mut delta = BTreeMap::new();
462        delta.insert(1, Change::Delete);
463        delta.insert(3, Change::Delete);
464        let delta_map = DeltaBTreeMap::new(&map, &delta);
465
466        assert_eq!(delta_map.first_key(), None);
467        assert_eq!(delta_map.last_key(), None);
468        assert!(delta_map.before(&1).is_none());
469        assert!(delta_map.before(&2).is_none());
470        assert!(delta_map.before(&3).is_none());
471        assert_eq!(delta_map.lower_bound(Bound::Included(&1)).peek_next(), None);
472        assert_eq!(delta_map.upper_bound(Bound::Excluded(&3)).peek_prev(), None);
473    }
474
475    #[test]
476    fn test_insert_middle() {
477        let mut map = BTreeMap::new();
478        map.insert(1, "1");
479        map.insert(3, "3");
480        let mut delta = BTreeMap::new();
481        delta.insert(2, Change::Insert("2"));
482        let delta_map = DeltaBTreeMap::new(&map, &delta);
483
484        assert_eq!(delta_map.first_key(), Some(&1));
485        assert_eq!(delta_map.last_key(), Some(&3));
486        assert!(delta_map.before(&10).is_none());
487        assert_eq!(
488            delta_map.lower_bound(Bound::Included(&1)).peek_next(),
489            Some((&1, &"1"))
490        );
491        assert_eq!(
492            delta_map.lower_bound(Bound::Excluded(&1)).peek_next(),
493            Some((&2, &"2"))
494        );
495        assert_eq!(
496            delta_map.upper_bound(Bound::Included(&2)).peek_prev(),
497            Some((&2, &"2"))
498        );
499        assert_eq!(
500            delta_map.upper_bound(Bound::Excluded(&2)).peek_prev(),
501            Some((&1, &"1"))
502        );
503
504        let mut cursor = delta_map.before(&2).unwrap();
505        assert_eq!(cursor.peek_next(), Some((&2, &"2")));
506        assert_eq!(cursor.peek_prev(), Some((&1, &"1")));
507        cursor.next();
508        assert_eq!(cursor.peek_next(), Some((&3, &"3")));
509        assert_eq!(cursor.peek_prev(), Some((&2, &"2")));
510    }
511
512    #[test]
513    fn test_update_first() {
514        let mut map = BTreeMap::new();
515        map.insert(1, "1");
516        map.insert(3, "3");
517        let mut delta = BTreeMap::new();
518        delta.insert(1, Change::Insert("1 new"));
519        let delta_map = DeltaBTreeMap::new(&map, &delta);
520
521        assert_eq!(delta_map.first_key(), Some(&1));
522        assert_eq!(delta_map.last_key(), Some(&3));
523
524        let mut cursor = delta_map.before(&1).unwrap();
525        assert_eq!(cursor.peek_next(), Some((&1, &"1 new")));
526        assert_eq!(cursor.peek_prev(), None);
527        cursor.next();
528        assert_eq!(cursor.peek_next(), Some((&3, &"3")));
529        assert_eq!(cursor.peek_prev(), Some((&1, &"1 new")));
530        cursor.prev();
531        assert_eq!(cursor.peek_next(), Some((&1, &"1 new")));
532        assert_eq!(cursor.peek_prev(), None);
533    }
534
535    #[test]
536    fn test_update_last() {
537        let mut map = BTreeMap::new();
538        map.insert(1, "1");
539        map.insert(3, "3");
540        let mut delta = BTreeMap::new();
541        delta.insert(3, Change::Insert("3 new"));
542        let delta_map = DeltaBTreeMap::new(&map, &delta);
543
544        assert_eq!(delta_map.first_key(), Some(&1));
545        assert_eq!(delta_map.last_key(), Some(&3));
546
547        let mut cursor = delta_map.before(&3).unwrap();
548        assert_eq!(cursor.peek_next(), Some((&3, &"3 new")));
549        assert_eq!(cursor.peek_prev(), Some((&1, &"1")));
550        cursor.next();
551        assert_eq!(cursor.peek_next(), None);
552        assert_eq!(cursor.peek_prev(), Some((&3, &"3 new")));
553        cursor.prev();
554        assert_eq!(cursor.peek_next(), Some((&3, &"3 new")));
555        assert_eq!(cursor.peek_prev(), Some((&1, &"1")));
556    }
557
558    #[test]
559    fn test_mixed() {
560        let mut map = BTreeMap::new();
561        map.insert(1, "1");
562        map.insert(2, "2");
563        map.insert(3, "3");
564        let mut delta = BTreeMap::new();
565        delta.insert(0, Change::Insert("0"));
566        delta.insert(1, Change::Insert("1 new"));
567        delta.insert(3, Change::Delete);
568        delta.insert(4, Change::Insert("4"));
569        let delta_map = DeltaBTreeMap::new(&map, &delta);
570
571        assert_eq!(delta_map.first_key(), Some(&0));
572        assert_eq!(delta_map.last_key(), Some(&4));
573        assert!(delta_map.before(&-1).is_none());
574        assert!(delta_map.before(&3).is_none());
575        assert!(delta_map.before(&10).is_none());
576        assert_eq!(
577            delta_map.lower_bound(Bound::Included(&0)).peek_next(),
578            Some((&0, &"0"))
579        );
580        assert_eq!(
581            delta_map.lower_bound(Bound::Excluded(&0)).peek_next(),
582            Some((&1, &"1 new"))
583        );
584        assert_eq!(
585            delta_map.lower_bound(Bound::Included(&3)).peek_next(),
586            Some((&4, &"4"))
587        );
588        assert_eq!(
589            delta_map.upper_bound(Bound::Included(&5)).peek_prev(),
590            Some((&4, &"4"))
591        );
592        assert_eq!(
593            delta_map.upper_bound(Bound::Excluded(&4)).peek_prev(),
594            Some((&2, &"2"))
595        );
596        assert_eq!(
597            delta_map.upper_bound(Bound::Excluded(&2)).peek_prev(),
598            Some((&1, &"1 new"))
599        );
600
601        let mut cursor = delta_map.before(&0).unwrap();
602        assert_eq!(cursor.peek_next(), Some((&0, &"0")));
603        cursor.next();
604        assert_eq!(cursor.peek_next(), Some((&1, &"1 new")));
605        cursor.next();
606        assert_eq!(cursor.peek_next(), Some((&2, &"2")));
607        cursor.next();
608        assert_eq!(cursor.peek_next(), Some((&4, &"4")));
609        cursor.next();
610        assert_eq!(cursor.peek_next(), None);
611        cursor.next();
612        assert_eq!(cursor.peek_next(), None);
613        cursor.prev();
614        assert_eq!(cursor.peek_next(), Some((&4, &"4")));
615        cursor.prev();
616        assert_eq!(cursor.peek_next(), Some((&2, &"2")));
617        cursor.prev();
618        assert_eq!(cursor.peek_next(), Some((&1, &"1 new")));
619        cursor.prev();
620        assert_eq!(cursor.peek_next(), Some((&0, &"0")));
621        assert_eq!(cursor.peek_prev(), None);
622        cursor.prev();
623        assert_eq!(cursor.peek_next(), Some((&0, &"0")));
624        assert_eq!(cursor.peek_prev(), None);
625    }
626
627    #[test]
628    fn test_mixed_complex() {
629        let mut map = BTreeMap::new();
630        map.insert(1, "1");
631        map.insert(3, "3");
632        map.insert(5, "5");
633        map.insert(7, "7");
634        map.insert(9, "9");
635        let mut delta = BTreeMap::new();
636        delta.insert(0, Change::Insert("0"));
637        delta.insert(1, Change::Insert("1 new"));
638        delta.insert(5, Change::Delete);
639        delta.insert(7, Change::Delete);
640        delta.insert(9, Change::Delete);
641        let delta_map = DeltaBTreeMap::new(&map, &delta);
642
643        assert_eq!(delta_map.first_key(), Some(&0));
644        assert_eq!(delta_map.last_key(), Some(&3));
645
646        let mut cursor = delta_map.before(&0).unwrap();
647        let mut res = vec![];
648        while let Some((k, v)) = cursor.next() {
649            res.push((*k, *v));
650        }
651        assert_eq!(res, vec![(0, "0"), (1, "1 new"), (3, "3")]);
652
653        let mut cursor = delta_map.after(&3).unwrap();
654        let mut res = vec![];
655        while let Some((k, v)) = cursor.prev() {
656            res.push((*k, *v));
657        }
658        assert_eq!(res, vec![(3, "3"), (1, "1 new"), (0, "0")]);
659    }
660}
delta_btree_map/lib.rs

delta_btree_map/
lib.rs
