Phil Trelford's Array
POKE 36879, 255

F# Rope

June 11, 2009 14:59 by phil

The ICFP 2009 programming contest starts on Friday 26th June.

Solving the ICFP 2007 contest task required a scalable string implementation, for which a Rope is a good fit, and the SGI C++ library provides as rope<T,alloc>. A Rope is represented as a binary tree with substrings as leaves.

Rope operations:

  • Appending a string involves creating a new branch with the left as the existing rope and the right as the string to add.
  • Truncation involves creating a new leaf substring with a reduced length.   
  • Insertion involves creating a new branch containing a branch with the left side to the insertion index and the string to insert, plus the right side from the insertion index.
  • Deletion involves creating a new branch with a left substring with reduced length and a right substring with an increased index. 
  • Iterating over the Rope’s characters involves recursively visiting the tree’s substrings.
    For performance, the character length of a branch may be stored, and on branch creation a check made for empty nodes. To optimize small appends branches may be reduced to new strings.
    Ropes are useful for manipulation of large strings, for example with a text editor.
    The following is a naive F# Rope, implemented for fun:
type Rope =
    | Sub of string * int * int
    | Concat of Rope * Rope * int    
    static member Empty = 
        Sub(String.Empty,0,0)
    member this.Length = 
        match this with
        | Sub(_,_,l) -> l
        | Concat(_,_,l) -> l        
    static member Create(s:string) = 
        Rope.Create(s, 0, s.Length)
    static member Create(s, i, l) = 
        Sub(s, i, l)
    static member private Create(lhs:Rope,rhs:Rope) =
        match lhs.Length, rhs.Length with        
        | 0,0 -> Rope.Empty
        | 0,n -> rhs
        | n,0 -> lhs
        | n1,n2 -> Concat(lhs,rhs,n1+n2)   
    member this.to_seq() =
        let rec to_seq = function
            | Sub(s,i,l) -> 
                seq { for n=0 to (l-1) do yield (s.Chars(i+n)) done }
            | Concat(lhs,rhs,_) -> 
                Seq.append (to_seq lhs) (to_seq rhs)
        to_seq this    
    override this.ToString() =
        let builder = System.Text.StringBuilder(this.Length)
        let rec toString = function
            | Sub(s,i,l) -> builder.Append(s, i, l) |> ignore
            | Concat(lhs,rhs,_) -> toString lhs; toString rhs
        toString this
        builder.ToString()
    member this.Append (s:string) = 
        Concat(this, Rope.Create s, this.Length + s.Length)    
    [<OverloadID("Insert(index,Rope)")>]
    member this.Insert(index,value:Rope) =
        let rec insert pos (rope:Rope) =            
            match rope.Length, rope with
            | n, _ when (pos+n) <= index || (pos) > index ->
                rope            
            | n, Sub(s,i,l) ->
                let lhs = Sub(s,i,max 0 (index-pos))
                let rhs = Sub(s,min (i+l) (i+(index-pos)),
                            max 0 (l-(index-pos)))
                Rope.Create(Rope.Create(lhs,value), rhs)
            | n, Concat(l,r,_) ->
                let n = l.Length
                Rope.Create (insert pos l, insert (pos+n) r)
        insert 0 this
    [<OverloadID("Insert(index,string)")>]
    member this.Insert(index,s:string) = 
        this.Insert(index,Sub(s,0,s.Length))      
    member this.Remove(index,length) =
        let rec remove pos (rope:Rope) =
            match rope.Length, rope with
            | n, _ when (pos + n) <= index || pos >= (index + length) ->
                rope            
            | n, Sub(s,i,l) when pos = index -> 
                Sub(s,i+length, max 0 (l-length))
            | n, Sub(s,i,l) when (pos+l) = (index+length) -> 
                Sub(s,i,max 0 (index-pos))
            | n, Sub(s,i,l) ->
                Rope.Create( 
                    Sub(s,i,max 0 (index-pos)), 
                    Sub(s,min (i+l) (i+(index-pos)+length),
                        max 0 (l-(index-pos)-length)))
            | n, Concat(lhs,rhs,_) -> 
                Rope.Create (
                    remove pos lhs, 
                    remove (pos+lhs.Length) rhs)
        remove 0 this                   
    member this.Item        
        with get (index:int) =
            let rec get pos = function
                | Sub(s,i,l) -> s.[i+index-pos]                   
                | Concat(lhs,rhs,_) -> 
                    if index >= (pos + lhs.Length) then 
                        get (pos+lhs.Length) rhs
                    else 
                        get pos lhs 
            get 0 this                     
    member this.Substring(index:int,length:int) =
        let rec sub pos (rope:Rope) = 
            match rope.Length, rope with            
            | n, Sub(s,i,l) ->                                                    
                let offset = index - pos
                if offset < 0 then     
                    Sub(s, i, min (length+offset) l)    
                else
                    Sub(s, i + offset, min length (l-offset))                                    
            | n, Concat(lhs,rhs,_) ->
                if index >= (pos + lhs.Length) then sub (pos+lhs.Length) rhs
                else
                    if (index+length) < (pos+lhs.Length) then
                        sub pos lhs
                    else
                        Rope.Create (sub pos lhs, sub (pos+lhs.Length) rhs)
        sub 0 this

Tags:
Categories: F#
Actions: E-mail | Permalink | Comments (0) | Comment RSSRSS comment feed

Comments

Add comment


(Will show your Gravatar icon)

  Country flag

biuquote
  • Comment
  • Preview
Loading