nit: Added link to `CONTRIBUTING.md` from the README

[nit.git] / lib / core / text / ropes.nit

diff --git a/lib/core/text/ropes.nit b/lib/core/text/ropes.nit
index 84afa5b..0bf97b8 100644 (file)
--- a/lib/core/text/ropes.nit
+++ b/lib/core/text/ropes.nit
@@ -115,6 +115,8 @@ private class Concat
                _bytelen = l.bytelen + r.bytelen
        end
 
+       redef fun is_empty do return _bytelen == 0
+
        redef fun output do
                _left.output
                _right.output
@@ -170,7 +172,7 @@ private class Concat
                        from = 0
                end
 
-               var ln = length
+               var ln = _length
                if (count + from) > ln then count = ln - from
                if count <= 0 then return ""
                var end_index = from + count - 1
@@ -219,23 +221,16 @@ private class Concat
        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
+               var l = _left
+               if src_offset < l.bytelen then
+                       var lcopy = l.bytelen - src_offset
+                       lcopy = if lcopy > n then n else lcopy
+                       l.copy_to_native(dest, lcopy, src_offset, dest_offset)
+                       dest_offset += lcopy
+                       n -= lcopy
+                       src_offset = 0
                end
+               _right.copy_to_native(dest, n, src_offset, dest_offset)
        end
 
        # Returns a balanced version of `self`
@@ -668,7 +663,7 @@ private class RopeByteIterator
        var ns: NativeString is noautoinit
        # Substrings of the Rope
        var subs: IndexedIterator[FlatString] is noautoinit
-       # Maximum position to iterate on (e.g. Rope.length)
+       # Maximum position to iterate on (e.g. Rope.bytelen)
        var max: Int is noautoinit
        # Position (char) in the Rope (0-indexed)
        var pos: Int is noautoinit
@@ -678,7 +673,7 @@ private class RopeByteIterator
                pns = pos - subs.index
                self.pos = pos
                ns = subs.item._items
-               max = root.length - 1
+               max = root.bytelen - 1
        end
 
        redef fun item do return ns[pns]
@@ -982,18 +977,45 @@ private class RopeBytes
 
        redef type SELFTYPE: Concat
 
+       var cache: FlatString is noinit
+
+       var cache_start: Int = -1
+
+       var cache_end: Int = -1
+
        redef fun [](i) do
-               var nod: String = target
+               assert i >= 0 and i < target._bytelen
+               var flps = _cache_start
+               if i >= flps and i <= _cache_end then
+                       return _cache.bytes[i - flps]
+               end
+               var lf = get_leaf_at(i)
+               return lf.bytes[i - _cache_start]
+       end
+
+       fun get_leaf_at(pos: Int): FlatString do
+               var flps = _cache_start
+               if pos >= flps and pos <= _cache_end then
+                       return _cache
+               end
+               var s: String = target
+               var st = pos
                loop
-                       if nod isa FlatString then return nod._items[i]
-                       if not nod isa Concat then abort
-                       var lft = nod._left
-                       if lft.bytelen >= i then
-                               nod = nod._right
+                       if s isa FlatString then break
+                       s = s.as(Concat)
+                       var lft = s._left
+                       var llen = lft.bytelen
+                       if pos >= llen then
+                               s = s._right
+                               pos -= llen
                        else
-                               nod = lft
+                               s = lft
                        end
                end
+               _cache_start = st - pos
+               _cache_end = st - pos + s.bytelen - 1
+               _cache = s
+               return s
        end
 
        redef fun iterator_from(i) do return new RopeByteIterator.from(target, i)