bitmap.rb

class Vocabulary
  def initialize
    @words = []
    @index = {}
  end

  def <<(word)
    unless @index[word]
      @index[word] = @words.length
      @words << word
    end
    self
  end

  def index(word)
    @index[word]
  end

  def each_with_index(&block)
    @words.each_with_index &block
  end
end

class Document
  def initialize(vocabulary, initial_bitmap=0)
    @vocabulary = vocabulary
    @bitmap = initial_bitmap
  end

  attr_reader :vocabulary
  attr_reader :bitmap

  def index(word)
    @vocabulary.index(word)
  end

  def <<(word)
    unless (i = index(word))
      @vocabulary << word
      i = index(word)
    end
    @bitmap |= 1 << i
    self
  end

  def &(document)
    check_compatibility(document)
    self.class.new(vocabulary, @bitmap & document.bitmap)
  end

  def |(document)
    check_compatibility(document)
    self.class.new(vocabulary, @bitmap | document.bitmap)
  end

  def ^(document)
    check_compatibility(document)
    self.class.new(vocabulary, @bitmap ^ document.bitmap)
  end

  def to_a
    [].tap do |ary|
      n = bitmap
      vocabulary.each_with_index do |word, index|
        ary << word if n & 1 > 0
        n >>= 1
      end
    end
  end

  private

  def check_compatibility(document)
    return if @vocabulary == document.vocabulary
    raise 'Incompatible document'
  end
end