Node that represents a concatenation between two `String`

# Node that represents a concatenation between two `String`
private class Concat
	super Rope
	super String

	redef fun chars do return new RopeChars(self)

	redef fun bytes do return new RopeBytes(self)

	redef var length is noinit

	redef var byte_length is noinit

	redef fun substrings do return new RopeSubstrings.from(self, 0)

	redef fun empty do return ""

	# Cache for the latest accessed FlatString in `self`
	var flat_cache: FlatString is noinit

	# Position of the beginning of `flat_cache` in `self`
	var flat_last_pos_start: Int is noinit

	redef fun to_cstring do
		var len = _byte_length
		var ns = new CString(len + 1)
		ns[len] = 0
		var off = 0
		for i in substrings do
			var ilen = i._byte_length
			i.as(FlatString)._items.copy_to(ns, ilen, i.as(FlatString)._first_byte, off)
			off += ilen
		end
		return ns
	end

	# Left child of the node
	var left: String
	# Right child of the node
	var right: String

	init do
		var l = _left
		var r = _right
		_length = l.length + r.length
		_byte_length = l.byte_length + r.byte_length
		_flat_last_pos_start = _length
	end

	redef fun is_empty do return _byte_length == 0

	redef fun output do
		_left.output
		_right.output
	end

	redef fun iterator do return new RopeCharIterator.from(self, 0)

	redef fun *(i) do
		var x: String = self
		for j in [1 .. i[ do x += self
		return x
	end

	redef fun [](i) do
		assert i >= 0 and i < _length
		var flps = _flat_last_pos_start
		if i >= flps then
			var fc = _flat_cache
			if i < flps + fc._length then return fc.fetch_char_at(i - flps)
		end
		var lf = get_leaf_at(i)
		return lf.fetch_char_at(i - _flat_last_pos_start)
	end

	fun get_leaf_at(pos: Int): FlatString do
		var flps = _flat_last_pos_start
		if pos >= flps then
			var fc = _flat_cache
			if pos < flps + fc._length then return fc
		end
		var s: String = self
		var st = pos
		loop
			if s isa FlatString then break
			s = s.as(Concat)
			var lft = s._left
			var llen = lft.length
			if pos >= llen then
				s = s._right
				pos -= llen
			else
				s = lft
			end
		end
		_flat_last_pos_start = st - pos
		_flat_cache = s
		return s
	end

	redef fun substring(from, count) do
		if from < 0 then
			count += from
			if count < 0 then return ""
			from = 0
		end

		var ln = _length
		if (count + from) > ln then count = ln - from
		if count <= 0 then return ""
		var end_index = from + count - 1

		var flps = _flat_last_pos_start
		if from >= flps then
			var fc = _flat_cache
			if end_index < flps + fc._length then
				return fc.substring_impl(from - flps, count, end_index - flps)
			end
		end

		var lft = _left
		var llen = lft.length
		if from < llen then
			if from + count < llen then return lft.substring(from, count)
			var lsublen = llen - from
			return lft.substring_from(from) + _right.substring(0, count - lsublen)
		else
			return _right.substring(from - llen, count)
		end
	end

	redef fun reversed do return new Concat(_right.reversed, _left.reversed)

	redef fun insert_at(s, pos) do
		var lft = _left
		if pos > lft.length then
			return lft + _right.insert_at(s, pos - lft.length)
		end
		return lft.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.byte_length
		if s isa Concat then
			return new Concat(self, s)
		else
			var r = _right
			var rlen = r.byte_length
			if rlen + slen > maxlen then return new Concat(self, s)
			return new Concat(_left, r + s)
		end
	end

	redef fun copy_to_native(dest, n, src_offset, dest_offset) do
		var l = _left
		if src_offset < l.byte_length then
			var lcopy = l.byte_length - 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`
	fun balance: String do
		var children = new Array[String]
		var rnod: String
		var iter: nullable RopeCharIteratorPiece = new RopeCharIteratorPiece(self, false, false, null)
		loop
			if iter == null then break
			rnod = iter.node
			if not rnod isa Concat then
				children.push rnod
				iter = iter.prev
				continue
			end
			if not iter.ldone then
				iter.ldone = true
				iter = new RopeCharIteratorPiece(rnod._left, false, false, iter)
			else if not iter.rdone then
				iter.rdone = true
				iter = new RopeCharIteratorPiece(rnod._right, false, false, iter)
			else
				iter = iter.prev
			end

		end
		return recurse_balance(children, children.length)
	end

	fun recurse_balance(nodes: Array[String], len: Int): String do
		var finpos = 0
		var stpos = 0
		while stpos < len do
			if len - stpos > 1 then
				nodes[finpos] = new Concat(nodes[stpos], nodes[stpos + 1])
				stpos += 2
			else
				nodes[finpos] = nodes[stpos]
				stpos += 1
			end
			finpos += 1
		end
		if finpos == 1 then return nodes[0]
		return recurse_balance(nodes, finpos)
	end
end

lib/core/text/ropes.nit:68,1--282,3

ropes_debug :: ropes_debug $ Concat

redef class Concat
	redef fun internal_to_dot
	do
		var s = "n{object_id} [label = {length}];\n"
		s += "n{object_id} -> n{left.object_id} [label = \"left\"];\n"
		s += left.internal_to_dot
		s += "n{object_id} -> n{right.object_id} [label = \"right\"];\n"
		s += right.internal_to_dot
		return s
	end
end

lib/ropes_debug/ropes_debug.nit:30,1--40,3

text_stat :: text_stat $ Concat

redef class Concat
	init do
		sys.concat_allocations += 1
	end

	redef fun byte_length do
		sys.byte_length_call.inc "Concat"
		return super
	end

	redef fun [](i) do
		sys.index_call.inc "Concat"
		if flat_last_pos_start != -1 then
			var fsp = i - flat_last_pos_start
			if fsp >= 0 and fsp < flat_cache.length then return flat_cache[fsp]
		end
		sys.concat_cache_miss += 1
		var s: String = self
		var st = i
		loop
			if s isa FlatString then break
			s = s.as(Concat)
			var lft = s.left
			var llen = lft.length
			if i >= llen then
				s = s.right
				i -= llen
			else
				s = s.left
			end
		end
		flat_last_pos_start = st - i
		flat_cache = s
		return s[i]
	end
end

lib/text_stat/text_stat.nit:133,1--168,3

private class Concat

Summary

Node that represents a concatenation between two String

Introduced properties

_byte_length

_flat_cache

_flat_last_pos_start

_left

_length

_right

balance

byte_length=

defaultinit

flat_cache

flat_cache=

flat_last_pos_start

flat_last_pos_start=

get_leaf_at

left

left=

length=

recurse_balance

right

right=

Redefined properties

*

+

SELF

[]

[]

byte_length

byte_length

bytes

chars

copy_to_native

empty

init

init

insert_at

internal_to_dot

is_empty

iterator

length

output

reversed

substring

substrings

to_cstring

to_lower

to_upper

Node that represents a concatenation between two String

Introduced properties

private var _byte_length: Int

private var _flat_cache: FlatString

private var _flat_last_pos_start: Int

private var _left: String

private var _length: Int

private var _right: String

private fun balance: String

protected fun byte_length=(byte_length: Int)

init defaultinit(left: String, right: String)

private fun flat_cache: FlatString

private fun flat_cache=(flat_cache: FlatString)

private fun flat_last_pos_start: Int

private fun flat_last_pos_start=(flat_last_pos_start: Int)

private fun get_leaf_at(pos: Int): FlatString

private fun left: String

private fun left=(left: String)

protected fun length=(length: Int)

private fun recurse_balance(nodes: Array[String], len: Int): String

private fun right: String

private fun right=(right: String)

Redefined properties

redef fun *(i: Int): SELFTYPE

redef fun +(o: Text): SELFTYPE

redef type SELF: Concat

redef fun [](i: Int): Char

redef fun [](i: Int): Char

redef fun byte_length: Int

redef fun byte_length: Int

Node that represents a concatenation between two `String`

Node that represents a concatenation between two `String`