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 # Introduces a self-balancing method on Rope, using a Splay Tree
15 intrude import standard
::ropes
19 # Performs a Left rotation on node `x`
20 # Since a Rope does not have any notion of parent in its node, they need to be passed as arguments if available.
21 private fun left_rotate
(r
: Concat): Concat
23 var rr
= r
.right
.as(Concat)
27 var nr
= new Concat(rl
, pl
)
28 var np
= new Concat(nr
, pr
)
32 # Performs a Right rotation on node `r`
33 # Since a Rope does not have any notion of parent in its node, they need to be passed as arguments if available.
34 private fun right_rotate
(r
: Concat): Concat
36 var rl
= r
.left
.as(Concat)
40 var nr
= new Concat(pr
, rr
)
41 var np
= new Concat(pl
, nr
)
45 # Performs a Splay operation on a complete path
46 # The last node of the path will become the root.
47 private fun splay
(path
: Path): nullable Concat
50 if st
.is_empty
then return null
52 while not st
.is_empty
do
56 nod
= new Concat(cct
, tmp
.node
.right
)
57 cct
= right_rotate
(nod
)
59 nod
= new Concat(tmp
.node
.left
, cct
)
60 cct
= left_rotate
(nod
)
67 redef class RopeString
69 # Inserts a String `str` at position `pos`
70 redef fun insert_at
(str
, pos
)
72 if str
.length
== 0 then return self
73 if self.length
== 0 then return new RopeString.from
(str
)
75 assert pos
>= 0 and pos
<= length
77 var path
= node_at
(pos
)
79 var last_concat
: Concat
81 if path
.offset
== 0 then
82 if str
isa FlatString then
83 last_concat
= new Concat(new StringLeaf(str
), path
.leaf
)
85 last_concat
= new Concat(str
.as(RopeString).root
, path
.leaf
)
87 else if path
.offset
== path
.leaf
.length
then
88 if str
isa FlatString then
89 last_concat
= new Concat(path
.leaf
, new StringLeaf(str
))
91 last_concat
= new Concat(path
.leaf
, str
.as(RopeString).root
)
95 var l_half
= s
.substring
(0, s
.length
- path
.offset
)
96 var r_half
= s
.substring_from
(s
.length
- path
.offset
)
98 var ll
= new StringLeaf(l_half
.as(FlatString))
99 if str
isa FlatString then
100 cct
= new Concat(ll
, new StringLeaf(str
))
102 cct
= new Concat(ll
, str
.as(RopeString).root
)
104 last_concat
= new Concat(cct
, new StringLeaf(r_half
.as(FlatString)))
109 if st
.is_empty
then return new RopeString.from_root
(last_concat
)
114 var n
= tmp
.node
.right
115 var r
= new Concat(last_concat
, n
)
116 st
.push
(new PathElement(r
))
118 var n
= tmp
.node
.left
119 var r
= new Concat(n
, last_concat
)
120 st
.push
(new PathElement(r
))
123 return new RopeString.from_root
(splay
(path
).as(not null))