# 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.

# 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)
#
# A rope is a kind of string but instead of being flat, it relies on a binary tree structure to store data.
module ropes

import file
intrude import string

# Structure, tuple containing a LeafNode and an Int
# Used for methods like [] or has/has_only
private class TupleLeafNodePos
	private var curr_node: LeafNode
	private var corrected_pos: Int
	private var visit_stack: List[TupleVisitNode]
end

# Abstract class, represents all the services offered by both mutable and immutable ropes
abstract class Rope
	super Comparable
	super StringCapable

	# Cached version of self as a flat String
	private var str_representation: nullable String = null

	redef type OTHER: Rope

	# The first node of the hierarchy
	private var parent_node: RopeNode

	# Needed by the compiler to avoid producing an error with constructors in subclasses
	init do
		self.parent_node = new ConcatNode
	end

	# Initializes a new Rope with a text embedded in directly
	init with_string(str: String) do
		self.parent_node = new ConcatNode
		parent_node.as(ConcatNode).right_child = new LeafNode(str)
		parent_node.as(ConcatNode).update_data
	end

	# Returns a view on the rope
	fun chars: SequenceRead[Char]
	do
		return new CharRopeView(self)
	end

	# Gets the total length of the Rope
	fun length: Int
	do
		return parent_node.length
	end

	# Returns a flat version of self
	redef fun to_s
	do
		if self.str_representation == null then flatten
		return str_representation.as(not null)
	end

	# Stores a flat version of self in cache
	private fun flatten: FlatString
	do
		var native_final_str = calloc_string(length + 1)

		native_final_str[length] = '\0'

		var offset = 0

		var iter = new DFSRopeLeafIterator(self)

		while iter.is_ok do
			iter.item.value.as(FlatString).items.copy_to(native_final_str, iter.item.value.length, 0, offset)
			offset += iter.item.value.length
			iter.next
		end

		return native_final_str.to_s_with_length(length)
	end

	# Gets a node containing the substring to seek the char at the require position
	private fun get_node_for_pos(position: Int): TupleLeafNodePos
	do
		assert position >= 0 and position < self.length

		var curr_node: nullable RopeNode = parent_node

		var visit_stack = new List[TupleVisitNode]

		var curr_visit_tuple: TupleVisitNode

		loop
			if curr_node isa ConcatNode then
				curr_visit_tuple = new TupleVisitNode(curr_node)
				if curr_node.left_child != null and position < curr_node.left_child.length then
					curr_visit_tuple.left_visited = true
					curr_node = curr_node.left_child
				else if curr_node.right_child != null then
					curr_visit_tuple.left_visited = true
					curr_visit_tuple.right_visited = true
					if curr_node.left_child != null then position -= curr_node.left_child.length
					curr_node = curr_node.right_child
				else
					print "Fatal Error"
					abort
				end
				visit_stack.push(curr_visit_tuple)
			else if curr_node isa LeafNode then
				return new TupleLeafNodePos(curr_node, position, visit_stack)
			end
		end
	end

	# Concats two ropes and returns a new one
	fun +(other: Rope): Rope do
		var new_rope = new BufferRope

		var first_iter = new DFSRopeLeafIterator(self)

		while first_iter.is_ok do
			new_rope.append(first_iter.item.value)
			first_iter.next
		end

		var second_iter = new DFSRopeLeafIterator(other)

		while second_iter.is_ok do
			new_rope.append(second_iter.item.value)
			second_iter.next
		end

		return new_rope
	end

	# Returns a copy of several ropes concatenated
	#
	# Is equivalent to a chain of + operations
	# Except this one is optimized for performance
	fun multi_concat(ropes: Rope...): Rope
	do
		var new_rope = new BufferRope

		var self_iter = self.iterator
		while self_iter.is_ok do
			new_rope.append(self_iter.item.value)
			self_iter.next
		end

		for i in ropes do
			var iter = i.iterator
			while iter.is_ok do
				new_rope.append(iter.item.value)
				iter.next
			end
		end

		return new_rope
	end

	# Appends the content of self multiple times in a new Rope object
	fun *(repeats: Int): Rope do

		var new_rope = new BufferRope

		var str = self.to_s

		for i in [1 .. repeats] do new_rope.append(str)

		return new_rope
	end

	# Returns an iterator on self
	#
	# Unsafe modifications on a MutableRope
	#
	private fun iterator: Iterator[LeafNode] do return new DFSRopeLeafIterator(self)

	# Creates a subrope.
	#
	# var rope = (new BufferRope).append("abcd")
	#
	#	assert rope.subrope(1, 2)         ==  "bc"
	#	assert rope.subrope(-1, )         ==  "a"
	#	assert rope.subrope(1, 0)         ==  ""
	#	assert rope.subrope(2, 5)         ==  "cd"
	#
	# A `index_from` index < 0 will be replaced by 0.
	# Unless a `count` value is > 0 at the same time.
	# In this case, `index_from += count` and `count -= index_from`.
	#
	fun subrope(index_from: Int, count: Int): Rope
	do
		assert count >= 0

		if index_from < 0 then
			count += index_from
			if count < 0 then count = 0
			index_from = 0
		end

		if count - index_from >= self.length then count = length - index_from

		var buffer = new BufferRope

		var iter = new DFSRopeLeafIterator.with_index(self, index_from)

		var curr_subrope_index = index_from - iter.pos

		while iter.is_ok do
			if count == 0 then break
			if curr_subrope_index > 0 then
				if count >= iter.item.value.length then
					buffer.append(iter.item.value.substring(curr_subrope_index, count))
					count -= iter.item.value.length - curr_subrope_index
					curr_subrope_index = 0
				else
					buffer.append(iter.item.value.substring(curr_subrope_index, count))
					break
				end
			else
				if count >= iter.item.value.length then
					buffer.append(iter.item.value)
					count -= iter.item.value.length
				else
					buffer.append(iter.item.value.substring(0, count))
					break
				end
			end

			iter.next
		end

		return buffer
	end

	# Returns an upper (capitalized) version of self
	fun to_upper: Rope
	do
		var new_rope = new BufferRope
		var iter = new DFSRopeLeafIterator(self)
		while iter.is_ok do
			new_rope.append(iter.item.value.to_upper)
			iter.next
		end
		return new_rope
	end

	# Returns a lower (minuscule) version of self
	fun to_lower: Rope
	do
		var new_rope = new BufferRope
		var iter = new DFSRopeLeafIterator(self)
		while iter.is_ok do
			new_rope.append(iter.item.value.to_lower)
			iter.next
		end
		return new_rope
	end

	############################################################################
	#                       Comparable Refined Methods                         #
	############################################################################

	# Compares the current Rope to another object (either another rope or a String)
	redef fun == (other)
	do
		if other == null or not (other isa Rope or other isa FlatText) then return false
		var self_iter = new RopeCharIterator(self)
		if other isa Rope then
			if self.length != other.length then return false
			var other_iterator = new RopeCharIterator(other)
			while self_iter.is_ok do
				if self_iter.item != other_iterator.item then return false
				self_iter.next
				other_iterator.next
			end
		else if other isa FlatText then
			var pos = 0
			if self.length != other.length then return false
			while self_iter.is_ok do
				if self_iter.item != other[pos] then return false
				pos += 1
				self_iter.next
			end
		end
		return true
	end

	# Checks if self is lesser than other
	#
	# Comparison done in lexicographical order
	# i.e. 'aa' < 'b'
	#
	redef fun <(other)
	do
		var other_iter = other.chars.iterator
		for i in self.chars do
			if not other_iter.is_ok then return false
			if i < other_iter.item then return true
			if i > other_iter.item then return false
			other_iter.next
		end
		if other_iter.is_ok then return true
		return false
	end

end

# Rope that can be modified
#
# /!\ Non Thread-safe /!\
#
class BufferRope
	super Rope

	var is_dirty: Bool = false

	init
	do
		super
	end

	redef init with_string(str)
	do
		super
	end

	############################################################################
	#                         Tree Balancing Methods                           #
	############################################################################

	# Performs a right rotation on a node of the Rope
	#
	#              Root                Pivot
	#             /    \              /     \
	#           Pivot Leaf3     =>  Leaf1  Root
	#          /     \                    /   \
	#       Leaf1   Leaf2              Leaf2  Leaf3
	private fun rotate_right(root: ConcatNode)
	do
		assert root.left_child != null
		var pivot = root.left_child.as(ConcatNode)
		var root_new_left = pivot.right_child
		var root_parent = root.parent

		root.left_child = root_new_left
		pivot.right_child = root
		if root_parent == null then
			self.parent_node = pivot
			pivot.parent = null
			return
		end

		if root_parent.left_child == root then
			root_parent.left_child = pivot
		else
			root_parent.right_child = pivot
		end

		root.update_data
		pivot.update_data
		root_parent.update_data
	end

	# Performs a left rotation on a node of the Rope
	#
	#      Root                    Pivot
	#     /    \                  /     \
	#  Leaf1  Pivot        =>   Root   Leaf3
	#        /     \           /    \
	#      Leaf2  Leaf3      Leaf1 Leaf2
	private fun rotate_left(root: ConcatNode)
	do
		assert root.right_child != null
		var pivot = root.right_child.as(ConcatNode)
		var root_new_right = pivot.left_child
		var root_parent = root.parent

		root.right_child = root_new_right
		pivot.left_child = root
		if root_parent == null then
			self.parent_node = pivot
			pivot.parent = null
			return
		end

		if root_parent.left_child == root then
			root_parent.left_child = pivot
		else
			root_parent.right_child = pivot
		end

		root.update_data
		pivot.update_data
		root_parent.update_data
	end

	# Shortcut method to balance a node and its parents
	# based on the rules of the AVL Tree
	private fun balance_from_node(parent_node: nullable ConcatNode)
	do
		while parent_node != null do
			parent_node.update_data
			var node_balance = parent_node.balance_factor
			if node_balance < -1 or node_balance > 1 then
				balance_node(parent_node)
			end
			parent_node = parent_node.parent
		end
	end

	# Performs rotations to balance a node according to AVL Tree rules
	private fun balance_node(node: ConcatNode)
	do
		var balance_factor = node.balance_factor
		if balance_factor < -1 then
			var right_balance = node.right_child.balance_factor
			if right_balance < 0 then
				rotate_left(node)
			else
				rotate_right(node.right_child.as(ConcatNode))
				rotate_left(node)
			end
		else
			var left_balance = node.left_child.balance_factor
			if left_balance > 0 then
				rotate_right(node)
			else
				rotate_left(node.left_child.as(ConcatNode))
				rotate_right(node)
			end
		end
	end

	############################################################################
	#                      BufferRope exclusive Methods                        #
	############################################################################

	# Appends a new Collection[Char] at the end of the current rope
	fun append(str: String): BufferRope
	do
		var last_node = parent_node

		while last_node isa ConcatNode and last_node.right_child != null do
			last_node = last_node.right_child.as(not null)
		end

		if last_node isa ConcatNode then
			last_node.right_child = new LeafNode(str.to_s)
		else if last_node isa LeafNode then
			var last_node_parent = last_node.parent
			var new_concat = new ConcatNode
			last_node_parent.right_child = new_concat
			new_concat.left_child = last_node
			new_concat.right_child = new LeafNode(str.to_s)
			last_node = new_concat
		else
			print "Fatal Error, please report to the developers for more insight."
			abort
		end

		balance_from_node(last_node)

		is_dirty = true

		return self
	end

	# Variatic function to append several collections of Chars
	fun append_multi(strs: String...): BufferRope
	do
		for i in strs do
			append(i)
		end
		return self
	end

	# Adds a new Collection[Char] at the beginning of the rope
	fun prepend(str: String): BufferRope
	do
		var curr_node = parent_node

		while curr_node isa ConcatNode and curr_node.left_child != null do
			curr_node = curr_node.left_child.as(not null)
		end

		if curr_node isa ConcatNode then
			curr_node.left_child = new LeafNode(str.to_s)
		else if curr_node isa LeafNode then
			var parent = curr_node.parent
			var new_concat = new ConcatNode
			var new_leaf = new LeafNode(str.to_s)
			new_concat.left_child = new_leaf
			new_concat.right_child = curr_node
			parent.left_child = new_concat
			curr_node = new_concat
		else
			print "Fatal Error"
			abort
		end

		balance_from_node(curr_node)

		is_dirty = true

		return self
	end

	# Variatic function to prepend several collections of Chars
	fun prepend_multi(strs: String...): BufferRope
	do
		for i in strs do
			prepend(i)
		end
		return self
	end

	# Adds the content of `str` after self, does not create a new rope object
	fun concat(str: Rope): Rope
	do
		var other_iter = new DFSRopeLeafIterator(str)

		var modif_list = new List[String]

		while other_iter.is_ok do
			modif_list.push(other_iter.item.value)
			other_iter.next
		end

		while modif_list.length > 0 do
			self.append(modif_list.shift)
		end

		if not is_dirty then is_dirty = true

		return self
	end

	# Returns the content of the current BufferRope object as an ImmutableRope
	fun freeze: ImmutableRope
	do
		var buffer_rope = new BufferRope
		var new_rope = new ImmutableRope

		var iter = new DFSRopeLeafIterator(self)

		while iter.is_ok do
			buffer_rope.append(iter.item.value)
			iter.next
		end

		new_rope.parent_node = buffer_rope.parent_node

		if not is_dirty then new_rope.str_representation = self.str_representation

		return new_rope
	end

	# Unsafe method to convert self as an ImmutableRope
	#
	# To be used internally only
	private fun to_immutable: ImmutableRope
	do
		var immutable_self = new ImmutableRope
		immutable_self.parent_node = self.parent_node
		return immutable_self
	end

	############################################################################
	#                          Rope refined Methods                            #
	############################################################################

	redef fun subrope(index_from: Int, count: Int): BufferRope
	do
		return super.as(BufferRope)
	end

	redef fun *(repeats: Int): BufferRope
	do
		return super.as(BufferRope)
	end

	redef fun +(other: Rope): BufferRope
	do
		return super.as(BufferRope)
	end

	redef fun multi_concat(ropes: Rope...): BufferRope
	do
		return super.as(BufferRope)
	end

	# Refines to add a cache method, calculates only once for every modification
	# the string representation for self
	redef fun to_s
	do
		if self.str_representation == null or is_dirty then
			self.str_representation = flatten
			is_dirty = false
		end
		return self.str_representation.as(not null)
	end

end

# Rope that cannot be modified
class ImmutableRope
	super Rope

	init
	do
		super
	end

	redef init with_string(str)
	do
		super
	end

	############################################################################
	#                          Rope refined Methods                            #
	############################################################################

	redef fun subrope(index_from: Int, count: Int): ImmutableRope
	do
		return (super.as(BufferRope)).to_immutable
	end

	redef fun *(repeats: Int): ImmutableRope
	do
		return (super.as(BufferRope)).to_immutable
	end

	redef fun +(other: Rope): ImmutableRope
	do
		return (super.as(BufferRope)).to_immutable
	end

	redef fun multi_concat(ropes: Rope...): ImmutableRope
	do
		return (super.as(BufferRope)).to_immutable
	end

end

############################################
#            Rope view classes             #
############################################

class CharRopeView
	super SequenceRead[Char]

	# Targeted Rope for the view
	private var target: Rope

	init(tgt: Rope)
	do
		self.target = tgt
	end

	redef fun [](position)
	do
		var tuple = target.get_node_for_pos(position)
		return tuple.curr_node.value[tuple.corrected_pos]
	end

	redef fun first do return self[0]

	redef fun index_of(char)
	do
		var intern_iter = new RopeCharIterator(target)
		while intern_iter.is_ok do
			if intern_iter.item == char then return intern_iter.index
			intern_iter.next
		end
		return -1
	end

	redef fun iterator do
		return new RopeCharIterator(target)
	end

	redef fun last do return self[self.length-1]

	redef fun length do return target.length

	redef fun count(item)
	do
		var count = 0
		var iter = self.iterator

		for i in self do
			if i == item then count += 1
		end

		return count
	end

	redef fun has_only(item)
	do
		for i in self do
			if i != item then return false
		end
		return true
	end

	redef fun is_empty do return length == 0

	redef fun to_a do
		return to_s.to_a
	end

	redef fun to_s do
		return target.to_s
	end

	redef fun ==(other)
	do
		if not other isa SequenceRead[Char] then return false

		if self.length != other then return false

		var iter = other.iterator

		for i in self do
			if i != iter.item then return false
			iter.next
		end

		return true
	end

end

###########################################
#            Iterator classes             #
###########################################

# A tuple representing the state of a node for a tree parsing algorithm
private class TupleVisitNode

	init(tgt: ConcatNode)
	do
		self.node = tgt
	end

	private var node: ConcatNode

	private var left_visited = false
	private var right_visited = false

end

# Any kind of iterator parsing a Rope for LeafNodes
private abstract class RopeIterator
	super IndexedIterator[LeafNode]

	# Rope meant to be visited
	private var _target: Rope

	private fun target: Rope do return self._target

	# Position in target
	private var pos = 0

	init(tgt: Rope)
	do
		self._target = tgt
	end

	init with_index(tgt: Rope, index: Int)
	do
		self._target = tgt
	end

end

# Iterator returning the content of a rope one char at a time
class RopeCharIterator
	super IndexedIterator[Char]

	# The iterator used to visit the rope
	private var sub_str_iter: DFSRopeLeafIterator

	# The current position in the rope
	private var abs_pos = 0

	# The position in the current substring
	private var sub_pos: Int = 0

	# The substring contained in the current node visited by `sub_str_iter`
	private var curr_substring: nullable String

	init(tgt: Rope)
	do
		sub_str_iter = new DFSRopeLeafIterator(tgt)
		if sub_str_iter.is_ok then curr_substring = sub_str_iter.item.value
	end

	redef fun item do return curr_substring[sub_pos]

	redef fun is_ok
	do
		if sub_str_iter.is_ok then return true
		if not sub_str_iter.is_ok and curr_substring != null and sub_pos < curr_substring.length then return true
		return false
	end

	redef fun next
	do
		assert is_ok
		if sub_pos < curr_substring.length - 1 then
			sub_pos += 1
		else
			sub_str_iter.next
			if sub_str_iter.is_ok then
				curr_substring = sub_str_iter.item.value
				sub_pos = 0
			else
				sub_pos = curr_substring.length
			end
		end
		abs_pos += 1
	end

	redef fun index do return abs_pos

end

# Special kind of iterator
#
# Performs a Depth-First Search on RopeLeaf items
#
private class DFSRopeLeafIterator
	super RopeIterator

	# Stack of the visited nodes in the rope
	private var visit_stack = new List[TupleVisitNode]

	# The leaf node being visited by the iterator
	private var curr_leaf: nullable LeafNode

	init(tgt: Rope)
	do
		super

		var first_node = target.parent_node

		if first_node isa ConcatNode then
			visit_stack.push(new TupleVisitNode(first_node))
		else if first_node isa LeafNode then
			curr_leaf = first_node
			return
		end

		next_body
	end

	# Creates a new iterator on `tgt` starting at `index`
	redef init with_index(tgt: Rope, index: Int)
	do
		super

		var returned_tuple = target.get_node_for_pos(index)
		curr_leaf = returned_tuple.curr_node
		visit_stack = returned_tuple.visit_stack
		pos = index - returned_tuple.corrected_pos
	end

	redef fun is_ok do return curr_leaf != null

	redef fun next
	do
		assert is_ok
		pos += curr_leaf.value.length
		next_body
	end

	private fun next_body
	do
		var next_node: nullable RopeNode
		while not visit_stack.is_empty do
			var curr_concat_tuple = visit_stack.last
			if not curr_concat_tuple.left_visited then

				curr_concat_tuple.left_visited = true

				next_node = curr_concat_tuple.node.left_child

				if next_node == null then continue

				if next_node isa ConcatNode then
					visit_stack.push(new TupleVisitNode(next_node))
				else if next_node isa LeafNode then
					curr_leaf = next_node
					return
				end

			else if not curr_concat_tuple.right_visited then

				curr_concat_tuple.right_visited = true

				next_node = curr_concat_tuple.node.right_child

				if next_node == null then continue

				if next_node isa ConcatNode then
					visit_stack.push(new TupleVisitNode(next_node))
				else if next_node isa LeafNode then
					curr_leaf = next_node
					return
				end

			else
				visit_stack.pop
			end
		end
		self.curr_leaf = null
	end

	redef fun item
	do
		assert is_ok
		return curr_leaf.as(not null)
	end

end

###########################################
#              Node classes               #
###########################################

# A node for a Rope
private abstract class RopeNode

	private var _length = 0

	private var parent: nullable ConcatNode = null

	private var height = 0

	# The balance factor of a node, if it is a Leaf, it equals its length
	# Else, it will be equal to the difference between the height on the left and on the right
	private fun balance_factor: Int do return height end

	fun length: Int do return _length

	private fun length=(len: Int)
	do
		_length = len
	end
end

# Node that represents a concatenation between two nodes (of any RopeNode type)
private class ConcatNode
	super RopeNode

	private var _left_child: nullable RopeNode = null
	private var _right_child: nullable RopeNode = null

	private fun left_child: nullable RopeNode
	do
		if _left_child != null then
			return _left_child
		else
			return null
		end
	end

	private fun right_child: nullable RopeNode
	do
		if _right_child != null then
			return _right_child
		else
			return null
		end
	end

	private fun left_child=(new_node: nullable RopeNode)
	do
		self._left_child = new_node
		new_node.parent = self
		update_data
	end

	private fun right_child=(new_node: nullable RopeNode)
	do
		self._right_child = new_node
		new_node.parent = self
		update_data
	end

	# Updates the internal data of the current node
	#
	# Concretely, updates the length and the height of the node
	private fun update_data
	do
		self.length = 0
		self.height = 1
		if left_child != null then
			self.length += left_child.length
			if left_child.height + 1 > self.height then self.height = left_child.height + 1
		end
		if right_child != null then
			self.length += right_child.length
			if right_child.height + 1 > self.height then self.height = right_child.height + 1
		end
	end

	# Computes and returns the balance factor (used for AVL trees)
	#
	# Formula : left.height - right.height
	redef private fun balance_factor
	do
		var left_height = 0
		var right_height = 0
		if left_child != null then left_height = left_child.height
		if right_child != null then right_height = right_child.height
		return left_height - right_height
	end
end

# A leaf node contains a substring of some sort
private class LeafNode
	super RopeNode

	# Encapsulated string in the leaf node
	private var _value: String

	init(val: String)
	do
		self._value = val.to_s
		self.length = val.length
	end

	private fun value: String do return self._value

	private fun value= (val: String)
	do
		_value = val
	end
end

#####################################################
#            Foreign classes refinement             #
#####################################################

redef class String
	redef fun ==(other)
	do
		if other isa Rope then
			return other == self
		else
			return super
		end
	end
end

redef class Buffer
	redef fun ==(other)
	do
		if other isa Rope then
			return other == self
		else
			return super
		end
	end
end