-# 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: AbstractString) 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: String
- 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._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 AbstractString) 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 AbstractString 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
-
- 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
-