begin
  require "levenshtein/levenshtein_fast"	# If compiled by RubyGems.
rescue LoadError
  begin
    require "levenshtein_fast"			# If compiled by the build script.
  rescue LoadError
    $stderr.puts "WARNING: Couldn't find the fast C implementation of Levenshtein.distance. Using the much slower Ruby version instead."
  end
end

module MusicCache

  # The Levenshtein distance is a metric for measuring the amount
  # of difference between two sequences (i.e., the so called edit
  # distance). The Levenshtein distance between two sequences is
  # given by the minimum number of operations needed to transform
  # one sequence into the other, where an operation is an
  # insertion, deletion, or substitution of a single element.
  #
  # More information about the Levenshtein distance algorithm:
  # http://en.wikipedia.org/wiki/Levenshtein_distance .

  module Levenshtein
    VERSION	= "0.2.0.1260096211"

    # Returns the Levenshtein distance as a number between 0.0 and
    # 1.0. It's basically the Levenshtein distance divided by the
    # length of the longest sequence.

    def self.normalized_distance(s1, s2, threshold=nil)
      s1, s2	= s2, s1	if s1.length > s2.length	# s1 is the short one; s2 is the long one.

      if s2.length == 0
        0.0	# Since s1.length < s2.length, s1 must be empty as well.
      else
        if threshold
          if d = self.distance(s1, s2, (threshold*s2.length+1).to_i)
            d.to_f/s2.length
          else
            nil
          end
        else
          self.distance(s1, s2).to_f/s2.length
        end
      end
    end

    # Returns the Levenshtein distance between two sequences.
    #
    # The two sequences can be two strings, two arrays, or two other
    # objects. Strings, arrays and arrays of strings are handled with
    # optimized (very fast) C code. All other sequences are handled
    # with generic (fast) C code.
    #
    # The sequences should respond to :length and :[] and all objects
    # in the sequences (as returned by []) should response to :==.

    def self.distance(s1, s2, threshold=nil)
      s1, s2	= s2, s1	if s1.length > s2.length	# s1 is the short one; s2 is the long one.

      # Handle some basic circumstances.

      return 0		if s1 == s2
      return s2.length	if s1.length == 0

      if threshold
        return nil	if (s2.length-s1.length) >= threshold

        a1, a2	= nil, nil
        a1, a2	= s1, s2			if s1.respond_to?(:-) and s2.respond_to?(:-)
        a1, a2	= s1.scan(/./), s2.scan(/./)	if s1.respond_to?(:scan) and s2.respond_to?(:scan)

        if a1 and a2
          return nil	if (a1-a2).length >= threshold
          return nil	if (a2-a1).length >= threshold
        end
      end

      distance_fast_or_slow(s1, s2, threshold)
    end

    def self.distance_fast_or_slow(s1, s2, threshold)	# :nodoc:
      if respond_to?(:levenshtein_distance_fast)
        levenshtein_distance_fast(s1, s2, threshold)	# Implemented in C.
      else
        levenshtein_distance_slow(s1, s2, threshold)	# Implemented in Ruby.
      end
    end

    def self.levenshtein_distance_slow(s1, s2, threshold)	# :nodoc:
      row	= (0..s1.length).to_a

      1.upto(s2.length) do |y|
        prow	= row
        row	= [y]

        1.upto(s1.length) do |x|
          row[x]	= [prow[x]+1, row[x-1]+1, prow[x-1]+(s1[x-1]==s2[y-1] ? 0 : 1)].min
        end

        # Stop analysing this sequence as soon as the best possible
        # result for this sequence is bigger than the best result so far.
        # (The minimum value in the next row will be equal to or greater
        # than the minimum value in this row.)

        return nil	if threshold and row.min >= threshold
      end

      row[-1]
    end
  end
end