diff options
Diffstat (limited to 'lib/pure/ropes.nim')
| -rw-r--r-- | lib/pure/ropes.nim | 156 |
1 files changed, 111 insertions, 45 deletions
diff --git a/lib/pure/ropes.nim b/lib/pure/ropes.nim index 41d6211b4..8750aca87 100644 --- a/lib/pure/ropes.nim +++ b/lib/pure/ropes.nim @@ -8,16 +8,19 @@ # ## This module contains support for a `rope`:idx: data type. -## Ropes can represent very long strings efficiently; especially concatenation +## Ropes can represent very long strings efficiently; in particular, concatenation ## is done in O(1) instead of O(n). They are essentially concatenation ## trees that are only flattened when converting to a native Nim -## string. The empty string is represented by ``nil``. Ropes are immutable and +## string. The empty string is represented by `nil`. Ropes are immutable and ## subtrees can be shared without copying. ## Leaves can be cached for better memory efficiency at the cost of ## runtime efficiency. -include "system/inclrtl" -import streams +include system/inclrtl +import std/streams + +when defined(nimPreviewSlimSystem): + import std/[syncio, formatfloat, assertions] {.push debugger: off.} # the user does not want to trace a part # of the standard library! @@ -29,11 +32,11 @@ var cacheEnabled = false type - Rope* = ref RopeObj ## empty rope is represented by nil - RopeObj {.acyclic.} = object + Rope* {.acyclic.} = ref object + ## A rope data type. The empty rope is represented by `nil`. left, right: Rope length: int - data: string # != nil if a leaf + data: string # not empty if a leaf # Note that the left and right pointers are not needed for leafs. # Leaves have relatively high memory overhead (~30 bytes on a 32 @@ -44,9 +47,8 @@ type # pointers. proc len*(a: Rope): int {.rtl, extern: "nro$1".} = - ## the rope's length - if a == nil: result = 0 - else: result = a.length + ## The rope's length. + if a == nil: 0 else: a.length proc newRope(): Rope = new(result) proc newRope(data: string): Rope = @@ -127,6 +129,10 @@ proc insertInCache(s: string, tree: Rope): Rope = proc rope*(s: string = ""): Rope {.rtl, extern: "nro$1Str".} = ## Converts a string to a rope. + runnableExamples: + let r = rope("I'm a rope") + doAssert $r == "I'm a rope" + if s.len == 0: result = nil else: @@ -142,10 +148,18 @@ proc rope*(s: string = ""): Rope {.rtl, extern: "nro$1Str".} = proc rope*(i: BiggestInt): Rope {.rtl, extern: "nro$1BiggestInt".} = ## Converts an int to a rope. + runnableExamples: + let r = rope(429) + doAssert $r == "429" + result = rope($i) proc rope*(f: BiggestFloat): Rope {.rtl, extern: "nro$1BiggestFloat".} = ## Converts a float to a rope. + runnableExamples: + let r = rope(4.29) + doAssert $r == "4.29" + result = rope($f) proc enableCache*() {.rtl, extern: "nro$1".} = @@ -154,12 +168,16 @@ proc enableCache*() {.rtl, extern: "nro$1".} = cacheEnabled = true proc disableCache*() {.rtl, extern: "nro$1".} = - ## the cache is discarded and disabled. The GC will reuse its used memory. + ## The cache is discarded and disabled. The GC will reuse its used memory. cache = nil cacheEnabled = false proc `&`*(a, b: Rope): Rope {.rtl, extern: "nroConcRopeRope".} = - ## the concatenation operator for ropes. + ## The concatenation operator for ropes. + runnableExamples: + let r = rope("Hello, ") & rope("Nim!") + doAssert $r == "Hello, Nim!" + if a == nil: result = b elif b == nil: @@ -171,44 +189,81 @@ proc `&`*(a, b: Rope): Rope {.rtl, extern: "nroConcRopeRope".} = result.right = b proc `&`*(a: Rope, b: string): Rope {.rtl, extern: "nroConcRopeStr".} = - ## the concatenation operator for ropes. + ## The concatenation operator for ropes. + runnableExamples: + let r = rope("Hello, ") & "Nim!" + doAssert $r == "Hello, Nim!" + result = a & rope(b) proc `&`*(a: string, b: Rope): Rope {.rtl, extern: "nroConcStrRope".} = - ## the concatenation operator for ropes. + ## The concatenation operator for ropes. + runnableExamples: + let r = "Hello, " & rope("Nim!") + doAssert $r == "Hello, Nim!" + result = rope(a) & b proc `&`*(a: openArray[Rope]): Rope {.rtl, extern: "nroConcOpenArray".} = - ## the concatenation operator for an openarray of ropes. - for i in countup(0, high(a)): result = result & a[i] + ## The concatenation operator for an `openArray` of ropes. + runnableExamples: + let r = &[rope("Hello, "), rope("Nim"), rope("!")] + doAssert $r == "Hello, Nim!" + + for item in a: result = result & item proc add*(a: var Rope, b: Rope) {.rtl, extern: "nro$1Rope".} = - ## adds `b` to the rope `a`. + ## Adds `b` to the rope `a`. + runnableExamples: + var r = rope("Hello, ") + r.add(rope("Nim!")) + doAssert $r == "Hello, Nim!" + a = a & b proc add*(a: var Rope, b: string) {.rtl, extern: "nro$1Str".} = - ## adds `b` to the rope `a`. + ## Adds `b` to the rope `a`. + runnableExamples: + var r = rope("Hello, ") + r.add("Nim!") + doAssert $r == "Hello, Nim!" + a = a & b proc `[]`*(r: Rope, i: int): char {.rtl, extern: "nroCharAt".} = - ## returns the character at position `i` in the rope `r`. This is quite - ## expensive! Worst-case: O(n). If ``i >= r.len``, ``\0`` is returned. + ## Returns the character at position `i` in the rope `r`. This is quite + ## expensive! Worst-case: O(n). If `i >= r.len or i < 0`, `\0` is returned. + runnableExamples: + let r = rope("Hello, Nim!") + + doAssert r[0] == 'H' + doAssert r[7] == 'N' + doAssert r[22] == '\0' + var x = r var j = i - if x == nil: return + if x == nil or i < 0 or i >= r.len: return while true: if x != nil and x.data.len > 0: - if j < x.data.len: return x.data[j] - return '\0' + # leaf + return x.data[j] else: if x.left.length > j: x = x.left else: + dec(j, x.left.length) x = x.right - dec(j, x.len) iterator leaves*(r: Rope): string = - ## iterates over any leaf string in the rope `r`. + ## Iterates over any leaf string in the rope `r`. + runnableExamples: + let r = rope("Hello") & rope(", Nim!") + let s = ["Hello", ", Nim!"] + var index = 0 + for leave in r.leaves: + doAssert leave == s[index] + inc(index) + if r != nil: var stack = @[r] while stack.len > 0: @@ -221,27 +276,36 @@ iterator leaves*(r: Rope): string = yield it.data iterator items*(r: Rope): char = - ## iterates over any character in the rope `r`. + ## Iterates over any character in the rope `r`. for s in leaves(r): for c in items(s): yield c proc write*(f: File, r: Rope) {.rtl, extern: "nro$1".} = - ## writes a rope to a file. + ## Writes a rope to a file. for s in leaves(r): write(f, s) proc write*(s: Stream, r: Rope) {.rtl, extern: "nroWriteStream".} = - ## writes a rope to a stream. + ## Writes a rope to a stream. for rs in leaves(r): write(s, rs) proc `$`*(r: Rope): string {.rtl, extern: "nroToString".} = - ## converts a rope back to a string. + ## Converts a rope back to a string. result = newStringOfCap(r.len) for s in leaves(r): add(result, s) -proc `%`*(frmt: string, args: openArray[Rope]): Rope {. - rtl, extern: "nroFormat".} = - ## `%` substitution operator for ropes. Does not support the ``$identifier`` - ## nor ``${identifier}`` notations. +proc `%`*(frmt: string, args: openArray[Rope]): Rope {.rtl, extern: "nroFormat".} = + ## `%` substitution operator for ropes. Does not support the `$identifier` + ## nor `${identifier}` notations. + runnableExamples: + let r1 = "$1 $2 $3" % [rope("Nim"), rope("is"), rope("a great language")] + doAssert $r1 == "Nim is a great language" + + let r2 = "$# $# $#" % [rope("Nim"), rope("is"), rope("a great language")] + doAssert $r2 == "Nim is a great language" + + let r3 = "${1} ${2} ${3}" % [rope("Nim"), rope("is"), rope("a great language")] + doAssert $r3 == "Nim is a great language" + var i = 0 var length = len(frmt) result = nil @@ -262,7 +326,7 @@ proc `%`*(frmt: string, args: openArray[Rope]): Rope {. while true: j = j * 10 + ord(frmt[i]) - ord('0') inc(i) - if frmt[i] notin {'0'..'9'}: break + if i >= frmt.len or frmt[i] notin {'0'..'9'}: break add(result, args[j-1]) of '{': inc(i) @@ -282,9 +346,13 @@ proc `%`*(frmt: string, args: openArray[Rope]): Rope {. if i - 1 >= start: add(result, substr(frmt, start, i - 1)) -proc addf*(c: var Rope, frmt: string, args: openArray[Rope]) {. - rtl, extern: "nro$1".} = - ## shortcut for ``add(c, frmt % args)``. +proc addf*(c: var Rope, frmt: string, args: openArray[Rope]) {.rtl, extern: "nro$1".} = + ## Shortcut for `add(c, frmt % args)`. + runnableExamples: + var r = rope("Dash: ") + r.addf "$1 $2 $3", [rope("Nim"), rope("is"), rope("a great language")] + doAssert $r == "Dash: Nim is a great language" + add(c, frmt % args) when not defined(js) and not defined(nimscript): @@ -292,7 +360,7 @@ when not defined(js) and not defined(nimscript): bufSize = 1024 # 1 KB is reasonable proc equalsFile*(r: Rope, f: File): bool {.rtl, extern: "nro$1File".} = - ## returns true if the contents of the file `f` equal `r`. + ## Returns true if the contents of the file `f` equal `r`. var buf: array[bufSize, char] bpos = buf.len @@ -307,21 +375,19 @@ when not defined(js) and not defined(nimscript): bpos = 0 blen = readBuffer(f, addr(buf[0]), buf.len) if blen == 0: # no more data in file - result = false - return + return false let n = min(blen - bpos, slen - spos) - # TODO There's gotta be a better way of comparing here... + # TODO: There's gotta be a better way of comparing here... if not equalMem(addr(buf[bpos]), - cast[pointer](cast[int](cstring(s))+spos), n): - result = false - return + cast[pointer](cast[int](cstring(s)) + spos), n): + return false spos += n bpos += n result = readBuffer(f, addr(buf[0]), 1) == 0 # check that we've read all proc equalsFile*(r: Rope, filename: string): bool {.rtl, extern: "nro$1Str".} = - ## returns true if the contents of the file `f` equal `r`. If `f` does not + ## Returns true if the contents of the file `f` equal `r`. If `f` does not ## exist, false is returned. var f: File result = open(f, filename) |