#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <ctime>
using namespace std;


class Alignment{
public:
	int start_x, start_y, end_x, end_y;
	float initial_score, score;
	string name;
	Alignment* predecessor;

	Alignment(int x0, int y0, int x1, int y1, float s, string n1){
		start_x = x0;
		start_y	= y0;
		end_x	= x1;
		end_y	= y1;
		initial_score	= s;
		score	= s;
		name	= new char[n1.length()];
		name	= n1;
		predecessor	= 0;
	}
	void print()const{
		if(name.length() > 0) 
			cout << name << "\t";
		cout << "(" <<	start_x << "," << start_y << ")\t-> (" << 
						end_x << ","  << end_y << ")\t score = " << score << endl;  
	}
	bool isStart(int x_coord)const{
		if(x_coord == start_x)
			return true;
		else
			return false;
	}
	void set_predecessor(Alignment* a){
		predecessor = a;
		score += a->score;
	}
};


void main()
{
	clock_t start_time, end_time, etime;
	start_time = clock();

	// テストデータの入力　BWT で計算したアラインメントに置き換える　
	// 重複したアラインメントは除くため set で実装

	// いつものテストデータ
	set<Alignment*> set_of_alignments;
	set_of_alignments.insert(new Alignment( 1, 1, 6, 9,10,"a")); // a
	set_of_alignments.insert(new Alignment( 3,23, 9,32,11,"b")); // b
	set_of_alignments.insert(new Alignment( 7,18,10,24, 5,"c")); // c
	set_of_alignments.insert(new Alignment(14,10,21,19,11,"d")); // d
	set_of_alignments.insert(new Alignment(20, 0,26, 7,11,"e")); // e
	set_of_alignments.insert(new Alignment(18,29,23,36, 5,"f")); // f
	set_of_alignments.insert(new Alignment(25,26,30,32, 7,"g")); // g
	set_of_alignments.insert(new Alignment(29,14,34,19, 5,"h")); // h
	set_of_alignments.insert(new Alignment(32,22,40,36,14,"i")); // i

/*	// 別のテストデータ 　Nの 4 乗のアラインメントが生成されるので注意
	int N = 30;
	for(int i=0; i<N*N; i++)
		for(int j=0; j<N*N; j++)
			set_of_alignments.insert(new Alignment( i, j, i+N, j+N, N,"")); 
*/

	// アラインメントの開始点および終了点でソート
	// 異なるアラインメントに同じ値の key (start_x, end_x) が重複対応する可能性を許容するため multimap を使う
	multimap<int, Alignment*> sorted_by_X;
	for(set<Alignment*>::iterator iter = set_of_alignments.begin();
		iter != set_of_alignments.end();	
		iter++){
			sorted_by_X.insert(make_pair((*iter)->start_x,*iter));
			sorted_by_X.insert(make_pair((*iter)->end_x,  *iter));
	}

	// Chaining　
	// sorted_by_Y では、同じ値の key (end_y) をもつアラインメントの重複は許さないので map を使う
	map<int, Alignment*> sorted_by_Y;
	map<int, Alignment*>::iterator iterY, tmpY;


   (ここを埋めてほしい)



	// お掃除！ new して heap にとったデータは必ず delete. STL で宣言したデータはプログラム終了時に STL が自動的に消去.

	for(set<Alignment*>::iterator iter = set_of_alignments.begin(); iter != set_of_alignments.end(); iter++){
		delete *iter;
	}

	end_time = clock();
	etime = (end_time - start_time); // CLOCKS_PER_SEC;
	cout << "This chaining took " << etime << " msec." << endl;

}