b493de9f18fd073e5cb44c7674a7555df1ae350a
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 # Nit implementation of the Ropes (see Ropes : An Alternative to Strings,
12 # SOFTWARE - PRACTICE AND EXPERIENCE, VOL. 25(12), 1315 - 1330 (DECEMBER 1995)
13 # Hans. J Boehm, Russ Atkinson and Michael Plass)
15 # A rope is a kind of string but instead of being flat, it relies on a binary tree structure to store data.
20 # Used when searching for a particular node
21 # Returns the path to the node from the root of the rope
22 # Also, the node and the offset for seeked position in the rope
28 # Stack of the nodes traversed, and the path used
29 var stack
: List[PathElement]
32 # An element for a Path, has the concat node and whether or not
33 # left or right child was visited.
34 private class PathElement
37 # Was the left child visited ?
39 # Was the right child visited ?
44 private abstract class RopeNode
49 # Node that represents a concatenation between two nodes (of any RopeNode type)
53 # Left child of the node
54 var _left
: nullable RopeNode = null
55 # Right child of the node
56 var _right
: nullable RopeNode = null
58 fun left
: nullable RopeNode do return _left
59 fun right
: nullable RopeNode do return _right
61 fun left
=(l
: RopeNode)
65 if _right
!= null then length
+= _right
.length
68 fun right
=(r
: RopeNode)
72 if _left
!= null then length
+= _left
.length
76 # Leaf of a Rope, contains a FlatString
80 # Encapsulated FlatString in the leaf node
83 init(val
: FlatString) do
90 # Basic structure, binary tree with a root node.
92 # Also shared services by subsequent implementations.
96 # Root node, entry point of a Rope.
97 private var root
: RopeNode
102 # Creates a new Rope with `s` as root
103 init from
(s
: String) do
104 if s
isa RopeString then root
= s
.root
else root
= new Leaf(s
.as(FlatString))
107 private init from_root
(r
: RopeNode)
112 redef fun length
do return root
.length
114 # Path to the Leaf for `position`
115 private fun node_at
(position
: Int): Path
117 assert position
>= 0 and position
< length
118 return get_node_from
(root
.as(not null), 0, position
, new List[PathElement])
121 # Builds the path to Leaf at position `seek_pos`
122 private fun get_node_from
(node
: RopeNode, curr_pos
: Int, seek_pos
: Int, stack
: List[PathElement]): Path
125 if node
isa Leaf then return new Path(node
, seek_pos
- curr_pos
, stack
)
126 node
= node
.as(Concat)
128 if node
.left
!= null then
129 var next_pos
= curr_pos
+ node
.left
.length
130 stack
.add
(new PathElement(node
))
131 if next_pos
> seek_pos
then
132 stack
.last
.left
= true
133 return get_node_from
(node
.left
.as(not null), curr_pos
, seek_pos
, stack
)
135 stack
.last
.right
= true
136 return get_node_from
(node
.right
.as(not null), next_pos
, seek_pos
, stack
)
138 var vis
= new PathElement(node
)
141 return get_node_from
(node
.right
.as(not null), curr_pos
, seek_pos
, stack
)
147 # Rope that cannot be modified
152 redef fun to_s
do return self
154 # Adds `s` at the end of self
155 fun append
(s
: String): String
157 if self.is_empty
then return s
158 return new RopeString.from_root
(append_to_path
(root
,s
))
161 # Builds a new path from root to the rightmost node with s appended
162 private fun append_to_path
(node
: RopeNode, s
: String): RopeNode
165 if node
isa Leaf then
167 if s
isa FlatString then cct
.right
= new Leaf(s
) else cct
.right
= s
.as(RopeString).root
168 else if node
isa Concat then
169 var right
= node
.right
170 if node
.left
!= null then cct
.left
= node
.left
.as(not null)
171 if right
== null then
172 if s
isa FlatString then cct
.right
= new Leaf(s
) else cct
.right
= s
.as(RopeString).root
174 cct
.right
= append_to_path
(right
, s
)