spec/runtime/interval_skip_list/expire_range_spec.rb

   1 require File.expand_path("#{File.dirname(__FILE__)}/spec_helper")
   2
   3 describe IntervalSkipList do
   4   it_should_behave_like "the palindromic fixture"
   5
   6   describe "#overlapping" do
   7     it "returns intervals :d, :e, :f, and :g for 7..9" do
   8       list.overlapping(7..9)[0].should have_markers(:d, :e, :f, :g)
   9     end
  10
  11     it "returns intervals :b, :c, :d, :e, :f, and :g for 3..7" do
  12       list.overlapping(3..7)[0].should have_markers(:b, :c, :d, :e, :f, :g )
  13     end
  14
  15     it "returns intervals :b, :c, :d, :e, :f, and :g for 3..6" do
  16       list.overlapping(3..6)[0].should have_markers(:b, :c, :d, :e, :f, :g )
  17     end
  18
  19     describe ", when :x is inserted on 3..7" do
  20       before do
  21         list.insert(3..7, :x)
  22       end
  23
  24       it "returns intervals :b, :c, :d, :e, :f, :x for 3..5" do
  25         list.overlapping(3..5)[0].should have_markers(:b, :c, :d, :e, :f, :x)
  26       end
  27     end
  28   end
  29
  30
  31   describe "when 7..7 is expired with a length change of 0" do
  32     before do
  33       list.expire(7..7, 0)
  34     end
  35
  36     describe " #nodes" do
  37       attr_reader :nodes, :node
  38
  39       before do
  40         @nodes = list.nodes
  41       end
  42
  43       it "has a size of 4" do
  44         nodes.size.should == 4
  45       end
  46
  47       describe "[0]" do
  48         before do
  49           @node = nodes[0]
  50         end
  51
  52         it "has a key of 1 and a height of 3" do
  53           node.key.should == 1
  54           node.height.should == 3
  55         end
  56
  57         it "has no forward markers at level 0" do
  58           node.forward_markers[0].should be_empty
  59         end
  60
  61         it "has :a and :b as its only forward markers on level 1" do
  62           node.forward_markers[1].should have_markers(:a, :b)
  63         end
  64
  65         it "has :c as its only forward marker on level 2" do
  66           node.forward_markers[2].should have_markers(:c)
  67         end
  68
  69         it "has no markers" do
  70           node.markers.should be_empty
  71         end
  72       end
  73
  74       describe "[1]" do
  75         before do
  76           @node = nodes[1]
  77         end
  78
  79         it "has a key of 3 and a height of 2" do
  80           node.key.should == 3
  81           node.height.should == 2
  82         end
  83
  84         it "has :b as its only forward marker on level 0" do
  85           node.forward_markers[0].should have_markers(:b)
  86         end
  87
  88         it "has no forward markers on level 1" do
  89           node.forward_markers[1].should be_empty
  90         end
  91
  92         it "has :a and :b as its only markers" do
  93           node.markers.should have_markers(:a, :b)
  94         end
  95       end
  96
  97       describe "[2]" do
  98         before do
  99           @node = nodes[2]
 100         end
 101
 102         it "has a key of 5 and a height of 1" do
 103           node.key.should == 5
 104           node.height.should == 1
 105         end
 106
 107         it "has no forward markers on level 0" do
 108           node.forward_markers[0].should be_empty
 109         end
 110
 111         it "has :b as its only marker" do
 112           node.markers.should have_markers(:b)
 113         end
 114       end
 115
 116       describe "[3]" do
 117         before do
 118           @node = nodes[3]
 119         end
 120
 121         it "has a key of 7 and a height of 3" do
 122           node.key.should == 7
 123           node.height.should == 3
 124         end
 125
 126         it "has no forward markers at any level" do
 127           node.forward_markers[0].should be_empty
 128           node.forward_markers[1].should be_empty
 129           node.forward_markers[2].should be_empty
 130         end
 131
 132         it "has :c as its only marker" do
 133           node.markers.should have_markers(:c)
 134         end
 135       end
 136     end
 137   end
 138
 139   describe "when 4..4 is expired with a length change of 2" do
 140     before do
 141       list.expire(4..4, 2)
 142     end
 143
 144     describe " #nodes" do
 145       attr_reader :nodes, :node
 146
 147       before do
 148         @nodes = list.nodes
 149       end
 150
 151       it "has a size of 4" do
 152         nodes.size.should == 4
 153       end
 154
 155       describe "[0]" do
 156         before do
 157           @node = nodes[0]
 158         end
 159
 160         it "has a key of 1 and a height of 3" do
 161           node.key.should == 1
 162           node.height.should == 3
 163         end
 164
 165         it "has no forward markers at level 0 and 2" do
 166           node.forward_markers[0].should be_empty
 167           node.forward_markers[2].should be_empty
 168         end
 169
 170         it "has :a as its only forward marker on level 1" do
 171           node.forward_markers[1].should have_markers(:a)
 172         end
 173
 174         it "has no markers" do
 175           node.markers.should be_empty
 176         end
 177       end
 178
 179       describe "[1]" do
 180         before do
 181           @node = nodes[1]
 182         end
 183
 184         it "has a key of 3 and a height of 2" do
 185           node.key.should == 3
 186           node.height.should == 2
 187         end
 188
 189         it "has no forward markers at any level" do
 190           node.forward_markers[0].should be_empty
 191           node.forward_markers[1].should be_empty
 192         end
 193
 194         it "has :a as its only marker" do
 195           node.markers.should have_markers(:a)
 196         end
 197       end
 198
 199       describe "[2]" do
 200         before do
 201           @node = nodes[2]
 202         end
 203
 204         it "has a key of 7 and a height of 1" do
 205           node.key.should == 7
 206           node.height.should == 1
 207         end
 208
 209         it "has :g as its only forward marker at level 0" do
 210           node.forward_markers[0].should have_markers(:g)
 211         end
 212
 213         it "has no markers" do
 214           node.markers.should be_empty
 215         end
 216       end
 217
 218       describe "[3]" do
 219         before do
 220           @node = nodes[3]
 221         end
 222
 223         it "has a key of 15 and a height of 3" do
 224           node.key.should == 15
 225           node.height.should == 3
 226         end
 227
 228         it "has no forward markers at any level" do
 229           node.forward_markers[0].should be_empty
 230           node.forward_markers[1].should be_empty
 231           node.forward_markers[2].should be_empty
 232         end
 233
 234         it "has :g as its only marker" do
 235           node.markers.should have_markers(:g)
 236         end
 237       end
 238     end
 239   end
 240
 241   describe "when :x is inserted on 1..5, :y on 7..11, and :z on 9..13" do
 242     before do
 243       list.insert(1..5, :x)
 244       list.insert(7..11, :y)
 245       list.insert(9..13, :z)
 246     end
 247
 248     describe "when 4..8 is expired with a length change of -3" do
 249       before do
 250         list.expire(4..8, -3)
 251       end
 252
 253       describe "#nodes" do
 254         attr_reader :nodes, :node
 255         before do
 256           @nodes = list.nodes
 257         end
 258
 259         it "has a size of 4" do
 260           nodes.size.should == 4
 261         end
 262
 263         describe "[0]" do
 264           before do
 265             @node = nodes[0]
 266           end
 267
 268           it "has a key of 1 and height of 3" do
 269             node.key.should == 1
 270             node.height.should == 3
 271           end
 272
 273           it "has :a as its only forward marker on level 1" do
 274             node.forward_markers[1].should have_markers(:a)
 275           end
 276
 277           it "has no forward markers at level 0 and 2" do
 278             node.forward_markers[0].should be_empty
 279             node.forward_markers[2].should be_empty
 280           end
 281
 282           it "has no markers" do
 283             node.markers.should be_empty
 284           end
 285         end
 286
 287         describe "[1]" do
 288           before do
 289             @node = nodes[1]
 290           end
 291
 292           it "has a key of 3 and height of 2" do
 293             node.key.should == 3
 294             node.height.should == 2
 295           end
 296
 297           it "has no forward markers" do
 298             node.forward_markers[0].should be_empty
 299             node.forward_markers[1].should be_empty
 300           end
 301
 302           it "has :a as its only marker" do
 303             node.markers.should have_markers(:a)
 304           end
 305         end
 306
 307         describe "[2]" do
 308           before do
 309             @node = nodes[2]
 310           end
 311
 312           it "has a key of 6 and a height of 1" do
 313             node.key.should == 6
 314             node.height.should == 1
 315           end
 316
 317           it "has :z as its only forward marker at level 0" do
 318             node.forward_markers[0].should have_markers(:z)
 319           end
 320
 321           it "has no markers" do
 322             node.markers.should be_empty
 323           end
 324         end
 325
 326         describe "[3]" do
 327           before do
 328             @node = nodes[3]
 329           end
 330
 331           it "has a key of 10 and height of 3" do
 332             node.key.should == 10
 333             node.height.should == 3
 334           end
 335
 336           it "has no forward markers at any level" do
 337             node.forward_markers[0].should be_empty
 338             node.forward_markers[1].should be_empty
 339             node.forward_markers[2].should be_empty
 340           end
 341
 342           it "has :z as its only marker" do
 343             node.markers.should have_markers(:z)
 344           end
 345         end
 346       end
 347     end
 348   end
 349 end