lib/standard/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 # 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)
  14 #
  15 # A rope is a kind of string but instead of being flat, it relies on a binary tree structure to store data.
  16 module ropes
  17
  18 intrude import string
  19
  20 # A node for a Rope
  21 private abstract class RopeNode
  22         # Length of the node
  23         var length = 0
  24 end
  25
  26 # Node that represents a concatenation between two nodes (of any RopeNode type)
  27 private class Concat
  28         super RopeNode
  29
  30         # Left child of the node
  31         var _left: nullable RopeNode = null
  32         # Right child of the node
  33         var _right: nullable RopeNode = null
  34
  35         fun left: nullable RopeNode do return _left
  36         fun right: nullable RopeNode do return _right
  37
  38         fun left=(l: RopeNode)
  39         do
  40                 _left = l
  41                 length = l.length
  42                 if _right != null then length += _right.length
  43         end
  44
  45         fun right=(r: RopeNode)
  46         do
  47                 _right = r
  48                 length = r.length
  49                 if _left != null then length += _left.length
  50         end
  51 end
  52
  53 # Leaf of a Rope, contains a FlatString
  54 private class Leaf
  55         super RopeNode
  56
  57         # Encapsulated FlatString in the leaf node
  58         var str: FlatString
  59
  60         init(val: FlatString) do
  61                 self.str = val
  62                 length = str.length
  63         end
  64
  65 end
  66