import re

from types import StringType,ListType

import biopython.pairwise2

from oldowan.polymorphism import Polymorphism

from reduction_funcs import prefer_known_substitutions
from reduction_funcs import prefer_fewer
from reduction_funcs import prefer_indels_at_end
from reduction_funcs import prefer_multi_inserts
from reduction_funcs import prefer_insertions_at_309_and_315
from reduction_funcs import prefer_315_insertion_over_double_310_insertion
from reduction_funcs import prefer_indels_over_ts_over_tv 
from reduction_funcs import prefer_end_of_sorted_list
from reduction_funcs import prefer_309del_315ins_over_309T_310C
from reduction_funcs import prefer_95ins_97del_over_96T_97C

# rCRSplus is an expanded rCRS sequence, which starts at position 15500,
#          then runs through the whole genome, then has the opening
#          1000 bases attached at the end again. This is used so that
#          query sequences that are not cut precisely at the canonical 
#          origin will still be analyzable.
# rCRSplus_positions maps the string indices of rCRSplus to their positions
#          in the reference sequence.
from oldowan.mtdna import rCRSplus, rCRSplus_positions

class MatchingRange(object):
    
    def __init__(self, query_start, target_start):
        self.query_start = query_start
        self.target_start = target_start
        self.query_end = None
        self.target_end = None
        
    def __str__(self):
        return '[(%s, %s),(%s,%s)]' % (self.query_start, 
                                       self.query_end, 
                                       self.target_start, 
                                       self.target_end)
    
    def __repr__(self):
        return 'MatchingRange: %s' % str(self)

    def query_slice(self):
        return slice(self.query_start, self.query_end)

    def target_slice(self):
        return slice(self.target_start, self.target_end)

    def intersect(self, other):
        other_query_range  = range(other.query_start, other.query_end)
        other_target_range = range(other.target_start, other.target_end)
        if ((self.query_start  in other_query_range  or
             self.query_end    in other_query_range )  and
            (self.target_start in other_target_range or
             self.target_end   in other_target_range)  ):
            return True
        return False

    def merge_with(self, other):
        self.query_start  = min([self.query_start, other.query_start])
        self.query_end    = max([self.query_end, other.query_end])
        self.target_start = min([self.target_start, other.target_start])
        self.target_end   = max([self.target_end, other.target_end])

def find_match_positions(query, reference, word_size=15):

    WS = word_size
    s1 = query
    s2 = reference
    
    word_starts = range(0, len(s1)-WS+1) 
    matches = []
    start = None
    for i in word_starts:
        if start is None:
            pos = s2.find(s1[i:i+WS])
        else:
            pos = s2.find(s1[i:i+WS], start, start+100)
        if pos != -1:
            start = pos
        matches.append(pos)

    return matches


def align(query, reference, word_size=15, mismatch_cutoff=0.7):
    """
    Align two similar sequences.
    
    """
    WS = word_size
    s1 = query
    s2 = reference
    
    matches = find_match_positions(s1, s2, WS)

    if -1 not in matches:
        return []
    
    if matches.count(-1)/float(len(matches)) > mismatch_cutoff:
        raise Exception('sequences do not match')

    mismatches = []
    mismatch = None
    for position, value in enumerate(matches):
        if value == -1:
            if mismatch is None:
                if position == 0:
                    # the query starts at 0, but the target doesn't have to
                    # so, figure out where the target start is
                    query_start = 0
                    count = 0
                    while matches[count] == -1:
                        count += 1
                    target_start = matches[count] - count 
                    mismatch = MatchingRange(query_start, target_start)
                else:
                    mismatch = MatchingRange(position, matches[position-1]+1)
        elif mismatch is not None:
            mismatch.query_end = position+WS
            mismatch.target_end = value+WS
            mismatches.append(mismatch)
            mismatch = None

    # if there is a mismatch at the end of the query, we will
    # never have set the proper end of the query and target
    if mismatch is not None:
        mismatch.query_end = len(query)
        mismatch.target_end = (mismatch.target_start + 
                               mismatch.query_end - 
                               mismatch.query_start)
        mismatches.append(mismatch)
        mismatch = None

    polymorphisms = []

    merged_matches = []
    for mm in mismatches: