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

diff --git a/lib/standard/ropes.nit b/lib/standard/ropes.nit
index 54226d5..db635d9 100644
--- a/lib/standard/ropes.nit
+++ b/lib/standard/ropes.nit
@@ -1,19 +1,935 @@
-# This file is part of NIT ( http://www.nitlanguage.org ).
+# This file is part of NIT (http://www.nitlanguage.org).
 #
-# This file is free software, which comes along with NIT.  This software is
-# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
-# without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
-# PARTICULAR PURPOSE.  You can modify it if you want,  provided this header
-# is kept unaltered, and a notification of the changes is added.
-# You  are  allowed  to  redistribute it and sell it, alone or as a part of
-# another product.
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
 
-# Nit implementation of the Ropes (see Ropes : An Alternative to Strings,
-# SOFTWARE - PRACTICE AND EXPERIENCE, VOL. 25(12), 1315 - 1330 (DECEMBER 1995)
-# Hans. J Boehm, Russ Atkinson and Michael Plass)
+# Tree-based representation of a String.
+#
+# 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)`.
+#
+# The implementation developed here provides an automatic change
+# of data structure depending on the length of the leaves.
+#
+# The length from which a `Rope` is built from a `flat` string
+# if defined at top-level (see `maxlen`) and can be redefined by clients
+# depending on their needs (e.g. if you need to bench the speed of
+# the creation of concat nodes, lower the size of maxlen).
 #
-# A rope is a kind of string but instead of being flat, it relies on a binary tree structure to store data.
+# A Rope as defined in the original paper is a Tree made of concatenation
+# nodes and containing `Flat` (that is Array-based) strings as Leaves.
+#
+# Example :
+#
+# `            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
+# height (hence, this rope here might actually be a `FlatString` !).
 module ropes
 
 intrude import string
 
+# Maxlen is the maximum length of a Leaf node
+#
+# When concatenating two leaves, if `new_length` > `maxlen`,
+# A `Concat` node is created instead
+#
+# Its purpose is to limit the depth of the `Rope` (this
+# improves performance when accessing/iterating).
+fun maxlen: Int do return 64
+
+# String using a tree-based representation with leaves as `FlatStrings`
+private abstract class Rope
+	super Text
+end
+
+private abstract class RopeString
+	super Rope
+	super String
+
+	redef fun chars is cached do return new RopeChars(self)
+end
+
+# Node that represents a concatenation between two `String`
+private class Concat
+	super RopeString
+
+	redef var length: Int
+
+	redef fun substrings do return new RopeSubstrings(self)
+
+	redef fun empty do return ""
+
+	redef fun to_cstring is cached do
+		var len = length
+		var ns = new NativeString(len + 1)
+		ns[len] = '\0'
+		var off = 0
+		for i in substrings do
+			var ilen = i.length
+			i.as(FlatString).items.copy_to(ns, ilen, i.as(FlatString).index_from, off)
+			off += ilen
+		end
+		return ns
+	end
+
+	# Left child of the node
+	var left: String
+	# Right child of the node
+	var right: String
+
+	init(l: String, r: String) is old_style_init do
+		left = l
+		right = r
+		length = l.length + r.length
+	end
+
+	redef fun output do
+		left.output
+		right.output
+	end
+
+	redef fun iterator do return new RopeIter(self)
+
+	redef fun *(i) do
+		var x: String = self
+		for j in [1 .. i[ do x += self
+		return x
+	end
+
+	redef fun [](i) do
+		var llen = left.length
+		if i >= llen then return right[i - llen]
+		return left[i]
+	end
+
+	redef fun substring(from, len) do
+		var llen = left.length
+		if from < llen then
+			if from + len < llen then return left.substring(from,len)
+			var lsublen = llen - from
+			return left.substring_from(from) + right.substring(0, len - lsublen)
+		else
+			return right.substring(from - llen, len)
+		end
+	end
+
+	redef fun reversed do return new Concat(right.reversed, left.reversed)
+
+	redef fun insert_at(s, pos) do
+		if pos > left.length then
+			return left + right.insert_at(s, pos - left.length)
+		end
+		return left.insert_at(s, pos) + right
+	end
+
+	redef fun to_upper do return new Concat(left.to_upper, right.to_upper)
+
+	redef fun to_lower do return new Concat(left.to_lower, right.to_lower)
+
+	redef fun +(o) do
+		var s = o.to_s
+		var slen = s.length
+		if s isa Concat then
+			return new Concat(self, s)
+		else
+			var r = right
+			var rlen = r.length
+			if rlen + slen > maxlen then return new Concat(left, new Concat(r, s))
+			return new Concat(left, r + s)
+		end
+	end
+end
+
+# Mutable `Rope`, optimized for concatenation operations
+#
+# A `RopeBuffer` is an efficient way of building a `String` when
+# concatenating small strings.
+#
+# It does concatenations in an optimized way by having a
+# mutable part and an immutable part built by efficiently
+# concatenating strings in chain.
+#
+# Every concatenation operation is done by copying a string to
+# the mutable part and flushing it when full.
+#
+# However, when a long string is appended to the `Buffer`,
+# the concatenation is done at it would be in a `Rope`.
+class RopeBuffer
+	super Rope
+	super Buffer
+
+	redef fun chars: Sequence[Char] is cached do return new RopeBufferChars(self)
+
+	# The final string being built on the fly
+	private var str: String is noinit
+
+	# Current concatenation buffer
+	private var ns: NativeString is noinit
+
+	# Next available (e.g. unset) character in the `Buffer`
+	private var rpos = 0
+
+	# Keeps track of the buffer's currently dumped part
+	#
+	# This might happen if for instance, a String was being
+	# built by concatenating small parts of string and suddenly
+	# a long string (length > maxlen) is appended.
+	private var dumped: Int is noinit
+
+	# Length of the complete rope
+	redef var length = 0
+
+	# Length of the mutable part
+	#
+	# Is also used as base to compute the size of the next
+	# mutable native string (`ns`)
+	private var buf_size: Int is noinit
+
+	redef fun substrings: Iterator[String] do return new RopeBufSubstringIterator(self)
+
+	# Builds an empty `RopeBuffer`
+	init do
+		str = ""
+		ns = new NativeString(maxlen)
+		buf_size = maxlen
+		dumped = 0
+	end
+
+	# Builds a new `RopeBuffer` with `str` in it.
+	init from(str: String) do
+		self.str = str
+		ns = new NativeString(maxlen)
+		buf_size = maxlen
+		length = str.length
+		dumped = 0
+	end
+
+	# Resets the informations of the `Buffer`
+	#
+	# This is called when doing in-place modifications
+	# on a previously to_s'd `RopeBuffer`
+	private fun reset do
+		var nns = new NativeString(buf_size)
+		var blen = rpos - dumped
+		ns.copy_to(nns, blen, dumped, 0)
+		dumped = 0
+		rpos = blen
+		written = false
+	end
+
+	redef fun empty do return new RopeBuffer
+
+	redef fun clear do
+		str = ""
+		length = 0
+		rpos = 0
+		dumped = 0
+	end
+
+	redef fun substring(from, count) do
+		var strlen = str.length
+
+		if from < 0 then
+			count += from
+			if count < 0 then count = 0
+			from = 0
+		end
+
+		if count > length then count = length - from
+
+		if count == 0 then return empty
+
+		if from < strlen then
+			var subpos = strlen - from
+			if count <= subpos then
+				return new RopeBuffer.from(str.substring(from, count))
+			else
+				var l = str.substring_from(from)
+				var rem = count - subpos
+				var nns = new NativeString(rem)
+				ns.copy_to(nns, rem, dumped, 0)
+				return new RopeBuffer.from(l + nns.to_s_with_length(rem))
+			end
+		else
+			var nns = new NativeString(count)
+			ns.copy_to(nns, count, dumped, 0)
+			return new RopeBuffer.from(nns.to_s_with_length(count))
+		end
+	end
+
+	redef fun append(s) do
+		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 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
+		var remsp = buf_size - rp
+		var sits: NativeString
+		var begin: Int
+		if s isa FlatString then
+			begin = s.index_from
+			sits = s.items
+		else if s isa FlatBuffer then
+			begin = 0
+			sits = s.items
+		else
+			if slen <= remsp then
+				for i in s.chars do
+					ns[rpos] = i
+					rpos += 1
+				end
+			else
+				var spos = 0
+				for i in [0..remsp[ do
+					ns[rpos] = s[spos]
+					rpos += 1
+					spos += 1
+				end
+				dump_buffer
+				while spos < slen do
+					ns[rpos] = s[spos]
+					spos += 1
+					rpos += 1
+				end
+			end
+			return
+		end
+		if slen <= remsp then
+			sits.copy_to(ns, slen, begin, rp)
+			if rp == buf_size then
+				rpos = buf_size
+				dump_buffer
+				rpos = 0
+			else
+				rpos += slen
+			end
+		else
+			sits.copy_to(ns, remsp, begin, rp)
+			rpos = buf_size
+			dump_buffer
+			var nlen = slen - remsp
+			sits.copy_to(ns, nlen, begin + remsp, 0)
+			rpos = nlen
+		end
+	end
+
+	redef fun add(c) do
+		var rp = rpos
+		length += 1
+		ns[rp] = c
+		rp += 1
+		if rp == buf_size then
+			rpos = rp
+			dump_buffer
+			rp = 0
+		end
+		rpos = rp
+	end
+
+	# Converts the Buffer to a FlatString, appends it to
+	# the final String and re-allocates a new larger Buffer.
+	private fun dump_buffer do
+		written = false
+		var nstr = new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1)
+		str += nstr
+		var bs = buf_size
+		bs = bs * 2
+		ns = new NativeString(bs)
+		buf_size = bs
+		dumped = 0
+	end
+
+	redef fun output do
+		str.output
+		new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1).output
+	end
+
+	# Enlarge is useless here since the `Buffer`
+	# part is automatically dumped when necessary.
+	#
+	# Also, since the buffer can not be overused by a
+	# single string, there is no need for manual
+	# resizing.
+	#
+	# "You have no power here !"
+	redef fun enlarge(i) do end
+
+	redef fun to_s do
+		written = true
+		var nnslen = rpos - dumped
+		if nnslen == 0 then return str
+		return str + new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1)
+	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
+		end
+		ns = nns
+	end
+
+	redef fun upper do
+		if written then reset
+		str = str.to_upper
+		var mits = ns
+		for i in [0 .. rpos[ do
+			mits[i] = mits[i].to_upper
+		end
+	end
+
+	redef fun lower do
+		if written then reset
+		str = str.to_lower
+		var mits = ns
+		for i in [0 .. rpos[ do
+			mits[i] = mits[i].to_lower
+		end
+	end
+end
+
+redef class FlatString
+
+	redef fun insert_at(s, pos) do
+		var l = substring(0, pos)
+		var r = substring_from(pos)
+		return l + s + r
+	end
+
+	redef fun +(o) do
+		var s = o.to_s
+		var slen = s.length
+		var mlen = length
+		if slen == 0 then return self
+		if mlen == 0 then return s
+		var nlen = slen + mlen
+		if s isa FlatString then
+			if nlen > maxlen then return new Concat(self, s)
+			var mits = items
+			var sifrom = s.index_from
+			var mifrom = index_from
+			var sits = s.items
+			var ns = new NativeString(nlen + 1)
+			mits.copy_to(ns, mlen, mifrom, 0)
+			sits.copy_to(ns, slen, sifrom, mlen)
+			return ns.to_s_with_length(nlen)
+		else if s isa Concat then
+			var sl = s.left
+			var sllen = sl.length
+			if sllen + mlen > maxlen then return new Concat(self, s)
+			return new Concat(self + sl, s.right)
+		else
+			abort
+		end
+	end
+end
+
+# A simple linked list for use with iterators
+private class RopeIterPiece
+	# The encapsulated node of the `Rope`
+	var node: String
+	# Was its left child (if any) visited ?
+	var ldone: Bool
+	# Was its right child (if any) visited ?
+	var rdone: Bool
+	# The previous node in the list.
+	var prev: nullable RopeIterPiece
+end
+
+# A reverse iterator capable of working with `Rope` objects
+private class RopeReviter
+	super IndexedIterator[Char]
+
+	# Current NativeString
+	var ns: String
+	# Current position in NativeString
+	var pns: Int
+	# Position in the Rope (0-indexed)
+	var pos: Int
+	# Iterator on the substrings, does the Postfix part of
+	# the Rope traversal.
+	var subs: IndexedIterator[String]
+
+	init(root: RopeString) is old_style_init do
+		pos = root.length - 1
+		subs = new ReverseRopeSubstrings(root)
+		ns = subs.item
+		pns = ns.length - 1
+	end
+
+	init from(root: RopeString, pos: Int) do
+		self.pos = pos
+		subs = new ReverseRopeSubstrings.from(root, pos)
+		ns = subs.item
+		pns = pos - subs.index
+	end
+
+	redef fun index do return pos
+
+	redef fun is_ok do return pos >= 0
+
+	redef fun item do return ns[pns]
+
+	redef fun next do
+		pns -= 1
+		pos -= 1
+		if pns >= 0 then return
+		if not subs.is_ok then return
+		subs.next
+		if not subs.is_ok then return
+		ns = subs.item
+		pns = ns.length - 1
+	end
+end
+
+# Forward iterator on the chars of a `Rope`
+private class RopeIter
+	super IndexedIterator[Char]
+
+	# Position in current `String`
+	var pns: Int
+	# Current `String` being iterated on
+	var str: String
+	# Substrings of the Rope
+	var subs: IndexedIterator[String]
+	# Maximum position to iterate on (e.g. Rope.length)
+	var max: Int
+	# Position (char) in the Rope (0-indexed)
+	var pos: Int
+
+	init(root: RopeString) is old_style_init do
+		subs = new RopeSubstrings(root)
+		pns = 0
+		str = subs.item
+		max = root.length - 1
+		pos = 0
+	end
+
+	init from(root: RopeString, pos: Int) do
+		subs = new RopeSubstrings.from(root, pos)
+		pns = pos - subs.index
+		self.pos = pos
+		str = subs.item
+		max = root.length - 1
+	end
+
+	redef fun item do return str[pns]
+
+	redef fun is_ok do return pos <= max
+
+	redef fun index do return pos
+
+	redef fun next do
+		pns += 1
+		pos += 1
+		if pns < subs.item.length then return
+		if not subs.is_ok then return
+		subs.next
+		if not subs.is_ok then return
+		str = subs.item
+		pns = 0
+	end
+end
+
+# Substrings of a Rope (i.e. Reverse postfix iterator on leaves)
+private class ReverseRopeSubstrings
+	super IndexedIterator[String]
+
+	# Visit Stack
+	var iter: RopeIterPiece is noinit
+	# Position in `Rope`
+	var pos: Int is noinit
+
+	# Current leaf
+	var str: String is noinit
+
+	init(root: RopeString) is old_style_init do
+		var r = new RopeIterPiece(root, false, true, null)
+		pos = root.length - 1
+		var lnod: String = root
+		loop
+			if lnod isa Concat then
+				lnod = lnod.right
+				r = new RopeIterPiece(lnod, false, true, r)
+			else
+				str = lnod
+				iter = r
+				break
+			end
+		end
+	end
+
+	init from(root: RopeString, pos: Int) do
+		var r = new RopeIterPiece(root, false, true, null)
+		var rnod: String = root
+		var off = pos
+		loop
+			if rnod isa Concat then
+				if off >= rnod.left.length then
+					off -= rnod.left.length
+					rnod = rnod.right
+					r = new RopeIterPiece(rnod, false, true, r)
+				else
+					r.ldone = true
+					rnod = rnod.left
+					r = new RopeIterPiece(rnod, false, true, r)
+				end
+			else
+				str = rnod
+				r.ldone = true
+				iter = r
+				self.pos = pos - off
+				break
+			end
+		end
+	end
+
+	redef fun item do return str
+
+	redef fun index do return pos
+
+	redef fun is_ok do return pos >= 0
+
+	redef fun next do
+		if pos < 0 then return
+		var curr = iter.prev
+		var currit = curr.node
+		while curr != null do
+			currit = curr.node
+			if not currit isa Concat then
+				str = currit
+				pos -= str.length
+				iter = curr
+				return
+			end
+			if not curr.rdone then
+				curr.rdone = true
+				curr = new RopeIterPiece(currit.right, false, false, curr)
+				continue
+			end
+			if not curr.ldone then
+				curr.ldone = true
+				curr = new RopeIterPiece(currit.left, false, false, curr)
+				continue
+			end
+			curr = curr.prev
+		end
+		pos = -1
+	end
+end
+
+private class RopeBufSubstringIterator
+	super Iterator[String]
+
+	# Iterator on the substrings of the building string
+	var iter: Iterator[String]
+	# Makes a String out of the buffered part of the Ropebuffer
+	var nsstr: String
+	# Did we attain the buffered part ?
+	var nsstr_done = false
+
+	init(str: RopeBuffer) is old_style_init do
+		iter = str.str.substrings
+		nsstr = new FlatString.with_infos(str.ns, str.rpos - str.dumped, str.dumped, str.rpos - 1)
+		if str.length == 0 then nsstr_done = true
+	end
+
+	redef fun is_ok do return iter.is_ok or not nsstr_done
+
+	redef fun item do
+		assert is_ok
+		if iter.is_ok then return iter.item
+		return nsstr
+	end
+
+	redef fun next do
+		if iter.is_ok then
+			iter.next
+			return
+		end
+		nsstr_done = true
+	end
+end
+
+# Substrings of a Rope (i.e. Postfix iterator on leaves)
+private class RopeSubstrings
+	super IndexedIterator[String]
+
+	# Visit Stack
+	var iter: RopeIterPiece is noinit
+	# Position in `Rope`
+	var pos: Int is noinit
+	# Maximum position in `Rope` (i.e. length - 1)
+	var max: Int is noinit
+
+	# Current leaf
+	var str: String is noinit
+
+	init(root: RopeString) is old_style_init do
+		var r = new RopeIterPiece(root, true, false, null)
+		pos = 0
+		max = root.length - 1
+		var rnod: String = root
+		loop
+			if rnod isa Concat then
+				rnod = rnod.left
+				r = new RopeIterPiece(rnod, true, false, r)
+			else
+				str = rnod
+				r.rdone = true
+				iter = r
+				break
+			end
+		end
+	end
+
+	init from(root: RopeString, pos: Int) do
+		var r = new RopeIterPiece(root, true, false, null)
+		max = root.length - 1
+		var rnod: String = root
+		var off = pos
+		loop
+			if rnod isa Concat then
+				if off >= rnod.left.length then
+					r.rdone = true
+					off -= rnod.left.length
+					rnod = rnod.right
+					r = new RopeIterPiece(rnod, true, false, r)
+				else
+					rnod = rnod.left
+					r = new RopeIterPiece(rnod, true, false, r)
+				end
+			else
+				str = rnod
+				r.rdone = true
+				iter = r
+				self.pos = pos - off
+				break
+			end
+		end
+	end
+
+	redef fun item do return str
+
+	redef fun is_ok do return pos <= max
+
+	redef fun index do return pos
+
+	redef fun next do
+		pos += str.length
+		if pos > max then return
+		var it = iter.prev
+		var rnod = it.node
+		loop
+			if not rnod isa Concat then
+				it.ldone = true
+				it.rdone = true
+				str = rnod
+				iter = it.as(not null)
+				break
+			end
+			if not it.ldone then
+				rnod = rnod.left
+				it.ldone = true
+				it = new RopeIterPiece(rnod, false, false, it)
+			else if not it.rdone then
+				it.rdone = true
+				rnod = rnod.right
+				it = new RopeIterPiece(rnod, false, false, it)
+			else
+				it = it.prev
+				rnod = it.node
+				continue
+			end
+		end
+	end
+end
+
+# Implementation of a `StringCharView` for `RopeString` objects
+private class RopeChars
+	super StringCharView
+
+	var tgt: RopeString
+
+	init(s: RopeString) is old_style_init do tgt = s
+
+	redef fun [](i) do
+		return tgt[i]
+	end
+
+	redef fun iterator_from(i) do return new RopeIter.from(tgt, i)
+
+	redef fun reverse_iterator_from(i) do return new RopeReviter.from(tgt, i)
+
+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
+		sit = t.str.chars.iterator
+		pns = t.dumped
+		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
+		sit = t.str.chars.iterator_from(pos)
+		pns = pos - t.str.length
+		index = pos
+	end
+
+	redef fun is_ok do return index < maxpos
+
+	redef fun item do
+		if sit.is_ok then return sit.item
+		return ns[pns]
+	end
+
+	redef fun next do
+		index += 1
+		if sit.is_ok then
+			sit.next
+		else
+			pns += 1
+		end
+	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
+		index = tgt.length - 1
+		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
+		index = pos
+		ns = tgt.ns
+	end
+
+	redef fun is_ok do return index > 0
+
+	redef fun item do
+		if pns >= 0 then return ns[pns]
+		return sit.item
+	end
+
+	redef fun next do
+		index -= 1
+		if pns >= 0 then
+			pns -= 1
+		else
+			sit.next
+		end
+	end
+end
+
+# View on the chars of a `RopeBuffer`
+class RopeBufferChars
+	super BufferCharView
+
+	redef type SELFTYPE: RopeBuffer
+
+	redef fun [](i) do
+		if i < target.str.length then
+			return target.str[i]
+		else
+			return target.ns[i - target.str.length]
+		end
+	end
+
+	redef fun []=(i,c) do
+		if i == target.length then target.add c
+		if i < target.str.length then
+			var s = target.str
+			var l = s.substring(0, i)
+			var r = s.substring_from(i + 1)
+			target.str = l + c.to_s + r
+		else
+			target.ns[i - target.str.length] = c
+		end
+	end
+
+	redef fun add(c) do target.add c
+
+	redef fun push(c) do target.add c
+
+	redef fun iterator_from(i) do return new RopeBufferIter.from(target, i)
+
+	redef fun reverse_iterator_from(i) do return new RopeBufferReviter.from(target, i)
+end