def swaprevmut(p, threshold, mutprob):
	if rand() <= mutprob:
		a = choose(range(len(p)))
		b = choose([i for i in range(max(0, a-threshold), min(a+threshold, len(p))) if i!=a])
		if a>b: a,b = b,a
		return p[:a] + p[a:b+1][::-1] + p[b+1:]
	else:
		return p

def revswapmut(p, threshold, mutprob):
	p = p[:]
	for a in xrange(len(p)):
		if rand() <= mutprob:
			a = choose(range(len(p)))
			b = choose([i for i in range(max(0, a-threshold), min(a+threshold, len(p))) if i!=a])
			p[a], p[b] = p[b], p[a]
	
	return p

def generateFull(F, T, root, height):
	if height < 0:
		root.operator = choose(T)
		return root
	
	else:
		root.operator = choose(F)
		for _ in spec(root.operator).args:
			n = Node()
			root.operands.append(generateFull(F, T, n, height-1))
	
		return root

def generateGrow(F, T, root, height, minheight):
	if height < 0:
		root.operator = choose(T)
		return root
	
	else:
		if minheight>0: root.operator = choose(F)
		else: root.operator = choose(F+T)
		if hasattr(root.operator, "__call__"):
			for _ in spec(root.operator).args:
				n = Node()
				root.operands.append(generateGrow(F, T, n, height-1, minheight-1))
			return root
		else:
			return root

def mutateSingleAllele(p, chrom, chars):
	""" get the `chrom`th chromosome of the Individual p.
		Replace a random gene in this chromosome with a different allele from chars 
		Precondition: p[chrom] should be castable into a list
		Return a new individual. Do not destroy the input
		
		pre:
			isinstance(p, Individual)
			isinstance(chrom, int)
			forall(p.chromosomes[chrom], lambda e: e in chars)
			(0 <= chrom <= len(p.chromosomes)-1) ^ (len(p.chromosomes)*-1 <= chrom <= -1)
			
		post[p, chrom]:
			__old__.p == p
			__old__.chrom == chrom
			__return__ is not p
			__return__ != p
			__return__.chromosomes != __old__.p.chromosomes
			forall(__return__.chromosomes[chrom], lambda e: e in chars)
			forall([i for i in range(len(p.chromosomes)) if i!=chrom], lambda c: __old__.p.chromosomes[i]==__return__.chromosomes[i])
		
	"""
	
	chromosome = p[chrom][:]
	gene = randint(0, len(chromosome)-1)
	allele = choose([i for i in chars if i!= chromosome[gene]])
	chromosome = chromosome[:gene] + [allele] + chromosome[gene+1:]
	
	answer = Individual(p.chromosomes[:])
	answer[chrom] = chromosome
	return answer

    def test_package_import__semantics(self):

        # Generate a couple of broken modules to try importing.

        # ...try loading the module when there's a SyntaxError
        self.rewrite_file('for')
        try: __import__(self.module_name)
        except SyntaxError: pass
        else: raise RuntimeError, 'Failed to induce SyntaxError'
        self.assertNotIn(self.module_name, sys.modules)
        self.assertFalse(hasattr(sys.modules[self.package_name], 'foo'))

        # ...make up a variable name that isn't bound in __builtins__
        var = 'a'
        while var in dir(__builtins__):
            var += random.choose(string.letters)

        # ...make a module that just contains that
        self.rewrite_file(var)

        try: __import__(self.module_name)
        except NameError: pass
        else: raise RuntimeError, 'Failed to induce NameError.'

        # ...now  change  the module  so  that  the NameError  doesn't
        # happen
        self.rewrite_file('%s = 1' % var)
        module = __import__(self.module_name).foo
        self.assertEqual(getattr(module, var), 1)

def insult(bot, event, *args):
    if args:
        insulttouse = choose(insultslist.insults)
        checkforbot = "".join(args)
        for c in string.punctuation:
            checkforbot = checkforbot.replace(c, "")
        for i in range(len(checkforbot)):
            if not checkforbot[i].isalnum == True:
                checkforbot[i].replace(checkforbot[i], "")
        tobeinsulted = " ".join(args)
        if (
            "@" in tobeinsulted
            or "0" in tobeinsulted.lower()
            or "()" in tobeinsulted.lower()
            or "soda" in tobeinsulted.lower()
            or "soda" in checkforbot.lower()
        ):
            msg = _("I'm not insulting myself")
        elif (
            "s" in tobeinsulted.lower()
            and "o" in tobeinsulted.lower()
            and "d" in tobeinsulted.lower()
            and "a" in tobeinsulted.lower()
        ):
            msg = _("I'm not insulting myself")
        else:
            msg = _("Hey {}, {}").format(tobeinsulted, insulttouse)
    else:
        msg = _("I'm not going to insult nobody. They dont' have a life anyways ;)")
    yield from bot.coro_send_message(event.conv, msg)

def generate_random_nick(base_name, max_length=16):
    max_length = max_length - len(base_name)
    chars = string.ascii_lowercase
    digits = string.digits
    selection = chars + digits
    random_string = "".join(choose(selection) for x in range(randint(max_length)))
    return "%s-%s" % (base_name, random_string)

def xkcd(bot, event, *args):
    '''Gets xkcd comic. Random number is chosen if number is not given. Format is /bot xkcd <number>'''
    try:
        numlist =  list(range(1, 1631))
        if len(args) == 1 and args[0].isdigit():
            num = int(args[0])
            link_image = str(pykcd.XKCDStrip(num).image_link)
            title = str(pykcd.XKCDStrip(num).title)
            alt_text = str(pykcd.XKCDStrip(num).alt_text)
            link = 'http://xkcd.com/' + str(num)
        else:
            chosencomic = choose(numlist)
            num = int(chosencomic)
            link_image = str(pykcd.XKCDStrip(num).image_link)
            title = str(pykcd.XKCDStrip(num).title)
            alt_text = str(pykcd.XKCDStrip(num).alt_text)
            link = 'http://xkcd.com/' + str(num)

        logger.info("getting {}".format(link_image))
        filename = os.path.basename(link_image)
        r = yield from aiohttp.request('get', link_image)
        raw = yield from r.read()
        image_data = io.BytesIO(raw)
        msg = _('Title: {}<br>Caption: {}<br>Number: {}<br>Link: {}').format(title, alt_text, num, link)
        image_id = yield from bot._client.upload_image(image_data, filename=filename)
        yield from bot.coro_send_message(event.conv.id_, None, image_id=image_id)
        yield from bot.coro_send_message(event.conv, msg)
    except BaseException as e:
        msg = _('{} -- {}').format(str(e), event.text)
        yield from bot.coro_send_message(CONTROL,msg)

    def getConfigForInstanceSingleFile(self, key, name):
        logging.debug("getConfigForInstanceSingleFile(%s, %s)" % (key, name))
        c = self.getConfig(name)
        if c is None:
            return None
        match = 0
        if key not in c:
            return None
        v = c[key]
        logging.debug("getConfigForInstanceSingleFile(%s, %s) value=%s" % (key, name, v))
        if isinstance(v, dict):
            rv = None
            for (key, value) in v.iteritems():
                tm = self.matchesInstance(key)
                if tm > match:
                    match = tm
                    rv = value
            v = rv

        if v is None:
            return None

        if isinstance(v, list):
            v = random.choose(v)

        return (match, v)

    def next(self):
        if len(self.children.keys()) == 0:
            raise GameEnded()
        else:
            names = self.children.keys()

            choice = -2

            while choice < 0 or choice > len(names)-1:
                for i in enumerate(names):
                    print "%d: %s" % i 

                try:
                    choice = int(raw_input("Choose from [0-%d] > " % (len(names) - 1)))
                except:
                    pass

            chosen_name = names[choice]

            possible_choices = filter(lambda x: x.predicate(), self.children[chosen_name])


            next_state = choose(possible_choices)
            history.append(next_state)

            print next_state.description

            if len(next_state.children.keys()) == 0:
                next_state.next()

            return next_state

 def select_action(self, friends, enemies):
   hp = self.properties.get('hit_points')
   if hp < self.properties('retreat_hit_points'):
     return self.retreat
   if hp < self.properties('defend_hit_points'):
     return self.defend
   return functools.partial(self.attack, random.choose(enemies))

def compliment(bot, event, *args):
    if args:
        if 'me' in ''.join(args).lower():
            complimenttouse = choose(compliments)
            tobecomplimented = event.user.first_name
            msg = _("Hey {}, {}").format(tobecomplimented, complimenttouse) 
        elif 'trump' not in ''.join(args).lower():
            complimenttouse = choose(compliments)
            tobecomplimented = ' '.join(args)
            msg = _("Hey {}, {}").format(tobecomplimented, complimenttouse)
        else:
            msg =_("Trump is unable to be complimented")
    else:
        compliment = choose(compliments)
        msg = _("{}").format(compliment)
    yield from bot.coro_send_message(event.conv, msg)

def swapmut(p, mutprob):
	""" Pick any two random cities and swap their positions in the tour """
#	i,j = sample(range(len(p)), 2)
#	if rand() <= mutprob: p[i], p[j] = p[j], p[i]
	for i in range(len(p)):
		if rand() <= mutprob:
			j = choose([ii for ii in range(len(p)) if ii != i])
			p[i], p[j] = p[j], p[i]
	return p

def pointMutation(indiv, F, T):
	M = getCrossPoint(indiv)
	iparent,isubtree = None, indiv
	i = [0] if not M else M
	
	while i:
		iparent = isubtree
		isubtree = isubtree.operands[i.pop(0)]
		
	if hasattr(isubtree.operator, "__call__"):
		arity = len(spec(isubtree.operator))
		otherGuys = [f for f in F if len(spec(f)) == arity and f!=isubtree.operator]
		isubtree.operator = choose(otherGuys)
	else:
		otherGuys = [t for t in T if t!=isubtree.operator]
		isubtree.operator = choose(otherGuys)
	
	return [indiv]

def genfixeddecimalstr(size=38, precision=12, signed=True):
    # voltdb decimal is 16-byte with fixed scale of 12 and precision of 38
    p = -1*precision
    r = ''.join(random.sample(NUMERIC_CHARSET, len(NUMERIC_CHARSET)))
    r = r * int(size/len(r)) + r[:size%len(r)]
    if (p>0):
        r = r[:p] + '.' + r[p:]
    if signed:
        r = random.choose(["-","+",""]) + r
    return r

def genPop(N, G):
	"""Return a population of N individuals. Each individual has G chromosomes"""
	
	answer = set()
	while N:
		indiv = ''.join(choose('01') for _ in range(G))
		if indiv not in answer:
			N -= 1
			answer.add(indiv)
	
	return list(answer)

    def _set_init_position(self):
        ''' puts the agent in an initial position, usually within the bounds of the
        cage

        Options: [the cage] door, or anywhere in the plane at x=.1 meters

        set initial velocity from fitted distribution
        '''

        # generate random intial velocity condition using normal distribution fitted to experimental data
        if self.initial_position_selection == 'realistic':
            """these were calculated by taking selecting the initial positions of all observed trajectories in all
            conditions. Then, for each dimension, I calculated the distance of each initial position to the nearest wall
            in that dimension (i.e. for each z I calculated the distance to the floor and ceiling and selected
            the smallest distance. Then, Decisions aand"""
            downwind, upwind, left, right, floor, ceiling = self.boundary
            x_avg_dist_to_wall = 0.268
            y_avg_dist_to_wall = 0.044
            z_avg_dist_to_wall = 0.049
            x = choose([(downwind + x_avg_dist_to_wall), (upwind - x_avg_dist_to_wall)])
            y = choose([left + y_avg_dist_to_wall, (right - y_avg_dist_to_wall)])
            z = ceiling - z_avg_dist_to_wall
            initial_position = np.array([x,y,z])
        elif self.initial_position_selection == 'downwind_high':
            initial_position = np.array(
                [0.05, np.random.uniform(-0.127, 0.127), 0.2373])  # 0.2373 is mode of z pos distribution
        elif type(self.initial_position_selection) is list:
            initial_position = np.array(self.initial_position_selection)
        elif self.initial_position_selection == "door":  # start trajectories as they exit the front door
            initial_position = np.array([0.1909, np.random.uniform(-0.0381, 0.0381), np.random.uniform(0., 0.1016)])
            # FIXME cage is actually suspending above floor
        elif self.initial_position_selection == 'downwind_plane':
            initial_position = np.array([0.1, np.random.uniform(-0.127, 0.127), np.random.uniform(0., 0.254)])
        else:
            raise Exception('invalid agent position specified: {}'.format(self.initial_position_selection))

        return initial_position

def injectionco(p1, p2):
	""" Order CrossOver from the handout """
	
	answer = []
	a,b = sample(range(len(p1)), 2)
	if a < b: a,b = b,a
	q = choose(range(len(p1)))
	
	ab = p1[a:b]
	for i in xrange(q):
		if p2[1] not in ab: answer.append(p2[i])
	answer.extend(ab)
	for city in p2:
		if city not in answer: answer.append(city)
	
	return answer

def genCharsChrom(l, chars):
	""" Return chromosome (list) of length l, each of which is made up of the characters from chars. 
		
		pre:
			isinstance(l, int)
			hasattr(chars, '__getitem__')
			hasattr(chars, '__len__')
			len(chars) > 0
		
		post[l, chars]:
			__old__.l == l
			__old__.chars == chars
			len(__return__) == l
			forall(__return__, lambda a: a in chars)
	"""
	
	return [choose(chars) for _ in xrange(l)]