(* 

   A B-tree-based rope.

   ocamlopt -g brope.ml bropetest.ml -o bropetest && ./bropetest
 *)

type brope = Leaf of string
             | Cat of int * brope list

type insertion = Subtree of brope
                 | Subtrees of brope * brope

let max_leaf_size = 256
let min_leaf_size = 80                (* try to coalesce if smaller *)
let length b = match b with
    Leaf s -> String.length s
  | Cat (len, _) -> len
let empty = Leaf ""
(* So, how do we add a leaf to a tree?
   Right now I have written down the case where the tree is a leaf.
   But there are other cases.
   Probably the correct thing to do is to append it as a leaf
   (splitting a Cat if necessary)
   and then maybe coalesce a bit.
   Not quite sure how to handle the coalescence.  Maybe a coalesce_children?
 *)
let coalesce_kids b = b
let rec add_kid leaf kids = match kids with
    [] -> [leaf]
  | kid :: kids -> kid :: add_kid leaf kids
exception Empty_cat of string
let rec add_descendant s kids = match kids with
    [] -> raise (Empty_cat s)
  | [kid] -> [add_leaf s kid]
  | kid :: kids -> kid :: add_descendant s kids
and add_leaf s b =
  let len = String.length s in 
  match b with
  (* Go towards the bottom of the tree. *)
  | Cat (clen, ((Cat _ :: _) as kids)) ->
    coalesce_kids (Cat (clen + len, add_descendant s kids))
  (* At the bottom of the tree. *)
  | Cat (clen, kids) -> coalesce_kids (Cat (clen + len, add_kid (Leaf s) kids))
  | Leaf bo when String.length bo + len < min_leaf_size -> Leaf (bo ^ s)
  | x -> coalesce_kids (Cat (length x + len, [x; (Leaf s)]))
let rec add_string s b =
  let len = String.length s in
  if len = 0 then b
  else if max_leaf_size >= len
  then add_leaf s b
  else add_string
    (String.sub s max_leaf_size (len - max_leaf_size))
    (add_leaf (String.sub s 0 max_leaf_size) b)
let of_string s = add_string s empty