X-Git-Url: http://nitlanguage.org

diff --git a/lib/bufferized_ropes.nit b/lib/bufferized_ropes.nit
index c2d6f20..18cfa4c 100644
--- a/lib/bufferized_ropes.nit
+++ b/lib/bufferized_ropes.nit
@@ -25,6 +25,28 @@ private class BufferLeaf
 
 end
 
+redef class Concat
+	redef fun to_leaf
+	do
+		if left == null then
+			if right == null then return new StringLeaf("".as(FlatString))
+			return right.to_leaf
+		end
+		if right == null then return left.as(not null).to_leaf
+		if left.length + right.length < buf_len then
+			var b = new FlatBuffer.with_capacity(buf_len)
+			b.append(left.to_leaf.str)
+			b.append(right.to_leaf.str)
+			return new BufferLeaf(b)
+		else
+			var b = new FlatBuffer.with_capacity(left.length + right.length)
+			b.append(left.to_leaf.str)
+			b.append(right.to_leaf.str)
+			return new StringLeaf(b.lazy_to_s(b.length))
+		end
+	end
+end
+
 redef class FlatText
 
 	# Creates a substring, only without any copy overhead for Buffers
@@ -83,5 +105,266 @@ redef class RopeString
 		end
 	end
 
+	redef fun +(o) do return insert_at(o.to_s, length)
+
+	# Inserts a String `str` at position `pos`
+	redef fun insert_at(str, pos)
+	do
+		if str.length == 0 then return self
+
+		assert pos >= 0 and pos <= length
+
+		if pos == length then
+			var r = root
+			if r isa BufferLeaf then
+				var b = r.str.as(FlatBuffer)
+				if r.length + str.length < b.capacity then
+					b.append(str)
+					return new RopeString.from_root(new BufferLeaf(b))
+				end
+			end
+		end
+
+		var path = node_at(pos)
+
+		var cct: RopeNode
+
+		if path.offset == path.leaf.length then
+			cct = build_node_len_offset(path, str)
+		else if path.offset == 0 then
+			cct = build_node_zero_offset(path, str)
+		else
+			cct = build_node_other(path,str)
+		end
+
+		if path.stack.is_empty then return new RopeString.from_root(cct)
+
+		var tmp = path.stack.pop
+		var last_concat: Concat
+
+		if tmp.left then
+			last_concat = new Concat(cct,tmp.node.right.as(not null))
+		else
+			last_concat = new Concat(tmp.node.left.as(not null), cct)
+		end
+
+		for i in path.stack.reverse_iterator do
+			var nod: Concat
+			if i.left then
+				nod = new Concat(last_concat, i.node.right.as(not null))
+			else
+				nod = new Concat(i.node.left.as(not null), last_concat)
+			end
+			last_concat = nod
+		end
+
+		return new RopeString.from_root(last_concat)
+	end
+
+	redef fun substring(pos, len)
+	do
+		if pos < 0 then
+			len += pos
+			pos = 0
+		end
+
+		if pos + len > length then len = length - pos
+
+		if len <= 0 then return new RopeString
+
+		var path = node_at(pos)
+
+		var lf = path.leaf
+		var offset = path.offset
+
+		var s: FlatString
+		if lf isa StringLeaf then
+			s = lf.str.as(FlatString)
+		else
+			s = lf.str.as(FlatBuffer).lazy_to_s(lf.length)
+		end
+
+		if path.leaf.str.length - offset > len then
+			lf = new StringLeaf(s.substring(offset,len).as(FlatString))
+		else
+			lf = new StringLeaf(s.substring_from(offset).as(FlatString))
+		end
+
+		var nod: RopeNode = lf
+
+		if lf.length == len then return new RopeString.from_root(lf)
+
+		var lft: nullable RopeNode
+		var rht: nullable RopeNode
+
+		for i in path.stack.reverse_iterator do
+			if i.right then continue
+			lft = nod
+			rht = i.node.right
+			nod = new Concat(lft, rht)
+		end
+
+		var ret = new RopeString
+		ret.root = nod
+
+		path = ret.node_at(len-1)
+
+		offset = path.offset
+
+		lf = path.leaf
+
+		if lf isa StringLeaf then
+			s = lf.str.as(FlatString)
+		else
+			s = lf.str.as(FlatBuffer).lazy_to_s(lf.length)
+		end
+
+		nod = new StringLeaf(s.substring(0, offset+1).as(FlatString))
+
+		for i in path.stack.reverse_iterator do
+			if i.left then continue
+			rht = nod
+			lft = i.node.left
+			nod = new Concat(lft, rht)
+		end
+
+		ret.root = nod
+
+		return ret
+	end
+
+	private fun build_node_zero_offset(path: Path, s: String): RopeNode
+	do
+		var finlen = path.leaf.length + s.length
+		if finlen <= buf_len then
+			var b = new FlatBuffer.with_capacity(buf_len)
+			b.append(s)
+			b.append(path.leaf.str)
+			if finlen == buf_len then return new StringLeaf(b.lazy_to_s(finlen))
+			return new BufferLeaf(b)
+		end
+		var rht = path.leaf
+		var lft: RopeNode
+		if s isa FlatString then
+			if s.length > buf_len then
+				lft = new StringLeaf(s)
+			else
+				var b = new FlatBuffer
+				b.append(s)
+				lft = new BufferLeaf(b)
+			end
+		else
+			lft = s.as(RopeString).root
+		end
+		return new Concat(lft, rht)
+	end
+
+	private fun build_node_len_offset(path: Path, s: String): RopeNode
+	do
+		var leaf = path.leaf
+		if leaf isa BufferLeaf then
+			if s.length > buf_len then
+				if s isa FlatString then
+					return new Concat(leaf, new StringLeaf(s))
+				else
+					return new Concat(leaf, s.as(Rope).root)
+				end
+			end
+			var finlen = leaf.length + s.length
+			var buf = leaf.str.as(FlatBuffer)
+			var cap = buf.capacity
+			# Meaning the buffer was modified elsewhere
+			# Therefore, we create a new one
+			if leaf.length != buf.length then
+				var b = new FlatBuffer.with_capacity(buf_len)
+				b.append(buf.lazy_to_s(leaf.length))
+				buf = b
+			end
+			if finlen <= cap then
+				buf.append(s)
+				if finlen == buf_len then return new StringLeaf(buf.lazy_to_s(finlen))
+				return new BufferLeaf(buf)
+			else
+				var l_len = finlen - cap
+				buf.append(s.substring(0,l_len))
+				var b2 = new FlatBuffer.with_capacity(buf_len)
+				b2.append(s.substring_from(l_len))
+				var left_leaf = new StringLeaf(buf.lazy_to_s(buf.length))
+				var right_leaf = new BufferLeaf(b2)
+				var cct = new Concat(left_leaf, right_leaf)
+				return cct
+			end
+		else
+			var lft = leaf
+			var rht: RopeNode
+			if s.length >= buf_len then
+				if s isa FlatString then rht = new StringLeaf(s) else rht = s.as(Rope).root
+			else
+				var buf = new FlatBuffer.with_capacity(buf_len)
+				buf.append(s)
+				rht = new BufferLeaf(buf)
+			end
+			return new Concat(lft,rht)
+		end
+	end
+
+	private fun build_node_other(path: Path,str: String): RopeNode
+	do
+		var lf = path.leaf
+		var s: FlatString
+		if lf isa BufferLeaf then
+			var b = lf.str.as(FlatBuffer)
+			s = b.lazy_to_s(lf.length)
+		else
+			s = lf.str.as(FlatString)
+		end
+		var l_str = s.lazy_substring(0, path.offset)
+		var r_str = s.lazy_substring_from(path.offset)
+		if s.length + str.length < buf_len then
+			var buf = new FlatBuffer.with_capacity(buf_len)
+			buf.append(l_str)
+			buf.append(str)
+			buf.append(r_str)
+			return new BufferLeaf(buf)
+		end
+		var child: RopeNode
+		if str isa FlatString then child = new StringLeaf(str) else child = str.as(Rope).root
+		var l_cct = new Concat(new StringLeaf(l_str), child)
+		var r_cct = new Concat(l_cct, new StringLeaf(r_str))
+		return r_cct
+	end
+
 end
 
+redef class SubstringsIterator
+
+	# Compute the bounds of the current substring and makes the substring
+	redef fun make_substring
+	do
+		var l = nodes.item
+		var s = l.str
+		var min = 0
+		var length = l.length
+		if nodes.index < pos then
+			min = pos - nodes.index
+		end
+		substring = s.lazy_substring(min, length)
+	end
+
+end
+
+redef class ReverseSubstringsIterator
+
+	redef fun make_substring
+	do
+		var l = leaves.item
+		var s = l.str
+		if pos > (leaves.index + l.length - 1) then return
+		str = s.lazy_substring(0, (pos - leaves.index + 1))
+	end
+
+end
+
+# Default size of a buffer in a rope leaf.
+fun buf_len: Int do return 200
+