diff options
| -rw-r--r-- | src/rope.rs | 93 |
1 files changed, 44 insertions, 49 deletions
diff --git a/src/rope.rs b/src/rope.rs index e7e62c8..8bbbace 100644 --- a/src/rope.rs +++ b/src/rope.rs @@ -3,7 +3,6 @@ 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 { @@ -101,16 +100,21 @@ impl Rope { })) } - fn branch(children: impl Iterator<Item = Rope>) -> Rope { - let children: Rc<[Rope]> = children.collect(); - let mut len = 0; - let mut lines = 0; - for c in children.iter() { - len += c.len(); - lines += c.lines(); - } + fn two(x: Rope, y: Rope) -> Rope { + let len = x.len() + y.len(); + let lines = x.lines() + y.lines(); Rope(Node::Branch(Branch { - children, + 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(); + Rope(Node::Branch(Branch { + children: Rc::new([x, y, z]), len, lines, })) @@ -149,31 +153,23 @@ impl Rope { other_height, ) { Insert::Node(new_child) => { - return Insert::Node(Rope::branch( - b.children[..b.children.len() - 1] - .iter() - .cloned() - .chain(std::iter::once(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, )); } Insert::Split(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]), - ), - ); + if b.children.len() == 2 { + return Insert::Node(Rope::three(b.children[0].clone(), child1, child2)); } - return Insert::Node(Rope::branch( - b.children[..b.children.len() - 1] - .iter() - .cloned() - .chain([child1, child2]), - )); + return Insert::Split( + Rope::two(b.children[0].clone(), b.children[1].clone()), + Rope::two(child1, child2), + ); } } } @@ -181,26 +177,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) => Insert::Node(Rope::branch( - std::iter::once(new_child).chain(b.children[1..].iter().cloned()), - )), - Insert::Split(child1, child2) => { - 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::Node(new_child) => { + if b.children.len() == 2 { + return Insert::Node(Rope::two(new_child, b.children[1].clone())); } - Insert::Node(Rope::branch( - [child1, child2] - .into_iter() - .chain(b.children[1..].iter().cloned()), + Insert::Node(Rope::three( + new_child, + b.children[1].clone(), + b.children[2].clone(), )) } + Insert::Split(child1, child2) => { + if b.children.len() == 2 { + return Insert::Node(Rope::three(child1, child2, b.children[1].clone())); + } + Insert::Split( + Rope::two(child1, child2), + Rope::two(b.children[1].clone(), b.children[2].clone()), + ) + } } } @@ -220,7 +215,7 @@ impl Rope { } match self.concat_height(self.height(), other, other.height()) { Insert::Node(r) => r, - Insert::Split(l, r) => Rope::branch([l, r].into_iter()), + Insert::Split(l, r) => Rope::two(l, r), } } |