From bb5480126fb4417339000f183b0d6787c7cb2b82 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Sat, 6 Jan 2024 22:05:37 -0800 Subject: Use a b-tree for the rope. Now it's balanced :D --- src/rope.rs | 338 +++++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 242 insertions(+), 96 deletions(-) (limited to 'src/rope.rs') diff --git a/src/rope.rs b/src/rope.rs index 34c459b..6c1cad6 100644 --- a/src/rope.rs +++ b/src/rope.rs @@ -1,10 +1,10 @@ +use std::error::Error; use std::fs::File; use std::io::{ErrorKind, Read, Write}; use std::path::Path; -use std::error::Error; use std::rc::Rc; -const MAX_NODE_SIZE: usize = 254; +const MAX_NODE_SIZE: usize = 255; #[derive(Debug, Clone)] struct Leaf { @@ -21,32 +21,103 @@ impl Leaf { #[derive(Debug, Clone)] struct Branch { - left: Rc, - right: Rc, len: usize, // Number of newline characters under this branch. lines: usize, + height: usize, + child1: Rope, + child2: Rope, + child3: Option, +} + +impl Branch { + fn children(&self) -> Children { + return Children { b: self, i: 0 }; + } +} + +#[derive(Debug, Clone, Copy)] +struct Children<'a> { + b: &'a Branch, + i: u8, +} + +impl<'a> Iterator for Children<'a> { + type Item = Rope; + + fn next(&mut self) -> Option { + let c = match self.i { + 0 => self.b.child1.clone(), + 1 => self.b.child2.clone(), + 2 => match &self.b.child3 { + Some(child3) => child3.clone(), + None => { + return None; + } + }, + _ => { + return None; + } + }; + self.i += 1; + return Some(c); + } } #[derive(Debug, Clone)] enum Node { Leaf(Leaf), - Branch(Branch), + Branch(Rc), } #[derive(Debug, Clone)] pub struct Rope(Node); -impl Rope { - fn leaf(buf: Vec) -> Rope { - let len = buf.len(); - return Rope(Node::Leaf(Leaf{ - buf: Rc::from(buf), - start: 0, - end: u8::try_from(len).expect("buffer too long"), - })); +fn leaf(buf: Vec) -> Rope { + let len = buf.len(); + return Rope(Node::Leaf(Leaf { + buf: Rc::from(buf), + start: 0, + end: u8::try_from(len).expect("buffer too long"), + })); +} + +// The two and three constructors maintain the size of the tree. +fn two(l: &Rope, r: &Rope) -> Rope { + if l.height() != r.height() { + panic!("Joining trees of different height"); } + return Rope(Node::Branch(Rc::new(Branch { + len: l.len() + r.len(), + lines: l.lines() + r.lines(), + height: l.height() + 1, + child1: l.clone(), + child2: r.clone(), + child3: None, + }))); +} + +fn three(a: &Rope, b: &Rope, c: &Rope) -> Rope { + if a.height() != b.height() || b.height() != c.height() { + panic!("Joining trees of different height"); + } + return Rope(Node::Branch(Rc::new(Branch { + len: a.len() + b.len() + c.len(), + lines: a.lines() + b.lines() + c.lines(), + height: a.height() + 1, + child1: a.clone(), + child2: b.clone(), + child3: Some(c.clone()), + }))); +} +#[derive(Debug)] +enum Insert { + Node(Rope), + Split(Rope, Rope), +} + +impl Rope { pub fn lines(&self) -> usize { match self { Rope(Node::Leaf(l)) => { @@ -75,6 +146,13 @@ impl Rope { } } + pub fn height(&self) -> usize { + match self { + Rope(Node::Leaf(_)) => 0, + Rope(Node::Branch(b)) => b.height, + } + } + pub fn print(&self, out: &mut dyn Write) -> Result<(), std::io::Error> { if self.len() == 0 { return Ok(()); @@ -86,8 +164,9 @@ impl Rope { return Ok(()); } Rope(Node::Branch(b)) => { - b.left.print(out)?; - b.right.print(out)?; + for child in b.children() { + child.print(out)?; + } return Ok(()); } } @@ -95,7 +174,7 @@ impl Rope { pub fn line_idx(&self, n: usize) -> usize { if n > self.lines() { - panic!("Index {} out of range 0..{}", n, self.lines()+1); + panic!("Index {} out of range 0..{}", n, self.lines() + 1); } if n == 0 { return 0; @@ -115,111 +194,191 @@ impl Rope { panic!("unreachable"); } Rope(Node::Branch(b)) => { - let left_lines = b.left.lines(); - if n <= left_lines { - return b.left.line_idx(n); + let mut offset = 0; + let mut n = n; + for child in b.children() { + let child_lines = child.lines(); + if n <= child_lines { + return offset + child.line_idx(n); + } + offset += child.len(); + n -= child_lines; } - return b.left.len() + b.right.line_idx(n - left_lines); + panic!("unreachable"); } } } - pub fn concat(&self, other: &Rope) -> Rope { + fn try_concat(&self, other: &Rope) -> Insert { if self.len() == 0 { - return other.clone(); + return Insert::Node(other.clone()); } if other.len() == 0 { - return self.clone(); + return Insert::Node(self.clone()); } - let len = self.len() + other.len(); - let lines = self.lines() + other.lines(); - return Rope(Node::Branch(Branch { - left: Rc::new(self.clone()), - right: Rc::new(other.clone()), - len: len, - lines: lines, - })); - } - - pub fn insert(&self, pos: usize, c: u8) -> Rope { - return self.slice(0, pos).concat(&Rope::leaf(vec![c])).concat(&self.slice(pos, self.len())); - } - - pub fn open(path: &Path) -> Result> { - let mut f = File::open(path).map_err(|err| format!("open file {}: {}", path.display(), err))?; - let mut rope = Rope::leaf(Vec::new()); - loop { - let mut buf = vec![0; MAX_NODE_SIZE]; - let n = match f.read(&mut buf) { - Ok(n) => n, - Err(err) => { - if err.kind() == ErrorKind::Interrupted { - continue; + if let (Rope(Node::Leaf(l)), Rope(Node::Leaf(r))) = (self, other) { + if self.len() <= MAX_NODE_SIZE - other.len() { + let mut buf = Vec::new(); + buf.extend_from_slice(&l.bytes()); + buf.extend_from_slice(&r.bytes()); + return Insert::Node(leaf(buf)); + } + if self.len() < MAX_NODE_SIZE / 2 || other.len() < MAX_NODE_SIZE / 2 { + let mut buf = Vec::new(); + buf.extend_from_slice(&l.bytes()); + buf.extend_from_slice(&r.bytes()); + let mut buf1 = Vec::new(); + buf1.extend_from_slice(&buf[..buf.len() / 2]); + let mut buf2 = Vec::new(); + buf2.extend_from_slice(&buf[buf.len() / 2..]); + return Insert::Split(leaf(buf1), leaf(buf2)); + } + } + if self.height() == other.height() { + return Insert::Split(self.clone(), other.clone()); + } + if self.height() > other.height() { + let Rope(Node::Branch(selfb)) = self else { + panic!("self should have height at least one, which means it's a branch"); + }; + match &selfb.child3 { + Some(child3) => match child3.try_concat(other) { + Insert::Node(new_child) => { + Insert::Node(three(&selfb.child1, &selfb.child2, &new_child)) } - return Err(Box::from(format!("read file {}: {}", path.display(), err))); - } + Insert::Split(child1, child2) => { + Insert::Split(two(&selfb.child1, &selfb.child2), two(&child1, &child2)) + } + }, + None => match selfb.child2.try_concat(other) { + Insert::Node(new_child) => Insert::Node(two(&selfb.child1, &new_child)), + Insert::Split(child1, child2) => { + Insert::Node(three(&selfb.child1, &child1, &child2)) + } + }, + } + } else { + let Rope(Node::Branch(otherb)) = other else { + panic!("other should have height at least one, which means it's a branch"); }; - if n == 0 { - break; + match &otherb.child3 { + Some(child3) => match self.try_concat(&otherb.child1) { + Insert::Node(new_child) => { + Insert::Node(three(&new_child, &otherb.child2, &child3)) + } + Insert::Split(child1, child2) => { + Insert::Split(two(&child1, &child2), two(&otherb.child2, &child3)) + } + }, + None => match self.try_concat(&otherb.child1) { + Insert::Node(new_child) => Insert::Node(two(&new_child, &otherb.child2)), + Insert::Split(child1, child2) => { + Insert::Node(three(&child1, &child2, &otherb.child2)) + } + }, } - buf.truncate(n); - rope = rope.concat(&Rope::leaf(buf)); } - // TODO: rebalance - return Ok(rope); } - pub fn save(&self, path: &Path) -> Result<(), Box> { - let mut f = File::create(path).map_err(|err| format!("save: create file {}: {}", path.display(), err))?; - self.print(&mut f).map_err(|err| format!("save: write file {}: {}", path.display(), err))?; - f.sync_all().map_err(|err| format!("save: write file {}: {}", path.display(), err))?; - return Ok(()); + pub fn concat(&self, other: &Rope) -> Rope { + match self.try_concat(other) { + Insert::Node(r) => r, + Insert::Split(l, r) => two(&l, &r), + } + } + + pub fn insert(&self, pos: usize, c: u8) -> Rope { + let res = self + .slice(0, pos) + .concat(&leaf(vec![c])) + .concat(&self.slice(pos, self.len())); + return res; } pub fn slice(&self, start: usize, end: usize) -> Rope { if start > self.len() { - panic!("Index {} out of range 0..{}", start, self.len()+1); + panic!("Index {} out of range 0..{}", start, self.len() + 1); } if end > self.len() { panic!("Index {} out of range 0..{}", end, self.len()); } if start > end { - panic!("Slice start index {} is greater than end index {}", start, end); + panic!( + "Slice start index {} is greater than end index {}", + start, end + ); } match self { Rope(Node::Leaf(l)) => { - return Rope(Node::Leaf(Leaf{ + return Rope(Node::Leaf(Leaf { buf: l.buf.clone(), start: l.start + u8::try_from(start).expect("buffer too long"), end: l.start + u8::try_from(end).expect("buffer too long"), })); } Rope(Node::Branch(b)) => { - let mut left = Rope::leaf(Vec::new()); - if start < b.left.len() { - left = b.left.slice(start, std::cmp::min(end, b.left.len())); + let mut start = start; + let mut end = end; + let mut slice = leaf(Vec::new()); + for child in b.children() { + if start < child.len() { + slice = slice.concat(&child.slice(start, std::cmp::min(end, child.len()))); + if end < child.len() { + break; + } + start = 0; + } else { + start -= child.len(); + } + end -= child.len(); } - let mut right = Rope::leaf(Vec::new()); - if end > b.left.len() { - let mut right_start = 0; - if start > b.left.len() { - right_start = start - b.left.len(); + return slice; + } + } + } + + pub fn open(path: &Path) -> Result> { + let mut f = + File::open(path).map_err(|err| format!("open file {}: {}", path.display(), err))?; + let mut rope = leaf(Vec::new()); + loop { + let mut buf = vec![0; MAX_NODE_SIZE]; + let n = match f.read(&mut buf) { + Ok(n) => n, + Err(err) => { + if err.kind() == ErrorKind::Interrupted { + continue; } - right = b.right.slice(right_start, end - b.left.len()); + return Err(Box::from(format!("read file {}: {}", path.display(), err))); } - return left.concat(&right); + }; + if n == 0 { + break; } + buf.truncate(n); + rope = rope.concat(&leaf(buf)); } + return Ok(rope); + } + + pub fn save(&self, path: &Path) -> Result<(), Box> { + let mut f = File::create(path) + .map_err(|err| format!("save: create file {}: {}", path.display(), err))?; + self.print(&mut f) + .map_err(|err| format!("save: write file {}: {}", path.display(), err))?; + f.sync_all() + .map_err(|err| format!("save: write file {}: {}", path.display(), err))?; + return Ok(()); } pub fn line(&self, n: usize) -> Rope { if n > self.lines() { - panic!("Index {} out of range 0..{}", n, self.lines()+1); + panic!("Index {} out of range 0..{}", n, self.lines() + 1); } let start = self.line_idx(n); let mut end = self.len(); if n < self.lines() { - end = self.line_idx(n+1)-1; + end = self.line_idx(n + 1) - 1; } return self.slice(start, end); } @@ -230,16 +389,20 @@ impl Rope { return l.bytes()[index] & 0xc0 != 0x80; } Rope(Node::Branch(b)) => { - if index < b.left.len() { - return b.left.is_char_boundary(index); + let mut index = index; + for child in b.children() { + if index < child.len() { + return child.is_char_boundary(index); + } + index -= child.len(); } - return b.right.is_char_boundary(index - b.left.len()); + return false; } } } pub fn floor_char_boundary(&self, index: usize) -> usize { - for i in (0..index+1).rev() { + for i in (0..index + 1).rev() { if self.is_char_boundary(i) { return i; } @@ -255,21 +418,4 @@ impl Rope { } return self.len(); } - - pub fn char(&self, index: usize) -> usize { - if index == 0 { - return 0; - } - let mut count = 1; - for i in 1..self.len() { - if !self.is_char_boundary(i) { - continue; - } - if count == index { - return i; - } - count += 1; - } - return self.len(); - } } -- cgit v1.3.1