tests/splay_test.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 intrude import splay_ropes
  12 intrude import standard::ropes
  13 intrude import ropes_debug
  14
  15 redef class Leaf
  16         redef fun to_dot(s): String
  17         do
  18                 s += "[label = \"{str}\" shape = rect];\n"
  19                 s += " -> [label = \"contains\"];\n"
  20                 s = str.to_dot(s)
  21                 return s
  22         end
  23 end
  24
  25 redef class Concat
  26         redef fun to_dot(s): String
  27         do
  28                 s += "[label = {length}];\n"
  29                 if left != null then
  30                         s += " ->  [label = \"left\"];\n"
  31                         s = left.to_dot(s)
  32                 end
  33                 if right != null then
  34                         s += " ->  [label = \"right\"];\n"
  35                         s = right.to_dot(s)
  36                 end
  37                 return s
  38         end
  39 end
  40
  41 redef class FlatString
  42         redef fun to_dot(s: String): String
  43         do
  44                 return s + " [label=\"FlatString\\nindex_from = {index_from}\\nindex_to = {index_to}\\nNativeString = {items.to_s_with_length(items.cstring_length)}\"];\n"
  45         end
  46 end
  47
  48 redef class FlatBuffer
  49         redef fun to_dot(s: String): String
  50         do
  51                 return s + " [label=\"FlatBuffer\\length = {length}\\ncapacity = {capacity}\\nitems = {items.to_s_with_length(items.cstring_length)}\"];\n"
  52         end
  53 end
  54
  55
  56 redef class RopeString
  57
  58         redef fun to_dot(f)
  59         do
  60                 var ret: String = new RopeString.from("digraph g \{\n")
  61                 ret = root.to_dot(ret).as(RopeString)
  62                 ret += "\}\n"
  63                 print ret
  64                 return ret
  65         end
  66
  67 end
  68
  69 var ab = new StringLeaf("AB".as(FlatString))
  70 var cd = new StringLeaf("CD".as(FlatString))
  71 var ef = new StringLeaf("EF".as(FlatString))
  72 var gh = new StringLeaf("GH".as(FlatString))
  73
  74 # Zig test
  75
  76 var c = new Concat(cd,ef)
  77 c = new Concat(ab,c)
  78 var ro = new RopeString.from_root(c)
  79
  80 ro.to_dot("Zig-Before_splay.dot")
  81 print ro
  82
  83 var p = ro.node_at(5)
  84
  85 ro = new RopeString.from_root(ro.splay(p).as(not null))
  86
  87 ro.to_dot("Zig-After_splay.dot")
  88 print ro
  89
  90 # Zig-zig test left left
  91
  92 var d = new Concat(ab,cd)
  93 var e = new Concat(d,ef)
  94 var f = new Concat(e,gh)
  95 ro = new RopeString.from_root(f)
  96
  97 p = ro.node_at(0)
  98
  99 print ro
 100 ro.to_dot("Zig-zigll-Before_splay.dot")
 101
 102 ro = new RopeString.from_root(ro.splay(p).as(not null))
 103
 104 print ro
 105 ro.to_dot("Zig-zigll-After_splay.dot")
 106
 107 # Zig-zig test right right
 108
 109 d = new Concat(ef,gh)
 110 e = new Concat(cd,d)
 111 f = new Concat(ab,e)
 112 ro = new RopeString.from_root(f)
 113
 114 p = ro.node_at(7)
 115
 116 print ro
 117 ro.to_dot("Zig-zigrr-Before_splay.dot")
 118
 119 ro = new RopeString.from_root(ro.splay(p).as(not null))
 120
 121 print ro
 122 ro.to_dot("Zig-zigrr-After_splay.dot")
 123
 124 # Zig-zag test left right
 125
 126 d = new Concat(cd,ef)
 127 e = new Concat(ab,d)
 128 f = new Concat(e,gh)
 129 ro = new RopeString.from_root(f)
 130
 131 p = ro.node_at(4)
 132
 133 print ro
 134 ro.to_dot("Zig-zaglr-Before_splay.dot")
 135
 136 ro = new RopeString.from_root(ro.splay(p).as(not null))
 137
 138 print ro
 139 ro.to_dot("Zig-zaglr-After_splay.dot")
 140
 141 # Zig-zag test right left
 142
 143 d = new Concat(cd,ef)
 144 e = new Concat(d,gh)
 145 f = new Concat(ab,e)
 146 ro = new RopeString.from_root(f)
 147
 148 p = ro.node_at(4)
 149
 150 print ro
 151 ro.to_dot("Zig-zagrl-Before_splay.dot")
 152
 153 ro = new RopeString.from_root(ro.splay(p).as(not null))
 154
 155 print ro
 156 ro.to_dot("Zig-zagrl-After_splay.dot")
 157