def G1DBinaryStringXTwoPoint(genome, **args):
   """ The 1D Binary String crossover, Two Point

   .. warning:: You can't use this crossover method for binary strings with length of 1.

   """
   sister = None
   brother = None
   gMom = args["mom"]
   gDad = args["dad"]
   
   if len(gMom) == 1:
      Util.raiseException("The Binary String have one element, can't use the Two Point Crossover method !", TypeError)

   cuts = [rand_randint(1, len(gMom)-1), rand_randint(1, len(gMom)-1)]

   if cuts[0] > cuts[1]:
      Util.listSwapElement(cuts, 0, 1)

   if args["count"] >= 1:
      sister = gMom.clone()
      sister.resetStats()
      sister[cuts[0]:cuts[1]] = gDad[cuts[0]:cuts[1]]

   if args["count"] == 2:
      brother = gDad.clone()
      brother.resetStats()
      brother[cuts[0]:cuts[1]] = gMom[cuts[0]:cuts[1]]

   return (sister, brother)

    def compare(self, other):
        """ This method will compare the currently tree with another one

        :param other: the other GTreeGP to compare
        """
        if not isinstance(other, GTreeGP):
            Util.raiseException("The other tree used to compare is not a GTreeGP class", TypeError)

        stack_self = []
        stack_other = []

        stack_self.append(self.getRoot())
        stack_other.append(other.getRoot())

        while len(stack_self) > 0:

            if (len(stack_self) <= 0) or (len(stack_other) <= 0):
                return -1

            tmp_self, tmp_other = stack_self.pop(), stack_other.pop()
            if tmp_self.compare(tmp_other) != 0:
                return -1

            stack_self.extend(tmp_self.getChilds())
            stack_other.extend(tmp_other.getChilds())

        return 0

    def writePopulationDotRaw(ga_engine, filename, start=0, end=0):
        """ Writes to a raw dot file using pydot, the population of trees

        Example:
           >>> GTreeGP.writePopulationDotRaw(ga_engine, "pop.dot", 0, 10)

        This example will draw the first ten individuals of the population into
        the file called "pop.dot".

        :param ga_engine: the GA Engine
        :param filename: the filename, ie. population.dot
        :param start: the start index of individuals
        :param end: the end index of individuals
        """
        if not HAVE_PYDOT:
            Util.raiseException("You must install Pydot to use this feature !")

        pop = ga_engine.getPopulation()
        graph = pydot.Dot(graph_type="digraph")

        if not isinstance(pop[0], GTreeGP):
            Util.raiseException("The population must have individuals of the GTreeGP chromosome !")

        n = 0
        end_index = len(pop) if end == 0 else end
        for i in xrange(start, end_index):
            ind = pop[i]
            subg = pydot.Cluster(
                "cluster_%d" % i,
                label="\"Ind. #%d - Score Raw/Fit.: %.4f/%.4f\"" % (i, ind.getRawScore(), ind.getFitnessScore())
            )
            n = ind.writeDotGraph(subg, n)
            graph.add_subgraph(subg)

        graph.write(filename, prog='dot', format="raw")

def G2DListMutatorSwap(genome, **args):
   """ The mutator of G1DList, Swap Mutator

   .. note:: this mutator is :term:`Data Type Independent`

   """

   if args["pmut"] <= 0.0:
      return 0
   height, width = genome.getSize()
   elements = height * width

   mutations = args["pmut"] * elements

   if mutations < 1.0:
      mutations = 0
      for i in xrange(height):
         for j in xrange(width):
            if Util.randomFlipCoin(args["pmut"]):
               index_b = (rand_randint(0, height - 1), rand_randint(0, width - 1))
               Util.list2DSwapElement(genome.genomeList, (i, j), index_b)
               mutations += 1
   else:
      for it in xrange(int(round(mutations))):
         index_a = (rand_randint(0, height - 1), rand_randint(0, width - 1))
         index_b = (rand_randint(0, height - 1), rand_randint(0, width - 1))
         Util.list2DSwapElement(genome.genomeList, index_a, index_b)

   return int(mutations)

def G2DBinaryStringMutatorSwap(genome, **args):
   """ The mutator of G2DBinaryString, Swap Mutator

   .. versionadded:: 0.6
      The *G2DBinaryStringMutatorSwap* function
   """

   if args["pmut"] <= 0.0:
      return 0
   height, width = genome.getSize()
   elements = height * width

   mutations = args["pmut"] * elements

   if mutations < 1.0:
      mutations = 0
      for i in xrange(height):
         for j in xrange(width):
            if Util.randomFlipCoin(args["pmut"]):
               index_b = (rand_randint(0, height - 1), rand_randint(0, width - 1))
               Util.list2DSwapElement(genome.genomeString, (i, j), index_b)
               mutations += 1
   else:
      for it in xrange(int(round(mutations))):
         index_a = (rand_randint(0, height - 1), rand_randint(0, width - 1))
         index_b = (rand_randint(0, height - 1), rand_randint(0, width - 1))
         Util.list2DSwapElement(genome.genomeString, index_a, index_b)

   return int(mutations)

def G1DListMutatorSIM(genome, **args):
   """ The mutator of G1DList, Simple Inversion Mutation

   .. note:: this mutator is :term:`Data Type Independent`

   """
   mutations = 0
   if args["pmut"] <= 0.0:
      return 0

   cuts = [rand_randint(0, len(genome)), rand_randint(0, len(genome))]

   if cuts[0] > cuts[1]:
      Util.listSwapElement(cuts, 0, 1)

   if (cuts[1] - cuts[0]) <= 0:
      cuts[1] = rand_randint(cuts[0], len(genome))

   if Util.randomFlipCoin(args["pmut"]):
      part = genome[cuts[0]:cuts[1]]
      if len(part) == 0:
         return 0
      part.reverse()
      genome[cuts[0]:cuts[1]] = part
      mutations += 1

   return mutations

def G1DListMutatorAllele(genome, **args):
   """ The mutator of G1DList, Allele Mutator

   To use this mutator, you must specify the *allele* genome parameter with the
   :class:`GAllele.GAlleles` instance.

   """
   if args["pmut"] <= 0.0:
      return 0
   listSize = len(genome)
   mutations = args["pmut"] * listSize

   allele = genome.getParam("allele", None)
   if allele is None:
      Util.raiseException("to use the G1DListMutatorAllele, you must specify the 'allele' parameter", TypeError)

   if mutations < 1.0:
      mutations = 0
      for it in xrange(listSize):
         if Util.randomFlipCoin(args["pmut"]):
            new_val = allele[it].getRandomAllele()
            genome[it] = new_val
            mutations += 1
   else:
      for it in xrange(int(round(mutations))):
         which_gene = rand_randint(0, listSize - 1)
         new_val = allele[which_gene].getRandomAllele()
         genome[which_gene] = new_val

   return int(mutations)

	def distanceFromCutToClosestRuleByLeft(self,cut):
		if ((cut < 0) or cut > self.ruleSetSize) :
			Util.raiseException("Crossover cut point %s is out of the bounds of the rule set <%s,%s>" %(cut,0,self.ruleSetSize), ValueError)
		shift = 0
		for lower,upper in self.rulePartition:
			if upper > cut: 
				return cut - lower

def G1DBinaryStringXSinglePoint(genome, **args):
#   """ The crossover of 1D Binary String, Single Point
#
#   .. warning:: You can't use this crossover method for binary strings with length of 1.
#
#   """
   sister = None
   brother = None
   gMom = args["mom"]
   gDad = args["dad"]

   if len(gMom) == 1:
      Util.raiseException("The Binary String have one element, can't use the Single Point Crossover method !", TypeError)

   cut = rand_randint(1, len(gMom)-1)

   if args["count"] >= 1:
      sister = gMom.clone()
      sister.resetStats()
      sister[cut:] = gDad[cut:]

   if args["count"] == 2:
      brother = gDad.clone()
      brother.resetStats()
      brother[cut:] = gMom[cut:]

   Pruner(sister)
   Pruner(brother)
   #print "\tsister :\t\t %s\n\n" % (sister.getBinary(),)
   #print "\tbrother:\t\t %s\n\n" % (brother.getBinary(),)
   return (sister, brother)

def rule_eval2(genome):

	MAX_ALLOWED_RULES = genome.getParam("maxrules")
	#genomes that surpass rule threshold are automatically discarded
	if len(genome.rulePartition) > MAX_ALLOWED_RULES: return 0 

	examples = genome.getExamplesRef()
	attribute_bits = [2, 5, 4, 4, 3, 14, 9, 4, 2, 2, 5, 2, 3, 3, 4]
	if not isinstance(genome,GD1BinaryStringSet):
			Util.raiseException("The rule must of type G1DBinaryString", ValueError)
	
	if (sum(attribute_bits) != genome.rule_length -1 ):
		Util.raiseException("Example is not consistent with its attributes", ValueError)

	rule_binary = genome.getBinary()
	rule_length = genome.rule_length
	rule_list = [rule_binary[i:i+rule_length] for i in xrange(0,len(rule_binary),rule_length)]


	corrects = 0.0
	for example in examples:
		corrects += match_example(example,rule_list, attribute_bits)

	accuracy = corrects/float(len(examples))
	genome.setAccuracy(accuracy)
	#the final score is the classification accuracy to the power of 2
	score = (accuracy)**2
	#applying ruleLength penalization. if not specified, decay is 1 and penalization is nonexistent
	decay = genome.getParam("decay")
	new_score = score*(decay**(len(rule_list) -1))
	#print 'correct: %.2f | total: %.2f | size: %.2f | score: %.2f/%.2f' % (corrects, len(examples), len(rule_list), score, new_score)
	return new_score

def RawScoreCriteria(ga_engine):
    """ Terminate the evolution using the **bestrawscore** and **rounddecimal**
    parameter obtained from the individual

    Example:
       >>> genome.setParams(bestrawscore=0.00, rounddecimal=2)
       (...)
       >>> ga_engine.terminationCriteria.set(GSimpleGA.RawScoreCriteria)

    """
    ind = ga_engine.bestIndividual()
    bestRawScore = ind.getParam("bestrawscore")
    roundDecimal = ind.getParam("rounddecimal")

    if bestRawScore is None:
        Util.raiseException("you must specify the bestrawscore parameter", ValueError)

    if ga_engine.getMinimax() == Consts.minimaxType["maximize"]:
        if roundDecimal is not None:
            return round(bestRawScore, roundDecimal) <= round(ind.score, roundDecimal)
        else:
            return bestRawScore <= ind.score
    else:
        if roundDecimal is not None:
            return round(bestRawScore, roundDecimal) >= round(ind.score, roundDecimal)
        else:
            return bestRawScore >= ind.score

def GTreeGPInitializator(genome, **args):
    """This initializator accepts the follow parameters:

    *max_depth*
       The max depth of the tree

    *method*
       The method, accepts "grow", "full" or "ramped"

    .. versionadded:: 0.6
       The *GTreeGPInitializator* function.
    """

    max_depth = genome.getParam("max_depth", 5)
    method = genome.getParam("method", "grow")
    ga_engine = args["ga_engine"]

    if method == "grow":
        root = GTree.buildGTreeGPGrow(ga_engine, 0, max_depth)
    elif method == "full":
        root = GTree.buildGTreeGPFull(ga_engine, 0, max_depth)
    elif method == "ramped":
        if Util.randomFlipCoin(0.5):
            root = GTree.buildGTreeGPFull(ga_engine, 0, max_depth)
        else:
            root = GTree.buildGTreeGPGrow(ga_engine, 0, max_depth)
    else:
        Util.raiseException("Unknown tree initialization method [%s] !" % method)

    genome.setRoot(root)
    genome.processNodes()
    assert genome.getHeight() <= max_depth

def G1DListCrossoverSinglePoint(genome, **args):
   """ The crossover of G1DList, Single Point

   .. warning:: You can't use this crossover method for lists with just one element.

   """
   sister = None
   brother = None
   gMom = args["mom"]
   gDad = args["dad"]

   if len(gMom) == 1:
      Util.raiseException("The 1D List have one element, can't use the Single Point Crossover method !", TypeError)

   cut = rand_randint(1, len(gMom) - 1)

   if args["count"] >= 1:
      sister = gMom.clone()
      sister.resetStats()
      sister[cut:] = gDad[cut:]

   if args["count"] == 2:
      brother = gDad.clone()
      brother.resetStats()
      brother[cut:] = gMom[cut:]

   return (sister, brother)

	def ruleExists(self,rule):
		if not (isinstance(rule,str) or isinstance(rule,G1DBinaryString)):
			Util.raiseException("BitString expected as input", ValueError)
		if isinstance(rule,G1DBinaryString): rule = G1DBinaryString.getBinary()
		for lowerCut,upperCut in self.rulePartition:
			currentRule = ''.join(map(str,self.ruleSet[lowerCut:upperCut]))
			if (currentRule[:-1]==rule): return True
		return False

   def setRoot(self, root):
      """ Sets the root of the tree

      :param root: the tree root node
      """
      if not isinstance(root, GTreeNodeBase):
         Util.raiseException("The root must be a node", TypeError)
      self.root_node = root

   def __typeCheck(self, func):
      """ Used internally to check if a function passed to the
      function slot is callable. Otherwise raises a TypeError exception.

      :param func: the function object
      """
      if not callable(func):
         Util.raiseException("The function must be a method or function", TypeError)

    def setElitism(self, flag):
        """ Sets the elitism option, True or False

        :param flag: True or False

        """
        if type(flag) != bool:
            Util.raiseException("Elitism option must be True or False", TypeError)
        self.elitism = flag

    def setMinimax(self, mtype):
        """ Sets the minimize/maximize mode, use Consts.minimaxType

        :param mtype: the minimax mode, from Consts.minimaxType

        """
        if mtype not in Consts.minimaxType.values():
            Util.raiseException("Minimax must be maximize or minimize", TypeError)
        self.minimax = mtype

    def setGenerations(self, num_gens):
        """ Sets the number of generations to evolve

        :param num_gens: the number of generations

        """
        if num_gens < 1:
            Util.raiseException("Number of generations must be >= 1", ValueError)
        self.nGenerations = num_gens

    def setCrossoverRate(self, rate):
        """ Sets the crossover rate, between 0.0 and 1.0

        :param rate: the rate, between 0.0 and 1.0

        """
        if (rate > 1.0) or (rate < 0.0):
            Util.raiseException("Crossover rate must be >= 0.0 and <= 1.0", ValueError)
        self.pCrossover = rate