# 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