RestrictionEnzyme_map

RestrictionEnzymeMap.cpp

#include <vector>
#include <algorithm>
#include <iostream>
#define IN
#define OUT

typedef std::vector<int>	int_v;

inline int diff(int a, int b)
{	return (a < b)? (b - a) : (a - b);	}

int calc_deltaX(IN int_v &v, OUT int_v &ret_v)
{
	for(int_v::iterator it = v.begin(); it != v.end(); it++) {
		for(int_v::iterator it2 = it + 1; it2 != v.end(); it2++) {
			ret_v.push_back(diff(*it, *it2));
		}
	}
	return 0;
}

// "_d" means destructive function. 
int insert_elm_d(int_v &v, int elm)
{
	int ret_val(0);
	int_v::iterator it = v.begin();
	for ( ; it != v.end() && *it < elm ; it++) {;}
	if ( elm < *it ) {
		v.insert(it, elm);
		ret_val++;
	}
	return ret_val;
}

int remove_elm_d(int_v &v, int elm)
{
	int ret_val(0);
	for(int_v::iterator it = v.begin(); it != v.end(); it++) {
		if (*it == elm) {
			v.erase(it);
			ret_val++;
			break;
		}
	}
	return ret_val;
}

void display_vector(int_v &v)
{
	bool first = true;
	for(int_v::iterator it = v.begin(); it != v.end(); it++) {
		if (first == true) {	
			first = false;
			std::cout << "{ ";
		} else {
			std::cout << ", ";	
		}
		std::cout << *it;
	}
	std::cout << " }";
	std::cout << std::endl;
}

static bool restriction_enzyme_recursive(int_v map, int_v dist, int_v **ans)
{
	/* コピーを作製 */
	int_v map2(map);
	int_v dist2(dist);

	//	0:	まだ分からない
	//	-1:	この答えはだめ
	//	1:	これで行ける
	int current_flg(0);
	int d(0);
	bool temp_ret;

	/* Phase 1 =================================*/
	/* from start distance */
	int new_point = dist.back();
	insert_elm_d(map, new_point);
	for(int_v::iterator it = map.begin(); it != map.end(); it++) {
		/* 一つづつ消していく */
		d = diff(*it, new_point);
		if(d != 0 && remove_elm_d(dist, d) == 0) {
			/* この入れ方はダメってこと */
			current_flg = -1;
			break;
		}
	}
	
	if (current_flg == -1) {
		// この段階でだめってわかったので、最後のポイントからの距離だと思って
		// 次のパターンでテスト。
		;
	} else if ( dist.size() == 0) {
		// この段階でOKってわかった */
		*ans = new int_v(map);
		return true;
	} else {
		/* 再帰を一つ深めてみる */
		if(true == restriction_enzyme_recursive(map, dist, ans)) {
			return true;
		}
	}
	
	current_flg = 0;	// reset
	/* Phase 2 =================================*/
	/* distance from end */
	new_point = map2.back() - dist2.back();
	insert_elm_d(map2, new_point);
	for(int_v::iterator it = map2.begin(); it != map2.end(); it++) {
		// ひとつずつ消していく 
		d = diff(*it, new_point);
		if (d != 0 && remove_elm_d(dist2, d) == 0) {
			current_flg = -1;
			break;
		}
	}
	if (current_flg == -1) {
		return false;
	} else if (dist2.size() == 0) {
		*ans = new int_v(map2);
		return true;
	} else {
		return restriction_enzyme_recursive(map2, dist2, ans);
	}

	/* ここには来ないはず */
	return false;
}

bool restriction_enzyme_map(IN int_v dist, OUT int_v **ans)
{
	if (dist.size() == 0) {
		return false;
	}
	std::sort(dist.begin(), dist.end());
	/* initialize */
	int_v map;
	/* まず、初めと終わりは決まる */
	map.push_back( 0 );		
	map.push_back(dist.back());
	dist.pop_back();
	if (dist.size() == 0) {
		*ans = new int_v(map);
		return true;
	} else if (restriction_enzyme_recursive(map, dist, ans) == true) {
		return true;
	} else {
		return false;
	}
}


int main(void)
{
	int_v 	*ans;
	int_v	dist;
	bool result;
	int l[] = {1,1,1,2,2,3,3,3,4,4,5,5,6,6,6,9,9,10,11,12,15};

	for(int i = 0; i < sizeof(l)/sizeof(int); i++) { 
		dist.push_back(l[i]); 
	}
	std::cout << "L:\t";
	display_vector(dist);
	result = restriction_enzyme_map(dist, &ans);
	if(result == true){
		std::cout << "Map:\t";
		display_vector( *ans );
	} else {
		std::cout << "Nothing\n";
	}
}