1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Tree-based representation of a String.
17 # Ropes are a data structure introduced in a 1995 paper from
18 # Hans J. Boehm, Russ Atkinson and Michael Plass.
22 # > Ropes: an Alternative to Strings,
23 # > *Software - Practice and Experience*,
24 # > Vol. 25(12), 1315-1330 (December 1995).
26 # The implementation developed here provides an automatic change
27 # of data structure depending on the length of the leaves.
29 # The length from which a `Rope` is built from a `flat` string
30 # if defined at top-level (see `maxlen`) and can be redefined by clients
31 # depending on their needs (e.g. if you need to bench the speed of
32 # the creation of concat nodes, lower the size of maxlen).
34 # A Rope as defined in the original paper is a Tree made of concatenation
35 # nodes and containing `Flat` (that is Array-based) strings as Leaves.
44 # "My" " Name" " is" " Simon."
47 # Note that the above example is not representative of the actual implementation
48 # of `Ropes`, since short leaves are merged to keep the rope at an acceptable
49 # height (hence, this rope here might actually be a `FlatString` !).
54 # Maxlen is the maximum length of a Leaf node
56 # When concatenating two leaves, if `new_length` > `maxlen`,
57 # A `Concat` node is created instead
59 # Its purpose is to limit the depth of the `Rope` (this
60 # improves performance when accessing/iterating).
61 fun maxlen
: Int do return 512
63 # String using a tree-based representation with leaves as `FlatStrings`
64 private abstract class Rope
68 # Node that represents a concatenation between two `String`
73 redef var chars
is lazy
do return new RopeChars(self)
75 redef var bytes
is lazy
do return new RopeBytes(self)
77 redef var length
is noinit
79 redef var byte_length
is noinit
81 redef fun substrings
do return new RopeSubstrings.from
(self, 0)
83 redef fun empty
do return ""
85 # Cache for the latest accessed FlatString in `self`
86 var flat_cache
: FlatString is noinit
88 # Position of the beginning of `flat_cache` in `self`
89 var flat_last_pos_start
: Int = -1
91 var flat_last_pos_end
: Int = -1
93 redef var to_cstring
is lazy
do
94 var len
= _byte_length
95 var ns
= new NativeString(len
+ 1)
98 for i
in substrings
do
99 var ilen
= i
._byte_length
100 i
.as(FlatString)._items
.copy_to
(ns
, ilen
, i
.as(FlatString)._first_byte
, off
)
106 # Left child of the node
108 # Right child of the node
114 length
= l
.length
+ r
.length
115 _byte_length
= l
.byte_length
+ r
.byte_length
118 redef fun is_empty
do return _byte_length
== 0
125 redef fun iterator
do return new RopeCharIterator.from
(self, 0)
129 for j
in [1 .. i
[ do x
+= self
134 assert i
>= 0 and i
<= _length
135 var flps
= _flat_last_pos_start
136 if flps
!= -1 and i
>= flps
and i
<= _flat_last_pos_end
then
137 return _flat_cache
.fetch_char_at
(i
- flps
)
139 var lf
= get_leaf_at
(i
)
140 return lf
.fetch_char_at
(i
- _flat_last_pos_start
)
143 fun get_leaf_at
(pos
: Int): FlatString do
144 var flps
= _flat_last_pos_start
145 if flps
!= -1 and pos
>= flps
and pos
<= _flat_last_pos_end
then
151 if s
isa FlatString then break
154 var llen
= lft
.length
162 _flat_last_pos_start
= st
- pos
163 _flat_last_pos_end
= st
- pos
+ s
.length
- 1
168 redef fun substring
(from
, count
) do
171 if count
< 0 then return ""
176 if (count
+ from
) > ln
then count
= ln
- from
177 if count
<= 0 then return ""
178 var end_index
= from
+ count
- 1
180 var flps
= _flat_last_pos_start
181 if flps
!= -1 and from
>= flps
and end_index
<= _flat_last_pos_end
then
182 return _flat_cache
.substring_impl
(from
- flps
, count
, end_index
- flps
)
186 var llen
= lft
.length
188 if from
+ count
< llen
then return lft
.substring
(from
, count
)
189 var lsublen
= llen
- from
190 return lft
.substring_from
(from
) + _right
.substring
(0, count
- lsublen
)
192 return _right
.substring
(from
- llen
, count
)
196 redef fun reversed
do return new Concat(_right
.reversed
, _left
.reversed
)
198 redef fun insert_at
(s
, pos
) do
200 if pos
> lft
.length
then
201 return lft
+ _right
.insert_at
(s
, pos
- lft
.length
)
203 return lft
.insert_at
(s
, pos
) + _right
206 redef fun to_upper
do return new Concat(_left
.to_upper
, _right
.to_upper
)
208 redef fun to_lower
do return new Concat(_left
.to_lower
, _right
.to_lower
)
212 var slen
= s
.byte_length
214 return new Concat(self, s
)
217 var rlen
= r
.byte_length
218 if rlen
+ slen
> maxlen
then return new Concat(self, s
)
219 return new Concat(_left
, r
+ s
)
223 redef fun copy_to_native
(dest
, n
, src_offset
, dest_offset
) do
225 if src_offset
< l
.byte_length
then
226 var lcopy
= l
.byte_length
- src_offset
227 lcopy
= if lcopy
> n
then n
else lcopy
228 l
.copy_to_native
(dest
, lcopy
, src_offset
, dest_offset
)
233 _right
.copy_to_native
(dest
, n
, src_offset
, dest_offset
)
236 # Returns a balanced version of `self`
237 fun balance
: String do
238 var children
= new Array[String]
240 var iter
: nullable RopeCharIteratorPiece = new RopeCharIteratorPiece(self, false, false, null)
242 if iter
== null then break
244 if not rnod
isa Concat then
249 if not iter
.ldone
then
251 iter
= new RopeCharIteratorPiece(rnod
._left
, false, false, iter
)
252 else if not iter
.rdone
then
254 iter
= new RopeCharIteratorPiece(rnod
._right
, false, false, iter
)
260 return recurse_balance
(children
, children
.length
)
263 fun recurse_balance
(nodes
: Array[String], len
: Int): String do
267 if len
- stpos
> 1 then
268 nodes
[finpos
] = new Concat(nodes
[stpos
], nodes
[stpos
+ 1])
271 nodes
[finpos
] = nodes
[stpos
]
276 if finpos
== 1 then return nodes
[0]
277 return recurse_balance
(nodes
, finpos
)
281 # Mutable `Rope`, optimized for concatenation operations
283 # A `RopeBuffer` is an efficient way of building a `String` when
284 # concatenating small strings.
286 # It does concatenations in an optimized way by having a
287 # mutable part and an immutable part built by efficiently
288 # concatenating strings in chain.
290 # Every concatenation operation is done by copying a string to
291 # the mutable part and flushing it when full.
293 # However, when a long string is appended to the `Buffer`,
294 # the concatenation is done at it would be in a `Rope`.
299 redef var chars
: Sequence[Char] is lazy
do return new RopeBufferChars(self)
301 redef var bytes
is lazy
do return new RopeBufferBytes(self)
303 # The final string being built on the fly
304 private var str
: String = ""
306 # Current concatenation buffer
307 private var ns
: NativeString is noinit
309 # Next available (e.g. unset) character in the `Buffer`
312 # Length (in chars) of the buffered part
313 private var nslen
= 0
315 # Keeps track of the buffer's currently dumped part
317 # This might happen if for instance, a String was being
318 # built by concatenating small parts of string and suddenly
319 # a long string (length > maxlen) is appended.
320 private var dumped
: Int is noinit
322 # Length of the complete rope in chars (0)
333 # Length of the complete rope in bytes
334 redef var byte_length
= 0
336 # Length of the mutable part (in bytes)
338 # Is also used as base to compute the size of the next
339 # mutable native string (`ns`)
340 private var buf_size
: Int is noinit
342 redef fun substrings
do return new RopeBufSubstringIterator.from
(self)
344 # Builds an empty `RopeBuffer`
346 ns
= new NativeString(maxlen
)
351 # Builds a new `RopeBuffer` with `str` in it.
352 init from
(str
: String) do
354 ns
= new NativeString(maxlen
)
356 _byte_length
= str
.length
360 # Resets the informations of the `Buffer`
362 # This is called when doing in-place modifications
363 # on a previously to_s'd `RopeBuffer`
365 var nns
= new NativeString(buf_size
)
366 var blen
= rpos
- dumped
367 ns
.copy_to
(nns
, blen
, dumped
, 0)
375 if i
< str
.length
then
378 var index
= ns
.char_to_byte_index_cached
(i
- str
.length
, 0, dumped
)
379 return ns
.char_at
(index
)
383 redef fun []=(i
, c
) do
384 assert i
>= 0 and i
<= length
385 if i
== length
then add c
386 if i
< str
.length
then
387 _byte_length
+= c
.u8char_len
- str
[i
].u8char_len
389 var l
= s
.substring
(0, i
)
390 var r
= s
.substring_from
(i
+ 1)
393 var reali
= i
- str
.length
394 var index
= ns
.char_to_byte_index_cached
(reali
, 0, dumped
)
395 var st_nxt
= ns
.char_to_byte_index_cached
(reali
+ 1, reali
, index
)
396 var loc_c
= ns
.char_at
(index
)
397 if loc_c
.u8char_len
!= c
.u8char_len
then
398 var delta
= c
.u8char_len
- loc_c
.u8char_len
399 var remsp
= buf_size
- rpos
400 if remsp
< delta
then
402 var nns
= new NativeString(buf_size
)
403 ns
.copy_to
(nns
, index
- dumped
, dumped
, 0)
404 ns
.copy_to
(nns
, rpos
- index
- loc_c
.u8char_len
, index
+ loc_c
.u8char_len
, index
- dumped
+ delta
)
406 index
= index
- dumped
408 ns
.copy_to
(ns
, rpos
- st_nxt
, st_nxt
, st_nxt
+ delta
)
410 _byte_length
+= delta
413 ns
.set_char_at
(index
, c
)
417 redef fun empty
do return new RopeBuffer
425 ns
= new NativeString(buf_size
)
430 redef fun substring
(from
, count
) do
431 var strlen
= str
.length
435 if count
< 0 then count
= 0
439 if count
> length
then count
= length
- from
441 if count
== 0 then return empty
443 if from
< strlen
then
444 var subpos
= strlen
- from
445 if count
<= subpos
then
446 return new RopeBuffer.from
(str
.substring
(from
, count
))
448 var l
= str
.substring_from
(from
)
449 var rem
= count
- subpos
450 var nns
= new NativeString(rem
)
451 ns
.copy_to
(nns
, rem
, dumped
, 0)
452 return new RopeBuffer.from
(l
+ nns
.to_s_unsafe
(rem
))
455 var nns
= new NativeString(count
)
456 ns
.copy_to
(nns
, count
, dumped
, 0)
457 return new RopeBuffer.from
(nns
.to_s_unsafe
(count
))
461 redef fun append
(s
) do
462 var slen
= s
.byte_length
463 if slen
>= maxlen
then
468 if s
isa FlatText then
470 var from
= s
.first_byte
471 var remsp
= buf_size
- rpos
472 if slen
<= remsp
then
473 oits
.copy_to
(ns
, slen
, from
, rpos
)
477 var brk
= oits
.find_beginning_of_char_at
(from
+ remsp
)
478 oits
.copy_to
(ns
, brk
, from
, rpos
)
481 oits
.copy_to
(ns
, slen
- remsp
, brk
, 0)
484 for i
in s
.substrings
do append i
490 var remsp
= buf_size
- rp
491 var cln
= c
.u8char_len
496 ns
.set_char_at
(rp
, c
)
502 # Converts the Buffer to a FlatString, appends it to
503 # the final String and re-allocates a new larger Buffer.
504 private fun dump_buffer
do
506 var nstr
= new FlatString.with_infos
(ns
, rpos
- dumped
, dumped
)
510 ns
= new NativeString(bs
)
516 # Similar to dump_buffer, but does not reallocate a new NativeString
517 private fun persist_buffer
do
518 if rpos
== dumped
then return
519 var nstr
= new FlatString.with_infos
(ns
, rpos
- dumped
, dumped
)
526 new FlatString.with_infos
(ns
, rpos
- dumped
, dumped
).output
529 # Enlarge is useless here since the `Buffer`
530 # part is automatically dumped when necessary.
532 # Also, since the buffer can not be overused by a
533 # single string, there is no need for manual
536 # "You have no power here !"
537 redef fun enlarge
(i
) do end
546 # Flush the buffer in order to only have to reverse `str`.
547 if rpos
> 0 and dumped
!= rpos
then
548 str
+= new FlatString.with_infos
(ns
, rpos
- dumped
, dumped
)
555 if written
then reset
561 if written
then reset
567 redef class FlatString
569 redef fun insert_at
(s
, pos
) do
570 var l
= substring
(0, pos
)
571 var r
= substring_from
(pos
)
577 var slen
= s
.byte_length
578 var mlen
= _byte_length
579 if slen
== 0 then return self
580 if mlen
== 0 then return s
581 var nlen
= slen
+ mlen
582 if s
isa FlatString then
583 if nlen
> maxlen
then return new Concat(self, s
)
585 var sifrom
= s
._first_byte
586 var mifrom
= _first_byte
588 var ns
= new NativeString(nlen
+ 1)
589 mits
.copy_to
(ns
, mlen
, mifrom
, 0)
590 sits
.copy_to
(ns
, slen
, sifrom
, mlen
)
591 return new FlatString.full
(ns
, nlen
, 0, length
+ s
.length
)
592 else if s
isa Concat then
594 var sllen
= sl
.byte_length
595 if sllen
+ mlen
> maxlen
then return new Concat(self, s
)
596 return new Concat(self + sl
, s
._right
)
603 # A simple linked list for use with iterators
604 private class RopeCharIteratorPiece
605 # The encapsulated node of the `Rope`
607 # Was its _left child (if any) visited ?
609 # Was its _right child (if any) visited ?
611 # The previous node in the list.
612 var prev
: nullable RopeCharIteratorPiece
615 # A reverse iterator capable of working with `Rope` objects
616 private class RopeByteReverseIterator
617 super IndexedIterator[Byte]
619 # Current NativeString
620 var ns
: NativeString is noautoinit
621 # Current position in NativeString
622 var pns
: Int is noautoinit
623 # Position in the Rope (0-indexed)
624 var pos
: Int is noautoinit
625 # Iterator on the substrings, does the Postfix part of
626 # the Rope traversal.
627 var subs
: IndexedIterator[FlatString] is noautoinit
629 init from
(root
: Concat, pos
: Int) do
631 subs
= new ReverseRopeSubstrings.from
(root
, pos
)
634 pns
= pos
- subs
.index
637 redef fun index
do return pos
639 redef fun is_ok
do return pos
>= 0
641 redef fun item
do return ns
[pns
]
646 if pns
>= 0 then return
647 if not subs
.is_ok
then return
649 if not subs
.is_ok
then return
656 # Forward iterator on the bytes of a `Rope`
657 private class RopeByteIterator
658 super IndexedIterator[Byte]
660 # Position in current `String`
661 var pns
: Int is noautoinit
662 # Current `String` being iterated on
663 var ns
: NativeString is noautoinit
664 # Substrings of the Rope
665 var subs
: IndexedIterator[FlatString] is noautoinit
666 # Maximum position to iterate on (e.g. Rope.byte_length)
667 var max
: Int is noautoinit
668 # Position (char) in the Rope (0-indexed)
669 var pos
: Int is noautoinit
671 init from
(root
: Concat, pos
: Int) do
672 subs
= new RopeSubstrings.from
(root
, pos
)
673 pns
= pos
- subs
.index
675 ns
= subs
.item
._items
676 max
= root
.byte_length
- 1
679 redef fun item
do return ns
[pns
]
681 redef fun is_ok
do return pos
<= max
683 redef fun index
do return pos
688 if pns
< subs
.item
._byte_length
then return
689 if not subs
.is_ok
then return
691 if not subs
.is_ok
then return
692 ns
= subs
.item
._items
698 # A reverse iterator capable of working with `Rope` objects
699 private class RopeCharReverseIterator
700 super IndexedIterator[Char]
702 # Current NativeString
703 var ns
: String is noautoinit
704 # Current position in NativeString
705 var pns
: Int is noautoinit
706 # Position in the Rope (0-indexed)
707 var pos
: Int is noautoinit
708 # Iterator on the substrings, does the Postfix part of
709 # the Rope traversal.
710 var subs
: IndexedIterator[String] is noautoinit
712 init from
(root
: Concat, pos
: Int) do
714 subs
= new ReverseRopeSubstrings.from
(root
, pos
)
716 pns
= pos
- subs
.index
719 redef fun index
do return pos
721 redef fun is_ok
do return pos
>= 0
723 redef fun item
do return ns
[pns
]
728 if pns
>= 0 then return
729 if not subs
.is_ok
then return
731 if not subs
.is_ok
then return
737 # Forward iterator on the chars of a `Rope`
738 private class RopeCharIterator
739 super IndexedIterator[Char]
741 # Position in current `String`
742 var pns
: Int is noautoinit
743 # Current `String` being iterated on
744 var str
: String is noautoinit
745 # Substrings of the Rope
746 var subs
: IndexedIterator[String] is noautoinit
747 # Maximum position to iterate on (e.g. Rope.length)
748 var max
: Int is noautoinit
749 # Position (char) in the Rope (0-indexed)
750 var pos
: Int is noautoinit
752 init from
(root
: Concat, pos
: Int) do
753 subs
= new RopeSubstrings.from
(root
, pos
)
754 pns
= pos
- subs
.index
757 max
= root
.length
- 1
760 redef fun item
do return str
[pns
]
762 redef fun is_ok
do return pos
<= max
764 redef fun index
do return pos
769 if pns
< subs
.item
.length
then return
770 if not subs
.is_ok
then return
772 if not subs
.is_ok
then return
778 # Substrings of a Rope (i.e. Reverse postfix iterator on leaves)
779 private class ReverseRopeSubstrings
780 super IndexedIterator[FlatString]
783 var iter
: RopeCharIteratorPiece is noinit
785 var pos
: Int is noinit
788 var str
: FlatString is noinit
790 init from
(root
: Concat, pos
: Int) do
791 var r
= new RopeCharIteratorPiece(root
, false, true, null)
792 var rnod
: String = root
795 if rnod
isa Concat then
796 if off
>= rnod
._left
.length
then
797 off
-= rnod
._left
.length
799 r
= new RopeCharIteratorPiece(rnod
, false, true, r
)
803 r
= new RopeCharIteratorPiece(rnod
, false, true, r
)
806 str
= rnod
.as(FlatString)
815 redef fun item
do return str
817 redef fun index
do return pos
819 redef fun is_ok
do return pos
>= 0
822 if pos
< 0 then return
824 var currit
= curr
.as(not null).node
825 while curr
!= null do
827 if not currit
isa Concat then
828 str
= currit
.as(FlatString)
833 if not curr
.rdone
then
835 curr
= new RopeCharIteratorPiece(currit
._right
, false, false, curr
)
838 if not curr
.ldone
then
840 curr
= new RopeCharIteratorPiece(currit
._left
, false, false, curr
)
849 private class RopeBufSubstringIterator
850 super Iterator[FlatText]
852 # Iterator on the substrings of the building string
853 var iter
: Iterator[FlatText] is noautoinit
854 # Makes a String out of the buffered part of the Ropebuffer
855 var nsstr
: FlatString is noautoinit
856 # Did we attain the buffered part ?
857 var nsstr_done
= false
859 init from
(str
: RopeBuffer) do
860 iter
= str
.str
.substrings
861 nsstr
= new FlatString.with_infos
(str
.ns
, str
.rpos
- str
.dumped
, str
.dumped
)
862 if str
.length
== 0 then nsstr_done
= true
865 redef fun is_ok
do return iter
.is_ok
or not nsstr_done
869 if iter
.is_ok
then return iter
.item
882 # Substrings of a Rope (i.e. Postfix iterator on leaves)
883 private class RopeSubstrings
884 super IndexedIterator[FlatString]
887 var iter
: RopeCharIteratorPiece is noinit
889 var pos
: Int is noinit
890 # Maximum position in `Rope` (i.e. length - 1)
891 var max
: Int is noinit
894 var str
: FlatString is noinit
896 init from
(root
: Concat, pos
: Int) do
897 var r
= new RopeCharIteratorPiece(root
, true, false, null)
898 max
= root
.length
- 1
899 var rnod
: String = root
902 if rnod
isa Concat then
903 if off
>= rnod
._left
.length
then
905 off
-= rnod
._left
.length
907 r
= new RopeCharIteratorPiece(rnod
, true, false, r
)
910 r
= new RopeCharIteratorPiece(rnod
, true, false, r
)
913 str
= rnod
.as(FlatString)
922 redef fun item
do return str
924 redef fun is_ok
do return pos
<= max
926 redef fun index
do return pos
930 if pos
> max
then return
931 var it
= iter
.prev
.as(not null)
934 if not rnod
isa Concat then
937 str
= rnod
.as(FlatString)
944 it
= new RopeCharIteratorPiece(rnod
, false, false, it
)
945 else if not it
.rdone
then
948 it
= new RopeCharIteratorPiece(rnod
, false, false, it
)
950 it
= it
.prev
.as(not null)
958 # Implementation of a `StringCharView` for `Concat` objects
959 private class RopeChars
962 redef type SELFTYPE: Concat
968 redef fun iterator_from
(i
) do return new RopeCharIterator.from
(target
, i
)
970 redef fun reverse_iterator_from
(i
) do return new RopeCharReverseIterator.from
(target
, i
)
974 # Implementation of a `StringCharView` for `Concat` objects
975 private class RopeBytes
978 redef type SELFTYPE: Concat
980 var cache
: FlatString is noinit
982 var cache_start
: Int = -1
984 var cache_end
: Int = -1
987 assert i
>= 0 and i
< target
._byte_length
988 var flps
= _cache_start
989 if i
>= flps
and i
<= _cache_end
then
990 return _cache
.bytes
[i
- flps
]
992 var lf
= get_leaf_at
(i
)
993 return lf
.bytes
[i
- _cache_start
]
996 fun get_leaf_at
(pos
: Int): FlatString do
997 var flps
= _cache_start
998 if pos
>= flps
and pos
<= _cache_end
then
1001 var s
: String = target
1004 if s
isa FlatString then break
1007 var llen
= lft
.byte_length
1015 _cache_start
= st
- pos
1016 _cache_end
= st
- pos
+ s
.byte_length
- 1
1021 redef fun iterator_from
(i
) do return new RopeByteIterator.from
(target
, i
)
1023 redef fun reverse_iterator_from
(i
) do return new RopeByteReverseIterator.from
(target
, i
)
1027 # An Iterator over a RopeBuffer.
1028 class RopeBufferCharIterator
1029 super IndexedIterator[Char]
1032 var sit
: IndexedIterator[Char] is noautoinit
1034 redef fun index
do return sit
.index
1036 # Init the iterator from a RopeBuffer starting from `pos`.
1037 init from
(t
: RopeBuffer, pos
: Int) do
1039 sit
= t
.str
.chars
.iterator_from
(pos
)
1042 redef fun is_ok
do return sit
.is_ok
1049 redef fun next
do sit
.next
1052 # Reverse iterator over a RopeBuffer.
1053 class RopeBufferCharReverseIterator
1054 super IndexedIterator[Char]
1057 var sit
: IndexedIterator[Char] is noautoinit
1059 redef fun index
do return sit
.index
1061 # Init the iterator from a RopeBuffer starting from `pos`.
1062 init from
(tgt
: RopeBuffer, pos
: Int) do
1064 sit
= tgt
.str
.chars
.reverse_iterator_from
(pos
)
1067 redef fun is_ok
do return sit
.is_ok
1074 redef fun next
do sit
.next
1077 # View on the chars of a `RopeBuffer`
1078 class RopeBufferChars
1079 super BufferCharView
1081 redef type SELFTYPE: RopeBuffer
1083 redef fun [](i
) do return target
[i
]
1085 redef fun []=(i
,c
) do target
[i
] = c
1087 redef fun add
(c
) do target
.add c
1089 redef fun push
(c
) do target
.add c
1091 redef fun iterator_from
(i
) do return new RopeBufferCharIterator.from
(target
, i
)
1093 redef fun reverse_iterator_from
(i
) do return new RopeBufferCharReverseIterator.from
(target
, i
)
1096 # An Iterator over a RopeBuffer.
1097 class RopeBufferByteIterator
1098 super IndexedIterator[Byte]
1101 var sit
: IndexedIterator[Byte] is noautoinit
1103 # Native string iterated over.
1104 var ns
: NativeString is noautoinit
1106 # Current position in `ns`.
1107 var pns
: Int is noautoinit
1109 # Maximum position iterable.
1110 var maxpos
: Int is noautoinit
1112 redef var index
is noautoinit
1114 # Init the iterator from a RopeBuffer starting from `pos`.
1115 init from
(t
: RopeBuffer, pos
: Int) do
1117 maxpos
= t
._byte_length
1118 sit
= t
.str
.bytes
.iterator_from
(pos
)
1119 pns
= pos
- t
.str
.length
1123 redef fun is_ok
do return index
< maxpos
1126 if sit
.is_ok
then return sit
.item
1140 # Reverse iterator over a RopeBuffer.
1141 class RopeBufferByteReverseIterator
1142 super IndexedIterator[Byte]
1145 var sit
: IndexedIterator[Byte] is noautoinit
1147 # Native string iterated over.
1148 var ns
: NativeString is noautoinit
1150 # Current position in `ns`.
1151 var pns
: Int is noautoinit
1153 redef var index
is noautoinit
1155 # Init the iterator from a RopeBuffer starting from `pos`.
1156 init from
(tgt
: RopeBuffer, pos
: Int) do
1157 sit
= tgt
.str
.bytes
.reverse_iterator_from
(pos
- (tgt
.rpos
- tgt
.dumped
))
1158 pns
= pos
- tgt
.str
.byte_length
+ tgt
.rpos
1163 redef fun is_ok
do return index
>= 0
1166 if pns
>= 0 then return ns
[pns
]
1180 # View on the chars of a `RopeBuffer`
1181 class RopeBufferBytes
1182 super BufferByteView
1184 redef type SELFTYPE: RopeBuffer
1187 if i
< target
.str
.byte_length
then
1188 return target
.str
.bytes
[i
]
1190 return target
.ns
[i
- target
.str
.byte_length
]
1194 redef fun iterator_from
(i
) do return new RopeBufferByteIterator.from
(target
, i
)
1196 redef fun reverse_iterator_from
(i
) do return new RopeBufferByteReverseIterator.from
(target
, i
)