1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # This file is free software, which comes along with NIT. This software is
4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
5 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
6 # PARTICULAR PURPOSE. You can modify it if you want, provided this header
7 # is kept unaltered, and a notification of the changes is added.
8 # You are allowed to redistribute it and sell it, alone or as a part of
11 # Nit implementation of the Ropes (see Ropes : An Alternative to Strings,
12 # SOFTWARE - PRACTICE AND EXPERIENCE, VOL. 25(12), 1315 - 1330 (DECEMBER 1995)
13 # Hans. J Boehm, Russ Atkinson and Michael Plass)
15 # A rope is a kind of string but instead of being flat, it relies on a binary tree structure to store data.
21 # Structure, tuple containing a LeafNode and an Int
22 # Used for methods like [] or has/has_only
23 private class TupleLeafNodePos
24 private var curr_node
: LeafNode
25 private var corrected_pos
: Int
26 private var visit_stack
: List[TupleVisitNode]
29 # Abstract class, represents all the services offered by both mutable and immutable ropes
34 # Cached version of self as a flat String
35 private var str_representation
: nullable String = null
37 redef type OTHER: Rope
39 # The first node of the hierarchy
40 private var parent_node
: RopeNode
42 # Needed by the compiler to avoid producing an error with constructors in subclasses
44 self.parent_node
= new ConcatNode
47 # Initializes a new Rope with a text embedded in directly
48 init with_string
(str
: String) do
49 self.parent_node
= new ConcatNode
50 parent_node
.as(ConcatNode).right_child
= new LeafNode(str
)
51 parent_node
.as(ConcatNode).update_data
54 # Returns a view on the rope
55 fun chars
: SequenceRead[Char]
57 return new CharRopeView(self)
60 # Gets the total length of the Rope
63 return parent_node
.length
66 # Returns a flat version of self
69 if self.str_representation
== null then flatten
70 return str_representation
.as(not null)
73 # Stores a flat version of self in cache
74 private fun flatten
: String
76 var native_final_str
= calloc_string
(length
+ 1)
78 native_final_str
[length
] = '\0'
82 var iter
= new DFSRopeLeafIterator(self)
85 iter
.item
.value
.items
.copy_to
(native_final_str
, iter
.item
.value
.length
, 0, offset
)
86 offset
+= iter
.item
.value
.length
90 return native_final_str
.to_s_with_length
(length
)
93 # Gets a node containing the substring to seek the char at the require position
94 private fun get_node_for_pos
(position
: Int): TupleLeafNodePos
96 assert position
>= 0 and position
< self.length
98 var curr_node
: nullable RopeNode = parent_node
100 var visit_stack
= new List[TupleVisitNode]
102 var curr_visit_tuple
: TupleVisitNode
105 if curr_node
isa ConcatNode then
106 curr_visit_tuple
= new TupleVisitNode(curr_node
)
107 if curr_node
.left_child
!= null and position
< curr_node
.left_child
.length
then
108 curr_visit_tuple
.left_visited
= true
109 curr_node
= curr_node
.left_child
110 else if curr_node
.right_child
!= null then
111 curr_visit_tuple
.left_visited
= true
112 curr_visit_tuple
.right_visited
= true
113 if curr_node
.left_child
!= null then position
-= curr_node
.left_child
.length
114 curr_node
= curr_node
.right_child
119 visit_stack
.push
(curr_visit_tuple
)
120 else if curr_node
isa LeafNode then
121 return new TupleLeafNodePos(curr_node
, position
, visit_stack
)
126 # Concats two ropes and returns a new one
127 fun +(other
: Rope): Rope do
128 var new_rope
= new BufferRope
130 var first_iter
= new DFSRopeLeafIterator(self)
132 while first_iter
.is_ok
do
133 new_rope
.append
(first_iter
.item
.value
)
137 var second_iter
= new DFSRopeLeafIterator(other
)
139 while second_iter
.is_ok
do
140 new_rope
.append
(second_iter
.item
.value
)
147 # Returns a copy of several ropes concatenated
149 # Is equivalent to a chain of + operations
150 # Except this one is optimized for performance
151 fun multi_concat
(ropes
: Rope...): Rope
153 var new_rope
= new BufferRope
155 var self_iter
= self.iterator
156 while self_iter
.is_ok
do
157 new_rope
.append
(self_iter
.item
.value
)
162 var iter
= i
.iterator
164 new_rope
.append
(iter
.item
.value
)
172 # Appends the content of self multiple times in a new Rope object
173 fun *(repeats
: Int): Rope do
175 var new_rope
= new BufferRope
179 for i
in [1 .. repeats
] do new_rope
.append
(str
)
184 # Returns an iterator on self
186 # Unsafe modifications on a MutableRope
188 private fun iterator
: Iterator[LeafNode] do return new DFSRopeLeafIterator(self)
192 # var rope = (new BufferRope).append("abcd")
194 # assert rope.subrope(1, 2) == "bc"
195 # assert rope.subrope(-1, ) == "a"
196 # assert rope.subrope(1, 0) == ""
197 # assert rope.subrope(2, 5) == "cd"
199 # A `index_from` index < 0 will be replaced by 0.
200 # Unless a `count` value is > 0 at the same time.
201 # In this case, `index_from += count` and `count -= index_from`.
203 fun subrope
(index_from
: Int, count
: Int): Rope
207 if index_from
< 0 then
209 if count
< 0 then count
= 0
213 if count
- index_from
>= self.length
then count
= length
- index_from
215 var buffer
= new BufferRope
217 var iter
= new DFSRopeLeafIterator.with_index
(self, index_from
)
219 var curr_subrope_index
= index_from
- iter
.pos
222 if count
== 0 then break
223 if curr_subrope_index
> 0 then
224 if count
>= iter
.item
.value
.length
then
225 buffer
.append
(iter
.item
.value
.substring
(curr_subrope_index
, count
))
226 count
-= iter
.item
.value
.length
- curr_subrope_index
227 curr_subrope_index
= 0
229 buffer
.append
(iter
.item
.value
.substring
(curr_subrope_index
, count
))
233 if count
>= iter
.item
.value
.length
then
234 buffer
.append
(iter
.item
.value
)
235 count
-= iter
.item
.value
.length
237 buffer
.append
(iter
.item
.value
.substring
(0, count
))
248 # Returns an upper (capitalized) version of self
251 var new_rope
= new BufferRope
252 var iter
= new DFSRopeLeafIterator(self)
254 new_rope
.append
(iter
.item
.value
.to_upper
)
260 # Returns a lower (minuscule) version of self
263 var new_rope
= new BufferRope
264 var iter
= new DFSRopeLeafIterator(self)
266 new_rope
.append
(iter
.item
.value
.to_lower
)
272 ############################################################################
273 # Comparable Refined Methods #
274 ############################################################################
276 # Compares the current Rope to another object (either another rope or a String)
279 if other
== null or not (other
isa Rope or other
isa FlatText) then return false
280 var self_iter
= new RopeCharIterator(self)
281 if other
isa Rope then
282 if self.length
!= other
.length
then return false
283 var other_iterator
= new RopeCharIterator(other
)
284 while self_iter
.is_ok
do
285 if self_iter
.item
!= other_iterator
.item
then return false
289 else if other
isa FlatText then
291 if self.length
!= other
.length
then return false
292 while self_iter
.is_ok
do
293 if self_iter
.item
!= other
[pos
] then return false
301 # Checks if self is lesser than other
303 # Comparison done in lexicographical order
308 var other_iter
= other
.chars
.iterator
309 for i
in self.chars
do
310 if not other_iter
.is_ok
then return false
311 if i
< other_iter
.item
then return true
312 if i
> other_iter
.item
then return false
315 if other_iter
.is_ok
then return true
321 # Rope that can be modified
323 # /!\ Non Thread-safe /!\
328 var is_dirty
: Bool = false
335 init with_string
(str
)
340 ############################################################################
341 # Tree Balancing Methods #
342 ############################################################################
344 # Performs a right rotation on a node of the Rope
348 # Pivot Leaf3 => Leaf1 Root
350 # Leaf1 Leaf2 Leaf2 Leaf3
351 private fun rotate_right
(root
: ConcatNode)
353 assert root
.left_child
!= null
354 var pivot
= root
.left_child
.as(ConcatNode)
355 var root_new_left
= pivot
.right_child
356 var root_parent
= root
.parent
358 root
.left_child
= root_new_left
359 pivot
.right_child
= root
360 if root_parent
== null then
361 self.parent_node
= pivot
366 if root_parent
.left_child
== root
then
367 root_parent
.left_child
= pivot
369 root_parent
.right_child
= pivot
374 root_parent
.update_data
377 # Performs a left rotation on a node of the Rope
381 # Leaf1 Pivot => Root Leaf3
383 # Leaf2 Leaf3 Leaf1 Leaf2
384 private fun rotate_left
(root
: ConcatNode)
386 assert root
.right_child
!= null
387 var pivot
= root
.right_child
.as(ConcatNode)
388 var root_new_right
= pivot
.left_child
389 var root_parent
= root
.parent
391 root
.right_child
= root_new_right
392 pivot
.left_child
= root
393 if root_parent
== null then
394 self.parent_node
= pivot
399 if root_parent
.left_child
== root
then
400 root_parent
.left_child
= pivot
402 root_parent
.right_child
= pivot
407 root_parent
.update_data
410 # Shortcut method to balance a node and its parents
411 # based on the rules of the AVL Tree
412 private fun balance_from_node
(parent_node
: nullable ConcatNode)
414 while parent_node
!= null do
415 parent_node
.update_data
416 var node_balance
= parent_node
.balance_factor
417 if node_balance
< -1 or node_balance
> 1 then
418 balance_node
(parent_node
)
420 parent_node
= parent_node
.parent
424 # Performs rotations to balance a node according to AVL Tree rules
425 private fun balance_node
(node
: ConcatNode)
427 var balance_factor
= node
.balance_factor
428 if balance_factor
< -1 then
429 var right_balance
= node
.right_child
.balance_factor
430 if right_balance
< 0 then
433 rotate_right
(node
.right_child
.as(ConcatNode))
437 var left_balance
= node
.left_child
.balance_factor
438 if left_balance
> 0 then
441 rotate_left
(node
.left_child
.as(ConcatNode))
447 ############################################################################
448 # BufferRope exclusive Methods #
449 ############################################################################
451 # Appends a new Collection[Char] at the end of the current rope
452 fun append
(str
: String): BufferRope
454 var last_node
= parent_node
456 while last_node
isa ConcatNode and last_node
.right_child
!= null do
457 last_node
= last_node
.right_child
.as(not null)
460 if last_node
isa ConcatNode then
461 last_node
.right_child
= new LeafNode(str
.to_s
)
462 else if last_node
isa LeafNode then
463 var last_node_parent
= last_node
.parent
464 var new_concat
= new ConcatNode
465 last_node_parent
.right_child
= new_concat
466 new_concat
.left_child
= last_node
467 new_concat
.right_child
= new LeafNode(str
.to_s
)
468 last_node
= new_concat
470 print
"Fatal Error, please report to the developers for more insight."
474 balance_from_node
(last_node
)
481 # Variatic function to append several collections of Chars
482 fun append_multi
(strs
: String...): BufferRope
490 # Adds a new Collection[Char] at the beginning of the rope
491 fun prepend
(str
: String): BufferRope
493 var curr_node
= parent_node
495 while curr_node
isa ConcatNode and curr_node
.left_child
!= null do
496 curr_node
= curr_node
.left_child
.as(not null)
499 if curr_node
isa ConcatNode then
500 curr_node
.left_child
= new LeafNode(str
.to_s
)
501 else if curr_node
isa LeafNode then
502 var parent
= curr_node
.parent
503 var new_concat
= new ConcatNode
504 var new_leaf
= new LeafNode(str
.to_s
)
505 new_concat
.left_child
= new_leaf
506 new_concat
.right_child
= curr_node
507 parent
.left_child
= new_concat
508 curr_node
= new_concat
514 balance_from_node
(curr_node
)
521 # Variatic function to prepend several collections of Chars
522 fun prepend_multi
(strs
: String...): BufferRope
530 # Adds the content of `str` after self, does not create a new rope object
531 fun concat
(str
: Rope): Rope
533 var other_iter
= new DFSRopeLeafIterator(str
)
535 var modif_list
= new List[String]
537 while other_iter
.is_ok
do
538 modif_list
.push
(other_iter
.item
.value
)
542 while modif_list
.length
> 0 do
543 self.append
(modif_list
.shift
)
546 if not is_dirty
then is_dirty
= true
551 # Returns the content of the current BufferRope object as an ImmutableRope
552 fun freeze
: ImmutableRope
554 var buffer_rope
= new BufferRope
555 var new_rope
= new ImmutableRope
557 var iter
= new DFSRopeLeafIterator(self)
560 buffer_rope
.append
(iter
.item
.value
)
564 new_rope
.parent_node
= buffer_rope
.parent_node
566 if not is_dirty
then new_rope
.str_representation
= self.str_representation
571 # Unsafe method to convert self as an ImmutableRope
573 # To be used internally only
574 private fun to_immutable
: ImmutableRope
576 var immutable_self
= new ImmutableRope
577 immutable_self
.parent_node
= self.parent_node
578 return immutable_self
581 ############################################################################
582 # Rope refined Methods #
583 ############################################################################
585 redef fun subrope
(index_from
: Int, count
: Int): BufferRope
587 return super.as(BufferRope)
590 redef fun *(repeats
: Int): BufferRope
592 return super.as(BufferRope)
595 redef fun +(other
: Rope): BufferRope
597 return super.as(BufferRope)
600 redef fun multi_concat
(ropes
: Rope...): BufferRope
602 return super.as(BufferRope)
605 # Refines to add a cache method, calculates only once for every modification
606 # the string representation for self
609 if self.str_representation
== null or is_dirty
then
610 self.str_representation
= flatten
613 return self.str_representation
.as(not null)
618 # Rope that cannot be modified
627 init with_string
(str
)
632 ############################################################################
633 # Rope refined Methods #
634 ############################################################################
636 redef fun subrope
(index_from
: Int, count
: Int): ImmutableRope
638 return (super.as(BufferRope)).to_immutable
641 redef fun *(repeats
: Int): ImmutableRope
643 return (super.as(BufferRope)).to_immutable
646 redef fun +(other
: Rope): ImmutableRope
648 return (super.as(BufferRope)).to_immutable
651 redef fun multi_concat
(ropes
: Rope...): ImmutableRope
653 return (super.as(BufferRope)).to_immutable
658 ############################################
659 # Rope view classes #
660 ############################################
663 super SequenceRead[Char]
665 # Targeted Rope for the view
666 private var target
: Rope
673 redef fun [](position
)
675 var tuple
= target
.get_node_for_pos
(position
)
676 return tuple
.curr_node
.value
[tuple
.corrected_pos
]
679 redef fun first
do return self[0]
681 redef fun index_of
(char
)
683 var intern_iter
= new RopeCharIterator(target
)
684 while intern_iter
.is_ok
do
685 if intern_iter
.item
== char
then return intern_iter
.index
691 redef fun iterator
do
692 return new RopeCharIterator(target
)
695 redef fun last
do return self[self.length-1
]
697 redef fun length
do return target
.length
699 redef fun count
(item
)
702 var iter
= self.iterator
705 if i
== item
then count
+= 1
711 redef fun has_only
(item
)
714 if i
!= item
then return false
719 redef fun is_empty
do return length
== 0
731 if not other
isa SequenceRead[Char] then return false
733 if self.length
!= other
then return false
735 var iter
= other
.iterator
738 if i
!= iter
.item
then return false
747 ###########################################
749 ###########################################
751 # A tuple representing the state of a node for a tree parsing algorithm
752 private class TupleVisitNode
754 init(tgt
: ConcatNode)
759 private var node
: ConcatNode
761 private var left_visited
= false
762 private var right_visited
= false
766 # Any kind of iterator parsing a Rope for LeafNodes
767 private abstract class RopeIterator
768 super IndexedIterator[LeafNode]
770 # Rope meant to be visited
771 private var _target
: Rope
773 private fun target
: Rope do return self._target
783 init with_index
(tgt
: Rope, index
: Int)
790 # Iterator returning the content of a rope one char at a time
791 class RopeCharIterator
792 super IndexedIterator[Char]
794 # The iterator used to visit the rope
795 private var sub_str_iter
: DFSRopeLeafIterator
797 # The current position in the rope
798 private var abs_pos
= 0
800 # The position in the current substring
801 private var sub_pos
: Int = 0
803 # The substring contained in the current node visited by `sub_str_iter`
804 private var curr_substring
: nullable String
808 sub_str_iter
= new DFSRopeLeafIterator(tgt
)
809 if sub_str_iter
.is_ok
then curr_substring
= sub_str_iter
.item
.value
812 redef fun item
do return curr_substring
[sub_pos
]
816 if sub_str_iter
.is_ok
then return true
817 if not sub_str_iter
.is_ok
and curr_substring
!= null and sub_pos
< curr_substring
.length
then return true
824 if sub_pos
< curr_substring
.length
- 1 then
828 if sub_str_iter
.is_ok
then
829 curr_substring
= sub_str_iter
.item
.value
832 sub_pos
= curr_substring
.length
838 redef fun index
do return abs_pos
842 # Special kind of iterator
844 # Performs a Depth-First Search on RopeLeaf items
846 private class DFSRopeLeafIterator
849 # Stack of the visited nodes in the rope
850 private var visit_stack
= new List[TupleVisitNode]
852 # The leaf node being visited by the iterator
853 private var curr_leaf
: nullable LeafNode
859 var first_node
= target
.parent_node
861 if first_node
isa ConcatNode then
862 visit_stack
.push
(new TupleVisitNode(first_node
))
863 else if first_node
isa LeafNode then
864 curr_leaf
= first_node
871 # Creates a new iterator on `tgt` starting at `index`
872 init with_index
(tgt
: Rope, index
: Int)
876 var returned_tuple
= target
.get_node_for_pos
(index
)
877 curr_leaf
= returned_tuple
.curr_node
878 visit_stack
= returned_tuple
.visit_stack
879 pos
= index
- returned_tuple
.corrected_pos
882 redef fun is_ok
do return curr_leaf
!= null
887 pos
+= curr_leaf
.value
.length
891 private fun next_body
893 var next_node
: nullable RopeNode
894 while not visit_stack
.is_empty
do
895 var curr_concat_tuple
= visit_stack
.last
896 if not curr_concat_tuple
.left_visited
then
898 curr_concat_tuple
.left_visited
= true
900 next_node
= curr_concat_tuple
.node
.left_child
902 if next_node
== null then continue
904 if next_node
isa ConcatNode then
905 visit_stack
.push
(new TupleVisitNode(next_node
))
906 else if next_node
isa LeafNode then
907 curr_leaf
= next_node
911 else if not curr_concat_tuple
.right_visited
then
913 curr_concat_tuple
.right_visited
= true
915 next_node
= curr_concat_tuple
.node
.right_child
917 if next_node
== null then continue
919 if next_node
isa ConcatNode then
920 visit_stack
.push
(new TupleVisitNode(next_node
))
921 else if next_node
isa LeafNode then
922 curr_leaf
= next_node
930 self.curr_leaf
= null
936 return curr_leaf
.as(not null)
941 ###########################################
943 ###########################################
946 private abstract class RopeNode
948 private var _length
= 0
950 private var parent
: nullable ConcatNode = null
952 private var height
= 0
954 # The balance factor of a node, if it is a Leaf, it equals its length
955 # Else, it will be equal to the difference between the height on the left and on the right
956 private fun balance_factor
: Int do return height
end
958 fun length
: Int do return _length
960 private fun length
=(len
: Int)
966 # Node that represents a concatenation between two nodes (of any RopeNode type)
967 private class ConcatNode
970 private var _left_child
: nullable RopeNode
971 private var _right_child
: nullable RopeNode
973 private fun left_child
: nullable RopeNode
975 if _left_child
!= null then
982 private fun right_child
: nullable RopeNode
984 if _right_child
!= null then
991 private fun left_child
=(new_node
: nullable RopeNode)
993 self._left_child
= new_node
994 new_node
.parent
= self
998 private fun right_child
=(new_node
: nullable RopeNode)
1000 self._right_child
= new_node
1001 new_node
.parent
= self
1005 # Updates the internal data of the current node
1007 # Concretely, updates the length and the height of the node
1008 private fun update_data
1012 if left_child
!= null then
1013 self.length
+= left_child
.length
1014 if left_child
.height
+ 1 > self.height
then self.height
= left_child
.height
+ 1
1016 if right_child
!= null then
1017 self.length
+= right_child
.length
1018 if right_child
.height
+ 1 > self.height
then self.height
= right_child
.height
+ 1
1022 # Computes and returns the balance factor (used for AVL trees)
1024 # Formula : left.height - right.height
1025 redef private fun balance_factor
1028 var right_height
= 0
1029 if left_child
!= null then left_height
= left_child
.height
1030 if right_child
!= null then right_height
= right_child
.height
1031 return left_height
- right_height
1035 # A leaf node contains a substring of some sort
1036 private class LeafNode
1039 # Encapsulated string in the leaf node
1040 private var _value
: String
1044 self._value
= val
.to_s
1045 self.length
= val
.length
1048 private fun value
: String do return self._value
1050 private fun value
= (val
: String)
1056 #####################################################
1057 # Foreign classes refinement #
1058 #####################################################
1063 if other
isa Rope then
1064 return other
== self
1074 if other
isa Rope then
1075 return other
== self