aboutsummaryrefslogtreecommitdiffstats
path: root/src/rope.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/rope.rs')
-rw-r--r--src/rope.rs338
1 files changed, 242 insertions, 96 deletions
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<Rope>,
- right: Rc<Rope>,
len: usize,
// Number of newline characters under this branch.
lines: usize,
+ height: usize,
+ child1: Rope,
+ child2: Rope,
+ child3: Option<Rope>,
+}
+
+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<Self::Item> {
+ 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<Branch>),
}
#[derive(Debug, Clone)]
pub struct Rope(Node);
-impl Rope {
- fn leaf(buf: Vec<u8>) -> 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<u8>) -> 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<Rope, Box<dyn Error>> {
- 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<dyn Error>> {
- 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<Rope, Box<dyn Error>> {
+ 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<dyn Error>> {
+ 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();
- }
}
generated by cgit v1.3.1 (git 2.54.0) at 2026-09-04 04:33:22 +0000