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: 
47: 
48: 
49: 
50:

/// 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: Map<int, string>
    Low: int
    High: int
    Length: int
  }

  type Rope = T
  
  let empty =
    {Value=Map.empty; Low=0; High=0; Length=0}

  let append s (t:T) =
    {t with 
      Value=t.Value.Add(t.High, s)
      High=t.High+1
      Length=t.Length+s.Length
    }

  let prepend s (t:T) =
    {t with 
      Value=t.Value.Add(t.Low-1, s)
      Low=t.Low-1
      Length=t.Length+s.Length
    }

  let toString (t:T) =
    let buffer = new StringBuilder(t.Length)
    for kvp in t.Value do
      buffer.Append(kvp.Value) |> ignore
    buffer.ToString()

/// Real: 00:00:00.033, CPU: 00:00:00.031, GC gen0: 1, gen1: 0, gen2: 0
let mutable r = Rope.empty
for i = 0 to 10000 do
  r <- r |> Rope.append "foo"

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

namespace System

namespace System.Text

type T =
  {Value: Map<int,string>;
   Low: int;
   High: int;
   Length: int;}

Full name: Script.Rope.T

T.Value: Map<int,string>

Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>

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<_>

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

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

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

Full name: Microsoft.FSharp.Core.string

T.Low: int

T.High: int

T.Length: int

type Rope = T

Full name: Script.Rope.Rope

val empty : T

Full name: Script.Rope.empty

val empty<'Key,'T (requires comparison)> : Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.empty

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

Full name: Script.Rope.append

val s : string

val t : T

member Map.Add : key:'Key * value:'Value -> Map<'Key,'Value>

property String.Length: int

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

Full name: Script.Rope.prepend

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 kvp : Collections.Generic.KeyValuePair<int,string>

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)

property Collections.Generic.KeyValuePair.Value: string

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.033, CPU: 00:00:00.031, GC gen0: 1, 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 : Rope.T

Full name: Script.Rope.empty

val i : int

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.344, CPU: 00:00:00.358, GC gen0: 282, gen1: 1, gen2: 1

Next Version Raw view Test code New version

More information

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