From b2d5db22601b830af2ae2eb4a2d14ac086f6d2b7 Mon Sep 17 00:00:00 2001 From: Lucas Bajolet Date: Fri, 6 Jun 2014 13:58:25 -0400 Subject: [PATCH] lib/standard/ropes: Added cache on indexed access. Signed-off-by: Lucas Bajolet --- lib/standard/ropes.nit | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) diff --git a/lib/standard/ropes.nit b/lib/standard/ropes.nit index c17e9bd..9220705 100644 --- 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 -- 1.7.9.5