Rope.fs

// Learn more about F# at http://fsharp.net
#light
module Module1

open System
open System.Collections.Generic

type Rope = Rope of int * int * RopeNode
and RopeNode = 
 Concat of Rope * Rope
 | Leaf of String

let depth = fun (Rope(depth,length,content)) -> depth
let length = fun (Rope(depth,length,content)) -> length

let concat r1 r2 = match r1, r2 with
  | Rope(d1, l1, c1), Rope(d2, l2, c2) ->
        let depth = max d1 d2
        let length = l1 + l2
        match c1, c2 with
            | Leaf(""), b -> r2
            | a , Leaf("") -> r1
            | a, b -> Rope(depth, length, Concat(r1, r2))

let fromString_bs blocksize =
    let rec fromString (str : string) =
        if str.Length < blocksize then
            Rope(1, str.Length, Leaf(str))
        else
            let left = str.Substring(0, str.Length/2)
            let right =  str.Substring(str.Length/2)
            concat (fromString left) (fromString right)
    fromString

let fromString = fromString_bs 20

let boundedsubstring (str : string) start off =
    let start = max 0 (min str.Length start)
    let off = max 0 (min (str.Length - start) off)
    str.Substring(start, off)

let emptyRope = fromString ""

let rec subrope start offset rope = 
    let subrope_ = function
        | Concat(rope1, rope2) -> 
            let left =
                if (start <= 0 && offset >= length rope1) then rope1
                else (subrope start offset rope1)
            let right =
                if (start <= length rope1 && start + offset >= length rope1 + length rope2) then rope2
                else (subrope (start - length rope1) (offset - length left) rope2)
            concat left right 
        | Leaf(str) -> 
            fromString (boundedsubstring str start offset)
    if offset <= 0 || start >= length rope then emptyRope
    else match rope with Rope(d, l, node) -> subrope_ node

let rec toStrings = function 
        | Rope(d,l,Leaf(str)) -> [str]
        | Rope(d,l,Concat(r1, r2)) -> toStrings r1 @ toStrings r2

let rec enumerate rope = seq {
        match rope with
            | Rope(d,l,Leaf(str)) -> yield str
            | Rope(d,l,Concat(r1,r2)) ->
                yield! enumerate r1
                yield! enumerate r2
}

let strcat = (+) : string -> string -> string
let concatStrings l = Seq.reduce strcat l
let ropeToString rope = rope |> enumerate |> concatStrings