#
# Ropes are a data structure introduced in a 1995 paper from
# Hans J. Boehm, Russ Atkinson and Michael Plass.
-# See : `Ropes : an Alternative to Strings`, `Software - Practice and Experience,
-# Vol. 25(12), 1315-1330 (December 1995)`.
+#
+# See:
+#
+# > Ropes: an Alternative to Strings,
+# > *Software - Practice and Experience*,
+# > Vol. 25(12), 1315-1330 (December 1995).
#
# The implementation developed here provides an automatic change
# of data structure depending on the length of the leaves.
#
# Example :
#
-# ` Concat `
-# ` / \ `
-# ` Concat Concat `
-# ` / \ / \ `
-# `"My" " Name" " is" " Simon." `
+# Concat
+# / \
+# Concat Concat
+# / \ / \
+# "My" " Name" " is" " Simon."
#
# Note that the above example is not representative of the actual implementation
# of `Ropes`, since short leaves are merged to keep the rope at an acceptable
super Rope
super String
- redef fun chars is cached do return new RopeChars(self)
+ redef var chars is lazy do return new RopeChars(self)
end
# Node that represents a concatenation between two `String`
private class Concat
super RopeString
- redef var length: Int
+ redef var length is noinit
redef fun substrings do return new RopeSubstrings(self)
redef fun empty do return ""
- redef fun to_cstring is cached do
+ redef var to_cstring is lazy do
var len = length
var ns = new NativeString(len + 1)
ns[len] = '\0'
# Right child of the node
var right: String
- init(l: String, r: String) do
- left = l
- right = r
- length = l.length + r.length
+ init do
+ length = left.length + right.length
end
redef fun output do
redef fun +(o) do
var s = o.to_s
- var mlen = length
var slen = s.length
if s isa Concat then
return new Concat(self, s)
else
var r = right
var rlen = r.length
- if rlen + slen > maxlen then return new Concat(left, new Concat(r, s))
+ if rlen + slen > maxlen then return new Concat(self, s)
return new Concat(left, r + s)
end
end
+
+ redef fun copy_to_native(dest, n, src_offset, dest_offset) do
+ var subs = new RopeSubstrings.from(self, src_offset)
+ var st = src_offset - subs.pos
+ var off = dest_offset
+ while n > 0 do
+ var it = subs.item
+ if n > it.length then
+ var cplen = it.length - st
+ it.items.copy_to(dest, cplen, st, off)
+ off += cplen
+ n -= cplen
+ else
+ it.items.copy_to(dest, n, st, off)
+ n = 0
+ end
+ subs.next
+ st = 0
+ end
+ end
end
# Mutable `Rope`, optimized for concatenation operations
super Rope
super Buffer
- redef fun chars: Sequence[Char] is cached do return new RopeBufferChars(self)
+ redef var chars: Sequence[Char] is lazy do return new RopeBufferChars(self)
# The final string being built on the fly
private var str: String is noinit
# mutable native string (`ns`)
private var buf_size: Int is noinit
- redef fun substrings: Iterator[String] do return new RopeBufSubstringIterator(self)
+ redef fun substrings do return new RopeBufSubstringIterator(self)
# Builds an empty `RopeBuffer`
init do
var nns = new NativeString(buf_size)
var blen = rpos - dumped
ns.copy_to(nns, blen, dumped, 0)
+ ns = nns
dumped = 0
rpos = blen
written = false
str = ""
length = 0
rpos = 0
+ dumped = 0
+ if written then
+ ns = new NativeString(buf_size)
+ written = false
+ end
end
redef fun substring(from, count) do
var slen = s.length
length += slen
var rp = rpos
- if s isa Rope then
- if rp > 0 and dumped != rp then
- str += new FlatString.with_infos(ns, rp - dumped, dumped, rp - 1)
- dumped = rp
- end
- str = str + s
- return
- end
- if slen > maxlen then
+ if s isa Rope or slen > maxlen then
if rp > 0 and dumped != rp then
str += new FlatString.with_infos(ns, rp - dumped, dumped, rp - 1)
dumped = rp
return
end
if slen <= remsp then
- sits.copy_to(ns, slen, begin, rp)
- if rp == buf_size then
- rpos = buf_size
+ if remsp <= 0 then
dump_buffer
rpos = 0
else
+ sits.copy_to(ns, slen, begin, rp)
rpos += slen
end
else
redef fun add(c) do
var rp = rpos
- length += 1
- ns[rp] = c
- rp += 1
- if rp == buf_size then
- rpos = rp
+ if rp >= buf_size then
dump_buffer
rp = 0
end
+ ns[rp] = c
+ rp += 1
+ length += 1
rpos = rp
end
end
redef fun reverse do
- str = str.reversed
- var nns = new NativeString(buf_size)
- var j = rpos
- var mits = ns
- for i in [0 .. rpos[ do
- nns[i] = mits[j]
- j -= 1
+ # Flush the buffer in order to only have to reverse `str`.
+ if rpos > 0 and dumped != rpos then
+ str += new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1)
+ dumped = rpos
end
- ns = nns
+ str = str.reversed
end
redef fun upper do
# the Rope traversal.
var subs: IndexedIterator[String]
- init(root: RopeString) do
+ init(root: RopeString) is old_style_init do
pos = root.length - 1
subs = new ReverseRopeSubstrings(root)
ns = subs.item
# Position (char) in the Rope (0-indexed)
var pos: Int
- init(root: RopeString) do
+ init(root: RopeString) is old_style_init do
subs = new RopeSubstrings(root)
pns = 0
str = subs.item
# Current leaf
var str: String is noinit
- init(root: RopeString) do
+ init(root: RopeString) is old_style_init do
var r = new RopeIterPiece(root, false, true, null)
pos = root.length - 1
var lnod: String = root
redef fun next do
if pos < 0 then return
- var curr: nullable RopeIterPiece = iter.prev
+ var curr = iter.prev
var currit = curr.node
while curr != null do
currit = curr.node
end
private class RopeBufSubstringIterator
- super Iterator[String]
+ super Iterator[FlatText]
# Iterator on the substrings of the building string
- var iter: Iterator[String]
+ var iter: Iterator[FlatText]
# Makes a String out of the buffered part of the Ropebuffer
- var nsstr: String
+ var nsstr: FlatString
# Did we attain the buffered part ?
var nsstr_done = false
- init(str: RopeBuffer) do
+ init(str: RopeBuffer) is old_style_init do
iter = str.str.substrings
nsstr = new FlatString.with_infos(str.ns, str.rpos - str.dumped, str.dumped, str.rpos - 1)
if str.length == 0 then nsstr_done = true
# Substrings of a Rope (i.e. Postfix iterator on leaves)
private class RopeSubstrings
- super IndexedIterator[String]
+ super IndexedIterator[FlatString]
# Visit Stack
var iter: RopeIterPiece is noinit
var max: Int is noinit
# Current leaf
- var str: String is noinit
+ var str: FlatString is noinit
- init(root: RopeString) do
+ init(root: RopeString) is old_style_init do
var r = new RopeIterPiece(root, true, false, null)
pos = 0
max = root.length - 1
rnod = rnod.left
r = new RopeIterPiece(rnod, true, false, r)
else
- str = rnod
+ str = rnod.as(FlatString)
r.rdone = true
iter = r
break
r = new RopeIterPiece(rnod, true, false, r)
end
else
- str = rnod
+ str = rnod.as(FlatString)
r.rdone = true
iter = r
self.pos = pos - off
pos += str.length
if pos > max then return
var it = iter.prev
- var rnod: String = it.node
+ var rnod = it.node
loop
if not rnod isa Concat then
it.ldone = true
it.rdone = true
- str = rnod
+ str = rnod.as(FlatString)
iter = it.as(not null)
break
end
private class RopeChars
super StringCharView
- var tgt: RopeString
-
- init(s: RopeString) do tgt = s
+ redef type SELFTYPE: RopeString
redef fun [](i) do
- return tgt[i]
+ return target[i]
end
- redef fun iterator_from(i) do return new RopeIter.from(tgt, i)
+ redef fun iterator_from(i) do return new RopeIter.from(target, i)
- redef fun reverse_iterator_from(i) do return new RopeReviter.from(tgt, i)
+ redef fun reverse_iterator_from(i) do return new RopeReviter.from(target, i)
end
+# An Iterator over a RopeBuffer.
class RopeBufferIter
super IndexedIterator[Char]
+ # Subiterator.
var sit: IndexedIterator[Char]
+ # Native string iterated over.
var ns: NativeString
+ # Current position in `ns`.
var pns: Int
+ # Maximum position iterable.
var maxpos: Int
- redef var index: Int
+ redef var index
- init(t: RopeBuffer) do
+ # Init the iterator from a RopeBuffer.
+ init(t: RopeBuffer) is old_style_init do
ns = t.ns
maxpos = t.rpos
sit = t.str.chars.iterator
index = 0
end
+ # Init the iterator from a RopeBuffer starting from `pos`.
init from(t: RopeBuffer, pos: Int) do
ns = t.ns
maxpos = t.length
end
end
+# Reverse iterator over a RopeBuffer.
class RopeBufferReviter
super IndexedIterator[Char]
+ # Subiterator.
var sit: IndexedIterator[Char]
+ # Native string iterated over.
var ns: NativeString
+ # Current position in `ns`.
var pns: Int
- redef var index: Int
+ redef var index
- init(tgt: RopeBuffer) do
+ # Init the iterator from a RopeBuffer.
+ init(tgt: RopeBuffer) is old_style_init do
sit = tgt.str.chars.reverse_iterator
pns = tgt.rpos - 1
index = tgt.length - 1
ns = tgt.ns
end
+ # Init the iterator from a RopeBuffer starting from `pos`.
init from(tgt: RopeBuffer, pos: Int) do
sit = tgt.str.chars.reverse_iterator_from(pos - tgt.rpos - tgt.dumped)
pns = pos - tgt.str.length
nitlanguage / nit.git / blobdiff