import java.io.*;
import java.util.*;

public class QTLPeak {
    final double Distance=50.0;
    final int MarkerNum=3795;
    final int GeneNum=45101;

    String ProbeSet="";

    String[] MarkerName = new String[MarkerNum];
    String[] MarkerChr = new String[MarkerNum];
    double[] MarkerMb = new double[MarkerNum];
    double[] LrsScore = new double[MarkerNum];

    private Vector PeakList;
    private Vector QtlList;

    public QTLPeak(String ResultFile) {
        try{
            BufferedReader in = new BufferedReader(new FileReader(ResultFile));
            PrintWriter out = new PrintWriter(new FileWriter(ResultFile+".QTL"));
            String data, s[];

            out.println(in.readLine());
            for (int n=0; n<GeneNum; n++) {
                for (int i=0; i<MarkerNum; i++) {
                    data = in.readLine();
                    s = data.split("\t");
                    ProbeSet = s[0];
                    MarkerName[i] = data;
                    MarkerChr[i] = s[9];
                    MarkerMb[i] = Double.parseDouble(s[10]);
                    LrsScore[i] = Double.parseDouble(s[6]);
                }

                getPeakList();
                getQtlList();


                System.out.println(ProbeSet);
                for (int i=0; i<QtlList.size(); i++) {
                    Peak aPeak = (Peak)QtlList.get(i);
                    for (int k=aPeak.Start; k<=aPeak.End; k++) {
                        out.println(MarkerName[k]);
                    }
                }
            }
            in.close();
            out.close();
        }
        catch (Exception e) {
            System.out.println(e);
        }
    }


    private void getPeakList() {
        PeakList = new Vector();
        boolean isRaise = true;
        int start=0, end=0, j;

        //given a marker, if its lrs score less than its previous marker's lrs score
        //and until the previous marker, the score still raise, it means its previous
        //marker is a peak
        for (int i=1; i<MarkerNum-1; i++) {
            if (MarkerChr[i].equals(MarkerChr[i-1])) {//deal inner of a chromosome
                if (LrsScore[i]>LrsScore[i-1]) {
                    isRaise = true;
                }
                else if (LrsScore[i]<LrsScore[i-1]) {
                    if (isRaise) {
                        start = i-1;
                        end = i-1;
                        j=i-1;
                        while (j>=0) {
                            if (MarkerChr[j].equals(MarkerChr[end]) &&
                                LrsScore[j]==LrsScore[start]) {
                                start = j;
                            }
                            else {
                                break;
                            }

                            j--;
                        }

                        Peak aPeak = new Peak();
                        aPeak.Start = findMiddlePeak(start, end);
                        aPeak.End = aPeak.Start;
                        PeakList.add(aPeak);
                    }

                    isRaise = false;
                }
            }
            else {//deal the end of a chromosome
                if (isRaise) {
                    start = i-1;
                    end = i-1;
                    j=i-1;
                    while (j>=0) {
                        if (MarkerChr[j].equals(MarkerChr[end]) &&
                            LrsScore[j]==LrsScore[start]) {
                            start = j;
                        }
                        else {
                            break;
                        }

                        j--;
                    }
                    Peak aPeak = new Peak();
                    aPeak.Start = findMiddlePeak(start, end);
                    aPeak.End = aPeak.Start;
                    PeakList.add(aPeak);
                }
            }
        }

        if (LrsScore[MarkerNum-1]>=LrsScore[MarkerNum-2]) {//deal the end of whole Marker
            if (isRaise) {
                start = MarkerNum - 1;
                end = MarkerNum - 1;
                j = MarkerNum - 1;
                while (j >= 0) {
                    if (MarkerChr[j].equals(MarkerChr[end]) &&
                        LrsScore[j] == LrsScore[start]) {
                        start = j;
                    } else {
                        break;
                    }

                    j--;
                }
                Peak aPeak = new Peak();
                aPeak.Start = findMiddlePeak(start, end);
                aPeak.End = aPeak.Start;
                PeakList.add(aPeak);
            }
        }
    }

    private int findMiddlePeak(int start, int end) {
        double MinDistance, Distance, Middle;
        int p;

        Middle = (MarkerMb[start]+MarkerMb[end])/2.0;
        MinDistance = Middle-MarkerMb[start];
        p = start;

        for (int i=start; i<=end; i++) {
            Distance = Math.abs(Middle-MarkerMb[i]);
            if (MinDistance > Distance) {
                MinDistance = Distance;
                p=i;
            }

            if (MinDistance == Distance && Math.random()>=0.5) {
                p=i;
            }
        }

        return p;
    }

    private void getQtlList() {
        QtlList = new Vector();

        double MaxPeakScore, Score;
        int MaxPeakIndex, PeakIndex;

        while (PeakList.size()>0) {
            //get the max peak and its position
            MaxPeakScore = 0.0;
            MaxPeakIndex = -1;
            for (int i=0; i<PeakList.size(); i++) {
                Peak aPeak = (Peak)PeakList.get(i);
                Score = LrsScore[aPeak.Start];
                if (MaxPeakScore < Score) {
                    MaxPeakScore = Score;
                    MaxPeakIndex = i;
                }
            }

            Peak MaxPeak = (Peak)PeakList.get(MaxPeakIndex);

            for (int i=0; i<PeakList.size(); i++) {
                Peak aPeak = (Peak) (PeakList.get(i));

                if (MarkerChr[MaxPeak.Start].equals(MarkerChr[aPeak.Start])) {
                    if (MarkerMb[MaxPeak.Start]-Distance<MarkerMb[aPeak.End] &&
                        MarkerMb[MaxPeak.End]+Distance>MarkerMb[aPeak.Start]) {
                        PeakList.remove(i);
                        i--;
                    }
                }
            }

            QtlList.add(MaxPeak);
        }
    }

    class Peak {
        int Start;
        int End;
    }

    public static void main(String[] args) {
        QTLPeak qtlpeak = new QTLPeak(args[0]);
    }
}