#
#
# Nim's Runtime Library
# (c) Copyright 2010 Andreas Rumpf
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
## This module contains support for a `rope`:idx: data type.
## 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
## 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
when defined(nimPreviewSlimSystem):
import std/syncio
{.push debugger: off.} # the user does not want to trace a part
# of the standard library!
const
countCacheMisses = false
var
cacheEnabled = false
type
Rope* {.acyclic.} = ref object
## A rope data type. The empty rope is represented by `nil`.
left, right: Rope
length: int
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
# bit machine) and we produce many of them. This is why we cache and
# share leafs across different rope trees.
# To cache them they are inserted in another tree, a splay tree for best
# performance. But for the caching tree we use the leaf's left and right
# pointers.
proc len*(a: Rope): int {.rtl, extern: "nro$1".} =
## The rope's length.
if a == nil: 0 else: a.length
proc newRope(): Rope = new(result)
proc newRope(data: string): Rope =
new(result)
result.length = len(data)
result.data = data
var
cache {.threadvar.}: Rope # the root of the cache tree
N {.threadvar.}: Rope # dummy rope needed for splay algorithm
when countCacheMisses:
var misses, hits: int
proc splay(s: string, tree: Rope, cmpres: var int): Rope =
var c: int
var t = tree
N.left = nil
N.right = nil # reset to nil
var le = N
var r = N
while true:
c = cmp(s, t.data)
if c < 0:
if (t.left != nil) and (s < t.left.data):
var y = t.left
t.left = y.right
y.right = t
t = y
if t.left == nil: break
r.left = t
r = t
t = t.left
elif c > 0:
if (t.right != nil) and (s > t.right.data):
var y = t.right
t.right = y.left
y.left = t
t = y
if t.right == nil: break
le.right = t
le = t
t = t.right
else:
break
cmpres = c
le.right = t.left
r.left = t.right
t.left = N.right
t.right = N.left
result = t
proc insertInCache(s: string, tree: Rope): Rope =
var t = tree
if t == nil:
result = newRope(s)
when countCacheMisses: inc(misses)
return
var cmp: int
t = splay(s, t, cmp)
if cmp == 0:
# We get here if it's already in the Tree
# Don't add it again
result = t
when countCacheMisses: inc(hits)
else:
when countCacheMisses: inc(misses)
result = newRope(s)
if cmp < 0:
result.left = t.left
result.right = t
t.left = nil
else:
# i > t.item:
result.right = t.right
result.left = t
t.right = nil
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:
when nimvm:
# No caching in VM context
result = newRope(s)
else:
if cacheEnabled:
result = insertInCache(s, cache)
cache = result
else:
result = newRope(s)
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".} =
## Enables the caching of leaves. This reduces the memory footprint at
## the cost of runtime efficiency.
cacheEnabled = true
proc disableCache*() {.rtl, extern: "nro$1".} =
## 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.
runnableExamples:
let r = rope("Hello, ") & rope("Nim!")
doAssert $r == "Hello, Nim!"
if a == nil:
result = b
elif b == nil:
result = a
else:
result = newRope()
result.length = a.length + b.length
result.left = a
result.right = b
proc `&`*(a: Rope, b: string): Rope {.rtl, extern: "nroConcRopeStr".} =
## 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.
runnableExamples:
let r = "Hello, " & rope("Nim!")
doAssert $r == "Hello, Nim!"
result = rope(a) & b
p
/* * (C)opyright MMVI Anselm R. Garbe <garbeam at gmail dot com> * See LICENSE file for license details. */enum{