diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/rope.rs | 93 |
1 files changed, 49 insertions, 44 deletions
diff --git a/src/rope.rs b/src/rope.rs index ec25f61..f22d103 100644 --- a/src/rope.rs +++ b/src/rope.rs @@ -3,6 +3,7 @@ use std::io::{ErrorKind, Read, Write}; use std::rc::Rc; const MAX_NODE_SIZE: usize = 1024; +const MAX_CHILDREN: usize = 5; fn read(r: &mut dyn Read, buf: &mut [u8]) -> Result<usize, std::io::Error> { loop { @@ -100,21 +101,16 @@ impl Rope { })) } - fn two(x: Rope, y: Rope) -> Rope { - let len = x.len() + y.len(); - let lines = x.lines() + y.lines(); - Rope(Node::Branch(Branch { - children: Rc::new([x, y]), - len, - lines, - })) - } - - fn three(x: Rope, y: Rope, z: Rope) -> Rope { - let len = x.len() + y.len() + z.len(); - let lines = x.lines() + y.lines() + z.lines(); + fn branch(children: impl Iterator<Item = Rope>) -> Rope { + let children = Rc::from_iter(children); + let mut len = 0; + let mut lines = 0; + for c in children.iter() { + len += c.len(); + lines += c.lines(); + } Rope(Node::Branch(Branch { - children: Rc::new([x, y, z]), + children, len, lines, })) @@ -153,23 +149,31 @@ impl Rope { other_height, ) { Insert::Node(new_child) => { - if b.children.len() == 2 { - return Insert::Node(Rope::two(b.children[0].clone(), new_child)); - } - return Insert::Node(Rope::three( - b.children[0].clone(), - b.children[1].clone(), - new_child, + return Insert::Node(Rope::branch( + b.children[..b.children.len() - 1] + .iter() + .cloned() + .chain(std::iter::once(new_child)), )); } Insert::Split(child1, child2) => { - if b.children.len() == 2 { - return Insert::Node(Rope::three(b.children[0].clone(), child1, child2)); + if b.children.len() == MAX_CHILDREN { + return Insert::Split( + Rope::branch(b.children[..(MAX_CHILDREN + 1) / 2].iter().cloned()), + Rope::branch( + b.children[(MAX_CHILDREN + 1) / 2..MAX_CHILDREN - 1] + .iter() + .cloned() + .chain([child1, child2].into_iter()), + ), + ); } - return Insert::Split( - Rope::two(b.children[0].clone(), b.children[1].clone()), - Rope::two(child1, child2), - ); + return Insert::Node(Rope::branch( + b.children[..b.children.len() - 1] + .iter() + .cloned() + .chain([child1, child2].into_iter()), + )); } } } @@ -177,24 +181,25 @@ impl Rope { panic!("other_height is at least 1, so it's a branch"); }; match self.concat_height(self_height, &b.children[0], other_height - 1) { - Insert::Node(new_child) => { - if b.children.len() == 2 { - return Insert::Node(Rope::two(new_child, b.children[1].clone())); - } - Insert::Node(Rope::three( - new_child, - b.children[1].clone(), - b.children[2].clone(), - )) - } + Insert::Node(new_child) => Insert::Node(Rope::branch( + std::iter::once(new_child).chain(b.children[1..].iter().cloned()), + )), Insert::Split(child1, child2) => { - if b.children.len() == 2 { - return Insert::Node(Rope::three(child1, child2, b.children[1].clone())); + if b.children.len() == MAX_CHILDREN { + return Insert::Split( + Rope::branch( + [child1, child2] + .into_iter() + .chain(b.children[1..MAX_CHILDREN / 2].iter().cloned()), + ), + Rope::branch(b.children[MAX_CHILDREN / 2..].iter().cloned()), + ); } - Insert::Split( - Rope::two(child1, child2), - Rope::two(b.children[1].clone(), b.children[2].clone()), - ) + Insert::Node(Rope::branch( + [child1, child2] + .into_iter() + .chain(b.children[1..].iter().cloned()), + )) } } } @@ -215,7 +220,7 @@ impl Rope { } match self.concat_height(self.height(), other, other.height()) { Insert::Node(r) => r, - Insert::Split(l, r) => Rope::two(l, r), + Insert::Split(l, r) => Rope::branch([l, r].into_iter()), } } |