import math,bisect,logging,argparse



# this class stores a dict composed of mass => peak pairs

class Measurement(object):



  def __init__(self,path):

    # read measurements from file

    with open(path,'rb') as f:

      f.readline() # discard csv header

      self.spec=dict(map(float,line.replace(b',',b'.').split(b';')) for line in f)

    self.maxpeak=max(self.spec.values())

    self.maxpeak_mass=max(x for x in self.spec if self.spec[x]==self.maxpeak)

    logging.info('found %d values in %s, maximum is %f found for mass %f' % \

        (len(self.spec.keys()),path,self.maxpeak,self.maxpeak_mass))



# the main matcher class

class Matcher(object):



  # brute force method

  # takes as input a list of lists and a checking function

  # checks all combinations of members from sets

  # yields all those combinations for which check returns True

  @staticmethod

  def brute_force(sets,check):

    state=len(sets)*[0]

    while True:

      if check(sum(sets[i][state[i]] for i in range(len(sets)))):

        yield state.copy()

      for i in range(len(state)):

        state[i]=(state[i]+1) % len(sets[i])

        if state[i]>0: break

      if i==len(state)-1 and state[i]==0: break



  # main matching function

  #   mass: target mass

  #   units: number of side chains to check for

  #   spec: dict of observed mass => peak pairs

  #   tolerance: tolerated error |measured_mass-computed_mass|

  #   sensitive: require mass of all subfragments to be present in spec (not only those that start with first side chain)

  def match(self,mass,units,spec,tolerance=0,sensitive=True):

    logging.info('matching mass %.05f' % mass)

    sets=[self.markers]+[[self.backbone+j[1] for j in self.sides] for i in range(units)]+[[self.end]]

    choices=len(sets)*[0]

    # helper to check if x is contained in sorted list S (up to errors)

    def contained(x,S):

      for e in self.errors:

        i=bisect.bisect(S,x+e)

        if i>0 and abs(x+e-S[i-1])<=tolerance: return True

        if i<len(S) and abs(x+e-S[i])<=tolerance: return True

    # helper to find matches of certain length (in side chains)

    def brute(right,x):

      if right==len(sets):

        if contained(x,[mass]): solutions.append(choices.copy())

      else:

        if 1<right<len(sets)-1:

          y=x

          for left in range(right if sensitive else 1):

            if left!=1 and not contained(y,peaks): return

            y-=sets[left][choices[left]]

        for choices[right] in range(len(sets[right])):

          brute(right+1,x+sets[right][choices[right]])

    (lower,upper)=(0,1)

    while upper-lower>0.001:

      cutoff=(lower+upper)/2

      threshold=cutoff*max(spec.values())

      peaks=sorted(x for x in spec.keys() if spec[x]>=threshold)

      solutions=[]

      brute(0,0)

      logging.debug('cutoff %.05f: %d solutions (%d peaks)' % (cutoff,len(solutions),len(peaks)))

      if len(solutions)==1:

        upper=lower

        for items in solutions:

          logging.info('%.05f ≈ %s (sides %s; error %.05f)' % (

              mass,

              ' + '.join(['%05f' % sets[i][items[i]] for i in range(len(items))]),

              ', '.join(self.sides[items[i+1]][0] for i in range(units)),

              sum(sets[i][items[i]] for i in range(len(items)))-mass,

            ))

      elif len(solutions)==0: upper=cutoff

      elif len(solutions)>1: lower=cutoff



  # initializes some parameters that remain constant across matches

  def __init__(self,markers,backbone,sides,end,errors):

    self.markers=markers

    self.backbone=backbone

    self.sides=sides

    self.end=end

    self.errors=errors



def main():

  logging.basicConfig(

      format='%(message)s',

      level=logging.DEBUG

    )

  parser=argparse.ArgumentParser(

      description='reconstruct molecular structure from measurement'

    )

  parser.add_argument('measurement')

  args=parser.parse_args()



  measurement=Measurement(args.measurement)



  # initialize matcher with example values

  matcher=Matcher(

      # masses of possible markers

      markers=[

          #463.02150,

          #299.01543,

          #121.00563,

          447.02659,

          283.02052,

          105.01702,

        ],

      # mass of backbone

      backbone=240.15997,

      # names and masses (w/o backbone) of side chains

      sides=[

          ('Acetaldehyde',       15.02348),

          ('Propionaldehyde',       29.03913),

          ('Isobutyraldehyde',       43.05478),

          ('3-Methylbutanal',       57.07043),

          ('2-Ethylbutanal',       71.08608),

          ('Cyclohexancarboxaldehyde',       83.08608),

          ('Heptanal',       85.10173),

          ('Octanal',       99.11738),

	  ('2-Phenylpropionaldehyde',      105.07043),

          ('Nonanal',      113.13303),

          ('Dodecanal',      155.17998),

          ('Tridecanal',      169.19563),

        ],

      # mass of molecule end

      #end=91.05478,

      end=107.04969,

      # possible measurement errors

      errors=[

          -1.007276,

          1.007276,

          2.014552,

          #21.981942,

          #22.996494,

          #23.996494,

        ],

    )



  # perform match (see above for meaning of parameters)

  matcher.match(

      mass=measurement.maxpeak_mass,

      units=6,

      spec=measurement.spec,

      tolerance=0.1,

      sensitive=False,

    )



main()

input('Press ENTER to quit ...')