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