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

Add comment

biuquote