976def94d707093095ae974a966e51c7e1aaa5ae
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
55 # Right child of the node
56 var right
: nullable RopeNode
58 init(l
: nullable RopeNode, r
: nullable RopeNode)
62 if l
!= null then length
+= l
.length
63 if r
!= null then length
+= r
.length
68 # Leaf of a Rope, contains a FlatString
69 private abstract class Leaf
72 # Encapsulated FlatString in the leaf node
77 private class StringLeaf
80 init(val
: FlatString) do
87 # Basic structure, binary tree with a root node.
89 # Also shared services by subsequent implementations.
93 # Root node, entry point of a Rope.
94 private var root
: RopeNode
96 # Cached version of self as a flat String
97 private var str_representation
: nullable NativeString = null
102 # Creates a new Rope with `s` as root
103 init from
(s
: String) do
104 if s
isa RopeString then root
= s
.root
else root
= new StringLeaf(s
.as(FlatString))
107 private init from_root
(r
: RopeNode)
112 redef fun length
do return root
.length
114 # Iterator on the nodes of the rope, in forward postfix order
115 private fun postfix
(from
: Int): Postfix do return new Postfix.from
(self, from
)
117 # Iterator on the leaves of the rope, forward order
118 private fun leaves
(from
: Int): LeavesIterator do return new LeavesIterator(self, from
)
120 # Iterator on the substrings from 0, in forward order
121 redef fun substrings
do return new SubstringsIterator(self, 0)
123 # Iterator on the substrings, starting at position `from`, in forward order
124 fun substrings_from
(from
: Int): IndexedIterator[Text] do return new SubstringsIterator(self, from
)
126 # Iterator on the nodes of the rope, in backwards postfix order
127 private fun reverse_postfix
(from
: Int): ReversePostfix do return new ReversePostfix.from
(self, from
)
129 # Iterator on the leaves of the rope, backwards order
130 private fun reverse_leaves
(from
: Int): ReverseLeavesIterator do return new ReverseLeavesIterator(self,from
)
132 # Iterator on the substrings, in reverse order
133 fun reverse_substrings
: IndexedIterator[Text] do return new ReverseSubstringsIterator(self, length-1
)
135 # Iterator on the substrings, in reverse order, starting iteration at position `from`
136 fun reverse_substrings_from
(from
: Int): IndexedIterator[Text] do return new ReverseSubstringsIterator(self, from
)
140 for i
in substrings
do
147 if str_representation
!= null then return str_representation
.as(not null)
149 var native_final_str
= calloc_string
(length
+ 1)
151 native_final_str
[length
] = '\0'
153 if self.length
== 0 then
154 str_representation
= native_final_str
155 return native_final_str
160 for i
in substrings
do
162 if str
isa FlatString then str
.items
.copy_to
(native_final_str
, str
.length
, str
.index_from
, offset
)
166 str_representation
= native_final_str
168 return native_final_str
171 # Path to the Leaf for `position`
172 private fun node_at
(position
: Int): Path
174 assert position
>= 0 and position
< length
175 return get_node_from
(root
.as(not null), 0, position
, new List[PathElement])
178 # Builds the path to Leaf at position `seek_pos`
179 private fun get_node_from
(node
: RopeNode, curr_pos
: Int, seek_pos
: Int, stack
: List[PathElement]): Path
182 if node
isa Leaf then return new Path(node
, seek_pos
- curr_pos
, stack
)
183 node
= node
.as(Concat)
185 if node
.left
!= null then
186 var next_pos
= curr_pos
+ node
.left
.length
187 stack
.add
(new PathElement(node
))
188 if next_pos
> seek_pos
then
189 stack
.last
.left
= true
190 return get_node_from
(node
.left
.as(not null), curr_pos
, seek_pos
, stack
)
192 stack
.last
.right
= true
193 return get_node_from
(node
.right
.as(not null), next_pos
, seek_pos
, stack
)
195 var vis
= new PathElement(node
)
198 return get_node_from
(node
.right
.as(not null), curr_pos
, seek_pos
, stack
)
204 if not o
isa Text then return false
205 if o
.length
!= self.length
then return false
206 var oit
= o
.chars
.iterator
207 for i
in self.chars
.iterator
do
208 if i
!= oit
.item
then return false
215 # Rope that cannot be modified
220 redef fun to_s
do return self
222 redef fun empty
do return once
new RopeString.from
("")
224 redef var chars
: SequenceRead[Char] = new RopeStringChars(self)
228 var ret
= empty
.as(RopeString)
229 for i
in substrings
do
230 ret
= ret
.prepend
(i
.reversed
.to_s
).as(RopeString)
238 for i
in substrings
do
247 for i
in substrings
do
253 redef fun +(o
) do return insert_at
(o
.to_s
, length
)
257 var ret
= new RopeString.from
("")
259 ret
= (ret
+ self).as(RopeString)
264 # Inserts a String `str` at position `pos`
265 redef fun insert_at
(str
, pos
)
267 if str
.length
== 0 then return self
268 if self.length
== 0 then return new RopeString.from
(str
)
270 assert pos
>= 0 and pos
<= length
272 if pos
== length
then return append
(str
).as(RopeString)
274 var path
= node_at
(pos
)
276 var last_concat
: Concat
278 if path
.offset
== 0 then
279 if str
isa FlatString then
280 last_concat
= new Concat(new StringLeaf(str
), path
.leaf
)
282 last_concat
= new Concat(str
.as(RopeString).root
, path
.leaf
)
284 else if path
.offset
== path
.leaf
.length
then
285 if str
isa FlatString then
286 last_concat
= new Concat(path
.leaf
, new StringLeaf(str
))
288 last_concat
= new Concat(path
.leaf
, str
.as(RopeString).root
)
291 var s
= path
.leaf
.str
292 var l_half
= s
.substring
(0, s
.length
- path
.offset
)
293 var r_half
= s
.substring_from
(s
.length
- path
.offset
)
295 var ll
= new StringLeaf(l_half
.as(FlatString))
296 if str
isa FlatString then
297 cct
= new Concat(ll
, new StringLeaf(str
))
299 cct
= new Concat(ll
, str
.as(RopeString).root
)
301 last_concat
= new Concat(cct
, new StringLeaf(r_half
.as(FlatString)))
304 for i
in path
.stack
.reverse_iterator
do
306 last_concat
= new Concat(last_concat
, i
.node
.right
)
308 last_concat
= new Concat(i
.node
.left
, last_concat
)
312 return new RopeString.from_root
(last_concat
)
315 # Adds `s` at the beginning of self
316 redef fun prepend
(s
) do return insert_at
(s
, 0)
318 # Adds `s` at the end of self
321 if self.is_empty
then return s
322 return new RopeString.from_root
(append_to_path
(root
,s
))
325 # Builds a new path from root to the rightmost node with s appended
326 private fun append_to_path
(node
: RopeNode, s
: String): RopeNode
329 if node
isa Leaf then
330 if s
isa FlatString then
331 cct
= new Concat(node
, new StringLeaf(s
))
333 cct
= new Concat(node
, s
.as(RopeString).root
)
336 var n
= node
.as(Concat)
338 var lft
= n
.left
.as(not null)
339 if right
== null then
340 if s
isa FlatString then
341 cct
= new Concat(lft
, new StringLeaf(s
))
343 cct
= new Concat(lft
, s
.as(RopeString).root
)
346 cct
= new Concat(lft
, append_to_path
(right
, s
))
354 # var rope = new RopeString.from("abcd")
355 # assert rope.substring(1, 2) == "bc"
356 # assert rope.substring(-1, 2) == "a"
357 # assert rope.substring(1, 0) == ""
358 # assert rope.substring(2, 5) == "cd"
360 redef fun substring
(pos
, len
)
367 if pos
+ len
> length
then len
= length
- pos
369 if len
<= 0 then return new RopeString.from
("")
371 var path
= node_at
(pos
)
374 var offset
= path
.offset
376 if path
.leaf
.str
.length
- offset
> len
then lf
= new StringLeaf(lf
.str
.substring
(offset
,len
).as(FlatString)) else lf
= new StringLeaf(lf
.str
.substring_from
(offset
).as(FlatString))
378 var nod
: RopeNode = lf
380 for i
in path
.stack
.reverse_iterator
do
381 if i
.right
then continue
382 nod
= new Concat(nod
, i
.node
.right
)
385 var ret
= new RopeString
388 path
= ret
.node_at
(len-1
)
391 nod
= new StringLeaf(path
.leaf
.str
.substring
(0, offset
+1).as(FlatString))
393 for i
in path
.stack
.reverse_iterator
do
394 if i
.left
then continue
395 nod
= new Concat(i
.node
.left
, nod
)
404 redef class FlatString
406 redef fun append
(s
) do return (new RopeString.from
(self)) + s
408 redef fun prepend
(s
) do return (new RopeString.from
(self)).prepend
(s
)
410 redef fun insert_at
(s
, pos
)
412 if pos
== 0 then return prepend
(s
)
413 if pos
== length
then return append
(s
)
415 var l
= substring
(0,pos
)
416 var r
= substring_from
(pos
)
417 var ret
: String = new RopeString.from
(l
)
424 private class RopeStringChars
425 super SequenceRead[Char]
431 assert pos
< tgt
.length
432 var path
= tgt
.node_at
(pos
)
433 return path
.leaf
.str
.chars
[path
.offset
]
436 redef fun iterator
do return iterator_from
(0)
438 redef fun iterator_from
(pos
) do return new RopeCharIterator(tgt
, pos
)
440 redef fun reverse_iterator
do return reverse_iterator_from
(tgt
.length-1
)
442 redef fun reverse_iterator_from
(pos
) do return new ReverseRopeCharIterator(tgt
, pos
)
445 # Used to iterate on a Rope
446 private class IteratorElement
457 # The node being visited
459 # If the node has a left child, was it visited ?
461 # If the node has a right child, was it visited ?
463 # Was the current node visited ?
467 # Simple Postfix iterator on the nodes of a Rope
468 private class Postfix
469 super IndexedIterator[RopeNode]
471 # Target Rope to iterate on
474 # Current position in Rope
478 var stack
= new List[IteratorElement]
480 init from
(tgt
: Rope, pos
: Int)
484 if pos
< 0 or pos
>= tgt
.length
then return
485 var path
= tgt
.node_at
(pos
)
486 self.pos
-= path
.offset
487 for i
in path
.stack
do
488 var item
= new IteratorElement(i
.node
)
490 if i
.right
then item
.right
= true
493 var item
= new IteratorElement(path
.leaf
)
501 return stack
.last
.node
504 redef fun is_ok
do return not stack
.is_empty
506 redef fun index
do return pos
509 if stack
.is_empty
then return
510 if pos
> target
.length-1
then
516 if lst
.node
isa Leaf then
517 pos
+= lst
.node
.length
526 if nod
isa Concat and nod
.left
!= null then
527 stack
.push
(new IteratorElement(nod
.left
.as(not null)))
532 if not lst
.right
then
535 if nod
isa Concat and nod
.right
!= null then
536 stack
.push
(new IteratorElement(nod
.right
.as(not null)))
545 # Iterates on the leaves (substrings) of the Rope
547 super IndexedIterator[Leaf]
549 private var nodes
: Postfix
551 init(tgt
: Rope, pos
: Int)
553 nodes
= tgt
.postfix
(pos
)
556 redef fun is_ok
do return nodes
.is_ok
561 return nodes
.item
.as(Leaf)
564 redef fun index
do return nodes
.index
570 if nodes
.is_ok
and nodes
.item
isa Leaf then break
575 # Uses the leaves and calculates a new substring on each iteration
576 class SubstringsIterator
577 super IndexedIterator[Text]
579 private var nodes
: IndexedIterator[Leaf]
581 # Current position in Rope
584 # Current substring, computed from the current Leaf and indexes
587 init(tgt
: Rope, pos
: Int)
589 nodes
= tgt
.leaves
(pos
)
591 if pos
< 0 or pos
>= tgt
.length
then return
595 # Compute the bounds of the current substring and makes the substring
596 private fun make_substring
598 substring
= nodes
.item
.str
600 var length
= substring
.length
601 if nodes
.index
< pos
then
602 min
= pos
- nodes
.index
604 substring
= substring
.substring
(min
, length
)
607 redef fun is_ok
do return nodes
.is_ok
615 redef fun index
do return pos
619 pos
+= substring
.length
621 if nodes
.is_ok
then make_substring
626 class RopeCharIterator
627 super IndexedIterator[Char]
629 var substrings
: IndexedIterator[Text]
635 var substr_iter
: IndexedIterator[Char]
637 init(tgt
: Rope, from
: Int)
639 substrings
= tgt
.substrings_from
(from
)
641 if not substrings
.is_ok
then
646 substr_iter
= substrings
.item
.chars
.iterator
649 redef fun item
do return substr_iter
.item
651 redef fun is_ok
do return pos
<= max
653 redef fun index
do return pos
658 if substr_iter
.is_ok
then
661 if not substr_iter
.is_ok
then
663 if substrings
.is_ok
then
664 substr_iter
= substrings
.item
.chars
.iterator
670 private class ReversePostfix
671 super IndexedIterator[RopeNode]
679 var stack
= new List[IteratorElement]
681 init from
(tgt
: Rope, pos
: Int)
685 if pos
< 0 or pos
>= tgt
.length
then return
686 var path
= tgt
.node_at
(pos
)
687 self.pos
-= path
.offset
688 for i
in path
.stack
do
689 var elemt
= new IteratorElement(i
.node
)
696 stack
.push
(new IteratorElement(path
.leaf
))
697 stack
.last
.done
= true
702 return stack
.last
.node
705 redef fun is_ok
do return not stack
.is_empty
707 redef fun index
do return pos
711 if stack
.is_empty
then return
722 if not lst
.right
then
723 var nod
= lst
.node
.as(Concat)
727 stack
.push
(new IteratorElement(rgt
))
733 var nod
= lst
.node
.as(Concat)
737 stack
.push
(new IteratorElement(lft
))
742 if lst
.node
isa Leaf then pos
-= lst
.node
.length
747 private class ReverseLeavesIterator
748 super IndexedIterator[Leaf]
750 var nodes
: ReversePostfix
752 init(tgt
: Rope, from
: Int)
754 nodes
= tgt
.reverse_postfix
(from
)
757 redef fun is_ok
do return nodes
.is_ok
761 return nodes
.item
.as(Leaf)
767 if nodes
.is_ok
then if nodes
.item
isa Leaf then break
771 redef fun index
do return nodes
.index
775 private class ReverseSubstringsIterator
776 super IndexedIterator[Text]
778 var leaves
: ReverseLeavesIterator
784 init(tgt
: Rope, from
: Int)
786 leaves
= tgt
.reverse_leaves
(from
)
788 if not leaves
.is_ok
then return
789 str
= leaves
.item
.str
795 if pos
>= (leaves
.index
+ str
.length
- 1) then return
796 str
= str
.substring
(0, (pos
- leaves
.index
+ 1))
799 redef fun is_ok
do return leaves
.is_ok
806 redef fun index
do return pos
811 if not leaves
.is_ok
then return
812 str
= leaves
.item
.str
817 private class ReverseRopeCharIterator
818 super IndexedIterator[Char]
820 var substrs
: IndexedIterator[Text]
824 var subiter
: IndexedIterator[Char]
826 init(tgt
: Rope, from
: Int)
828 substrs
= tgt
.reverse_substrings_from
(from
)
829 if not substrs
.is_ok
then
833 subiter
= substrs
.item
.chars
.reverse_iterator
837 redef fun is_ok
do return pos
>= 0
844 redef fun index
do return pos
848 if subiter
.is_ok
then subiter
.next
849 if not subiter
.is_ok
then
850 if substrs
.is_ok
then substrs
.next
851 if substrs
.is_ok
then subiter
= substrs
.item
.chars
.reverse_iterator