insert_spec.rb

require File.expand_path("#{File.dirname(__FILE__)}/spec_helper")

describe IntervalSkipList, " when #next_node_height returns 1, 3, 2, 3, 1 in order" do
  include IntervalSkipListSpecHelper
  attr_reader :list, :node

  before do
    @list = IntervalSkipList.new
  end

  it_should_behave_like "#next_node_height is deterministic"

  def expected_node_heights
    [1, 3, 2, 3, 1]
  end

  describe ", when :a is inserted on 1..7" do
    before do
      list.insert(1..7, :a)
    end

    describe ", #containing" do
      it "returns only :a from 2 through 6" do
        (2..6).should contain_marker(:a)
      end

      it "returns nothing at 1 and 7" do
        list.containing(1).should be_empty
        list.containing(7).should be_empty
      end
    end

    describe " #nodes[0]" do
      before do
        @node = list.nodes[0]
      end

      it "has a key of 1 and height of 1" do
        node.key.should == 1
        node.height.should == 1
      end

      it "has :a as its only marker at level 0" do
        node.forward_markers[0].should have_marker(:a)
      end

      it "has no markers" do
        node.markers.should be_empty
      end

      it "is an endpoint of only :a" do
        node.endpoint_of.should have_marker(:a)
      end
    end

    describe " #nodes[1]" do
      before do
        @node = list.nodes[1]
      end

      it "has a key of 7 and height of 3" do
        node.key.should == 7
        node.height.should == 3
      end

      it "has no forward markers at any level" do
        node.forward_markers[0].should be_empty
        node.forward_markers[1].should be_empty
        node.forward_markers[2].should be_empty
      end

      it "has :a as its only marker" do
        node.markers.should have_marker(:a)
      end

      it "is an endpoint of only :a" do
        node.endpoint_of.should have_marker(:a)
      end
    end

    describe ", and then :b is inserted on 1..5" do
      before do
        list.insert(1..5, :b)
      end

      describe ", #containing" do
        it "returns only :a and :b from 2 through 4" do
          (2..4).should contain_markers(:a, :b)
        end

        it "returns only :a from 5 through 6" do
          (5..6).should contain_marker(:a)
        end

        it "returns nothing at 1 and 7" do
          list.containing(1).should be_empty
          list.containing(7).should be_empty
        end
      end

      describe " #nodes[0]" do
        before do
          @node = list.nodes[0]
        end

        it "has a key of 1 and height of 1" do
          node.key.should == 1
          node.height.should == 1
        end

        it "has :a and :b as its only forward markers at level 0" do
          node.forward_markers[0].should have_markers(:a, :b)
        end

        it "has no markers" do
          node.markers.should be_empty
        end

        it "is an endpoint of only :a and :b" do
          node.endpoint_of.should have_markers(:a, :b)
        end
      end

      describe " #nodes[1]" do
        before do
          @node = list.nodes[1]
        end

        it "has a key of 5 and height of 2" do
          node.key.should == 5
          node.height.should == 2
        end

        it "has :a as its only forward marker at level 1" do
          node.forward_markers[1].should have_marker(:a)
        end

        it "has no forward markers at level 0" do
          node.forward_markers[0].should be_empty
        end

        it "has :a and :b as its only markers" do
          node.markers.should have_markers(:a, :b)
        end

        it "is an endpoint of only :b" do
          node.endpoint_of.should have_marker(:b)
        end
      end

      describe " #nodes[2]" do
        before do
          @node = list.nodes[2]
        end

        it "has a key of 7 and height of 3" do
          node.key.should == 7
          node.height.should == 3
        end

        it "has no forward markers at any level" do
          node.forward_markers[0].should be_empty
          node.forward_markers[1].should be_empty
          node.forward_markers[2].should be_empty
        end

        it "has :a its only marker" do
          node.markers.should have_marker(:a)
        end

        it "is an endpoint of only :a" do
          node.endpoint_of.should have_marker(:a)
        end
      end

      describe ", and then :c is inserted on 1..3" do
        before do
          list.insert(1..3, :c)
        end

        describe ", #containing" do
          it "returns only :a, :b, and :c for 2" do
            (2..2).should contain_markers(:a, :b, :c)
          end

          it "returns only :a, :b from 3..4" do
            (3..4).should contain_markers(:a, :b)
          end

          it "returns only :a from 5..6" do
            (5..6).should contain_markers(:a)
          end

          it "returns nothing at 1 and 7" do
            list.containing(1).should be_empty
            list.containing(7).should be_empty
          end
        end

        describe " #nodes[0]" do
          before do
            @node = list.nodes[0]
          end

          it "has a key of 1 and height of 1" do
            node.key.should == 1
            node.height.should == 1
          end

          it "has :a, :b, :c as its only forward markers at level 0" do
            node.forward_markers[0].should have_markers(:a, :b, :c)
          end

          it "has no markers" do
            node.markers.should be_empty
          end

          it "is an endpoint of only :a, :b, :c" do
            node.endpoint_of.should have_markers(:a, :b, :c)
          end
        end

        describe " #nodes[1]" do
          before do
            @node = list.nodes[1]
          end

          it "has a key of 3 and height of 3" do
            node.key.should == 3
            node.height.should == 3
          end

          it "has :a as its only forward marker at level 2" do
            node.forward_markers[2].should have_marker(:a)
          end

          it "has :b as its only forward marker at level 1" do
            node.forward_markers[1].should have_marker(:b)
          end

          it "has no forward markers at level 0" do
            node.forward_markers[0].should be_empty
          end

          it "has :a, :b, and :c as its only markers" do
            node.markers.should have_markers(:a, :b, :c)
          end

          it "is an endpoint of only :c" do
            node.endpoint_of.should have_marker(:c)
          end
        end

        describe " #nodes[2]" do
          before do
            @node = list.nodes[2]
          end

          it "has a key of 5 and height of 2" do
            node.key.should == 5
            node.height.should == 2
          end

          it "has no forward markers at any level" do
            node.forward_markers[0].should be_empty
            node.forward_markers[1].should be_empty
          end

          it "has :b as its only markers" do
            node.markers.should have_marker(:b)
          end

          it "is an endpoint of only :b" do
            node.endpoint_of.should have_marker(:b)
          end
        end

        describe " #nodes[3]" do
          before do
            @node = list.nodes[3]
          end

          it "has a key of 7 and height of 3" do
            node.key.should == 7
            node.height.should == 3
          end

          it "has no forward markers at any level" do
            node.forward_markers[0].should be_empty
            node.forward_markers[1].should be_empty
            node.forward_markers[2].should be_empty
          end

          it "has :a as its only marker" do
            node.markers.should have_marker(:a)
          end

          it "is an endpoint of only :a" do
            node.endpoint_of.should have_marker(:a)
          end
        end

        describe ", and then :d is inserted on 1..9" do
          before do
            list.insert(1..9, :d)
          end

          describe ", #containing" do
            it "returns only :a, :b, :c, and :d for 2" do
              (2..2).should contain_markers(:a, :b, :c, :d)
            end

            it "returns only :a, :b from 3..4" do
              (3..4).should contain_markers(:a, :b, :d)
            end

            it "returns only :a from 5..6" do
              (5..6).should contain_markers(:a, :d)
            end

            it "returns only :a from 7..8" do
              (7..8).should contain_markers(:d)
            end

            it "returns nothing at 1 and 9" do
              list.containing(1).should be_empty
              list.containing(9).should be_empty
            end

            it "returns nothing for -1, 0, and 10" do
              list.containing(-1).should be_empty
              list.containing(0).should be_empty
              list.containing(10).should be_empty
            end
          end

          describe " #nodes[0]" do
            before do
              @node = list.nodes[0]
            end

            it "has a key of 1 and height of 1" do
              node.key.should == 1
              node.height.should == 1
            end

            it "has :a, :b, :c, :d as its only forward markers at level 0" do
              node.forward_markers[0].should have_markers(:a, :b, :c, :d)
            end

            it "has no markers" do
              node.markers.should be_empty
            end

            it "is an endpoint of only :a, :b, :c, and :d" do
              node.endpoint_of.should have_markers(:a, :b, :c, :d)
            end
          end

          describe " #nodes[1]" do
            before do
              @node = list.nodes[1]
            end

            it "has a key of 3 and height of 3" do
              node.key.should == 3
              node.height.should == 3
            end

            it "has :a and :d as its only forward markers at level 2" do
              node.forward_markers[2].should have_markers(:a, :d)
            end

            it "has :b as its only marker at level 1" do
              node.forward_markers[1].should have_marker(:b)
            end

            it "has no forward markers at level 0" do
              node.forward_markers[0].should be_empty
            end

            it "has :a, :b, :c, :d as its only markers" do
              node.markers.should have_markers(:a, :b, :c, :d)
            end

            it "is an endpoint of only :c" do
              node.endpoint_of.should have_marker(:c)
            end
          end

          describe " #nodes[2]" do
            before do
              @node = list.nodes[2]
            end

            it "has a key of 5 and height of 2" do
              node.key.should == 5
              node.height.should == 2
            end

            it "has no markers on any level" do
              node.forward_markers[0].should be_empty
              node.forward_markers[1].should be_empty
            end

            it "has :b as its only marker" do
              node.markers.should have_marker(:b)
            end

            it "is an endpoint of only :b" do
              node.endpoint_of.should have_marker(:b)
            end
          end

          describe " #nodes[3]" do
            before do
              @node = list.nodes[3]
            end

            it "has a key of 7 and height of 3" do
              node.key.should == 7
              node.height.should == 3
            end

            it "has :d as its only marker at level 0" do
              node.forward_markers[0].should have_marker(:d)
            end

            it "has no forward markers at levels 1 and 2" do
              node.forward_markers[1].should be_empty
              node.forward_markers[2].should be_empty
            end

            it "has :a, :d as its only markers" do
              node.markers.should have_markers(:a, :d)
            end

            it "is an endpoint of only :a" do
              node.endpoint_of.should have_marker(:a)
            end
          end

          describe " #nodes[4]" do
            before do
              @node = list.nodes[4]
            end

            it "has a key of 9 and height of 1" do
              node.key.should == 9
              node.height.should == 1
            end

            it "has no forward markers at level 0" do
              node.forward_markers[0].should be_empty
            end

            it "has :d as its only marker" do
              node.markers.should have_marker(:d)
            end

            it "is an endpoint of only :d" do
              node.endpoint_of.should have_marker(:d)
            end
          end

          describe ", and then :d is deleted" do
            before do
              list.delete(:d)
            end

            it "has only 4 nodes" do
              list.nodes.size.should == 4
            end

            describe " #nodes[0]" do
              before do
                @node = list.nodes[0]
              end

              it "has a key of 1 and height of 1" do
                node.key.should == 1
                node.height.should == 1
              end

              it "has :a, :b, and :c as its only forward markers at level 0" do
                node.forward_markers[0].should have_markers(:a, :b, :c)
              end
            end

            describe " #nodes[1]" do
              before do
                @node = list.nodes[1]
              end

              it "has a key of 3 and height of 3" do
                node.key.should == 3
                node.height.should == 3
              end

              it "has :a as its only forward marker at level 2" do
                node.forward_markers[2].should have_marker(:a)
              end

              it "has :b as its only forward marker at level 1" do
                node.forward_markers[1].should have_marker(:b)
              end

              it "has no forward markers at level 0" do
                node.forward_markers[0].should be_empty
              end

              it "has :a, :b, and :c as its only markers" do
                node.markers.should have_markers(:a, :b, :c)
              end

              it "is the endpoint of only :c" do
                node.endpoint_of.should have_marker(:c)
              end
            end

            describe " #nodes[2]" do
              before do
                @node = list.nodes[2]
              end

              it "has a key of 5 and height of 2" do
                node.key.should == 5
                node.height.should == 2
              end

              it "has no forward markers at any level" do
                node.forward_markers[0].should be_empty
                node.forward_markers[1].should be_empty
              end

              it "has :b as its only marker" do
                node.markers.should have_marker(:b)
              end

              it "is the endpoint of only :b" do
                node.endpoint_of.should have_marker(:b)
              end
            end

            describe " #nodes[3]" do
              before do
                @node = list.nodes[3]
              end

              it "has a key of 7 and height of 3" do
                node.key.should == 7
                node.height.should == 3
              end

              it "has no forward markers at any level" do
                node.forward_markers[0].should be_empty
                node.forward_markers[1].should be_empty
                node.forward_markers[2].should be_empty
              end

              it "has :a as its only marker" do
                node.markers.should have_marker(:a)
              end

              it "is the endpoint of only :a" do
                node.endpoint_of.should have_marker(:a)
              end
            end

            describe ", and then :c is deleted" do
              before do
                list.delete(:c)
              end

              it "has only 3 nodes" do
                list.nodes.size.should == 3
              end

              describe " #nodes[0]" do
                before do
                  @node = list.nodes[0]
                end

                it "has a key of 1 and height of 1" do
                  node.key.should == 1
                  node.height.should == 1
                end

                it "has :a and :b as its only forward markers at level 0" do
                  node.forward_markers[0].should have_markers(:a, :b)
                end

                it "has no markers" do
                  node.markers.should be_empty
                end

                it "is an endpoint of only :a and :b" do
                  node.endpoint_of.should have_markers(:a, :b)
                end
              end

              describe " #nodes[1]" do
                before do
                  @node = list.nodes[1]
                end

                it "has a key of 5 and height of 2" do
                  node.key.should == 5
                  node.height.should == 2
                end

                it "has :a as its only forward marker at level 1" do
                  node.forward_markers[1].should have_marker(:a)
                end

                it "has no forward markers at level 0" do
                  node.forward_markers[0].should be_empty
                end

                it "has :a and :b as its only markers" do
                  node.markers.should have_markers(:a, :b)
                end

                it "is an endpoint of only :b" do
                  node.endpoint_of.should have_marker(:b)
                end
              end

              describe " #nodes[2]" do
                before do
                  @node = list.nodes[2]
                end

                it "has a key of 7 and height of 3" do
                  node.key.should == 7
                  node.height.should == 3
                end

                it "has no forward markers at any level" do
                  node.forward_markers[0].should be_empty
                  node.forward_markers[1].should be_empty
                  node.forward_markers[2].should be_empty
                end

                it "has :a its only marker" do
                  node.markers.should have_marker(:a)
                end

                it "is an endpoint of only :a" do
                  node.endpoint_of.should have_marker(:a)
                end
              end
            end
          end
        end
      end
    end
  end
end