# Computing minimum alignments and minimum scores using a brute-force iterative approach.

# min_alignment_brute_force(seq0,seq1)
#
# param seq0, seq1: sequences.
# result: a minimum alignment.
# effects: none.
#
# Computes the minimum alignment by comparing all extension sequences of length seq0.length + seq1.length
# with each other.
#
def min_alignment_brute_force(seq0, seq1)
  # Initialize.
  min_score = seq0.length + seq1.length + 1  # min score
  eseq0 = Ext_Sequence.new(seq1.length, seq0)  # first extension sequence to test

  while eseq0.length == seq0.length + seq1.length
    # Initialize.
    eseq1 = Ext_Sequence.new(seq0.length, seq1)  # rist extension sequence to compare with

    while eseq1.length == seq0.length + seq1.length
      # Check if new alignment is better and if so update min score and min alignment.
      if eseq0.score(eseq1) < min_score
        min_score = eseq0.score(eseq1)
        min_align = [eseq0, eseq1]
      end

      eseq1 = eseq1.next()
    end

    eseq0 = eseq0.next()
  end
  min_align
end

class Ext_Sequence < Array
  # Construct an extension sequence from seq with n leading nil.
  #
  # param n: non-negative integer
  # param seq: a sequence
  #
  def initialize(n, seq)
    super(n)
    self.concat(seq)
  end

  # score(eseq)
  #
  # param eseq: extension sequence of the same length.
  # result: score of alignment.
  # effects: none.
  #
  def score(eseq)
    score = 0
    for i in 0 ... self.length
      score += if self[i] == eseq[i] then 0 else 1 end
    end
    score
  end

  # next()
  #
  # result: the next extension sequence extending the same sequence.
  # effects: constructs the extension sequence.
  #
  def next()
    i = self.length-1
    nils = 0
    # Determine position of last non-nil and number of nils.
    while i >= 0 and self[i] == nil
      nils += 1
      i -= 1
    end
    non_nil = i
    if i == -1
      Ext_Sequence.new(0, self + [nil])
    else
      # Determine where nil and its right neighbor switch positions.
      while i >= 0 and self[i] != nil
        i -= 1
      end
      if i < 0
        # No position found: extension sequences is extended by one.
        Ext_Sequence.new(nils + 1, self[i+1 .. non_nil])
        # Switch and move nils to the left.
      else
        Ext_Sequence.new(0, self[0, i] + [self[i+1]] + [nil] + ([nil] *  nils) + self[i+2 .. non_nil])
      end
    end
  end
end