lib/standard/ropes: Added cache on indexed access.

Signed-off-by: Lucas Bajolet <r4pass@hotmail.com>

diff --git a/lib/standard/ropes.nit b/lib/standard/ropes.nit
index c17e9bd..9220705 100644 (file)
--- a/lib/standard/ropes.nit
+++ b/lib/standard/ropes.nit
@@ -99,6 +99,14 @@ private class StringLeaf
        redef fun to_leaf do return self
 end
 
+# Used as a cache when using indexed access to a substring in the Rope
+private class LeafCache
+       # Cached leaf
+       var leaf: Leaf
+       # Position in Rope
+       var pos: Int
+end
+
 # Basic structure, binary tree with a root node.
 #
 # Also shared services by subsequent implementations.
@@ -111,6 +119,8 @@ abstract class Rope
        # Cached version of self as a flat String
        private var str_representation: nullable NativeString = null
 
+       private var leaf_cache: nullable LeafCache = null
+
        # Empty Rope
        init do from("")
 
@@ -225,7 +235,10 @@ abstract class Rope
        private fun get_node_from(node: RopeNode, curr_pos: Int, seek_pos: Int, stack: List[PathElement]): Path
        do
                assert curr_pos >= 0
-               if node isa Leaf then return new Path(node, seek_pos - curr_pos, stack)
+               if node isa Leaf then
+                       self.leaf_cache = new LeafCache(node, curr_pos)
+                       return new Path(node, seek_pos - curr_pos, stack)
+               end
                node = node.as(Concat)
 
                if node.left != null then
@@ -439,6 +452,7 @@ private class RopeStringChars
        redef fun [](pos)
        do
                assert pos < tgt.length
+               if tgt.leaf_cache != null and pos >= tgt.leaf_cache.pos and (tgt.leaf_cache.pos + tgt.leaf_cache.leaf.length) > pos then return tgt.leaf_cache.leaf.str.chars[pos - tgt.leaf_cache.pos]
                var path = tgt.node_at(pos)
                return path.leaf.str.chars[path.offset]
        end