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 is 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 is a part of
11 # Ropes with a special kind of Leaves that act similar to a `Buffer`
13 # When using this module, re-allocations are limited by the introduction
14 # of a larger-than-necessary buffered area for the native part of a `String`
15 # in an append-only fashion.
17 # Concretely, when concatenating two small strings of length `n` + `m` < `maxlen`
18 # What happens is that a `maxlen` byte buffer is allocated, ready to receive more
19 # bytes a posteriori without necessarily reallocating a new byte array.
21 # Theoretically, this should lower the number of concatenations
22 # and reallocations when concatenating `String` objects.
25 intrude import standard
::ropes
27 # Hidden buffer, used to simulate a `FlatBuffer` on a short string.
29 # This is to be used by low-level APIs because of its lack of
30 # safety, if you use it, make sure you know what you are doing !
32 # Practically, it is the underlying representation of a `Leaf` in
33 # the `Rope` block, its advantage is that it saves a bit more space
34 # for future concatenations, without risking to overwrite previously
35 # used space, making it suitable for Strings.
37 # Note for future use : Should there be parallel capacity in Nit at
38 # some point, this is NOT thread safe !
39 private class ManualBuffer
40 var ns
: NativeString is noinit
41 # Current position in the `NativeString`
43 # It is used by the clients of `ManualBuffer` as a guard
44 # to detect if the concatenation in the `ManualBuffer`
48 # Say we have two strings `x` and `y` referencing the
49 # same `ManualBuffer` `b`, `y` is the concatenation of
50 # `x` and another string.
52 # If we try to concatenate a `String` `z` to `x`, a new
53 # `ManualBuffer` will be created since `pos` and `x.length`
56 # However, if we concatenate the same `String` to `y`,
57 # the contents of `z` will be copied to the `ManualBuffer`.
60 init do ns
= new NativeString(maxlen
)
62 fun [](i
: Int): Char do return ns
[i
]
65 # Simple implementation of the iterator on Substrings for `Leaf`
67 # Basically just returns `self` encapsulated in a `FlatString`.
68 private class LeafSubstrings
69 super IndexedIterator[Text]
74 init(l
: Leaf) do str
= new FlatString.with_infos
(l
.buf
.ns
, l
.length
, 0, l
.length
- 1)
76 redef fun is_ok
do return avail
78 redef fun next
do avail
= false
80 redef fun index
do return 0
82 redef fun item
do return str
85 # Leaf of a `Rope`, used as a buffered area for speedy concatenation.
89 private var buf
: ManualBuffer
90 private var bns
: NativeString is noinit
91 redef var length
: Int is noinit
93 redef fun empty
do return new Leaf(new ManualBuffer)
95 redef fun to_cstring
do
97 var ns
= new NativeString(len
+ 1)
99 buf
.ns
.copy_to
(ns
, len
, 0, 0)
103 redef fun substrings
do return new LeafSubstrings(self)
105 redef fun [](i
) do return buf
[i
]
112 redef fun output
do new FlatString.with_infos
(buf
.ns
, length
, 0, length
- 1).output
114 redef fun to_upper
do
115 var x
= new ManualBuffer
119 for i
in [0..mlen
[ do
120 nns
[i
] = ns
[i
].to_upper
126 redef fun to_lower
do
127 var x
= new ManualBuffer
131 for i
in [0..mlen
[ do
132 nns
[i
] = ns
[i
].to_lower
138 redef fun reversed
do
139 var x
= new ManualBuffer
144 for i
in [0 .. mlen
[ do
152 redef fun substring
(from
, len
) do
153 return new FlatString.with_infos
(buf
.ns
, len
, from
, from
+ len
- 1)
156 redef fun insert_at
(s
, pos
) do
157 var l
= substring
(0, pos
)
158 var r
= substring_from
(pos
)
166 if slen
== 0 then return self
167 if mlen
== 0 then return s
168 var nlen
= mlen
+ slen
169 if nlen
> maxlen
then return new Concat(self, s
)
170 if s
isa FlatString then
174 sits
.copy_to
(buf
.ns
, slen
, s
.index_from
, bpos
)
175 buf
.pos
= bpos
+ slen
178 var b
= new ManualBuffer
180 bns
.copy_to
(nbns
, mlen
, 0, 0)
181 sits
.copy_to
(nbns
, slen
, s
.index_from
, mlen
)
185 else if s
isa Leaf then
189 sbns
.copy_to
(bns
, slen
, 0, bpos
)
193 var b
= new ManualBuffer
195 bns
.copy_to
(nbns
, mlen
, 0, 0)
196 sbns
.copy_to
(nbns
, slen
, 0, mlen
)
200 else if s
isa Concat then
201 if not s
.left
isa Concat then
202 return new Concat(self + s
.left
, s
.right
)
204 return new Concat(self, s
)
210 bns
.copy_to
(b
.ns
, mlen
, 0, 0)
222 redef fun to_cstring
do
224 var ns
= new NativeString(len
+ 1)
227 for i
in substrings
do
229 if i
isa FlatString then
230 i
.items
.copy_to
(ns
, ilen
, i
.index_from
, off
)
231 else if i
isa Leaf then
232 i
.buf
.ns
.copy_to
(ns
, ilen
, 0, off
)
245 if s
isa FlatString then
248 if rlen
+ slen
> maxlen
then return new Concat(left
, new Concat(r
, s
))
249 return new Concat(left
, r
+ s
)
250 else if s
isa Concat then
251 return new Concat(self, s
)
252 else if s
isa Leaf then
255 if rlen
+ slen
> maxlen
then return new Concat(left
, new Concat(r
, s
))
256 return new Concat(left
, r
+ s
)
263 redef class FlatString
268 if slen
== 0 then return self
269 if mlen
== 0 then return s
270 if s
isa FlatString then
271 if slen
+ mlen
> maxlen
then return new Concat(self, s
)
273 var sifrom
= s
.index_from
274 var mifrom
= index_from
276 var b
= new ManualBuffer
278 mits
.copy_to
(bns
, mlen
, mifrom
, 0)
279 sits
.copy_to
(bns
, slen
, sifrom
, mlen
)
282 else if s
isa Concat then
284 var sllen
= sl
.length
285 if sllen
+ mlen
> maxlen
then return new Concat(self, s
)
286 return new Concat(sl
+ self, s
.right
)
287 else if s
isa Leaf then
288 if slen
+ mlen
> maxlen
then return new Concat(self, s
)
290 var mifrom
= index_from
292 var b
= new ManualBuffer
294 items
.copy_to
(bns
, mlen
, mifrom
, 0)
295 sb
.ns
.copy_to
(bns
, slen
, 0, mlen
)
306 # Fast implementation
309 if l
== 0 then return ""
310 if l
== 1 then if self[0] == null then return "" else return self[0].to_s
312 var na
= new NativeArray[String](l
)
328 var ns
= new NativeString(sl
+ 1)
335 if tmp
isa FlatString then
336 tmp
.items
.copy_to
(ns
, tpl
, tmp
.index_from
, off
)
339 for j
in tmp
.substrings
do
341 if j
isa FlatString then
342 j
.items
.copy_to
(ns
, slen
, j
.index_from
, off
)
343 else if j
isa Leaf then
344 j
.buf
.ns
.copy_to
(ns
, slen
, 0, off
)
351 return ns
.to_s_with_length
(sl
)