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
: AbstractString) 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 new String.with_native
(native_final_str
, 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 AbstractString) 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 AbstractString 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
: Collection[Char]): BufferRope
454 if str
isa AbstractString then
455 var last_node
= parent_node
457 while last_node
isa ConcatNode and last_node
.right_child
!= null do
458 last_node
= last_node
.right_child
.as(not null)
461 if last_node
isa ConcatNode then
462 last_node
.right_child
= new LeafNode(str
.to_s
)
463 else if last_node
isa LeafNode then
464 var last_node_parent
= last_node
.parent
465 var new_concat
= new ConcatNode
466 last_node_parent
.right_child
= new_concat
467 new_concat
.left_child
= last_node
468 new_concat
.right_child
= new LeafNode(str
.to_s
)
469 last_node
= new_concat
471 print
"Fatal Error, please report to the developers for more insight."
475 balance_from_node
(last_node
)
477 var buf
= new Buffer.with_capacity
(str
.length
)
484 if not is_dirty
then is_dirty
= true
489 # Variatic function to append several collections of Chars
490 fun append_multi
(strs
: Collection[Char]...): BufferRope
498 # Adds a new Collection[Char] at the beginning of the rope
499 fun prepend
(str
: Collection[Char]): BufferRope
501 if str
isa AbstractString then
502 var curr_node
= parent_node
504 while curr_node
isa ConcatNode and curr_node
.left_child
!= null do
505 curr_node
= curr_node
.left_child
.as(not null)
508 if curr_node
isa ConcatNode then
509 curr_node
.left_child
= new LeafNode(str
.to_s
)
510 else if curr_node
isa LeafNode then
511 var parent
= curr_node
.parent
512 var new_concat
= new ConcatNode
513 var new_leaf
= new LeafNode(str
.to_s
)
514 new_concat
.left_child
= new_leaf
515 new_concat
.right_child
= curr_node
516 parent
.left_child
= new_concat
517 curr_node
= new_concat
523 balance_from_node
(curr_node
)
525 var buf
= new Buffer.with_capacity
(str
.length
)
532 if not is_dirty
then is_dirty
= true
537 # Variatic function to prepend several collections of Chars
538 fun prepend_multi
(strs
: Collection[Char]...): BufferRope
546 # Adds the content of `str` after self, does not create a new rope object
547 fun concat
(str
: Rope): Rope
549 var other_iter
= new DFSRopeLeafIterator(str
)
551 var modif_list
= new List[String]
553 while other_iter
.is_ok
do
554 modif_list
.push
(other_iter
.item
.value
)
558 while modif_list
.length
> 0 do
559 self.append
(modif_list
.shift
)
562 if not is_dirty
then is_dirty
= true
567 # Returns the content of the current BufferRope object as an ImmutableRope
568 fun freeze
: ImmutableRope
570 var buffer_rope
= new BufferRope
571 var new_rope
= new ImmutableRope
573 var iter
= new DFSRopeLeafIterator(self)
576 buffer_rope
.append
(iter
.item
.value
)
580 new_rope
.parent_node
= buffer_rope
.parent_node
582 if not is_dirty
then new_rope
.str_representation
= self.str_representation
587 # Unsafe method to convert self as an ImmutableRope
589 # To be used internally only
590 private fun to_immutable
: ImmutableRope
592 var immutable_self
= new ImmutableRope
593 immutable_self
.parent_node
= self.parent_node
594 return immutable_self
597 ############################################################################
598 # Rope refined Methods #
599 ############################################################################
601 redef fun subrope
(index_from
: Int, count
: Int): BufferRope
603 return super.as(BufferRope)
606 redef fun *(repeats
: Int): BufferRope
608 return super.as(BufferRope)
611 redef fun +(other
: Rope): BufferRope
613 return super.as(BufferRope)
616 redef fun multi_concat
(ropes
: Rope...): BufferRope
618 return super.as(BufferRope)
621 # Refines to add a cache method, calculates only once for every modification
622 # the string representation for self
625 if self.str_representation
== null or is_dirty
then
626 self.str_representation
= flatten
629 return self.str_representation
.as(not null)
634 # Rope that cannot be modified
643 init with_string
(str
)
648 ############################################################################
649 # Rope refined Methods #
650 ############################################################################
652 redef fun subrope
(index_from
: Int, count
: Int): ImmutableRope
654 return (super.as(BufferRope)).to_immutable
657 redef fun *(repeats
: Int): ImmutableRope
659 return (super.as(BufferRope)).to_immutable
662 redef fun +(other
: Rope): ImmutableRope
664 return (super.as(BufferRope)).to_immutable
667 redef fun multi_concat
(ropes
: Rope...): ImmutableRope
669 return (super.as(BufferRope)).to_immutable
674 ############################################
675 # Rope view classes #
676 ############################################
679 super SequenceRead[Char]
681 # Targeted Rope for the view
682 private var target
: Rope
689 redef fun [](position
)
691 var tuple
= target
.get_node_for_pos
(position
)
692 return tuple
.curr_node
.value
[tuple
.corrected_pos
]
695 redef fun first
do return self[0]
697 redef fun index_of
(char
)
699 var intern_iter
= new RopeCharIterator(target
)
700 while intern_iter
.is_ok
do
701 if intern_iter
.item
== char
then return intern_iter
.index
707 redef fun iterator
do
708 return new RopeCharIterator(target
)
711 redef fun last
do return self[self.length-1
]
713 redef fun length
do return target
.length
715 redef fun count
(item
)
718 var iter
= self.iterator
721 if i
== item
then count
+= 1
727 redef fun has_only
(item
)
730 if i
!= item
then return false
735 redef fun is_empty
do return length
== 0
747 if not other
isa SequenceRead[Char] then return false
749 if self.length
!= other
then return false
751 var iter
= other
.iterator
754 if i
!= iter
.item
then return false
763 ###########################################
765 ###########################################
767 # A tuple representing the state of a node for a tree parsing algorithm
768 private class TupleVisitNode
770 init(tgt
: ConcatNode)
775 private var node
: ConcatNode
777 private var left_visited
= false
778 private var right_visited
= false
782 # Any kind of iterator parsing a Rope for LeafNodes
783 private abstract class RopeIterator
784 super IndexedIterator[LeafNode]
786 # Rope meant to be visited
787 private var _target
: Rope
789 private fun target
: Rope do return self._target
799 init with_index
(tgt
: Rope, index
: Int)
806 # Iterator returning the content of a rope one char at a time
807 class RopeCharIterator
808 super IndexedIterator[Char]
810 # The iterator used to visit the rope
811 private var sub_str_iter
: DFSRopeLeafIterator
813 # The current position in the rope
814 private var abs_pos
= 0
816 # The position in the current substring
817 private var sub_pos
: Int = 0
819 # The substring contained in the current node visited by `sub_str_iter`
820 private var curr_substring
: nullable String
824 sub_str_iter
= new DFSRopeLeafIterator(tgt
)
825 if sub_str_iter
.is_ok
then curr_substring
= sub_str_iter
.item
.value
828 redef fun item
do return curr_substring
[sub_pos
]
832 if sub_str_iter
.is_ok
then return true
833 if not sub_str_iter
.is_ok
and curr_substring
!= null and sub_pos
< curr_substring
.length
then return true
840 if sub_pos
< curr_substring
.length
- 1 then
844 if sub_str_iter
.is_ok
then
845 curr_substring
= sub_str_iter
.item
.value
848 sub_pos
= curr_substring
.length
854 redef fun index
do return abs_pos
858 # Special kind of iterator
860 # Performs a Depth-First Search on RopeLeaf items
862 private class DFSRopeLeafIterator
865 # Stack of the visited nodes in the rope
866 private var visit_stack
= new List[TupleVisitNode]
868 # The leaf node being visited by the iterator
869 private var curr_leaf
: nullable LeafNode
875 var first_node
= target
.parent_node
877 if first_node
isa ConcatNode then
878 visit_stack
.push
(new TupleVisitNode(first_node
))
879 else if first_node
isa LeafNode then
880 curr_leaf
= first_node
887 # Creates a new iterator on `tgt` starting at `index`
888 init with_index
(tgt
: Rope, index
: Int)
892 var returned_tuple
= target
.get_node_for_pos
(index
)
893 curr_leaf
= returned_tuple
.curr_node
894 visit_stack
= returned_tuple
.visit_stack
895 pos
= index
- returned_tuple
.corrected_pos
898 redef fun is_ok
do return curr_leaf
!= null
903 pos
+= curr_leaf
.value
.length
907 private fun next_body
909 var next_node
: nullable RopeNode
910 while not visit_stack
.is_empty
do
911 var curr_concat_tuple
= visit_stack
.last
912 if not curr_concat_tuple
.left_visited
then
914 curr_concat_tuple
.left_visited
= true
916 next_node
= curr_concat_tuple
.node
.left_child
918 if next_node
== null then continue
920 if next_node
isa ConcatNode then
921 visit_stack
.push
(new TupleVisitNode(next_node
))
922 else if next_node
isa LeafNode then
923 curr_leaf
= next_node
927 else if not curr_concat_tuple
.right_visited
then
929 curr_concat_tuple
.right_visited
= true
931 next_node
= curr_concat_tuple
.node
.right_child
933 if next_node
== null then continue
935 if next_node
isa ConcatNode then
936 visit_stack
.push
(new TupleVisitNode(next_node
))
937 else if next_node
isa LeafNode then
938 curr_leaf
= next_node
946 self.curr_leaf
= null
952 return curr_leaf
.as(not null)
957 ###########################################
959 ###########################################
962 private abstract class RopeNode
964 private var _length
= 0
966 private var parent
: nullable ConcatNode = null
968 private var height
= 0
970 # The balance factor of a node, if it is a Leaf, it equals its length
971 # Else, it will be equal to the difference between the height on the left and on the right
972 private fun balance_factor
: Int do return height
end
974 fun length
: Int do return _length
976 private fun length
=(len
: Int)
982 # Node that represents a concatenation between two nodes (of any RopeNode type)
983 private class ConcatNode
986 private var _left_child
: nullable RopeNode
987 private var _right_child
: nullable RopeNode
989 private fun left_child
: nullable RopeNode
991 if _left_child
!= null then
998 private fun right_child
: nullable RopeNode
1000 if _right_child
!= null then
1007 private fun left_child
=(new_node
: nullable RopeNode)
1009 self._left_child
= new_node
1010 new_node
.parent
= self
1014 private fun right_child
=(new_node
: nullable RopeNode)
1016 self._right_child
= new_node
1017 new_node
.parent
= self
1021 # Updates the internal data of the current node
1023 # Concretely, updates the length and the height of the node
1024 private fun update_data
1028 if left_child
!= null then
1029 self.length
+= left_child
.length
1030 if left_child
.height
+ 1 > self.height
then self.height
= left_child
.height
+ 1
1032 if right_child
!= null then
1033 self.length
+= right_child
.length
1034 if right_child
.height
+ 1 > self.height
then self.height
= right_child
.height
+ 1
1038 # Computes and returns the balance factor (used for AVL trees)
1040 # Formula : left.height - right.height
1041 redef private fun balance_factor
1044 var right_height
= 0
1045 if left_child
!= null then left_height
= left_child
.height
1046 if right_child
!= null then right_height
= right_child
.height
1047 return left_height
- right_height
1051 # A leaf node contains a substring of some sort
1052 private class LeafNode
1055 # Encapsulated string in the leaf node
1056 private var _value
: String
1058 init(val
: AbstractString)
1060 self._value
= val
.to_s
1061 self.length
= val
.length
1064 private fun value
: String do return self._value
1066 private fun value
= (val
: String)
1072 #####################################################
1073 # Foreign classes refinement #
1074 #####################################################
1079 if other
isa Rope then
1080 return other
== self
1090 if other
isa Rope then
1091 return other
== self