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[FlatText]
72 var str
: FlatString is noinit
76 str
= new FlatString.with_infos
(leaf
.buf
.ns
, leaf
.length
, 0, leaf
.length
- 1)
79 redef fun is_ok
do return avail
81 redef fun next
do avail
= false
83 redef fun index
do return 0
85 redef fun item
do return str
88 # Leaf of a `Rope`, used as a buffered area for speedy concatenation.
93 var bns
: NativeString is noinit
94 redef var length
: Int is noinit
96 redef fun empty
do return new Leaf(new ManualBuffer)
98 redef fun to_cstring
do
100 var ns
= new NativeString(len
+ 1)
102 buf
.ns
.copy_to
(ns
, len
, 0, 0)
106 redef fun substrings
do return new LeafSubstrings(self)
108 redef fun [](i
) do return buf
[i
]
115 redef fun output
do new FlatString.with_infos
(buf
.ns
, length
, 0, length
- 1).output
117 redef fun to_upper
do
118 var x
= new ManualBuffer
122 for i
in [0..mlen
[ do
123 nns
[i
] = ns
[i
].to_upper
129 redef fun to_lower
do
130 var x
= new ManualBuffer
134 for i
in [0..mlen
[ do
135 nns
[i
] = ns
[i
].to_lower
141 redef fun reversed
do
142 var x
= new ManualBuffer
147 for i
in [0 .. mlen
[ do
155 redef fun substring
(from
, len
) do
156 return new FlatString.with_infos
(buf
.ns
, len
, from
, from
+ len
- 1)
159 redef fun insert_at
(s
, pos
) do
160 var l
= substring
(0, pos
)
161 var r
= substring_from
(pos
)
169 if slen
== 0 then return self
170 if mlen
== 0 then return s
171 var nlen
= mlen
+ slen
172 if nlen
> maxlen
then return new Concat(self, s
)
173 if s
isa FlatString then
177 sits
.copy_to
(buf
.ns
, slen
, s
.index_from
, bpos
)
178 buf
.pos
= bpos
+ slen
181 var b
= new ManualBuffer
183 bns
.copy_to
(nbns
, mlen
, 0, 0)
184 sits
.copy_to
(nbns
, slen
, s
.index_from
, mlen
)
188 else if s
isa Leaf then
192 sbns
.copy_to
(bns
, slen
, 0, bpos
)
196 var b
= new ManualBuffer
198 bns
.copy_to
(nbns
, mlen
, 0, 0)
199 sbns
.copy_to
(nbns
, slen
, 0, mlen
)
203 else if s
isa Concat then
204 if not s
.left
isa Concat then
205 return new Concat(self + s
.left
, s
.right
)
207 return new Concat(self, s
)
213 bns
.copy_to
(b
.ns
, mlen
, 0, 0)
225 redef fun to_cstring
do
227 var ns
= new NativeString(len
+ 1)
230 for i
in substrings
do
232 if i
isa FlatString then
233 i
.items
.copy_to
(ns
, ilen
, i
.index_from
, off
)
234 else if i
isa Leaf then
235 i
.buf
.ns
.copy_to
(ns
, ilen
, 0, off
)
247 if s
isa FlatString then
250 if rlen
+ slen
> maxlen
then return new Concat(left
, new Concat(r
, s
))
251 return new Concat(left
, r
+ s
)
252 else if s
isa Concat then
253 return new Concat(self, s
)
254 else if s
isa Leaf then
257 if rlen
+ slen
> maxlen
then return new Concat(left
, new Concat(r
, s
))
258 return new Concat(left
, r
+ s
)
265 redef class FlatString
270 if slen
== 0 then return self
271 if mlen
== 0 then return s
272 if s
isa FlatString then
273 if slen
+ mlen
> maxlen
then return new Concat(self, s
)
275 var sifrom
= s
.index_from
276 var mifrom
= index_from
278 var b
= new ManualBuffer
280 mits
.copy_to
(bns
, mlen
, mifrom
, 0)
281 sits
.copy_to
(bns
, slen
, sifrom
, mlen
)
284 else if s
isa Concat then
286 var sllen
= sl
.length
287 if sllen
+ mlen
> maxlen
then return new Concat(self, s
)
288 return new Concat(sl
+ self, s
.right
)
289 else if s
isa Leaf then
290 if slen
+ mlen
> maxlen
then return new Concat(self, s
)
291 var mifrom
= index_from
293 var b
= new ManualBuffer
295 items
.copy_to
(bns
, mlen
, mifrom
, 0)
296 sb
.ns
.copy_to
(bns
, slen
, 0, mlen
)
307 # Fast implementation
310 if l
== 0 then return ""
311 if l
== 1 then if self[0] == null then return "" else return self[0].to_s
313 var na
= new NativeArray[String](l
)
329 var ns
= new NativeString(sl
+ 1)
336 if tmp
isa FlatString then
337 tmp
.items
.copy_to
(ns
, tpl
, tmp
.index_from
, off
)
340 for j
in tmp
.substrings
do
342 if j
isa FlatString then
343 j
.items
.copy_to
(ns
, slen
, j
.index_from
, off
)
344 else if j
isa Leaf then
345 j
.buf
.ns
.copy_to
(ns
, slen
, 0, off
)
352 return ns
.to_s_with_length
(sl
)