flo_rope 0.2.0

An attributed and streaming implementation of the rope data structure
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

use super::attributed_rope::*;

use crate::api::*;

use std::iter;
use std::ops::{AddAssign};

// These extensions will work for any implementation of Rope, but Rust doesn't let us a provide a universal implementation

impl<Cell, Attribute> AddAssign<Cell> for AttributedRope<Cell, Attribute>
where
Cell:       Clone, 
Attribute:  PartialEq+Clone+Default {
    fn add_assign(&mut self, other: Cell) {
        let len = self.len();
        self.replace(len..len, iter::once(other));
    }
}

impl<Cell, Attribute> Extend<Cell> for AttributedRope<Cell, Attribute> 
where
Cell:       Clone, 
Attribute:  PartialEq+Clone+Default {
    fn extend<I: IntoIterator<Item=Cell>>(&mut self, iter: I) {
        let len = self.len();
        self.replace(len..len, iter);
    }
}

impl<'a, Cell, Attribute> Extend<&'a Cell> for AttributedRope<Cell, Attribute> 
where
Cell:       'a+Clone, 
Attribute:  PartialEq+Clone+Default {
    fn extend<I: IntoIterator<Item=&'a Cell>>(&mut self, iter: I) {
        let len = self.len();
        self.replace(len..len, iter.into_iter().cloned());
    }
}

impl<Cell, Attribute> PartialEq for AttributedRope<Cell, Attribute>
where
Cell:       Clone+PartialEq, 
Attribute:  PartialEq+Clone+Default {
    fn eq(&self, other: &AttributedRope<Cell, Attribute>) -> bool {
        // Compare lengths
        if self.len() != other.len() {
            return false;
        }

        // Compare cells
        let mut cells_a = self.read_cells(0..self.len());
        let mut cells_b = other.read_cells(0..other.len());

        while let (Some(a), Some(b)) = (cells_a.next(), cells_b.next()) {
            if a != b {
                return false;
            }
        }

        // Compare attributes (coverage of each attribute may vary between the two styles)
        let len                         = self.len();
        let (mut attr_a, mut range_a)   = self.read_attributes(0);
        let (mut attr_b, mut range_b)   = other.read_attributes(0);

        loop {
            // Ranges should never be 0-length
            debug_assert!(range_a.len() != 0 && range_b.len() != 0);

            // Move the 'a' range on if range_b starts after it, similarly for range_b
            if range_b.start >= range_a.end || range_a.start == range_a.end {
                let (new_attr, new_range) = self.read_attributes(range_b.start);
                attr_a  = new_attr;
                range_a = new_range;
            }

            if range_a.start >= range_b.end || range_b.start == range_b.end {
                let (new_attr, new_range) = other.read_attributes(range_a.start);
                attr_b  = new_attr;
                range_b = new_range;
            }

            // range_a and range_b should now overlap
            if attr_a != attr_b {
                return false;
            }

            // Move range_a or range_b onwards
            if range_a.end >= len && range_b.end >= len {
                // All attributes compared
                break;
            }

            if range_a.end <= range_b.end {
                let (new_attr, new_range) = self.read_attributes(range_a.end);
                attr_a  = new_attr;
                range_a = new_range;
            } else {
                let (new_attr, new_range) = other.read_attributes(range_b.end);
                attr_b  = new_attr;
                range_b = new_range;
            }
        }

        // All equality tests passed
        return true;
    }
}