source: cpp/frams/genetics/f4/f4_oper.cpp @ 1227

// This file is a part of Framsticks SDK.  http://www.framsticks.com/
// Copyright (C) 1999-2023  Maciej Komosinski and Szymon Ulatowski.
// See LICENSE.txt for details.

// Copyright (C) 1999,2000  Adam Rotaru-Varga (adam_rotaru@yahoo.com), GNU LGPL
// Copyright (C) since 2001 Maciej Komosinski
// 2018, Grzegorz Latosinski, added support for new API for neuron types and their properties


// This representation has a tendency to bloat - adding a small penalty to fitness such as "this.velocity - 0.000000001*String.len(this.genotype);"
// may help, but it would be better to improve the source code to make genetic operators neutral in terms of genotype length. Adding such a penalty
// removes "work in progress" changes in genotypes thus promoting immediate, straightforward improvements while hindering slower, multifaceted progress.
// TODO getting rid of redundancy (having valid genotypes with a lot of "junk code") in this representation looks like a good idea.
// 
// Note: symbols after the last > are ignored, for example /*4*/<X>N:N>N:N[2:-0.5]XXXwhatever but since they are not parsed into the f4_Node tree, they will be lost after any mutation.
//
// TODO the behavior of neuron input indexes during mutation seems badly implemented (see also TREAT_BAD_CONNECTIONS_AS_ERRORS). Are they kept properly maintained when nodes are added and removed? This could be done well because during mutation we operate on the tree structure with cross-references between nodes (so they should not be affected by local changes in the tree), and then convert the tree back to string. Yet, the f4_Node.conn_from is an integer and these fields in nodes do not seem to be maintained on tree node adding/removal... change these integer offsets to references to node objects? But actually, do the offsets that constitute relative connection references concern the f4_Node tree structure (and all these sophisticated calculations of offsets during mutation are useful) or rather they concern the f4_Cells development? verify all situations in f4_Cell::oneStep(), case '['.
// TODO add simplifying sequences of modifiers (so capital and small letter cancel out, like in f1) - but seems like each single modifier is a separate f4_Node? and perhaps we don't want to use the repair mechanism for this... maybe mutations, when they add/modify/remove a modifier node, should be "cleaning" the tree by removing nodes when they encounter contradictory modifiers on the same subpath?
// TODO add support for properties of (any class of) neurons - not just sigmoid/force/intertia (':' syntax) for N
// TODO add mapping genotype character ranges for neural [connections]


#include "f4_oper.h"
#include <frams/util/sstring.h>
#include <common/log.h>

#include <stdio.h>
#include <stdlib.h>
#include "common/nonstd_math.h"
#include <string.h>


const char *Geno_f4::all_modifiers = F14_MODIFIERS ","; //comma in f4 is handled the same way (simple node, F4_ADD_SIMP) as modifiers

// codes that can be changed (apart from being added/deleted)
#define F4_MUT_CHANGE_CODES "<[#"

#define FIELDSTRUCT Geno_f4

static ParamEntry geno_f4_paramtab[] =
{
        { "Genetics: f4", 1, F4_COUNT + F4_ADD_COUNT + F4_MODNEU_COUNT + 2, },
        { "f4_mut_add", 0, 0, "Add node", "f 0 100 50", FIELD(prob[F4_ADD]), "Mutation: probability of adding a node", },
        { "f4_mut_add_div", 0, 0, "- add division", "f 0 100 20", FIELD(probadd[F4_ADD_DIV]), "Add node mutation: probability of adding a division", },
        { "f4_mut_add_conn", 0, 0, "- add connection", "f 0 100 15", FIELD(probadd[F4_ADD_CONN]), "Add node mutation: probability of adding a neural connection", },
        { "f4_mut_add_neupar", 0, 0, "- add neuron property", "f 0 100 5", FIELD(probadd[F4_ADD_NEUPAR]), "Add node mutation: probability of adding a neuron property/modifier", },
        { "f4_mut_add_rep", 0, 0, "- add repetition '#'", "f 0 100 10", FIELD(probadd[F4_ADD_REP]), "Add node mutation: probability of adding the '#' repetition gene", },
        { "f4_mut_add_simp", 0, 0, "- add simple node", "f 0 100 50", FIELD(probadd[F4_ADD_SIMP]), "Add node mutation: probability of adding a random, simple gene", },

        { "f4_mut_del", 0, 0, "Delete node", "f 0 100 20", FIELD(prob[F4_DEL]), "Mutation: probability of deleting a node", },

        { "f4_mut_mod", 0, 0, "Modify node", "f 0 100 30", FIELD(prob[F4_MOD]), "Mutation: probability of changing a node", },
        { "f4_mut_modneu_conn", 0, 0, "- neuron input: modify source", "f 0 100 60", FIELD(probmodneu[F4_MODNEU_CONN]), "Neuron input mutation: probability of changing its source neuron", },
        { "f4_mut_modneu_weight", 0, 0, "- neuron input: modify weight", "f 0 100 40", FIELD(probmodneu[F4_MODNEU_WEIGHT]), "Neuron input mutation: probability of changing its weight", },

        { "f4_mut_max_rep", 1, 0, "Maximum number for '#' repetitions", "d 2 20 6", FIELD(mut_max_rep), "Maximum allowed number of repetitions for the '#' repetition gene", },
        { "f4_mut_exmod", 1, 0, "Excluded modifiers", "s 0 30", FIELD(excluded_modifiers), "Modifiers that will not be added nor deleted during mutation\n(all: " F14_MODIFIERS ")", },
        { 0, },
};

#undef FIELDSTRUCT


Geno_f4::Geno_f4()
{
        supported_format = '4';
        par.setParamTab(geno_f4_paramtab);
        par.select(this);
        par.setDefault();

        mutation_method_names = new const char*[F4_COUNT + F4_ADD_COUNT - 1];
        int index = 0;
        mutation_method_names[index++] = "added division";
        mutation_method_names[index++] = "added neural connection";
        mutation_method_names[index++] = "added neuron property";
        mutation_method_names[index++] = "added repetition gene";
        mutation_method_names[index++] = "added a simple node";
        mutation_method_names[index++] = "deleted a node";
        mutation_method_names[index++] = "modified a node";
        if (index != F4_COUNT + F4_ADD_COUNT - 1) logMessage("Geno_f4", "Constructor", LOG_CRITICAL, "Mutation names init error");
}

void Geno_f4::setDefaults()
{
        excluded_modifiers = F14_MODIFIERS_RARE F14_MODIFIERS_VISUAL;
}

int Geno_f4::ValidateRec(f4_Node *geno, int retrycount) const
{
        // ! the genotype is geno->child (not geno) !
        // build from it with repair on

        f4_Cells cells(geno->child, 1);
        cells.simulate();  //we should simulate?!

        // errors not fixed:
        if (cells.getErrorCode() == GENOPER_OPFAIL)
        {
                if (cells.getErrorPos() >= 0) return 1 + cells.getErrorPos();
                return GENOPER_OPFAIL;
        }
        // errors can be fixed
        if (cells.getErrorCode() == GENOPER_REPAIR)
        {
                cells.repairGeno(geno, 1);
                // note: geno might have been fixed
                // check again
                int res2 = GENOPER_OK;
                if (retrycount > 0)
                        res2 = ValidateRec(geno, retrycount - 1);

                if (res2 == GENOPER_OK) return GENOPER_REPAIR;
                return res2;
        }
        // no errors:
        return GENOPER_OK;
}


int Geno_f4::validate(char *& geno, const char *genoname)
{
        // convert geno to tree, then try to validate 20 times
        f4_Node root;
        if (f4_processrec(geno, 0, &root) || root.childCount() != 1) return GENOPER_OK; // cannot repair
        if (ValidateRec(&root, 20) == GENOPER_REPAIR) // if repaired, make it back to string
        {
                geno[0] = 0;
                root.child->sprintAdj(geno);
        }
        return GENOPER_OK;
}


int Geno_f4::checkValidity(const char* geno, const char *genoname)
{
        f4_Node root;
        int res = f4_processrec(geno, 0, &root);
        if (res) return res;  // errorpos, >0
        if (root.childCount() != 1) return 1; //earlier: GENOPER_OPFAIL
        f4_Cells cells(root.child, 0);
        cells.simulate();
        if (cells.getErrorCode() == GENOPER_OPFAIL || cells.getErrorCode() == GENOPER_REPAIR)
        {
                if (cells.getErrorPos() >= 0) return 1 + cells.getErrorPos();
                else return 1; //earlier: GENOPER_OPFAIL;
        }
        else return GENOPER_OK;
}


int Geno_f4::MutateOne(f4_Node *& g, int &method) const
{
        // ! the genotype is g->child (not g) !

        // do the mutation
        // pick a random node
        f4_Node *node_mutated = g->child->randomNode();
        //DB( printf("%c\n", node_mutated->name); )

        switch (roulette(prob, F4_COUNT))
        {
        case F4_ADD:
        {
                // add a node
                switch (method = roulette(probadd, F4_ADD_COUNT))
                {
                case F4_ADD_DIV:
                {
                        // add division ('<')
                        f4_Node *node_mutated_parent = node_mutated->parent;
                        node_mutated_parent->removeChild(node_mutated);
                        f4_Node *node_new_div = new f4_Node('<', node_mutated_parent, node_mutated_parent->pos);
                        node_new_div->addChild(node_mutated);
                        // new cell is stick or neuron
                        // "X>" or "N>"
                        constexpr double STICK_OR_NEURON = 0.5; // hardcoded probability... could be parametrized, but in a general case (unknown fitness goal) 0.5 makes sense?
                        f4_Node *node_new = NULL; //stick or neuron or neural connection
                        if (rndDouble(1) < STICK_OR_NEURON)
                                node_new = new f4_Node('X', node_new_div, node_new_div->pos);
                        else
                        {
                                // make neuron
                                NeuroClass *rndclass = GenoOperators::getRandomNeuroClass(Model::SHAPETYPE_BALL_AND_STICK);
                                if (rndclass == NULL) //no active neurons?
                                {
                                        node_new = new f4_Node('X', node_new_div, node_new_div->pos);
                                }
                                else
                                {
                                        f4_Node *node_new_neuron = new f4_Node(rndclass->getName().c_str(), node_new_div, node_new_div->pos);
                                        node_new_neuron->neuclass = rndclass;
                                        node_new = node_new_neuron; //can be changed below if all goes well and we add a new connection too
                                        if (probadd[F4_ADD_CONN] > 0) //user wants to add connections
                                        {
                                                if (rndclass->getPreferredInputs() != 0) //neuron also wants connections?
                                                {
                                                        int node_new_neuron_index, other_neuron_index;
                                                        bool ok = findConnectionNeuronIndexes(g, node_new_neuron, true, node_new_neuron_index, other_neuron_index); //node_new_neuron_index==-1 should never happen, we just added node_new_neuron we are looking for
                                                        if (ok) //we can create a new connection
                                                        {
                                                                node_new = new f4_Node('[', node_new_neuron, node_new_div->pos);
                                                                connectionNodeChangeRandom(node_new, node_new_neuron_index, other_neuron_index);
                                                        }
                                                }
                                                else if (rndclass->getPreferredOutput() > 0) //neuron also wants connections?
                                                {
                                                        // Not so easy: we would need to add a '[' node as a child not of node_new_neuron, but of other neuron that would get an input from node_new_neuron (and need to properly calculate relative connection reference).
                                                        // The "false" argument in findConnectionNeuronIndexes() below is not suffient, because we also need to access (find) the f4_Node of the other neuron.
                                                        // A similar logic is implemented in F4_ADD_CONN below, but let's not complicate this F4_ADD_DIV mutation anymore.
                                                        // A disadvantage is that the node_new_neuron added here which is a neuron that provides output (e.g., a receptor, N, etc.) will not get connected immediately here even when there are already existing neurons wanting inputs (e.g., muscles, N, etc.).
                                                        //bool ok = findConnectionNeuronIndexes(g, ... , false, ..., ...);
                                                }
                                        }
                                }
                        }
                        new f4_Node('>', node_new, node_new->pos); //adds to node_new
                        node_mutated->parent = node_new_div;
                        // now, swap children with 50% chance
                        if (rndUint(2) == 0)
                        {
                                node_mutated_parent = node_new_div->child;
                                node_new_div->child = node_new_div->child2;
                                node_new_div->child2 = node_mutated_parent;
                        }
                }
                break;
                case F4_ADD_CONN:
                {
                        // add connection

                        // the probability that a randomly selected node will be a neuron and additionally this neuron will accept inputs is low,
                        // so we disregard randomly picked node_mutated and build a list of all valid candidate nodes here, then select a random one from them.

                        vector<f4_Node*> candidate_nodes; //neurons that accept input(s)
                        for (int i = 0; i < g->count(); i++)
                        {
                                f4_Node *node = g->ordNode(i);
                                f4_Node *node_parent = node->parent;
                                if (node_parent == NULL || node_parent->neuclass == NULL) continue;
                                int prefinputs = node_parent->neuclass->getPreferredInputs();
                                if (prefinputs == -1 ||
                                        prefinputs > 0) //would be nice if we could easily and quickly check if the parent already has its preferred inputs used, so that we do not produce an invalid mutation here... it is possible through the f4_Cell.n_conns field, but only during organism development
                                        candidate_nodes.push_back(node);
                        }

                        if (candidate_nodes.size() == 0)
                                return GENOPER_OPFAIL;

                        node_mutated = candidate_nodes[rndUint((unsigned int)candidate_nodes.size())];
                        f4_Node *node_mutated_parent = node_mutated->parent;

                        int node_mutated_parent_index, other_neuron_index;
                        bool ok = findConnectionNeuronIndexes(g, node_mutated_parent, true, node_mutated_parent_index, other_neuron_index); //node_mutated_parent_index==-1 should never happen, we earlier selected the neuron we are now looking for
                        if (!ok)
                                return GENOPER_OPFAIL;

                        node_mutated->parent->removeChild(node_mutated); //this subtree will be reconnected below, as a child to node_new_conn
                        f4_Node *node_new_conn = new f4_Node('[', node_mutated->parent, node_mutated->parent->pos);
                        node_new_conn->addChild(node_mutated);
                        node_mutated->parent = node_new_conn; // node_mutated_parent is the neuron, node_mutated->parent is '['
                        connectionNodeChangeRandom(node_new_conn, node_mutated_parent_index, other_neuron_index);
                }
                break;
                case F4_ADD_NEUPAR:
                {
                        // add neuron modifier
                        node_mutated->parent->removeChild(node_mutated);
                        f4_Node *n2 = new f4_Node(':', node_mutated->parent, node_mutated->parent->pos);
                        nparNodeMakeRandom(n2);
                        n2->addChild(node_mutated);
                        node_mutated->parent = n2;
                }
                break;
                case F4_ADD_REP:
                {
                        // add repetition ('#')
                        // repeated code (left child) is the original, right child is empty, count is set to 2
                        f4_Node *n3 = node_mutated->parent;
                        n3->removeChild(node_mutated);
                        f4_Node *n2 = new f4_Node('#', n3, n3->pos);
                        n2->reps = 2;
                        n2->addChild(node_mutated);
                        new f4_Node('>', n2, n2->pos);
                        node_mutated->parent = n2;
                }
                break;
                case F4_ADD_SIMP:
                {
                        // add simple node
                        // choose a simple node from ADD_SIMPLE_CODES
                        node_mutated->parent->removeChild(node_mutated);
                        //f4_Node *n2 = new f4_Node(ADD_SIMPLE_CODES[rndUint(strlen(ADD_SIMPLE_CODES))], n1->parent, n1->parent->pos);
                        int modifierid = GenoOperators::getRandomChar(all_modifiers, excluded_modifiers.c_str());
                        f4_Node *n2 = new f4_Node(all_modifiers[modifierid], node_mutated->parent, node_mutated->parent->pos);
                        n2->addChild(node_mutated);
                        node_mutated->parent = n2;
                }
                break;
                }
        }
        break;

        case F4_DEL:
        {
                method = F4_ADD_COUNT - 1 + F4_DEL;
                // delete a node
                // must pick a node with parent, and at least one child
                // already picked a node, but repeat may be needed
                for (int i = 0; i < 10; i++)
                {
                        if ((node_mutated->parent != NULL) && (g != node_mutated->parent))
                                if (node_mutated->child != NULL)
                                        break;
                        // try a new one
                        node_mutated = g->child->randomNode();
                }
                if ((node_mutated->parent != NULL) && (g != node_mutated->parent))
                {
                        switch (node_mutated->childCount())
                        {
                        case 0: break;
                        case 1:  // one child
                        {
                                f4_Node *node_mutated_parent = node_mutated->parent;
                                node_mutated_parent->removeChild(node_mutated);
                                if (node_mutated->child != NULL)
                                {
                                        node_mutated->child->parent = node_mutated_parent;
                                        node_mutated_parent->addChild(node_mutated->child);
                                        node_mutated->child = NULL;
                                }
                                if (node_mutated->child2 != NULL)
                                {
                                        node_mutated->child2->parent = node_mutated_parent;
                                        node_mutated_parent->addChild(node_mutated->child2);
                                        node_mutated->child2 = NULL;
                                }
                                // destroy n1
                                node_mutated->parent = NULL;
                                delete node_mutated;
                        }
                        break;

                        case 2:  // two children
                        {
                                // two children
                                f4_Node *n2 = node_mutated->parent;
                                n2->removeChild(node_mutated);
                                // n1 has two children. pick one randomly 50-50, destroy other
                                if (rndUint(2) == 0)
                                {
                                        node_mutated->child->parent = n2;
                                        n2->addChild(node_mutated->child);
                                        node_mutated->child = NULL;
                                        node_mutated->child2->parent = NULL;
                                }
                                else
                                {
                                        node_mutated->child2->parent = n2;
                                        n2->addChild(node_mutated->child2);
                                        node_mutated->child2 = NULL;
                                        node_mutated->child->parent = NULL;
                                }
                                // destroy n1
                                node_mutated->parent = NULL;
                                delete node_mutated;
                        }
                        break;
                        }
                }
                else return GENOPER_OPFAIL;
        }
        break;
        case F4_MOD:
        {
                method = F4_ADD_COUNT - 1 + F4_MOD;
                // change a node
                // the only nodes that are modifiable are F4_MUT_CHANGE_CODES
                // try to get a modifiable node
                // already picked a node, but repeat may be needed
                int i = 0;
                while (1)
                {
                        if (strchr(F4_MUT_CHANGE_CODES, node_mutated->name[0])) break;
                        // try a new one
                        node_mutated = g->child->randomNode();
                        i++;
                        if (i >= 20) return GENOPER_OPFAIL;
                }
                switch (node_mutated->name[0])
                {
                case '<':
                {
                        // swap children
                        f4_Node *n2 = node_mutated->child;
                        node_mutated->child = node_mutated->child2;
                        node_mutated->child2 = n2;
                }
                break;
                case '[':
                {
                        switch (roulette(probmodneu, F4_MODNEU_COUNT))
                        {
                        case F4_MODNEU_CONN:
                        {
                                f4_Node *neuron = node_mutated; //we start in '[' node and follow up parents until we find the neuron with these connections
                                while (neuron != NULL && neuron->neuclass == NULL) neuron = neuron->parent;
                                if (neuron == NULL)
                                        return GENOPER_OPFAIL; //did not find a neuron on the way up tree


                                int neuron_index, other_neuron_index;
                                bool ok = findConnectionNeuronIndexes(g, neuron, true, neuron_index, other_neuron_index); //neuron_index==-1 should never happen, we know the neuron is in the tree
                                if (!ok)
                                        return GENOPER_OPFAIL;

                                connectionNodeChangeRandom(node_mutated, neuron_index, other_neuron_index);
                                break;
                        }
                        case F4_MODNEU_WEIGHT:
                                node_mutated->conn_weight = GenoOperators::getMutatedNeuronConnectionWeight(node_mutated->conn_weight);
                                break;
                        }
                }
                break;

                case '#':
                {
                        repeatNodeChangeRandom(node_mutated);
                }
                break;
                }
        }
        break;

        default: //no mutations allowed?
                return GENOPER_OPFAIL;
        }
        return GENOPER_OK;
}

// find all neurons and the needle
vector<NeuroClass*> Geno_f4::findAllNeuronsAndNode(f4_Node * const & g, f4_Node* const &needle_neuron, int &found_index)
{
        found_index = -1; // not found (for example, needle_neuron is not a neuroclass node or not added to the "g" tree)
        vector<NeuroClass*> neulist;
        for (int i = 0; i < g->count(); i++)
        {
                f4_Node *node = g->ordNode(i);
                if (node->neuclass != NULL)
                {
                        neulist.push_back(node->neuclass);
                        if (node == needle_neuron)
                                found_index = int(neulist.size()) - 1;
                }
        }
        return neulist;
}

bool Geno_f4::findConnectionNeuronIndexes(f4_Node * const &g, f4_Node *neuron, bool other_has_output, int &neuron_index, int &other_neuron_index)
{
        vector<NeuroClass*> neulist = findAllNeuronsAndNode(g, neuron, neuron_index);
        if (neuron_index == -1)
                return false;

        other_neuron_index = other_has_output ?
                GenoOperators::getRandomNeuroClassWithOutput(neulist) //find an existing neuron that provides an output
                :
                GenoOperators::getRandomNeuroClassWithInput(neulist); //find an existing neuron that accepts input(s)
        return other_neuron_index >= 0;
}

// change a [ node
void Geno_f4::connectionNodeChangeRandom(f4_Node *nn, int nn_index, int other_index) const
{
        // relative input connection to some existing neuron
        nn->conn_from = nn_index - other_index;
        //nn->conn_from = (int)(4.0f * (rndDouble(1) - 0.5f)); //in very old times - did not care about neuron input/output preferences

        nn->conn_weight = GenoOperators::getMutatedNeuronConnectionWeight(nn->conn_weight);
}


// make a random : node
void Geno_f4::nparNodeMakeRandom(f4_Node *nn) const
{
        unsigned int prop = rndUint(3); //random neuron property
        nn->prop_symbol = "!=/"[prop];
        nn->prop_increase = rndUint(2) == 1;
}

// change a repeat # node
void Geno_f4::repeatNodeChangeRandom(f4_Node *nn) const
{
        if (rndDouble(1) < 0.5f) nn->reps++; else nn->reps--; // change count
        if (nn->reps < 1) nn->reps = 1;
        if (nn->reps > mut_max_rep) nn->reps = mut_max_rep;
}


int Geno_f4::MutateOneValid(f4_Node *& g, int &method) const
// mutate one, until a valid genotype is obtained
{
        // ! the genotype is g->child (not g) !
        int i, res;
        f4_Node *gcopy = NULL;
        const int TRY_MUTATE = 20;
        // try this at most TRY_MUTATE times: copy, mutate, then validate
        for (i = 0; i < TRY_MUTATE; i++)
        {
                gcopy = g->duplicate();

                res = MutateOne(gcopy, method);

                if (GENOPER_OK != res)
                {
                        // mutation failed, try again
                        delete gcopy;
                        continue;  // for
                }
                // try to validate it
                res = ValidateRec(gcopy, 10);
                // accept if it is OK, or was repaired
                if (GENOPER_OK == res)
                        //(GENOPER_REPAIR == res)
                {
                        // destroy the original one
                        g->destroy();
                        // make it the new one
                        *g = *gcopy;
                        gcopy->child = NULL;
                        gcopy->child2 = NULL;
                        delete gcopy;
                        res = GENOPER_OK;
                        goto retm1v;
                }
                delete gcopy;
        }
        // attempts failed
        res = GENOPER_OPFAIL;
retm1v:
        return res;
}


int Geno_f4::mutate(char *& g, float & chg, int &method)
{
        f4_Node *root = new f4_Node;
        if (f4_processrec(g, 0, root) || root->childCount() != 1)
        {
                delete root;
                return GENOPER_OPFAIL;
        } // could not convert or bad: fail
        // mutate one node, set chg as this percent
        chg = 1.0 / float(root->child->count());
        if (MutateOneValid(root, method) != GENOPER_OK)
        {
                delete root;
                return GENOPER_OPFAIL;
        }
        // OK, convert back to string
        g[0] = 0;
        root->child->sprintAdj(g);
        delete root;
        return GENOPER_OK;
}


/*
int Geno_f4::MutateMany(char *& g, float & chg)
// check if original is valid, then
// make a number of mutations
{
int res, n, i;
int totNodes = 0;
int maxToMut = 0;

// convert to tree
f4_Node *root;
root = new f4_Node();
res = f4_processrec(g, 0, root);
if (res) {
// could not convert, fail
goto retm;
}
if (1 != root->childCount()) {
res = GENOPER_OPFAIL;
goto retm;
}

// check if original is valid
res = ValidateRec( root, 20 );
// might have been repaired!
if (GENOPER_REPAIR==res) {
res = GENOPER_OK;
}
if (GENOPER_OK != res) {
goto retm;
}

// decide number of nodes to mutate
// decide maximum number of nodes to mutate: 0.25*nodes, min 2
totNodes = root->child->count();
maxToMut = (int)( 0.25f * totNodes);
if (maxToMut<2) maxToMut=2;
if (maxToMut>totNodes) maxToMut=totNodes;

// decide number of nodes to mutate
n = (int)( 0.5f + rndDouble(1) * maxToMut );
if (n<1) n=1;
if (n>totNodes) n=totNodes;
// set chg as this percent
chg = ((float)n) / ((float)totNodes);
for (i=0; i<n; i++)
{
res = MutateOneValid(root);
if (GENOPER_OK != res)
{
res = GENOPER_OPFAIL;
goto retm;
}
}
// OK, convert back to string
g[0]=0;
root->child->sprintAdj(g);
retm:
delete root;
return res;
}
*/


int Geno_f4::CrossOverOne(f4_Node *g1, f4_Node *g2, float chg) const
{
        // ! the genotypes are g1->child and g2->child (not g1 g2) !
        // single offspring in g1
        int smin, smax;
        float size;
        f4_Node *n1, *n2, *n1p, *n2p;

        // determine desired size
        size = (1 - chg) * (float)g1->count();
        smin = (int)(size * 0.9f - 1);
        smax = (int)(size * 1.1f + 1);
        // get a random node with desired size
        n1 = g1->child->randomNodeWithSize(smin, smax);

        // determine desired size
        size = (1 - chg) * (float)g2->count();
        smin = (int)(size * 0.9f - 1);
        smax = (int)(size * 1.1f + 1);
        // get a random node with desired size
        n2 = g2->child->randomNodeWithSize(smin, smax);

        // exchange the two nodes:
        n1p = n1->parent;
        n2p = n2->parent;
        n1p->removeChild(n1);
        n1p->addChild(n2);
        n2p->removeChild(n2);
        n2p->addChild(n1);
        n1->parent = n2p;
        n2->parent = n1p;

        return GENOPER_OK;
}

int Geno_f4::crossOver(char *&g1, char *&g2, float &chg1, float &chg2)
{
        f4_Node root1, root2, *copy1, *copy2;

        // convert genotype strings into tree structures
        if (f4_processrec(g1, 0, &root1) || (root1.childCount() != 1)) return GENOPER_OPFAIL;
        if (f4_processrec(g2, 0, &root2) || (root2.childCount() != 1)) return GENOPER_OPFAIL;

        // decide amounts of crossover, 0.25-0.75
        // adam: seems 0.1-0.9 -- MacKo
        chg1 = 0.1 + rndDouble(0.8);
        chg2 = 0.1 + rndDouble(0.8);

        copy1 = root1.duplicate();
        if (CrossOverOne(copy1, &root2, chg1) != GENOPER_OK) { delete copy1; copy1 = NULL; }
        copy2 = root2.duplicate();
        if (CrossOverOne(copy2, &root1, chg2) != GENOPER_OK) { delete copy2; copy2 = NULL; }

        g1[0] = 0;
        g2[0] = 0;
        if (copy1) { copy1->child->sprintAdj(g1); delete copy1; }
        if (copy2) { copy2->child->sprintAdj(g2); delete copy2; }
        if (g1[0] || g2[0]) return GENOPER_OK; else return GENOPER_OPFAIL;
}

uint32_t Geno_f4::style(const char *g, int pos)
{
        char ch = g[pos];

        // style categories
#define STYL4CAT_MODIFIC F14_MODIFIERS ","
#define STYL4CAT_NEUMOD "/!="
#define STYL4CAT_NEUSPECIAL "|@*"
#define STYL4CAT_DIGIT "+-0123456789.[]" //'+' is only for adjusting old-style properties "/!="
#define STYL4CAT_REST ":XN<># "

        if (!isalpha(ch) && !strchr(STYL4CAT_MODIFIC STYL4CAT_NEUMOD STYL4CAT_NEUSPECIAL STYL4CAT_DIGIT STYL4CAT_REST "\t", ch))
        {
                return GENSTYLE_CS(0, GENSTYLE_INVALID);
        }
        uint32_t style = GENSTYLE_CS(0, GENSTYLE_STRIKEOUT); //default, should be changed below
        if (strchr("X", ch))                     style = GENSTYLE_CS(0, GENSTYLE_BOLD);
        else if (strchr(":", ch))                style = GENSTYLE_CS(0, GENSTYLE_NONE);
        else if (strchr("#", ch))                style = GENSTYLE_RGBS(220, 0, 0, GENSTYLE_BOLD);
        else if (strchr("/=!", ch))              style = GENSTYLE_RGBS(255, 140, 0, GENSTYLE_BOLD); //property... for now, f4 does not supoprt properties in general for any neuron class, like f1 does
        else if (strchr("N@|*", ch))             style = GENSTYLE_RGBS(150, 0, 150, GENSTYLE_BOLD); //neuroclass
        else if (strchr("<", ch))                style = GENSTYLE_RGBS(0, 0, 200, GENSTYLE_BOLD);
        else if (strchr(">", ch))                style = GENSTYLE_RGBS(0, 0, 100, GENSTYLE_NONE);
        else if (strchr(STYL4CAT_DIGIT, ch))     style = GENSTYLE_CS(GENCOLOR_NUMBER, GENSTYLE_NONE);
        else if (strchr(STYL4CAT_MODIFIC, ch))   style = GENSTYLE_RGBS(100, 100, 100, GENSTYLE_NONE);
        else if (strchr(STYL4CAT_NEUMOD, ch))    style = GENSTYLE_RGBS(0, 150, 0, GENSTYLE_NONE);
        if (isalpha(ch))
        {
                // allowed neuron formats:
                //   N:CLASSNAME
                //   N:@
                //   N:|
                // old syntax still supported in coloring, but no longer valid:
                //   [SENSOR, WEIGHT]
                //   N@
                //   N|
                // ...so must have N: or [ before neuroclass name (or just N, but this is handled above - for N@|* only)

                while (pos > 0)
                {
                        pos--;
                        if (!isalpha(g[pos]))
                        {
                                if (isupper(g[pos + 1]) && (g[pos] == '[') || (g[pos] == ':' && pos > 0 && g[pos - 1] == 'N')) //we may have sequences like :-/:I (even though they are not valid) - in this example "I" should not be treated as neuron name, hence there must also be a "N" before ":"
                                        style = GENSTYLE_RGBS(150, 0, 150, GENSTYLE_BOLD); // neuroclass
                                //(...) else (...)
                                //      style = GENSTYLE_RGBS(255, 140, 0, GENSTYLE_BOLD); // property - current f4 does not support neuron properties in a general case, only those old-style "/=!" as +! -! += -= +/ -/
                                break;
                        }
                }
        }
        return style;
}