ebc33771107e1911d88a8c3eeb769c6b9a1a358c
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
48 # Transforms the current node to a Leaf.
49 # This might be costly to invoke since this produces a FlatString concatenation.
50 # Can be used internally to limit the growth of the Rope when working with small leaves.
51 fun to_leaf
: Leaf is abstract
54 # Node that represents a concatenation between two nodes (of any RopeNode type)
58 # Left child of the node
59 var left
: nullable RopeNode
60 # Right child of the node
61 var right
: nullable RopeNode
63 init(l
: nullable RopeNode, r
: nullable RopeNode)
67 if l
!= null then length
+= l
.length
68 if r
!= null then length
+= r
.length
74 if right
== null then return new StringLeaf("".as(FlatString))
77 if right
== null then return left
.as(not null).to_leaf
78 return new StringLeaf((left
.to_leaf
.str
.as(FlatString) + right
.to_leaf
.str
.as(FlatString)).as(FlatString))
82 # Leaf of a Rope, contains a FlatString
83 private abstract class Leaf
86 # Encapsulated FlatString in the leaf node
91 private class StringLeaf
94 init(val
: FlatString) do
99 redef fun to_leaf
do return self
102 # Used as a cache when using indexed access to a substring in the Rope
103 private class LeafCache
110 # Basic structure, binary tree with a root node.
112 # Also shared services by subsequent implementations.
116 # Root node, entry point of a Rope.
117 private var root
: RopeNode
119 # Cached version of self as a flat String
120 private var str_representation
: nullable NativeString = null
122 private var leaf_cache
: nullable LeafCache = null
127 # Creates a new Rope with `s` as root
128 init from
(s
: String) do
129 if s
isa RopeString then root
= s
.root
else root
= new StringLeaf(s
.as(FlatString))
132 private init from_root
(r
: RopeNode)
137 redef fun length
do return root
.length
139 # Iterator on the nodes of the rope, in forward postfix order
140 private fun postfix
(from
: Int): Postfix do return new Postfix.from
(self, from
)
142 # Iterator on the leaves of the rope, forward order
143 private fun leaves
(from
: Int): LeavesIterator do return new LeavesIterator(self, from
)
145 # Iterator on the substrings from 0, in forward order
146 redef fun substrings
do return new SubstringsIterator(self, 0)
148 # Iterator on the substrings, starting at position `from`, in forward order
149 fun substrings_from
(from
: Int): IndexedIterator[Text] do return new SubstringsIterator(self, from
)
151 # Iterator on the nodes of the rope, in backwards postfix order
152 private fun reverse_postfix
(from
: Int): ReversePostfix do return new ReversePostfix.from
(self, from
)
154 # Iterator on the leaves of the rope, backwards order
155 private fun reverse_leaves
(from
: Int): ReverseLeavesIterator do return new ReverseLeavesIterator(self,from
)
157 # Iterator on the substrings, in reverse order
158 fun reverse_substrings
: IndexedIterator[Text] do return new ReverseSubstringsIterator(self, length-1
)
160 # Iterator on the substrings, in reverse order, starting iteration at position `from`
161 fun reverse_substrings_from
(from
: Int): IndexedIterator[Text] do return new ReverseSubstringsIterator(self, from
)
165 for i
in substrings
do
172 if str_representation
!= null then return str_representation
.as(not null)
174 var native_final_str
= calloc_string
(length
+ 1)
176 native_final_str
[length
] = '\0'
178 if self.length
== 0 then
179 str_representation
= native_final_str
180 return native_final_str
185 for i
in substrings
do
187 if str
isa FlatString then str
.items
.copy_to
(native_final_str
, str
.length
, str
.index_from
, offset
)
191 str_representation
= native_final_str
193 return native_final_str
196 # Path to the Leaf for `position`
197 private fun node_at
(position
: Int): Path
199 assert position
>= 0 and position
<= length
200 if position
== length
then
201 var st
= new List[PathElement]
202 stack_to_end
(root
,st
)
203 if not st
.is_empty
then
205 var lf
= lst
.node
.right
207 return new Path(lf
.as(Leaf), lf
.length
, st
)
210 return new Path(lf
.as(Leaf), lf
.length
, st
)
213 return new Path(root
.as(Leaf), length
, st
)
216 return get_node_from
(root
, 0, position
, new List[PathElement])
219 # Special case for when the required pos is length
220 private fun stack_to_end
(nod
: RopeNode, st
: List[PathElement])
222 if nod
isa Leaf then return
223 var n
= nod
.as(Concat)
225 var ele
= new PathElement(n
)
234 # Builds the path to Leaf at position `seek_pos`
235 private fun get_node_from
(node
: RopeNode, curr_pos
: Int, seek_pos
: Int, stack
: List[PathElement]): Path
238 if node
isa Leaf then
239 self.leaf_cache
= new LeafCache(node
, curr_pos
)
240 return new Path(node
, seek_pos
- curr_pos
, stack
)
242 node
= node
.as(Concat)
244 if node
.left
!= null then
245 var next_pos
= curr_pos
+ node
.left
.length
246 stack
.add
(new PathElement(node
))
247 if next_pos
> seek_pos
then
248 stack
.last
.left
= true
249 return get_node_from
(node
.left
.as(not null), curr_pos
, seek_pos
, stack
)
251 stack
.last
.right
= true
252 return get_node_from
(node
.right
.as(not null), next_pos
, seek_pos
, stack
)
254 var vis
= new PathElement(node
)
257 return get_node_from
(node
.right
.as(not null), curr_pos
, seek_pos
, stack
)
263 if not o
isa Text then return false
264 if o
.length
!= self.length
then return false
265 var oit
= o
.chars
.iterator
266 for i
in self.chars
.iterator
do
267 if i
!= oit
.item
then return false
274 # Rope that cannot be modified
279 redef fun to_s
do return self
281 redef fun empty
do return once
new RopeString.from
("")
283 redef var chars
: SequenceRead[Char] = new RopeStringChars(self)
288 for i
in substrings
do
289 ret
= i
.as(String).reversed
+ ret
297 for i
in substrings
do
298 ret
+= i
.as(String).to_upper
306 for i
in substrings
do
307 ret
+= i
.as(String).to_lower
313 if self.length
== 0 then return o
.to_s
314 if o
.length
== 0 then return self
316 if str
isa FlatString then
317 return new RopeString.from_root
(new Concat(root
, new StringLeaf(str
)))
318 else if str
isa RopeString then
319 return new RopeString.from_root
(new Concat(root
, str
.root
))
327 var ret
= new RopeString.from
("")
329 ret
= (ret
+ self).as(RopeString)
334 # Inserts a String `str` at position `pos`
335 redef fun insert_at
(str
, pos
)
337 if str
.length
== 0 then return self
338 if self.length
== 0 then return new RopeString.from
(str
)
340 assert pos
>= 0 and pos
<= length
342 var path
= node_at
(pos
)
344 var last_concat
: Concat
346 if path
.offset
== 0 then
347 if str
isa FlatString then
348 last_concat
= new Concat(new StringLeaf(str
), path
.leaf
)
350 last_concat
= new Concat(str
.as(RopeString).root
, path
.leaf
)
352 else if path
.offset
== path
.leaf
.length
then
353 if str
isa FlatString then
354 last_concat
= new Concat(path
.leaf
, new StringLeaf(str
))
356 last_concat
= new Concat(path
.leaf
, str
.as(RopeString).root
)
359 var s
= path
.leaf
.str
360 var l_half
= s
.substring
(0, s
.length
- path
.offset
)
361 var r_half
= s
.substring_from
(s
.length
- path
.offset
)
363 var ll
= new StringLeaf(l_half
.as(FlatString))
364 if str
isa FlatString then
365 cct
= new Concat(ll
, new StringLeaf(str
))
367 cct
= new Concat(ll
, str
.as(RopeString).root
)
369 last_concat
= new Concat(cct
, new StringLeaf(r_half
.as(FlatString)))
372 for i
in path
.stack
.reverse_iterator
do
374 last_concat
= new Concat(last_concat
, i
.node
.right
)
376 last_concat
= new Concat(i
.node
.left
, last_concat
)
380 return new RopeString.from_root
(last_concat
)
385 # var rope = new RopeString.from("abcd")
386 # assert rope.substring(1, 2) == "bc"
387 # assert rope.substring(-1, 2) == "a"
388 # assert rope.substring(1, 0) == ""
389 # assert rope.substring(2, 5) == "cd"
391 redef fun substring
(pos
, len
)
398 if pos
+ len
> length
then len
= length
- pos
400 if len
<= 0 then return new RopeString.from
("")
402 var path
= node_at
(pos
)
405 var offset
= path
.offset
407 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))
409 var nod
: RopeNode = lf
411 for i
in path
.stack
.reverse_iterator
do
412 if i
.right
then continue
413 nod
= new Concat(nod
, i
.node
.right
)
416 var ret
= new RopeString
419 path
= ret
.node_at
(len-1
)
422 nod
= new StringLeaf(path
.leaf
.str
.substring
(0, offset
+1).as(FlatString))
424 for i
in path
.stack
.reverse_iterator
do
425 if i
.left
then continue
426 nod
= new Concat(i
.node
.left
, nod
)
435 redef class FlatString
437 redef fun insert_at
(s
, pos
)
441 var r
= new RopeString.from
(s
)
444 if pos
== length
then
445 var r
= new RopeString.from
(self)
449 var l
= substring
(0,pos
)
450 var r
= substring_from
(pos
)
451 var ret
: String = new RopeString.from
(l
)
458 private class RopeStringChars
459 super SequenceRead[Char]
465 assert pos
< tgt
.length
466 if tgt
.leaf_cache
!= null and pos
>= tgt
.leaf_cache
.pos
and (tgt
.leaf_cache
.pos
+ tgt
.leaf_cache
.leaf
.length
) > pos
then return tgt
.leaf_cache
.leaf
.str
.chars
[pos
- tgt
.leaf_cache
.pos
]
467 var path
= tgt
.node_at
(pos
)
468 return path
.leaf
.str
.chars
[path
.offset
]
471 redef fun iterator
do return iterator_from
(0)
473 redef fun iterator_from
(pos
) do return new RopeCharIterator(tgt
, pos
)
475 redef fun reverse_iterator
do return reverse_iterator_from
(tgt
.length-1
)
477 redef fun reverse_iterator_from
(pos
) do return new ReverseRopeCharIterator(tgt
, pos
)
480 # Used to iterate on a Rope
481 private class IteratorElement
492 # The node being visited
494 # If the node has a left child, was it visited ?
496 # If the node has a right child, was it visited ?
498 # Was the current node visited ?
502 # Simple Postfix iterator on the nodes of a Rope
503 private class Postfix
504 super IndexedIterator[RopeNode]
506 # Target Rope to iterate on
509 # Current position in Rope
513 var stack
= new List[IteratorElement]
515 init from
(tgt
: Rope, pos
: Int)
519 if pos
< 0 or pos
>= tgt
.length
then return
520 var path
= tgt
.node_at
(pos
)
521 self.pos
-= path
.offset
522 for i
in path
.stack
do
523 var item
= new IteratorElement(i
.node
)
525 if i
.right
then item
.right
= true
528 var item
= new IteratorElement(path
.leaf
)
536 return stack
.last
.node
539 redef fun is_ok
do return not stack
.is_empty
541 redef fun index
do return pos
544 if stack
.is_empty
then return
545 if pos
> target
.length-1
then
551 if lst
.node
isa Leaf then
552 pos
+= lst
.node
.length
561 if nod
isa Concat and nod
.left
!= null then
562 stack
.push
(new IteratorElement(nod
.left
.as(not null)))
567 if not lst
.right
then
570 if nod
isa Concat and nod
.right
!= null then
571 stack
.push
(new IteratorElement(nod
.right
.as(not null)))
580 # Iterates on the leaves (substrings) of the Rope
582 super IndexedIterator[Leaf]
584 private var nodes
: Postfix
586 init(tgt
: Rope, pos
: Int)
588 nodes
= tgt
.postfix
(pos
)
591 redef fun is_ok
do return nodes
.is_ok
596 return nodes
.item
.as(Leaf)
599 redef fun index
do return nodes
.index
605 if nodes
.is_ok
and nodes
.item
isa Leaf then break
610 # Uses the leaves and calculates a new substring on each iteration
611 class SubstringsIterator
612 super IndexedIterator[Text]
614 private var nodes
: IndexedIterator[Leaf]
616 # Current position in Rope
619 # Current substring, computed from the current Leaf and indexes
622 init(tgt
: Rope, pos
: Int)
624 nodes
= tgt
.leaves
(pos
)
626 if pos
< 0 or pos
>= tgt
.length
then return
630 # Compute the bounds of the current substring and makes the substring
631 private fun make_substring
633 substring
= nodes
.item
.str
635 var length
= substring
.length
636 if nodes
.index
< pos
then
637 min
= pos
- nodes
.index
639 substring
= substring
.substring
(min
, length
)
642 redef fun is_ok
do return nodes
.is_ok
650 redef fun index
do return pos
654 pos
+= substring
.length
656 if nodes
.is_ok
then make_substring
661 class RopeCharIterator
662 super IndexedIterator[Char]
664 var substrings
: IndexedIterator[Text]
670 var substr_iter
: IndexedIterator[Char]
672 init(tgt
: Rope, from
: Int)
674 substrings
= tgt
.substrings_from
(from
)
676 if not substrings
.is_ok
then
681 substr_iter
= substrings
.item
.chars
.iterator
684 redef fun item
do return substr_iter
.item
686 redef fun is_ok
do return pos
<= max
688 redef fun index
do return pos
693 if substr_iter
.is_ok
then
696 if not substr_iter
.is_ok
then
698 if substrings
.is_ok
then
699 substr_iter
= substrings
.item
.chars
.iterator
705 private class ReversePostfix
706 super IndexedIterator[RopeNode]
714 var stack
= new List[IteratorElement]
716 init from
(tgt
: Rope, pos
: Int)
720 if pos
< 0 or pos
>= tgt
.length
then return
721 var path
= tgt
.node_at
(pos
)
722 self.pos
-= path
.offset
723 for i
in path
.stack
do
724 var elemt
= new IteratorElement(i
.node
)
731 stack
.push
(new IteratorElement(path
.leaf
))
732 stack
.last
.done
= true
737 return stack
.last
.node
740 redef fun is_ok
do return not stack
.is_empty
742 redef fun index
do return pos
746 if stack
.is_empty
then return
757 if not lst
.right
then
758 var nod
= lst
.node
.as(Concat)
762 stack
.push
(new IteratorElement(rgt
))
768 var nod
= lst
.node
.as(Concat)
772 stack
.push
(new IteratorElement(lft
))
777 if lst
.node
isa Leaf then pos
-= lst
.node
.length
782 private class ReverseLeavesIterator
783 super IndexedIterator[Leaf]
785 var nodes
: ReversePostfix
787 init(tgt
: Rope, from
: Int)
789 nodes
= tgt
.reverse_postfix
(from
)
792 redef fun is_ok
do return nodes
.is_ok
796 return nodes
.item
.as(Leaf)
802 if nodes
.is_ok
then if nodes
.item
isa Leaf then break
806 redef fun index
do return nodes
.index
810 private class ReverseSubstringsIterator
811 super IndexedIterator[Text]
813 var leaves
: ReverseLeavesIterator
819 init(tgt
: Rope, from
: Int)
821 leaves
= tgt
.reverse_leaves
(from
)
823 if not leaves
.is_ok
then return
824 str
= leaves
.item
.str
830 if pos
>= (leaves
.index
+ str
.length
- 1) then return
831 str
= str
.substring
(0, (pos
- leaves
.index
+ 1))
834 redef fun is_ok
do return leaves
.is_ok
841 redef fun index
do return pos
846 if not leaves
.is_ok
then return
847 str
= leaves
.item
.str
852 private class ReverseRopeCharIterator
853 super IndexedIterator[Char]
855 var substrs
: IndexedIterator[Text]
859 var subiter
: IndexedIterator[Char]
861 init(tgt
: Rope, from
: Int)
863 substrs
= tgt
.reverse_substrings_from
(from
)
864 if not substrs
.is_ok
then
868 subiter
= substrs
.item
.chars
.reverse_iterator
872 redef fun is_ok
do return pos
>= 0
879 redef fun index
do return pos
883 if subiter
.is_ok
then subiter
.next
884 if not subiter
.is_ok
then
885 if substrs
.is_ok
then substrs
.next
886 if substrs
.is_ok
then subiter
= substrs
.item
.chars
.reverse_iterator