X-Git-Url: http://nitlanguage.org diff --git a/lib/standard/ropes.nit b/lib/standard/ropes.nit index 8918aa0..8186ec9 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 @@ -229,6 +233,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 @@ -240,6 +245,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 @@ -277,15 +287,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 @@ -325,12 +327,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 @@ -345,14 +346,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 @@ -392,15 +392,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 @@ -626,7 +623,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 @@ -753,7 +750,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 @@ -797,19 +794,25 @@ private class RopeChars 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 the iterator from a RopeBuffer. init(t: RopeBuffer) is old_style_init do ns = t.ns maxpos = t.rpos @@ -818,6 +821,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 @@ -843,17 +847,22 @@ 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 the iterator from a RopeBuffer. init(tgt: RopeBuffer) is old_style_init do sit = tgt.str.chars.reverse_iterator pns = tgt.rpos - 1 @@ -861,6 +870,7 @@ class RopeBufferReviter 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