From b9fe028f88ed6d6975576ae9b2891294d0054035 Mon Sep 17 00:00:00 2001
From: Rose Hogenson <rosehogenson@posteo.net>
Date: Sat, 13 Jan 2024 20:49:45 -0800
Subject: Allow changing the btree max children.

---
 src/rope.rs | 93 ++++++++++++++++++++++++++++++++-----------------------------
 1 file changed, 49 insertions(+), 44 deletions(-)

(limited to 'src/rope.rs')

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()),
         }
     }
 
-- 
cgit v1.3.1