eef9360a05e4cfb6a21ae740baa9421747374538
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.
21 private abstract class RopeNode
26 # Node that represents a concatenation between two nodes (of any RopeNode type)
30 # Left child of the node
31 var _left
: nullable RopeNode = null
32 # Right child of the node
33 var _right
: nullable RopeNode = null
35 fun left
: nullable RopeNode do return _left
36 fun right
: nullable RopeNode do return _right
38 fun left
=(l
: RopeNode)
42 if _right
!= null then length
+= _right
.length
45 fun right
=(r
: RopeNode)
49 if _left
!= null then length
+= _left
.length
53 # Leaf of a Rope, contains a FlatString
57 # Encapsulated FlatString in the leaf node
60 init(val
: FlatString) do
67 # Basic structure, binary tree with a root node.
69 # Also shared services by subsequent implementations.
73 # Root node, entry point of a Rope.
74 private var root
: RopeNode
79 # Creates a new Rope with `s` as root
80 init from
(s
: String) do
81 if s
isa RopeString then root
= s
.root
else root
= new Leaf(s
.as(FlatString))
84 private init from_root
(r
: RopeNode)
89 redef fun length
do return root
.length
92 # Rope that cannot be modified
97 redef fun to_s
do return self