Rope

Simple implementation of the rope data structure, http://en.wikipedia.org/wiki/Rope_(computer_science)

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46:

/// Simple implementation of the rope data structure
/// http://en.wikipedia.org/wiki/Rope_(computer_science) 
/// 
/// Uses an F# Map<int, string> for internal storage
module Rope =

  open System
  open System.Text

  type T = {
    Value: string array
    Index: int
    Length: int
  }

  type Rope = T
  
  let empty() =
    {Value=Array.zeroCreate 200; Index=0; Length=0}

  let append s (t:T) =
    t.Value.[t.Index] <- s
    {t with 
      Index=t.Index+1
      Length=t.Length+s.Length
    }

  let toString (t:T) =
    let buffer = new StringBuilder(t.Length)
    for i = 0 to t.Index-1 do
      buffer.Append(t.Value.[i]) |> ignore
    buffer.ToString()

/// Real: 00:00:00.045, CPU: 00:00:00.046, GC gen0: 27, gen1: 0, gen2: 0
let mutable r = Rope.empty()
for i = 0 to 10000 do
  r <- Rope.empty()
  for i = 0 to 100 do
    r <- r |> Rope.append "foo"

/// Real: 00:00:00.359, CPU: 00:00:00.358, GC gen0: 308, gen1: 0, gen2: 0
let mutable s = ""
for i = 0 to 10000 do
  s <- ""
  for i = 0 to 100 do
    s <- s + "foo"

namespace System

namespace System.Text

type T =
  {Value: string array;
   Index: int;
   Length: int;}

Full name: Script.Rope.T

T.Value: string array

Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string

type 'T array = 'T []

Full name: Microsoft.FSharp.Core.array<_>

T.Index: int

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

T.Length: int

type Rope = T

Full name: Script.Rope.Rope

val empty : unit -> T

Full name: Script.Rope.empty

type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...

Full name: System.Array

val zeroCreate : count:int -> 'T []

Full name: Microsoft.FSharp.Collections.Array.zeroCreate

val append : s:string -> t:T -> T

Full name: Script.Rope.append

val s : string

val t : T

property String.Length: int

val toString : t:T -> string

Full name: Script.Rope.toString

val buffer : StringBuilder

Multiple items
type StringBuilder =
  new : unit -> StringBuilder + 5 overloads
  member Append : value:string -> StringBuilder + 18 overloads
  member AppendFormat : format:string * arg0:obj -> StringBuilder + 4 overloads
  member AppendLine : unit -> StringBuilder + 1 overload
  member Capacity : int with get, set
  member Chars : int -> char with get, set
  member Clear : unit -> StringBuilder
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EnsureCapacity : capacity:int -> int
  member Equals : sb:StringBuilder -> bool
  ...

Full name: System.Text.StringBuilder

--------------------
StringBuilder() : unit
StringBuilder(capacity: int) : unit
StringBuilder(value: string) : unit
StringBuilder(value: string, capacity: int) : unit
StringBuilder(capacity: int, maxCapacity: int) : unit
StringBuilder(value: string, startIndex: int, length: int, capacity: int) : unit

val i : int

StringBuilder.Append(value: char []) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: obj) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: uint64) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: uint32) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: uint16) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: decimal) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: float) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: float32) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: int64) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: int) : StringBuilder
   (+0 other overloads)

val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore

StringBuilder.ToString() : string
StringBuilder.ToString(startIndex: int, length: int) : string

val mutable r : Rope.T

Full name: Script.r

Real: 00:00:00.045, CPU: 00:00:00.046, GC gen0: 27, gen1: 0, gen2: 0

module Rope

from Script

Simple implementation of the rope data structure
http://en.wikipedia.org/wiki/Rope_(computer_science)

Uses an F# Map<int, string> for internal storage

val empty : unit -> Rope.T

Full name: Script.Rope.empty

val append : s:string -> t:Rope.T -> Rope.T

Full name: Script.Rope.append

val mutable s : string

Full name: Script.s

Real: 00:00:00.359, CPU: 00:00:00.358, GC gen0: 308, gen1: 0, gen2: 0

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/4e
Posted:	13 years ago
Author:	fholm
Tags:	rope , string , concat