X-Git-Url: http://nitlanguage.org diff --git a/lib/standard/ropes.nit b/lib/standard/ropes.nit index c4915fd..644e3dc 100644 --- a/lib/standard/ropes.nit +++ b/lib/standard/ropes.nit @@ -16,8 +16,12 @@ # # 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. @@ -32,11 +36,11 @@ # # 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 @@ -63,20 +67,20 @@ private abstract class RopeString 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: Int 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' @@ -94,10 +98,8 @@ private class Concat # 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 @@ -145,14 +147,13 @@ private class Concat 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 @@ -176,7 +177,7 @@ class RopeBuffer 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 @@ -230,6 +231,7 @@ class RopeBuffer 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 @@ -241,6 +243,11 @@ class RopeBuffer 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 @@ -278,15 +285,7 @@ class RopeBuffer 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 @@ -326,12 +325,11 @@ class RopeBuffer 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 @@ -346,14 +344,13 @@ class RopeBuffer 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 @@ -393,15 +390,12 @@ class RopeBuffer 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 @@ -485,7 +479,7 @@ private class RopeReviter # 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 @@ -532,7 +526,7 @@ private class RopeIter # 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 @@ -578,7 +572,7 @@ private class ReverseRopeSubstrings # 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 @@ -627,7 +621,7 @@ private class ReverseRopeSubstrings 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 @@ -663,7 +657,7 @@ private class RopeBufSubstringIterator # 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 @@ -700,7 +694,7 @@ private class RopeSubstrings # Current leaf var str: String 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 @@ -754,7 +748,7 @@ private class RopeSubstrings 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 @@ -784,34 +778,38 @@ 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 - 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 @@ -819,6 +817,7 @@ class RopeBufferIter 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 @@ -844,24 +843,30 @@ class RopeBufferIter 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 - 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