lib/splay_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 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
   9 # another product.
  10
  11 # Introduces a self-balancing method on Rope, using a Splay Tree
  12 module splay_ropes
  13
  14 import standard
  15 intrude import standard::ropes
  16
  17 redef class Rope
  18
  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
  22         do
  23                 var rr = r.right.as(Concat)
  24                 var rl = r.left
  25                 var pl = rr.left
  26                 var pr = rr.right
  27                 var nr = new Concat(rl, pl)
  28                 var np = new Concat(nr, pr)
  29                 return np
  30         end
  31
  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
  35         do
  36                 var rl = r.left.as(Concat)
  37                 var rr = r.right
  38                 var pr = rl.right
  39                 var pl = rl.left
  40                 var nr = new Concat(pr, rr)
  41                 var np = new Concat(pl, nr)
  42                 return np
  43         end
  44
  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
  48         do
  49                 var st = path.stack
  50                 if st.is_empty then return null
  51                 var cct = st.pop.node
  52                 while not st.is_empty do
  53                         var tmp = st.pop
  54                         var nod: Concat
  55                         if tmp.left then
  56                                 nod = new Concat(cct, tmp.node.right)
  57                                 cct = right_rotate(nod)
  58                         else
  59                                 nod = new Concat(tmp.node.left, cct)
  60                                 cct = left_rotate(nod)
  61                         end
  62                 end
  63                 return cct
  64         end
  65 end
  66
  67 redef class RopeString
  68
  69         # Inserts a String `str` at position `pos`
  70         redef fun insert_at(str, pos)
  71         do
  72                 if str.length == 0 then return self
  73                 if self.length == 0 then return new RopeString.from(str)
  74
  75                 assert pos >= 0 and pos <= length
  76
  77                 var path = node_at(pos)
  78
  79                 var last_concat: Concat
  80
  81                 if path.offset == 0 then
  82                         if str isa FlatString then
  83                                 last_concat = new Concat(new StringLeaf(str), path.leaf)
  84                         else
  85                                 last_concat = new Concat(str.as(RopeString).root, path.leaf)
  86                         end
  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))
  90                         else
  91                                 last_concat = new Concat(path.leaf, str.as(RopeString).root)
  92                         end
  93                 else
  94                         var s = path.leaf.str
  95                         var l_half = s.substring(0, s.length - path.offset)
  96                         var r_half = s.substring_from(s.length - path.offset)
  97                         var cct: Concat
  98                         var ll = new StringLeaf(l_half.as(FlatString))
  99                         if str isa FlatString then
 100                                 cct = new Concat(ll, new StringLeaf(str))
 101                         else
 102                                 cct = new Concat(ll, str.as(RopeString).root)
 103                         end
 104                         last_concat = new Concat(cct, new StringLeaf(r_half.as(FlatString)))
 105                 end
 106
 107                 var st = path.stack
 108
 109                 if st.is_empty then return new RopeString.from_root(last_concat)
 110
 111                 var tmp = st.pop
 112
 113                 if tmp.left then
 114                         var n = tmp.node.right
 115                         var r = new Concat(last_concat, n)
 116                         st.push(new PathElement(r))
 117                 else
 118                         var n = tmp.node.left
 119                         var r = new Concat(n, last_concat)
 120                         st.push(new PathElement(r))
 121                 end
 122
 123                 return new RopeString.from_root(splay(path).as(not null))
 124         end
 125
 126 end
 127