b1aad2e2079588de865785bf9407c0f70dfcb3d3
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.
20 # Used when searching for a particular node
21 # Returns the path to the node from the root of the rope
22 # Also, the node and the offset for seeked position in the rope
28 # Stack of the nodes traversed, and the path used
29 var stack
: List[PathElement]
32 # An element for a Path, has the concat node and whether or not
33 # left or right child was visited.
34 private class PathElement
37 # Was the left child visited ?
39 # Was the right child visited ?
44 private abstract class RopeNode
49 # Node that represents a concatenation between two nodes (of any RopeNode type)
53 # Left child of the node
54 var _left
: nullable RopeNode = null
55 # Right child of the node
56 var _right
: nullable RopeNode = null
58 fun left
: nullable RopeNode do return _left
59 fun right
: nullable RopeNode do return _right
61 fun left
=(l
: RopeNode)
65 if _right
!= null then length
+= _right
.length
68 fun right
=(r
: RopeNode)
72 if _left
!= null then length
+= _left
.length
76 # Leaf of a Rope, contains a FlatString
80 # Encapsulated FlatString in the leaf node
83 init(val
: FlatString) do
90 # Basic structure, binary tree with a root node.
92 # Also shared services by subsequent implementations.
96 # Root node, entry point of a Rope.
97 private var root
: RopeNode
99 # Cached version of self as a flat String
100 private var str_representation
: nullable NativeString = null
105 # Creates a new Rope with `s` as root
106 init from
(s
: String) do
107 if s
isa RopeString then root
= s
.root
else root
= new Leaf(s
.as(FlatString))
110 private init from_root
(r
: RopeNode)
115 redef fun length
do return root
.length
117 # Iterator on the nodes of the rope, in forward postfix order
118 private fun postfix
(from
: Int): Postfix do return new Postfix.from
(self, from
)
120 # Iterator on the leaves of the rope, forward order
121 private fun leaves
(from
: Int): LeavesIterator do return new LeavesIterator(self, from
)
123 # Iterator on the substrings from 0, in forward order
124 fun substrings
: IndexedIterator[Text] do return new SubstringsIterator(self, 0)
126 # Iterator on the substrings, starting at position `from`, in forward order
127 fun substrings_from
(from
: Int): IndexedIterator[Text] do return new SubstringsIterator(self, from
)
129 # Iterator on the nodes of the rope, in backwards postfix order
130 private fun reverse_postfix
(from
: Int): ReversePostfix do return new ReversePostfix.from
(self, from
)
132 # Iterator on the leaves of the rope, backwards order
133 private fun reverse_leaves
(from
: Int): ReverseLeavesIterator do return new ReverseLeavesIterator(self,from
)
135 # Iterator on the substrings, in reverse order
136 fun reverse_substrings
: IndexedIterator[Text] do return new ReverseSubstringsIterator(self, length-1
)
138 # Iterator on the substrings, in reverse order, starting iteration at position `from`
139 fun reverse_substrings_from
(from
: Int): IndexedIterator[Text] do return new ReverseSubstringsIterator(self, from
)
143 for i
in substrings
do
150 if str_representation
!= null then return str_representation
.as(not null)
152 var native_final_str
= calloc_string
(length
+ 1)
154 native_final_str
[length
] = '\0'
156 if self.length
== 0 then
157 str_representation
= native_final_str
158 return native_final_str
163 for i
in substrings
do
165 if str
isa FlatString then str
.items
.copy_to
(native_final_str
, str
.length
, str
.index_from
, offset
)
169 str_representation
= native_final_str
171 return native_final_str
174 # Path to the Leaf for `position`
175 private fun node_at
(position
: Int): Path
177 assert position
>= 0 and position
< length
178 return get_node_from
(root
.as(not null), 0, position
, new List[PathElement])
181 # Builds the path to Leaf at position `seek_pos`
182 private fun get_node_from
(node
: RopeNode, curr_pos
: Int, seek_pos
: Int, stack
: List[PathElement]): Path
185 if node
isa Leaf then return new Path(node
, seek_pos
- curr_pos
, stack
)
186 node
= node
.as(Concat)
188 if node
.left
!= null then
189 var next_pos
= curr_pos
+ node
.left
.length
190 stack
.add
(new PathElement(node
))
191 if next_pos
> seek_pos
then
192 stack
.last
.left
= true
193 return get_node_from
(node
.left
.as(not null), curr_pos
, seek_pos
, stack
)
195 stack
.last
.right
= true
196 return get_node_from
(node
.right
.as(not null), next_pos
, seek_pos
, stack
)
198 var vis
= new PathElement(node
)
201 return get_node_from
(node
.right
.as(not null), curr_pos
, seek_pos
, stack
)
207 if not o
isa Text then return false
208 if o
.length
!= self.length
then return false
209 var oit
= o
.chars
.iterator
210 for i
in self.chars
.iterator
do
211 if i
!= oit
.item
then return false
218 # Rope that cannot be modified
223 redef fun to_s
do return self
225 redef fun empty
do return once
new RopeString.from
("")
229 var ret
= empty
.as(RopeString)
230 for i
in substrings
do
231 ret
= ret
.prepend
(i
.reversed
.to_s
).as(RopeString)
239 for i
in substrings
do
248 for i
in substrings
do
254 redef fun +(o
) do return insert_at
(o
.to_s
, length
)
258 var ret
= new RopeString.from
("")
260 ret
= (ret
+ self).as(RopeString)
265 # Inserts a String `str` at position `pos`
266 fun insert_at
(str
: String, pos
: Int): RopeString
268 if str
.length
== 0 then return self
269 if self.length
== 0 then return new RopeString.from
(str
)
271 assert pos
>= 0 and pos
<= length
273 if pos
== length
then return append
(str
).as(RopeString)
275 var path
= node_at
(pos
)
277 var last_concat
= new Concat
279 if path
.offset
== 0 then
280 last_concat
.right
= path
.leaf
281 if str
isa FlatString then last_concat
.left
= new Leaf(str
) else last_concat
.left
= str
.as(RopeString).root
282 else if path
.offset
== path
.leaf
.length
then
283 if str
isa FlatString then last_concat
.right
= new Leaf(str
) else last_concat
.right
= str
.as(RopeString).root
284 last_concat
.left
= path
.leaf
286 var s
= path
.leaf
.str
287 var l_half
= s
.substring
(0, s
.length
- path
.offset
)
288 var r_half
= s
.substring_from
(s
.length
- path
.offset
)
290 cct
.right
= new Leaf(r_half
)
291 last_concat
.left
= new Leaf(l_half
)
292 if str
isa FlatString then last_concat
.right
= new Leaf(str
) else last_concat
.right
= str
.as(RopeString).root
293 cct
.left
= last_concat
297 for i
in path
.stack
.reverse_iterator
do
300 nod
.right
= i
.node
.right
.as(not null)
301 nod
.left
= last_concat
303 nod
.left
= i
.node
.left
.as(not null)
304 nod
.right
= last_concat
309 return new RopeString.from_root
(last_concat
)
312 # Adds `s` at the beginning of self
313 fun prepend
(s
: String): String do return insert_at
(s
, 0)
315 # Adds `s` at the end of self
316 fun append
(s
: String): String
318 if self.is_empty
then return s
319 return new RopeString.from_root
(append_to_path
(root
,s
))
322 # Builds a new path from root to the rightmost node with s appended
323 private fun append_to_path
(node
: RopeNode, s
: String): RopeNode
326 if node
isa Leaf then
328 if s
isa FlatString then cct
.right
= new Leaf(s
) else cct
.right
= s
.as(RopeString).root
329 else if node
isa Concat then
330 var right
= node
.right
331 if node
.left
!= null then cct
.left
= node
.left
.as(not null)
332 if right
== null then
333 if s
isa FlatString then cct
.right
= new Leaf(s
) else cct
.right
= s
.as(RopeString).root
335 cct
.right
= append_to_path
(right
, s
)
343 # var rope = new RopeString.from("abcd")
344 # assert rope.substring(1, 2) == "bc"
345 # assert rope.substring(-1, 2) == "a"
346 # assert rope.substring(1, 0) == ""
347 # assert rope.substring(2, 5) == "cd"
349 redef fun substring
(pos
, len
)
356 if pos
+ len
> length
then len
= length
- pos
358 if len
<= 0 then return new RopeString.from
("")
360 var path
= node_at
(pos
)
363 var offset
= path
.offset
365 if path
.leaf
.str
.length
- offset
> len
then lf
= new Leaf(lf
.str
.substring
(offset
,len
)) else lf
= new Leaf(lf
.str
.substring_from
(offset
))
367 var nod
: RopeNode = lf
369 for i
in path
.stack
.reverse_iterator
do
370 if i
.right
then continue
374 if r
!= null then tmp
.right
= r
378 var ret
= new RopeString
381 path
= ret
.node_at
(len-1
)
384 nod
= new Leaf(path
.leaf
.str
.substring
(0, offset
+1))
386 for i
in path
.stack
.reverse_iterator
do
387 if i
.left
then continue
391 if l
!= null then tmp
.left
= l
401 # Used to iterate on a Rope
402 private class IteratorElement
413 # The node being visited
415 # If the node has a left child, was it visited ?
417 # If the node has a right child, was it visited ?
419 # Was the current node visited ?
423 # Simple Postfix iterator on the nodes of a Rope
424 private class Postfix
425 super IndexedIterator[RopeNode]
427 # Target Rope to iterate on
430 # Current position in Rope
434 var stack
= new List[IteratorElement]
436 init from
(tgt
: Rope, pos
: Int)
440 if pos
< 0 or pos
>= tgt
.length
then return
441 var path
= tgt
.node_at
(pos
)
442 self.pos
-= path
.offset
443 for i
in path
.stack
do
444 var item
= new IteratorElement(i
.node
)
446 if i
.right
then item
.right
= true
449 var item
= new IteratorElement(path
.leaf
)
457 return stack
.last
.node
460 redef fun is_ok
do return not stack
.is_empty
462 redef fun index
do return pos
465 if stack
.is_empty
then return
466 if pos
> target
.length-1
then
472 if lst
.node
isa Leaf then
473 pos
+= lst
.node
.length
482 if nod
isa Concat and nod
.left
!= null then
483 stack
.push
(new IteratorElement(nod
.left
.as(not null)))
488 if not lst
.right
then
491 if nod
isa Concat and nod
.right
!= null then
492 stack
.push
(new IteratorElement(nod
.right
.as(not null)))
501 # Iterates on the leaves (substrings) of the Rope
503 super IndexedIterator[Leaf]
505 private var nodes
: Postfix
507 init(tgt
: Rope, pos
: Int)
509 nodes
= tgt
.postfix
(pos
)
512 redef fun is_ok
do return nodes
.is_ok
517 return nodes
.item
.as(Leaf)
520 redef fun index
do return nodes
.index
526 if nodes
.is_ok
and nodes
.item
isa Leaf then break
531 # Uses the leaves and calculates a new substring on each iteration
532 class SubstringsIterator
533 super IndexedIterator[Text]
535 private var nodes
: IndexedIterator[Leaf]
537 # Current position in Rope
540 # Current substring, computed from the current Leaf and indexes
543 init(tgt
: Rope, pos
: Int)
545 nodes
= tgt
.leaves
(pos
)
547 if pos
< 0 or pos
>= tgt
.length
then return
551 # Compute the bounds of the current substring and makes the substring
552 private fun make_substring
554 substring
= nodes
.item
.str
556 var length
= substring
.length
557 if nodes
.index
< pos
then
558 min
= pos
- nodes
.index
560 substring
= substring
.substring
(min
, length
)
563 redef fun is_ok
do return nodes
.is_ok
571 redef fun index
do return pos
575 pos
+= substring
.length
577 if nodes
.is_ok
then make_substring
582 class RopeCharIterator
583 super IndexedIterator[Char]
585 var substrings
: IndexedIterator[Text]
591 var substr_iter
: IndexedIterator[Char]
593 init(tgt
: Rope, from
: Int)
595 substrings
= tgt
.substrings_from
(from
)
597 if not substrings
.is_ok
then
602 substr_iter
= substrings
.item
.chars
.iterator
605 redef fun item
do return substr_iter
.item
607 redef fun is_ok
do return pos
<= max
609 redef fun index
do return pos
614 if substr_iter
.is_ok
then
617 if not substr_iter
.is_ok
then
619 if substrings
.is_ok
then
620 substr_iter
= substrings
.item
.chars
.iterator
626 private class ReversePostfix
627 super IndexedIterator[RopeNode]
635 var stack
= new List[IteratorElement]
637 init from
(tgt
: Rope, pos
: Int)
641 if pos
< 0 or pos
>= tgt
.length
then return
642 var path
= tgt
.node_at
(pos
)
643 self.pos
-= path
.offset
644 for i
in path
.stack
do
645 var elemt
= new IteratorElement(i
.node
)
652 stack
.push
(new IteratorElement(path
.leaf
))
653 stack
.last
.done
= true
658 return stack
.last
.node
661 redef fun is_ok
do return not stack
.is_empty
663 redef fun index
do return pos
667 if stack
.is_empty
then return
678 if not lst
.right
then
679 var nod
= lst
.node
.as(Concat)
683 stack
.push
(new IteratorElement(rgt
))
689 var nod
= lst
.node
.as(Concat)
693 stack
.push
(new IteratorElement(lft
))
698 if lst
.node
isa Leaf then pos
-= lst
.node
.length
703 private class ReverseLeavesIterator
704 super IndexedIterator[Leaf]
706 var nodes
: ReversePostfix
708 init(tgt
: Rope, from
: Int)
710 nodes
= tgt
.reverse_postfix
(from
)
713 redef fun is_ok
do return nodes
.is_ok
717 return nodes
.item
.as(Leaf)
723 if nodes
.is_ok
then if nodes
.item
isa Leaf then break
727 redef fun index
do return nodes
.index
731 private class ReverseSubstringsIterator
732 super IndexedIterator[Text]
734 var leaves
: ReverseLeavesIterator
740 init(tgt
: Rope, from
: Int)
742 leaves
= tgt
.reverse_leaves
(from
)
744 if not leaves
.is_ok
then return
745 str
= leaves
.item
.str
751 if pos
>= (leaves
.index
+ str
.length
- 1) then return
752 str
= str
.substring
(0, (pos
- leaves
.index
+ 1))
755 redef fun is_ok
do return leaves
.is_ok
762 redef fun index
do return pos
767 if not leaves
.is_ok
then return
768 str
= leaves
.item
.str
773 private class ReverseRopeCharIterator
774 super IndexedIterator[Char]
776 var substrs
: IndexedIterator[Text]
780 var subiter
: IndexedIterator[Char]
782 init(tgt
: Rope, from
: Int)
784 substrs
= tgt
.reverse_substrings_from
(from
)
785 if not substrs
.is_ok
then
789 subiter
= substrs
.item
.chars
.reverse_iterator
793 redef fun is_ok
do return pos
>= 0
800 redef fun index
do return pos
804 if subiter
.is_ok
then subiter
.next
805 if not subiter
.is_ok
then
806 if substrs
.is_ok
then substrs
.next
807 if substrs
.is_ok
then subiter
= substrs
.item
.chars
.reverse_iterator