# File lib/hashdiff/diff.rb, line 72
  def self.diff(obj1, obj2, options = {}, &block)
    opts = {
      :prefix      =>   '',
      :similarity  =>   0.8,
      :delimiter   =>   '.',
      :strict      =>   true,
      :strip       =>   false,
      :numeric_tolerance => 0,
      :array_path  =>   false,
      :use_lcs     =>   true
    }.merge!(options)

    opts[:prefix] = [] if opts[:array_path] && opts[:prefix] == ''

    opts[:comparison] = block if block_given?

    # prefer to compare with provided block
    result = custom_compare(opts[:comparison], opts[:prefix], obj1, obj2)
    return result if result

    if obj1.nil? and obj2.nil?
      return []
    end

    if obj1.nil?
      return [['~', opts[:prefix], nil, obj2]]
    end

    if obj2.nil?
      return [['~', opts[:prefix], obj1, nil]]
    end

    unless comparable?(obj1, obj2, opts[:strict])
      return [['~', opts[:prefix], obj1, obj2]]
    end

    result = []
    if obj1.is_a?(Array) && opts[:use_lcs]
      changeset = diff_array_lcs(obj1, obj2, opts) do |lcs|
        # use a's index for similarity
        lcs.each do |pair|
          prefix = prefix_append_array_index(opts[:prefix], pair[0], opts)
          result.concat(diff(obj1[pair[0]], obj2[pair[1]], opts.merge(:prefix => prefix)))
        end
      end

      changeset.each do |change|
        change_key = prefix_append_array_index(opts[:prefix], change[1], opts)
        if change[0] == '-'
          result << ['-', change_key, change[2]]
        elsif change[0] == '+'
          result << ['+', change_key, change[2]]
        end
      end
    elsif obj1.is_a?(Array) && !opts[:use_lcs]
      result.concat(LinearCompareArray.call(obj1, obj2, opts))
    elsif obj1.is_a?(Hash)

      deleted_keys = obj1.keys - obj2.keys
      common_keys = obj1.keys & obj2.keys
      added_keys = obj2.keys - obj1.keys

      # add deleted properties
      deleted_keys.sort_by{|k,v| k.to_s }.each do |k|
        change_key = prefix_append_key(opts[:prefix], k, opts)
        custom_result = custom_compare(opts[:comparison], change_key, obj1[k], nil)

        if custom_result
          result.concat(custom_result)
        else
          result << ['-', change_key, obj1[k]]
        end
      end

      # recursive comparison for common keys
      common_keys.sort_by{|k,v| k.to_s }.each do |k|
        prefix = prefix_append_key(opts[:prefix], k, opts)
        result.concat(diff(obj1[k], obj2[k], opts.merge(:prefix => prefix)))
      end

      # added properties
      added_keys.sort_by{|k,v| k.to_s }.each do |k|
        change_key = prefix_append_key(opts[:prefix], k, opts)
        unless obj1.key?(k)
          custom_result = custom_compare(opts[:comparison], change_key, nil, obj2[k])

          if custom_result
            result.concat(custom_result)
          else
            result << ['+', change_key, obj2[k]]
          end
        end
      end
    else
      return [] if compare_values(obj1, obj2, opts)
      return [['~', opts[:prefix], obj1, obj2]]
    end

    result
  end