lib/bufferized_ropes.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   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
   9 # another product.
  10
  11 # Introduces ropes with buffered leaves
  12 module bufferized_ropes
  13
  14 import standard
  15 intrude import standard::ropes
  16
  17 # Leaf containing a FlatBuffer to optimize concatenation operations
  18 private class BufferLeaf
  19         super Leaf
  20
  21         init(val: FlatBuffer) do
  22                 self.str = val
  23                 length = str.length
  24         end
  25
  26 end
  27
  28 redef class Concat
  29         redef fun to_leaf
  30         do
  31                 if left == null then
  32                         if right == null then return new StringLeaf("".as(FlatString))
  33                         return right.to_leaf
  34                 end
  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)
  41                 else
  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))
  46                 end
  47         end
  48 end
  49
  50 redef class FlatText
  51
  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
  55
  56         # Same as substring_from, but without copy of the data for Buffers.
  57         private fun lazy_substring_from(from: Int): FlatString is abstract
  58 end
  59
  60 redef class FlatBuffer
  61
  62         # Same as to_s, only will not copy self before returning a String.
  63         private fun lazy_to_s(len: Int): FlatString
  64         do
  65                 return new FlatString.with_infos(items, len, 0, length - 1)
  66         end
  67
  68         redef fun lazy_substring(from,length)
  69         do
  70                 return new FlatString.with_infos(items, length, from, from + length - 1)
  71         end
  72
  73         redef fun lazy_substring_from(from)
  74         do
  75                 var newlen = length - from
  76                 return new FlatString.with_infos(items, newlen, from, from + newlen - 1)
  77         end
  78
  79 end
  80
  81 redef class FlatString
  82
  83         redef fun lazy_substring(from, len) do return substring(from,len).as(FlatString)
  84
  85         redef fun lazy_substring_from(from) do return substring_from(from).as(FlatString)
  86
  87 end
  88
  89 redef class Rope
  90
  91         # Empty Rope
  92         init do root = new BufferLeaf(new FlatBuffer.with_capacity(buf_len))
  93
  94 end
  95
  96 redef class RopeString
  97
  98         init from(s: String) do
  99                 if s.length < buf_len then
 100                         var b = new FlatBuffer.with_capacity(buf_len)
 101                         b.append(s)
 102                         root = new BufferLeaf(b)
 103                 else
 104                         if s isa RopeString then root = s.root else root = new StringLeaf(s.as(FlatString))
 105                 end
 106         end
 107
 108         redef fun +(o) do return insert_at(o.to_s, length)
 109
 110         # Inserts a String `str` at position `pos`
 111         redef fun insert_at(str, pos)
 112         do
 113                 if str.length == 0 then return self
 114
 115                 assert pos >= 0 and pos <= length
 116
 117                 if pos == length then
 118                         var r = root
 119                         if r isa BufferLeaf then
 120                                 var b = r.str.as(FlatBuffer)
 121                                 if r.length + str.length < b.capacity then
 122                                         b.append(str)
 123                                         return new RopeString.from_root(new BufferLeaf(b))
 124                                 end
 125                         end
 126                 end
 127
 128                 var path = node_at(pos)
 129
 130                 var cct: RopeNode
 131
 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)
 136                 else
 137                         cct = build_node_other(path,str)
 138                 end
 139
 140                 if path.stack.is_empty then return new RopeString.from_root(cct)
 141
 142                 var tmp = path.stack.pop
 143                 var last_concat: Concat
 144
 145                 if tmp.left then
 146                         last_concat = new Concat(cct,tmp.node.right.as(not null))
 147                 else
 148                         last_concat = new Concat(tmp.node.left.as(not null), cct)
 149                 end
 150
 151                 for i in path.stack.reverse_iterator do
 152                         var nod: Concat
 153                         if i.left then
 154                                 nod = new Concat(last_concat, i.node.right.as(not null))
 155                         else
 156                                 nod = new Concat(i.node.left.as(not null), last_concat)
 157                         end
 158                         last_concat = nod
 159                 end
 160
 161                 return new RopeString.from_root(last_concat)
 162         end
 163
 164         redef fun substring(pos, len)
 165         do
 166                 if pos < 0 then
 167                         len += pos
 168                         pos = 0
 169                 end
 170
 171                 if pos + len > length then len = length - pos
 172
 173                 if len <= 0 then return new RopeString
 174
 175                 var path = node_at(pos)
 176
 177                 var lf = path.leaf
 178                 var offset = path.offset
 179
 180                 var s: FlatString
 181                 if lf isa StringLeaf then
 182                         s = lf.str.as(FlatString)
 183                 else
 184                         s = lf.str.as(FlatBuffer).lazy_to_s(lf.length)
 185                 end
 186
 187                 if path.leaf.str.length - offset > len then
 188                         lf = new StringLeaf(s.substring(offset,len).as(FlatString))
 189                 else
 190                         lf = new StringLeaf(s.substring_from(offset).as(FlatString))
 191                 end
 192
 193                 var nod: RopeNode = lf
 194
 195                 if lf.length == len then return new RopeString.from_root(lf)
 196
 197                 var lft: nullable RopeNode
 198                 var rht: nullable RopeNode
 199
 200                 for i in path.stack.reverse_iterator do
 201                         if i.right then continue
 202                         lft = nod
 203                         rht = i.node.right
 204                         nod = new Concat(lft, rht)
 205                 end
 206
 207                 var ret = new RopeString
 208                 ret.root = nod
 209
 210                 path = ret.node_at(len-1)
 211
 212                 offset = path.offset
 213
 214                 lf = path.leaf
 215
 216                 if lf isa StringLeaf then
 217                         s = lf.str.as(FlatString)
 218                 else
 219                         s = lf.str.as(FlatBuffer).lazy_to_s(lf.length)
 220                 end
 221
 222                 nod = new StringLeaf(s.substring(0, offset+1).as(FlatString))
 223
 224                 for i in path.stack.reverse_iterator do
 225                         if i.left then continue
 226                         rht = nod
 227                         lft = i.node.left
 228                         nod = new Concat(lft, rht)
 229                 end
 230
 231                 ret.root = nod
 232
 233                 return ret
 234         end
 235
 236         private fun build_node_zero_offset(path: Path, s: String): RopeNode
 237         do
 238                 var finlen = path.leaf.length + s.length
 239                 if finlen <= buf_len then
 240                         var b = new FlatBuffer.with_capacity(buf_len)
 241                         b.append(s)
 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)
 245                 end
 246                 var rht = path.leaf
 247                 var lft: RopeNode
 248                 if s isa FlatString then
 249                         if s.length > buf_len then
 250                                 lft = new StringLeaf(s)
 251                         else
 252                                 var b = new FlatBuffer
 253                                 b.append(s)
 254                                 lft = new BufferLeaf(b)
 255                         end
 256                 else
 257                         lft = s.as(RopeString).root
 258                 end
 259                 return new Concat(lft, rht)
 260         end
 261
 262         private fun build_node_len_offset(path: Path, s: String): RopeNode
 263         do
 264                 var leaf = path.leaf
 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))
 269                                 else
 270                                         return new Concat(leaf, s.as(Rope).root)
 271                                 end
 272                         end
 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))
 281                                 buf = b
 282                         end
 283                         if finlen <= cap then
 284                                 buf.append(s)
 285                                 if finlen == buf_len then return new StringLeaf(buf.lazy_to_s(finlen))
 286                                 return new BufferLeaf(buf)
 287                         else
 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)
 295                                 return cct
 296                         end
 297                 else
 298                         var lft = leaf
 299                         var rht: RopeNode
 300                         if s.length >= buf_len then
 301                                 if s isa FlatString then rht = new StringLeaf(s) else rht = s.as(Rope).root
 302                         else
 303                                 var buf = new FlatBuffer.with_capacity(buf_len)
 304                                 buf.append(s)
 305                                 rht = new BufferLeaf(buf)
 306                         end
 307                         return new Concat(lft,rht)
 308                 end
 309         end
 310
 311         private fun build_node_other(path: Path,str: String): RopeNode
 312         do
 313                 var lf = path.leaf
 314                 var s: FlatString
 315                 if lf isa BufferLeaf then
 316                         var b = lf.str.as(FlatBuffer)
 317                         s = b.lazy_to_s(lf.length)
 318                 else
 319                         s = lf.str.as(FlatString)
 320                 end
 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)
 325                         buf.append(l_str)
 326                         buf.append(str)
 327                         buf.append(r_str)
 328                         return new BufferLeaf(buf)
 329                 end
 330                 var child: RopeNode
 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))
 334                 return r_cct
 335         end
 336
 337 end
 338
 339 redef class SubstringsIterator
 340
 341         # Compute the bounds of the current substring and makes the substring
 342         redef fun make_substring
 343         do
 344                 var l = nodes.item
 345                 var s = l.str
 346                 var min = 0
 347                 var length = l.length
 348                 if nodes.index < pos then
 349                         min = pos - nodes.index
 350                 end
 351                 substring = s.lazy_substring(min, length)
 352         end
 353
 354 end
 355
 356 redef class ReverseSubstringsIterator
 357
 358         redef fun make_substring
 359         do
 360                 var l = leaves.item
 361                 var s = l.str
 362                 if pos > (leaves.index + l.length - 1) then return
 363                 str = s.lazy_substring(0, (pos - leaves.index + 1))
 364         end
 365
 366 end
 367
 368 # Default size of a buffer in a rope leaf.
 369 fun buf_len: Int do return 200
 370