import random


def roulette_wheel_selection(scores):
	r_pos = random.uniform(0, sum(scores))
	c_pos = 0
	for idx, score in enumerate(scores):
		c_pos += score
		if r_pos <= c_pos:
			return idx


def roulette_wheel_selection2(scores):
	idx1 = roulette_wheel_selection(scores)
	idx2 = roulette_wheel_selection(scores)

	return idx1, idx2


def crossover(individual1, individual2):
	assert len(individual1) == len(individual2)
	assert len(individual1) % 2 == 0
	assert len(individual1) > 1 and len(individual2) > 1

	genes_first_half = random.randint(1, len(individual1) - 2)

	new1 = individual1[:genes_first_half] + individual2[genes_first_half:]
	new2 = individual2[:genes_first_half] + individual1[genes_first_half:]

	return new1, new2


def crossover_pool(pool, scores, new_pool_size):
	assert new_pool_size % 2 == 0

	new_pool = []
	for _ in range(new_pool_size / 2):
		idx1, idx2 = roulette_wheel_selection2(scores)
		new1, new2 = crossover(pool[idx1], pool[idx2])
		new_pool.append(new1)
		new_pool.append(new2)
	return new_pool


class Crossover:
	def __init__(self):
		pass

	def call(self, pool, new_pool, scores):
		new_pool.extend(crossover_pool(pool, scores, len(pool) - len(new_pool)))
		return new_pool

	def summary(self):
		print 'Crossover'

import random


def roulette_wheel_selection(scores):
	r_pos = random.uniform(0, sum(scores))
	c_pos = 0
	for idx, score in enumerate(scores):
		c_pos += score
		if r_pos <= c_pos:
			return idx


def roulette_wheel_selection2(scores):
	idx1 = roulette_wheel_selection(scores)
	idx2 = roulette_wheel_selection(scores)

	return idx1, idx2


def crossover(individual1, individual2):
	assert len(individual1) == len(individual2)
	assert len(individual1) % 2 == 0
	assert len(individual1) > 1 and len(individual2) > 1

	genes_first_half = random.randint(1, len(individual1) - 2)

	new1 = individual1[:genes_first_half] + individual2[genes_first_half:]
	new2 = individual2[:genes_first_half] + individual1[genes_first_half:]

	return new1, new2


def crossover_pool(pool, scores, new_pool_size):
	assert new_pool_size % 2 == 0

	new_pool = []
	for _ in range(new_pool_size / 2):
		idx1, idx2 = roulette_wheel_selection2(scores)
		new1, new2 = crossover(pool[idx1], pool[idx2])
		new_pool.append(new1)
		new_pool.append(new2)
	return new_pool


class Crossover:
	def __init__(self):
		pass

	def call(self, pool, new_pool, scores):
		new_pool.extend(crossover_pool(pool, scores, len(pool) - len(new_pool)))
		return new_pool

	def summary(self):
		print 'Crossover'
