skip_list.rb

class LinkedList
  include Enumerable

  def initialize(head, tail)
    @head = head
    @tail = tail
  end

  attr_reader :head
  attr_reader :tail

  def each
    return to_enum(:each) unless block_given?
    each_node do |x|
      yield x.head
    end
  end

  def each_node(&block)
    return to_enum(:each_node) unless block

    x = self
    while x
      yield x
      x = x.tail
    end
  end

  def insert(x)
    @tail = LinkedList.new(x, @tail)
  end
end

class SkipList
  include Enumerable

  Node = Struct.new(:value, :below) do
    include Comparable
    def <=>(other)
      value <=> other.value if other.is_a? Node
    end
  end

  def initialize
    @lists = [nil]
  end

  def <<(x)
    insert(x)
    self
  end

  def include?(x)
    i = @lists.size - 1

    start = @lists[i]
    return true if i > 0 and start.head.value == x
    while i >= 1
      node = start.each_node.find { |n|
        n.tail.nil? or n.tail.head.value >= x
      }

      if node.tail && node.tail.head.value == x
        return true
      else
        start = node.head.below
      end

      i -= 1
    end

    start.include? x
  end

  def each(&block)
    return to_enum(:each) unless block
    @lists[0].each(&block) if @lists[0]
  end

  def insert(x)
    if !@lists[0] || x < @lists[0].head
      prev = x
      @lists.map! do |rest|
        head = LinkedList.new(prev, rest)
        prev = Node.new(x, head)
        head
      end
    else
      nodes = []

      i = @lists.size - 1

      start = @lists[i]
      while i >= 1
        node = start.each_node.find { |n|
          n.tail.nil? or n.tail.head.value >= x
        }

        nodes << node
        start = node.head.below

        i -= 1
      end

      bottom = start.each_node.find { |n|
        n.tail.nil? or n.tail.head >= x
      }.insert(x)

      i = nodes.size - 1
      while rand(2).zero? && i >= 0
        bottom = nodes[i].insert Node.new(x, bottom)
        i -= 1
      end

      if i < 0
        while rand(2).zero?
          @lists << LinkedList.new(Node.new(@lists[0].head, @lists.last), nil)
          bottom = @lists.last.insert Node.new(x, bottom)
        end
      end
    end
  end
end

welcome back.