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 # Introduces ropes with buffered leaves
12 module bufferized_ropes
15 intrude import standard
::ropes
17 # Leaf containing a FlatBuffer to optimize concatenation operations
18 private class BufferLeaf
21 init(val
: FlatBuffer) do
32 if right
== null then return new StringLeaf("".as(FlatString))
35 if right
== null then return left
.as(not null).to_leaf
36 if left
.length
+ right
.length
< buf_len
then
37 var b
= new FlatBuffer.with_capacity
(buf_len
)
38 b
.append
(left
.to_leaf
.str
)
39 b
.append
(right
.to_leaf
.str
)
40 return new BufferLeaf(b
)
42 var b
= new FlatBuffer.with_capacity
(left
.length
+ right
.length
)
43 b
.append
(left
.to_leaf
.str
)
44 b
.append
(right
.to_leaf
.str
)
45 return new StringLeaf(b
.lazy_to_s
(b
.length
))
52 # Creates a substring, only without any copy overhead for Buffers
53 # The call to lazy_substring ensures the creation of a FlatString, which is required for Leaves.
54 private fun lazy_substring
(from
: Int, length
: Int): FlatString is abstract
56 # Same as substring_from, but without copy of the data for Buffers.
57 private fun lazy_substring_from
(from
: Int): FlatString is abstract
60 redef class FlatBuffer
62 # Same as to_s, only will not copy self before returning a String.
63 private fun lazy_to_s
(len
: Int): FlatString
65 return new FlatString.with_infos
(items
, len
, 0, length
- 1)
68 redef fun lazy_substring
(from
,length
)
70 return new FlatString.with_infos
(items
, length
, from
, from
+ length
- 1)
73 redef fun lazy_substring_from
(from
)
75 var newlen
= length
- from
76 return new FlatString.with_infos
(items
, newlen
, from
, from
+ newlen
- 1)
81 redef class FlatString
83 redef fun lazy_substring
(from
, len
) do return substring
(from
,len
).as(FlatString)
85 redef fun lazy_substring_from
(from
) do return substring_from
(from
).as(FlatString)
92 init do root
= new BufferLeaf(new FlatBuffer.with_capacity
(buf_len
))
96 redef class RopeString
98 init from
(s
: String) do
99 if s
.length
< buf_len
then
100 var b
= new FlatBuffer.with_capacity
(buf_len
)
102 root
= new BufferLeaf(b
)
104 if s
isa RopeString then root
= s
.root
else root
= new StringLeaf(s
.as(FlatString))
108 redef fun +(o
) do return insert_at
(o
.to_s
, length
)
110 # Inserts a String `str` at position `pos`
111 redef fun insert_at
(str
, pos
)
113 if str
.length
== 0 then return self
115 assert pos
>= 0 and pos
<= length
117 if pos
== length
then
119 if r
isa BufferLeaf then
120 var b
= r
.str
.as(FlatBuffer)
121 if r
.length
+ str
.length
< b
.capacity
then
123 return new RopeString.from_root
(new BufferLeaf(b
))
128 var path
= node_at
(pos
)
132 if path
.offset
== path
.leaf
.length
then
133 cct
= build_node_len_offset
(path
, str
)
134 else if path
.offset
== 0 then
135 cct
= build_node_zero_offset
(path
, str
)
137 cct
= build_node_other
(path
,str
)
140 if path
.stack
.is_empty
then return new RopeString.from_root
(cct
)
142 var tmp
= path
.stack
.pop
143 var last_concat
: Concat
146 last_concat
= new Concat(cct
,tmp
.node
.right
.as(not null))
148 last_concat
= new Concat(tmp
.node
.left
.as(not null), cct
)
151 for i
in path
.stack
.reverse_iterator
do
154 nod
= new Concat(last_concat
, i
.node
.right
.as(not null))
156 nod
= new Concat(i
.node
.left
.as(not null), last_concat
)
161 return new RopeString.from_root
(last_concat
)
164 redef fun substring
(pos
, len
)
171 if pos
+ len
> length
then len
= length
- pos
173 if len
<= 0 then return new RopeString
175 var path
= node_at
(pos
)
178 var offset
= path
.offset
181 if lf
isa StringLeaf then
182 s
= lf
.str
.as(FlatString)
184 s
= lf
.str
.as(FlatBuffer).lazy_to_s
(lf
.length
)
187 if path
.leaf
.str
.length
- offset
> len
then
188 lf
= new StringLeaf(s
.substring
(offset
,len
).as(FlatString))
190 lf
= new StringLeaf(s
.substring_from
(offset
).as(FlatString))
193 var nod
: RopeNode = lf
195 if lf
.length
== len
then return new RopeString.from_root
(lf
)
197 var lft
: nullable RopeNode
198 var rht
: nullable RopeNode
200 for i
in path
.stack
.reverse_iterator
do
201 if i
.right
then continue
204 nod
= new Concat(lft
, rht
)
207 var ret
= new RopeString
210 path
= ret
.node_at
(len-1
)
216 if lf
isa StringLeaf then
217 s
= lf
.str
.as(FlatString)
219 s
= lf
.str
.as(FlatBuffer).lazy_to_s
(lf
.length
)
222 nod
= new StringLeaf(s
.substring
(0, offset
+1).as(FlatString))
224 for i
in path
.stack
.reverse_iterator
do
225 if i
.left
then continue
228 nod
= new Concat(lft
, rht
)
236 private fun build_node_zero_offset
(path
: Path, s
: String): RopeNode
238 var finlen
= path
.leaf
.length
+ s
.length
239 if finlen
<= buf_len
then
240 var b
= new FlatBuffer.with_capacity
(buf_len
)
242 b
.append
(path
.leaf
.str
)
243 if finlen
== buf_len
then return new StringLeaf(b
.lazy_to_s
(finlen
))
244 return new BufferLeaf(b
)
248 if s
isa FlatString then
249 if s
.length
> buf_len
then
250 lft
= new StringLeaf(s
)
252 var b
= new FlatBuffer
254 lft
= new BufferLeaf(b
)
257 lft
= s
.as(RopeString).root
259 return new Concat(lft
, rht
)
262 private fun build_node_len_offset
(path
: Path, s
: String): RopeNode
265 if leaf
isa BufferLeaf then
266 if s
.length
> buf_len
then
267 if s
isa FlatString then
268 return new Concat(leaf
, new StringLeaf(s
))
270 return new Concat(leaf
, s
.as(Rope).root
)
273 var finlen
= leaf
.length
+ s
.length
274 var buf
= leaf
.str
.as(FlatBuffer)
275 var cap
= buf
.capacity
276 # Meaning the buffer was modified elsewhere
277 # Therefore, we create a new one
278 if leaf
.length
!= buf
.length
then
279 var b
= new FlatBuffer.with_capacity
(buf_len
)
280 b
.append
(buf
.lazy_to_s
(leaf
.length
))
283 if finlen
<= cap
then
285 if finlen
== buf_len
then return new StringLeaf(buf
.lazy_to_s
(finlen
))
286 return new BufferLeaf(buf
)
288 var l_len
= finlen
- cap
289 buf
.append
(s
.substring
(0,l_len
))
290 var b2
= new FlatBuffer.with_capacity
(buf_len
)
291 b2
.append
(s
.substring_from
(l_len
))
292 var left_leaf
= new StringLeaf(buf
.lazy_to_s
(buf
.length
))
293 var right_leaf
= new BufferLeaf(b2
)
294 var cct
= new Concat(left_leaf
, right_leaf
)
300 if s
.length
>= buf_len
then
301 if s
isa FlatString then rht
= new StringLeaf(s
) else rht
= s
.as(Rope).root
303 var buf
= new FlatBuffer.with_capacity
(buf_len
)
305 rht
= new BufferLeaf(buf
)
307 return new Concat(lft
,rht
)
311 private fun build_node_other
(path
: Path,str
: String): RopeNode
315 if lf
isa BufferLeaf then
316 var b
= lf
.str
.as(FlatBuffer)
317 s
= b
.lazy_to_s
(lf
.length
)
319 s
= lf
.str
.as(FlatString)
321 var l_str
= s
.lazy_substring
(0, path
.offset
)
322 var r_str
= s
.lazy_substring_from
(path
.offset
)
323 if s
.length
+ str
.length
< buf_len
then
324 var buf
= new FlatBuffer.with_capacity
(buf_len
)
328 return new BufferLeaf(buf
)
331 if str
isa FlatString then child
= new StringLeaf(str
) else child
= str
.as(Rope).root
332 var l_cct
= new Concat(new StringLeaf(l_str
), child
)
333 var r_cct
= new Concat(l_cct
, new StringLeaf(r_str
))
339 redef class SubstringsIterator
341 # Compute the bounds of the current substring and makes the substring
342 redef fun make_substring
347 var length
= l
.length
348 if nodes
.index
< pos
then
349 min
= pos
- nodes
.index
351 substring
= s
.lazy_substring
(min
, length
)
356 redef class ReverseSubstringsIterator
358 redef fun make_substring
362 if pos
> (leaves
.index
+ l
.length
- 1) then return
363 str
= s
.lazy_substring
(0, (pos
- leaves
.index
+ 1))
368 # Default size of a buffer in a rope leaf.
369 fun buf_len
: Int do return 200