ian@0: //  Copyright 2011, Ian Hobson.
ian@0: //
ian@0: //  This file is part of gpsynth.
ian@0: //
ian@0: //  gpsynth is free software: you can redistribute it and/or modify
ian@0: //  it under the terms of the GNU General Public License as published by
ian@0: //  the Free Software Foundation, either version 3 of the License, or
ian@0: //  (at your option) any later version.
ian@0: //
ian@0: //  gpsynth is distributed in the hope that it will be useful,
ian@0: //  but WITHOUT ANY WARRANTY; without even the implied warranty of
ian@0: //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
ian@0: //  GNU General Public License for more details.
ian@0: //
ian@0: //  You should have received a copy of the GNU General Public License
ian@0: //  along with gpsynth in the file COPYING. 
ian@0: //  If not, see http://www.gnu.org/licenses/.
ian@0: 
ian@0: #include "sc_grammar.hpp"
ian@0: 
ian@0: #include "boost_ex.hpp"
ian@0: #include "graph_helpers.hpp"
ian@0: #include "logger.hpp"
ian@0: #include "statistics.hpp"
ian@0: #include "std_ex.hpp"
ian@0: 
ian@0: #include "json/json.h"
ian@0: 
ian@0: #include "boost/graph/random.hpp"
ian@0: #include "boost/graph/topological_sort.hpp"
ian@0: 
ian@0: #include <iostream>
ian@0: #include <iterator>
ian@0: #include <fstream>
ian@0: #include <set>
ian@0: #include <sstream>
ian@0: 
ian@0: const int g_maximum_mixer_channels = 3;
ian@0: 
ian@0: const double g_probability_command_node_command = 0.85;
ian@0: const double g_probability_command_node_special = 0.15;
ian@0: 
ian@0: const double g_probability_mod_node_command = 0.25;
ian@0: const double g_probability_mod_node_special = 0.15;
ian@0: const double g_probability_mod_node_constant = 0.4;
ian@0: 
ian@0: const double g_probability_argument_affected = 1.0;
ian@0: 
ian@0: const double g_probability_input_mutation = 1.0;
ian@0: const double g_probability_connection_mutation = 1.0;
ian@0: 
ian@0: const double g_minimum_connection_weight = 0.001;
ian@0: 
ian@0: namespace {
ian@0:   
ian@0:   double MapCoefficientToRange(double c, const stdx::Range<double>& range) {
ian@0:     return range.minimum_ + (range.Size() * c);
ian@0:   }
ian@0:   
ian@0:   // Returns argument connection weight and offset, scaled to argument input
ian@0:   void GenerateWeightAndOffset(const sc::Argument& argument,
ian@0:                                sg::CommandRate rate,
ian@0:                                sg::Connection* connection) {
ian@0:     const stdx::Range<double>& scale_range = (rate == sg::kControlRate) 
ian@0:                                              ? argument.range_control_
ian@0:                                              : argument.range_;
ian@0:     if (argument.fixed_range_) {
ian@0:       connection->weight_ = scale_range.Size();
ian@0:       connection->offset_ = scale_range.Minimum();
ian@0:     } else if (argument.name_ == "in") {
ian@0:       // input connections don't have an offset
ian@0:       double weight = stdx::RandomCoefficient();
ian@0:       if (rate == sg::kAudioRate) {
ian@0:         // square audio weightings
ian@0:         connection->weight_ = weight * weight;
ian@0:       }
ian@0:     } else {
ian@0:       // generate random weight and offset
ian@0:       double weight;
ian@0:       do {
ian@0:         weight = stdx::RandomCoefficient();
ian@0:       } while (weight < g_minimum_connection_weight);
ian@0:       double offset = stdx::RandomRange(0.0, 1.0 - weight);
ian@0:       switch (argument.scaling_mode_) {
ian@0:         case sc::Argument::kScalingLinear:
ian@0:           connection->weight_ = MapCoefficientToRange(weight, scale_range);
ian@0:           connection->offset_ = MapCoefficientToRange(offset, scale_range);
ian@0:           break;
ian@0: 
ian@0:         case sc::Argument::kScalingLog:
ian@0:           connection->weight_ = MapCoefficientToRange(weight * weight * weight,
ian@0:                                                       scale_range);
ian@0:           connection->offset_ = MapCoefficientToRange(offset * offset * offset,
ian@0:                                                       scale_range);
ian@0:           break;
ian@0: 
ian@0:         case sc::Argument::kConstant:
ian@0:           throw std::runtime_error("ApplyRandomWeightAndOffset - preset argument provided");
ian@0:       }
ian@0:     }
ian@0:   }
ian@0: 
ian@0: sc::Argument ParseArgument(const Json::Value& json) {
ian@0:   sc::Argument arg;
ian@0:   arg.name_ = json.get("name", "").asString();
ian@0:   if (json.isMember("constant")) {
ian@0:     arg.scaling_mode_ = sc::Argument::kConstant;
ian@0:     arg.constant_value_ = json["constant"].asDouble();
ian@0:     return arg;
ian@0:   }
ian@0:   if (json.isMember("range")) {
ian@0:     const Json::Value range = json["range"];
ian@0:     arg.range_.SetMinimum(range[0].asDouble());
ian@0:     arg.range_.SetMaximum(range[1].asDouble());
ian@0:   }
ian@0:   if (json.isMember("range_control")) {
ian@0:     const Json::Value range = json["range_control"];
ian@0:     arg.range_control_.SetMinimum(range[0].asDouble());
ian@0:     arg.range_control_.SetMaximum(range[1].asDouble());
ian@0:   } else {
ian@0:     arg.range_control_ = arg.range_;
ian@0:   }
ian@0:   if (json.isMember("fixed_range")) {
ian@0:     arg.fixed_range_ = json["fixed_range"].asBool();
ian@0:   }
ian@0:   std::string scaling = json.get("scaling", "linear").asString();
ian@0:   if (scaling == "linear") {
ian@0:     arg.scaling_mode_ = sc::Argument::kScalingLinear;
ian@0:   } else if (scaling == "log") {
ian@0:     arg.scaling_mode_ = sc::Argument::kScalingLog;
ian@0:   }
ian@0:   return arg;
ian@0: }
ian@0: 
ian@0: sc::Command ParseCommand(const Json::Value& json,
ian@0:                          const std::map<std::string, sc::Argument>& types,
ian@0:                          sc::Command::CommandMode command_mode) {
ian@0:   if (json.type() == Json::stringValue) {
ian@0:     return sc::Command(json.asString(), command_mode);
ian@0:   }
ian@0:   // name
ian@0:   std::string name = json["name"].asString();
ian@0:   // output type
ian@0:   sc::Command::OutputType output_type = sc::Command::kAll;
ian@0:   if (json.isMember("output")) {
ian@0:     std::string output = json["output"].asString();
ian@0:     if (output == "control") {
ian@0:       output_type = sc::Command::kControl;
ian@0:     } else if (output == "audio") {
ian@0:       output_type = sc::Command::kAudio;
ian@0:     }
ian@0:   }
ian@0:   // arguments
ian@0:   std::vector<sc::Argument> args;
ian@0:   // [in] argument for modifiers
ian@0:   if (command_mode == sc::Command::kModifier) {
ian@0:     args.push_back(sc::Argument("in"));
ian@0:   }
ian@0:   Json::Value json_args = json["args"];
ian@0:   Json::ValueType arg_type = json_args.type();
ian@0:   if (arg_type == Json::stringValue) {
ian@0:     // single argument as string
ian@0:     args.push_back(sc::Argument(json_args.asString()));
ian@0:   } else if (arg_type == Json::objectValue) {
ian@0:     // single argument object
ian@0:     if (json_args.isMember("type")) {
ian@0:       args.push_back(stdx::GetFromMap(types, json_args["type"].asString()));
ian@0:       args.back().name_ = json_args["name"].asString();
ian@0:     } else {
ian@0:       args.push_back(ParseArgument(json_args));
ian@0:     }      
ian@0:   } else {
ian@0:     // array of arguments
ian@0:     for (int i = 0; i < json_args.size(); i++) {
ian@0:       Json::Value arg = json_args[i];
ian@0:       if (arg.type() == Json::stringValue) {
ian@0:         args.push_back(sc::Argument(arg.asString()));
ian@0:       } else {
ian@0:         if (arg.isMember("type")) {
ian@0:           args.push_back(stdx::GetFromMap(types, arg["type"].asString()));
ian@0:           args.back().name_ = arg["name"].asString();
ian@0:         } else {
ian@0:           args.push_back(ParseArgument(arg));
ian@0:         }
ian@0:       }
ian@0:     }
ian@0:   }
ian@0:   // success
ian@0:   return sc::Command(name, command_mode, output_type, args);
ian@0: }
ian@0: 
ian@0: 
ian@0: sc::Command ParseSource(const Json::Value& json,
ian@0:                         const std::map<std::string, sc::Argument>& types) {
ian@0:   return ParseCommand(json, types, sc::Command::kSource);
ian@0: }
ian@0: 
ian@0: sc::Command ParseModifier(const Json::Value& json,
ian@0:                           const std::map<std::string, sc::Argument>& types) {
ian@0:   return ParseCommand(json, types, sc::Command::kModifier);
ian@0: }
ian@0: 
ian@0: void MutateValue(double* value, bool* mutation_occurred,
ian@0:                  double range_min = 0.0, double range_max = 1.0) {
ian@0:   // add gaussian noise to values, low variance 
ian@0:   static bx::GaussianGenerator generator = bx::MakeGaussianGenerator(0, 0.125);
ian@0:   double new_value = stdx::Clamp(*value + generator(), range_min, range_max);
ian@0:   if (*value != new_value) {
ian@0:     *value = new_value;
ian@0:     *mutation_occurred = true;
ian@0:   }
ian@0: }
ian@0:   
ian@0: } // namespace
ian@0: 
ian@0: 
ian@0: 
ian@0: namespace sc {
ian@0:   
ian@0: Grammar::Grammar(const std::string& json_data)
ian@0: : max_depth_(3)
ian@0: { 
ian@0:   ParseJSON(json_data); 
ian@0: }
ian@0: 
ian@0: void Grammar::ParseJSON(const std::string& json_data) {
ian@0:   commands_.clear();
ian@0:   Json::Reader reader;
ian@0:   Json::Value root;
ian@0:   if (!reader.parse(json_data, root)) {
ian@0:     std::stringstream message;
ian@0:     message << "Grammar::Parse: Failed to parse data\n"
ian@0:             << reader.getFormattedErrorMessages();
ian@0:     throw std::runtime_error(message.str());
ian@0:   }
ian@0:   try {
ian@0:     // argument types
ian@0:     // stores predefined argument types while parsing grammar
ian@0:     std::map<std::string, Argument> argument_types;
ian@0:     const Json::Value& args = root["arg-types"];
ian@0:     for (int i = 0; i < args.size(); i++) {
ian@0:       const Json::Value& arg = args[i];
ian@0:       argument_types[arg["type"].asString()] = ParseArgument(arg);
ian@0:     }
ian@0:     // sound sources
ian@0:     const Json::Value& sources = root["sources"];
ian@0:     for (int i = 0; i < sources.size(); i++) {
ian@0:       commands_.push_back(ParseSource(sources[i], argument_types)); 
ian@0:     }
ian@0:     // modifiers
ian@0:     const Json::Value& modifiers = root["modifiers"];
ian@0:     for (int i = 0; i < modifiers.size(); i++) {
ian@0:       commands_.push_back(ParseModifier(modifiers[i], argument_types));
ian@0:     }
ian@0:   } catch (const std::exception& e) {
ian@0:     std::stringstream message;
ian@0:     message << "Grammar::Parse: " << e.what();
ian@0:     throw std::runtime_error(message.str());
ian@0:   }
ian@0: }
ian@0:   
ian@0: int Grammar::RandomCommand(sg::CommandRate rate,
ian@0:                            int tree_depth,
ian@0:                            bool must_be_modifier /* = false */) const {
ian@0:   Command::OutputType output;
ian@0:   Command::CommandMode mode;
ian@0:   CommandID command = -1;
ian@0:   CommandID number_of_commands = commands_.size();
ian@0:   // if we're at or one away from maximum depth then the command needs to 
ian@0:   // be a source, headroom of 1 for some parameter control
ian@0:   bool must_be_source = (tree_depth >= (max_depth_ - 1));
ian@0:   do {
ian@0:     command = stdx::Random(number_of_commands);
ian@0:     output = commands_[command].Output();
ian@0:     if (rate == sg::kAudioRate) {
ian@0:       do {
ian@0:         command = stdx::Random(number_of_commands);
ian@0:         output = commands_[command].Output();
ian@0:       } while (!(output == Command::kAll || output == Command::kAudio));
ian@0:     } else {
ian@0:       do {
ian@0:         command = stdx::Random(number_of_commands);
ian@0:         output = commands_[command].Output();
ian@0:       } while (!(output == Command::kAll || output == Command::kControl));
ian@0:     }
ian@0:     mode = commands_[command].Mode();
ian@0:   } while ((must_be_source && (mode != Command::kSource))
ian@0:            || (must_be_modifier && (mode != Command::kModifier)));
ian@0:   return static_cast<int>(command);
ian@0: }
ian@0:   
ian@0: sg::Vertex Grammar::CreateCommand(sg::Graph &graph,
ian@0:                                   sg::CommandRate rate,
ian@0:                                   int depth,
ian@0:                                   bool must_be_modifier /* = false */,
ian@0:                                   bool make_modifier_input /* = true */) const {
ian@0:   // select a random command for the node
ian@0:   int command_id = RandomCommand(rate, depth, must_be_modifier);
ian@0:   // create the node and add it to the graph
ian@0:   sg::Node command_info(command_id, sg::kCommand, rate);
ian@0:   sg::Vertex vertex = boost::add_vertex(command_info, graph);
ian@0:   // a modifier command has to have further nodes added to its main input
ian@0:   const Command& command = commands_[command_id];
ian@0:   for (int i = 0; i < command.Arguments().size(); i++) {
ian@0:     const Argument& argument = command.GetArgument(i);
ian@0:     if (argument.name_ == "in") {
ian@0:       if (make_modifier_input) {
ian@0:         // modifier input must be given a command tree
ian@0:         sg::Vertex tree = RandomTree(graph, rate, kTreeMode_Command, depth + 1);
ian@0:         sg::Connection connection(i);
ian@0:         GenerateWeightAndOffset(argument, rate, &connection);
ian@0:         boost::add_edge(tree, vertex, connection, graph);
ian@0:       }
ian@0:     } else if (argument.scaling_mode_ == sc::Argument::kConstant) {
ian@0:       // don't attach inputs to predefined arguments
ian@0:       continue;
ian@0:     } else if (stdx::Chance(g_probability_argument_affected)) {
ian@0:       // randomly create input for command arguments
ian@0:       sg::Vertex tree = RandomTree(graph,
ian@0:                                    sg::kControlRate,
ian@0:                                    kTreeMode_Mod,
ian@0:                                    depth + 1);
ian@0:       sg::Connection connection(i);
ian@0:       GenerateWeightAndOffset(argument, rate, &connection);
ian@0:       boost::add_edge(tree, vertex, connection, graph);  
ian@0:     }
ian@0:   }
ian@0:   return vertex;
ian@0: }
ian@0:   
ian@0: sg::Vertex Grammar::RandomTree(sg::Graph &graph,
ian@0:                                sg::CommandRate rate,
ian@0:                                TreeMode tree_mode,
ian@0:                                int depth) const {
ian@0:   enum NodeType {
ian@0:     kCommand,
ian@0:     kSpecial,
ian@0:     kConstant,
ian@0:     kParameter
ian@0:   };
ian@0:   static stats::ProbabilitySelector node_type_selector;
ian@0:   if (!node_type_selector.Initialized()) {
ian@0:     std::vector<double> probabilities(3);
ian@0:     probabilities[kCommand] = g_probability_mod_node_command;
ian@0:     probabilities[kSpecial] = g_probability_mod_node_special;
ian@0:     probabilities[kConstant] = g_probability_mod_node_constant;
ian@0:     node_type_selector.SetProbabilities(probabilities);
ian@0:   }
ian@0:   // establish the type of node to create
ian@0:   int node_type;
ian@0:   if (depth >= max_depth_) {
ian@0:     if (tree_mode == kTreeMode_Command) {
ian@0:       // if we're at maximum depth in command mode then create a command
ian@0:       node_type = kCommand;
ian@0:     } else {
ian@0:       // in mod mode at maximum depth pick either a constant or parameter
ian@0:       if (stdx::Chance(g_probability_mod_node_constant)) {
ian@0:         node_type = kConstant;
ian@0:       } else {
ian@0:         node_type = kParameter;
ian@0:       }
ian@0:     }
ian@0:   } else {
ian@0:     if (tree_mode == kTreeMode_Command) {
ian@0:       if (stdx::Chance(g_probability_command_node_command)) {
ian@0:         node_type = kCommand;
ian@0:       } else {
ian@0:         node_type = kSpecial;
ian@0:       }
ian@0:     } else {
ian@0:       // mod mode below max depth, any node type is ok
ian@0:       node_type = static_cast<NodeType>(node_type_selector());
ian@0:     }   
ian@0:   }
ian@0:   if (node_type == kCommand) {
ian@0:     return CreateCommand(graph, rate, depth);
ian@0:   } else if (node_type == kSpecial) {
ian@0:     int command = stdx::Random(Command::kNumberOfSpecialCommands);
ian@0:     return SpecialCommand(command, graph, rate, tree_mode, depth + 1);   
ian@0:   } else if (node_type == kConstant) {
ian@0:     return boost::add_vertex(sg::Node(stdx::RandomCoefficient()), graph);
ian@0:   } else if (node_type == kParameter) {
ian@0:     return boost::add_vertex(sg::Node(RandomParameter(graph), sg::kParameter),
ian@0:                              graph);
ian@0:   }
ian@0:   throw std::runtime_error("Grammar::RandomTree - unknown node type"); 
ian@0: }
ian@0: 
ian@0: int Grammar::RandomParameter(sg::Graph& graph) const {
ian@0:   // as a simple rule, randomly pick an existing parameter, or if chosen 
ian@0:   // parameter is greater than # of parameters, then add a new one
ian@0:   std::vector<double>& parameters = graph[boost::graph_bundle].parameters_;
ian@0:   int number_of_parameters = static_cast<int>(parameters.size());
ian@0:   // parameter ids start at 1
ian@0:   int parameter = stdx::RandomRangeInt(1, number_of_parameters + 1);
ian@0:   // bump parameter count if we've got a new parameter
ian@0:   if (parameter > number_of_parameters) {
ian@0:     // store a random value for the new parameter
ian@0:     parameters.push_back(stdx::RandomCoefficient());
ian@0:   }
ian@0:   return parameter;
ian@0: }
ian@0: 
ian@0: void Grammar::AddTreeToSpecialCommand(sg::Vertex command_node,
ian@0:                                       sg::Graph& graph,
ian@0:                                       int input_id,
ian@0:                                       TreeMode tree_mode,
ian@0:                                       sg::CommandRate command_rate,
ian@0:                                       bool* constant_added,
ian@0:                                       std::set<int>* parameters,
ian@0:                                       int depth) const {
ian@0:   bool success = false;
ian@0:   while (!success) {
ian@0:     sg::Vertex tree;
ian@0:     // first channel or audio command should enforce a command source
ian@0:     if (input_id == 0) {
ian@0:       tree = RandomTree(graph, command_rate, kTreeMode_Command, depth + 1);
ian@0:     } else {
ian@0:       tree = RandomTree(graph, command_rate, tree_mode, depth + 1);
ian@0:     }
ian@0:     sg::NodeType tree_type = graph[tree].type_;
ian@0:     if (tree_type == sg::kConstant) {
ian@0:       // we only need one constant per mixer
ian@0:       if (*constant_added) {
ian@0:         RemoveSubTree(tree, graph);
ian@0:         continue;
ian@0:       }
ian@0:       *constant_added = true;
ian@0:     } else if (tree_type == sg::kParameter) {
ian@0:       // we don't want duplicated parameters for special command inputs
ian@0:       if (parameters->find(graph[tree].id_) != parameters->end()) {
ian@0:         RemoveSubTree(tree, graph);
ian@0:         continue;
ian@0:       }
ian@0:       // store the parameter id
ian@0:       parameters->insert(graph[tree].id_);
ian@0:     }
ian@0:     // apply weighting
ian@0:     double weight = stdx::RandomCoefficient();
ian@0:     if (command_rate == sg::kAudioRate) {
ian@0:       // scale audio to curve
ian@0:       weight *= weight;
ian@0:     }
ian@0:     // make the connection to the generated tree
ian@0:     boost::add_edge(tree, command_node, sg::Connection(weight), graph);
ian@0:     success = true;
ian@0:   }
ian@0: }
ian@0:   
ian@0: sg::Vertex Grammar::SpecialCommand(int command_id,
ian@0:                                    sg::Graph& graph,
ian@0:                                    sg::CommandRate command_rate,
ian@0:                                    TreeMode tree_mode,
ian@0:                                    int depth /* = 0 */,
ian@0:                                    int minimum_channels /* = 2 */) const {
ian@0:   // create the special command node
ian@0:   sg::Node command_info(command_id, sg::kSpecial, command_rate);
ian@0:   sg::Vertex mixer = boost::add_vertex(command_info, graph);
ian@0:   // pick a random number of channels to create for this command
ian@0:   int channels = stdx::RandomRangeInt(minimum_channels,
ian@0:                                       g_maximum_mixer_channels);
ian@0:   bool constant_added = false;
ian@0:   std::set<int> parameters;
ian@0:   // add a tree for each channel
ian@0:   for (int i = 0; i < channels; i++) {
ian@0:     AddTreeToSpecialCommand(mixer,
ian@0:                             graph,
ian@0:                             i,
ian@0:                             tree_mode,
ian@0:                             command_rate,
ian@0:                             &constant_added,
ian@0:                             &parameters,
ian@0:                             depth);
ian@0:   }
ian@0:   return mixer;
ian@0: }
ian@0: 
ian@0: void Grammar::RandomGraph(sg::Graph& graph) const {
ian@0:   graph.clear();
ian@0:   // root output node
ian@0:   SpecialCommand(sc::Command::kMixer, graph, sg::kAudioRate, kTreeMode_Command);
ian@0: }
ian@0:   
ian@0: void Grammar::PickCrossoverNodes(const sg::Graph& parent_1, 
ian@0:                                  const sg::Graph& parent_2,
ian@0:                                  sg::Vertex* crossover_node_1,
ian@0:                                  sg::Vertex* crossover_node_2) const {
ian@0:   sg::Vertex source_node_1;
ian@0:   sg::Vertex source_node_2;
ian@0:   bool nodes_found = false;
ian@0:   do {
ian@0:     // pick random edges and their nodes
ian@0:     source_node_1 = boost::random_vertex(parent_1, bx::RandomEngine());
ian@0:     source_node_2 = boost::random_vertex(parent_2, bx::RandomEngine());
ian@0:     // avoid the root output node
ian@0:     if ((source_node_1 == 0) || (source_node_2 == 0)) {
ian@0:       continue;
ian@0:     }
ian@0:     // check it's ok to swap these nodes
ian@0:     const sg::Node& info_1 = parent_1[source_node_1];
ian@0:     const sg::Node& info_2 = parent_2[source_node_2];
ian@0:     // command rates need to match
ian@0:     if (info_1.rate_ != info_2.rate_) {
ian@0:       continue;
ian@0:     }
ian@0:     // we don't want to swap two constants
ian@0:     if (info_1.type_ == sg::kConstant && info_2.type_ == sg::kConstant) {
ian@0:       continue;
ian@0:     }
ian@0:     // we don't want to swap parameter inputs with same parameter id
ian@0:     if ((info_1.type_ == sg::kParameter)
ian@0:         && (info_2.type_ == sg::kParameter)
ian@0:         && (info_1.id_ == info_2.id_)) {
ian@0:       continue;
ian@0:     }
ian@0:     // check that we're not replacing a control modifer's input with non-command
ian@0:     sg::Edge connection_1 = *(boost::out_edges(source_node_1, parent_1).first);
ian@0:     sg::Edge connection_2 = *(boost::out_edges(source_node_2, parent_2).first);
ian@0:     sg::Vertex target_node_1 = boost::target(connection_1, parent_1);
ian@0:     sg::Vertex target_node_2 = boost::target(connection_2, parent_2);
ian@0:     const sg::Node& info_target_1 = parent_1[target_node_1];
ian@0:     const sg::Node& info_target_2 = parent_2[target_node_2];
ian@0:     if ((info_target_1.type_ == sg::kCommand)
ian@0:         || (info_target_1.type_ == sg::kSpecial)) {
ian@0:       const sc::Command& target_command_1 = commands_[info_target_1.id_];
ian@0:       const std::vector<Argument>& arguments_1 = target_command_1.Arguments();
ian@0:       const sg::Connection& info_connection_1 = parent_1[connection_1];
ian@0:       if (arguments_1[info_connection_1.input_].name_ == "in") {
ian@0:         // target input is a modifier's 'in' argument, only allow commands to
ian@0:         // be swapped in
ian@0:         if (!(info_2.type_ == sg::kCommand || info_2.type_ == sg::kSpecial)) {
ian@0:           continue;
ian@0:         }
ian@0:       }
ian@0:     }
ian@0:     if ((info_target_2.type_ == sg::kCommand)
ian@0:         || (info_target_2.type_ == sg::kSpecial)) {
ian@0:       const sc::Command& target_command_2 = commands_[info_target_2.id_];
ian@0:       const std::vector<Argument>& arguments_2 = target_command_2.Arguments();
ian@0:       const sg::Connection& info_connection_2 = parent_1[connection_2];
ian@0:       if (arguments_2[info_connection_2.input_].name_ == "in") {
ian@0:         // target input is a modifier's 'in' argument, only allow commands to
ian@0:         // be swapped in
ian@0:         if (!(info_1.type_ == sg::kCommand || info_1.type_ == sg::kSpecial)) {
ian@0:           continue;
ian@0:         }
ian@0:       }
ian@0:     }
ian@0:     nodes_found = true;
ian@0:   } while (!nodes_found);
ian@0:   *crossover_node_1 = source_node_1;
ian@0:   *crossover_node_2 = source_node_2;
ian@0: }
ian@0:   
ian@0: bool Grammar::MutationReplaceSubTree(sg::Graph& graph) const {
ian@0:   // sanity check
ian@0:   if (boost::num_vertices(graph) <= 1) {
ian@0:     throw std::runtime_error("sc::Grammar::MutationReplaceSubTree - graph has too few nodes");
ian@0:   }
ian@0:   // pick node to replace
ian@0:   sg::Vertex node_to_replace;
ian@0:   do {
ian@0:     node_to_replace = boost::random_vertex(graph, bx::RandomEngine());
ian@0:   } while (node_to_replace == 0);
ian@0:   sg::CommandRate new_tree_rate = graph[node_to_replace].rate_;
ian@0:   sg::Edge connection = *(boost::out_edges(node_to_replace, graph).first);
ian@0:   sg::Vertex connection_target = boost::target(connection, graph);
ian@0:   // store the connection info contained in the connection edge
ian@0:   sg::Connection connection_info = graph[connection];
ian@0:   const sg::Node& target_info = graph[connection_target];
ian@0:   // determine new tree mode
ian@0:   TreeMode new_tree_mode = kTreeMode_Mod;
ian@0:   if (new_tree_rate == sg::kAudioRate) {
ian@0:     // audio rate nodes always require command tree replacements
ian@0:     new_tree_mode = kTreeMode_Command;
ian@0:   } else if (target_info.type_ == sg::kCommand) {
ian@0:     // if the connection target is a modifier 
ian@0:     // and the connection input is 0 then a command tree is needed
ian@0:     if (commands_[target_info.id_].Mode() == Command::kModifier) {
ian@0:       if (connection_info.input_ == 0) {
ian@0:         new_tree_mode = kTreeMode_Command;
ian@0:       }
ian@0:     }
ian@0:   } else if (target_info.type_ == sg::kSpecial) {
ian@0:     // first input to special commands is a command tree
ian@0:     if (connection_info.input_ == 0) {
ian@0:       new_tree_mode = kTreeMode_Command;
ian@0:     }
ian@0:   }
ian@0:   // remove the sub tree
ian@0:   RemoveSubTree(connection, graph);
ian@0:   // generate new tree
ian@0:   sg::Vertex new_tree = RandomTree(graph, new_tree_rate, new_tree_mode, 0);
ian@0:   // connect tree to graph
ian@0:   boost::add_edge(new_tree, connection_target, connection_info, graph);
ian@0:   return true;
ian@0: }
ian@0:   
ian@0:   
ian@0:   
ian@0: bool Grammar::MutationAddSubTree(sg::Graph& graph) const {
ian@0:   // sanity check
ian@0:   if (graph[0].type_ != sg::kSpecial) {
ian@0:     throw std::runtime_error("sc::Grammar::MutationAddSubTree - missing root mixer node");
ian@0:   }
ian@0:   bool mutation_occurred = false;
ian@0:   while (!mutation_occurred) {
ian@0:     // pick a command or special node to add a tree input to
ian@0:     sg::Vertex node;
ian@0:     sg::NodeType node_type;
ian@0:     do {
ian@0:       node = boost::random_vertex(graph, bx::RandomEngine());
ian@0:       node_type = graph[node].type_;
ian@0:     } while (!(node_type == sg::kCommand || node_type == sg::kSpecial));
ian@0:     if (node_type == sg::kCommand) {
ian@0:       int node_id = graph[node].id_;
ian@0:       const std::vector<Argument>& arguments = commands_[node_id].Arguments();
ian@0:       std::size_t number_of_arguments = arguments.size();
ian@0:       sg::InEdgeIterator edge;
ian@0:       sg::InEdgeIterator edge_end;
ian@0:       std::vector<bool> used_arguments(arguments.size(), false);
ian@0:       for (boost::tie(edge, edge_end) = boost::in_edges(node, graph);
ian@0:            edge != edge_end;
ian@0:            ++edge) {
ian@0:         used_arguments[graph[*edge].input_] = true;
ian@0:       }
ian@0:       // check that there is an unused argument available for this command
ian@0:       bool argument_available = false;
ian@0:       for (std::size_t i = 0; i < number_of_arguments; i++) {
ian@0:         if (used_arguments[i] == false) {
ian@0:           // we don't want to attach a tree to a preset argument
ian@0:           if (arguments[i].scaling_mode_ != Argument::kConstant) {
ian@0:             argument_available = true;
ian@0:             break;
ian@0:           }
ian@0:         }
ian@0:       }
ian@0:       if (argument_available) {
ian@0:         // find a random argument to insert a tree into
ian@0:         std::size_t argument;
ian@0:         do {
ian@0:           argument = stdx::Random(arguments.size());
ian@0:         } while (used_arguments[argument] == true
ian@0:                  || arguments[argument].scaling_mode_ == Argument::kConstant);
ian@0:         // add a tree and connect to the unused argument
ian@0:         sg::Vertex tree = RandomTree(graph,
ian@0:                                      sg::kControlRate,
ian@0:                                      kTreeMode_Mod,
ian@0:                                      0);
ian@0:         sg::Connection connection(static_cast<int>(argument));
ian@0:         GenerateWeightAndOffset(arguments[argument],
ian@0:                                 sg::kControlRate,
ian@0:                                 &connection);
ian@0:         boost::add_edge(tree, node, connection, graph);
ian@0:         mutation_occurred = true;
ian@0:       }
ian@0:     } else if (node_type == sg::kSpecial) {
ian@0:       int node_inputs = static_cast<int>(boost::in_degree(node, graph));
ian@0:       // we need to check the special command's inputs to avoid adding redundant
ian@0:       // constants or parameters
ian@0:       bool constant_added = false;
ian@0:       std::set<int> parameters;
ian@0:       sg::InEdgeIterator edge;
ian@0:       sg::InEdgeIterator edge_end;
ian@0:       for (boost::tie(edge, edge_end) = boost::in_edges(node, graph);
ian@0:            edge != edge_end;
ian@0:            ++edge) {
ian@0:         const sg::Node& source = graph[boost::source(*edge, graph)];
ian@0:         if (source.type_ == sg::kConstant) {
ian@0:           constant_added = true;
ian@0:         }
ian@0:         if (source.type_ == sg::kParameter) {
ian@0:           parameters.insert(source.id_);
ian@0:         }
ian@0:       }
ian@0:       // select tree mode based on command rate
ian@0:       TreeMode tree_mode;
ian@0:       if (graph[node].rate_ == sg::kAudioRate) {
ian@0:         tree_mode = kTreeMode_Command;
ian@0:       } else {
ian@0:         tree_mode = kTreeMode_Mod;
ian@0:       }
ian@0:       // add the tree
ian@0:       AddTreeToSpecialCommand(node,
ian@0:                               graph,
ian@0:                               node_inputs,
ian@0:                               tree_mode,
ian@0:                               graph[node].rate_,
ian@0:                               &constant_added,
ian@0:                               &parameters,
ian@0:                               0);
ian@0:       mutation_occurred = true;
ian@0:     }  
ian@0:   }
ian@0:   return true;
ian@0: }
ian@0: 
ian@0: bool Grammar::MutationModifyInputs(sg::Graph& graph) const {
ian@0:   // sanity check
ian@0:   if (graph[boost::graph_bundle].parameters_.size() == 0) {
ian@0:     sg::VertexIterator vertex;
ian@0:     sg::VertexIterator vertex_end;
ian@0:     bool constant_found = false;
ian@0:     for (boost::tie(vertex, vertex_end) = boost::vertices(graph);
ian@0:          vertex != vertex_end;
ian@0:          ++vertex) {
ian@0:       sg::Node& node = graph[*vertex];
ian@0:       if (node.type_ == sg::kConstant) {
ian@0:         constant_found = true;
ian@0:         break;
ian@0:       }
ian@0:     }
ian@0:     if (!constant_found) {
ian@0:       // no parameters, no constants, nothing to do..
ian@0:       return false;
ian@0:     }
ian@0:   }
ian@0:   // make a random generator with a narrow guassian distribution 
ian@0:   bx::GaussianGenerator gaussian = bx::MakeGaussianGenerator(0, 0.125);
ian@0:   bool mutation_occurred = false;
ian@0:   while (!mutation_occurred) {
ian@0:     // mutate parameters
ian@0:     foreach (double& parameter, graph[boost::graph_bundle].parameters_) {
ian@0:       if (stdx::Chance(g_probability_input_mutation)) {
ian@0:         MutateValue(&parameter, &mutation_occurred);
ian@0:       }
ian@0:     }
ian@0:     // mutate constants
ian@0:     sg::VertexIterator vertex;
ian@0:     sg::VertexIterator vertex_end;
ian@0:     for (boost::tie(vertex, vertex_end) = boost::vertices(graph);
ian@0:          vertex != vertex_end;
ian@0:          ++vertex) {
ian@0:       sg::Node& node = graph[*vertex];
ian@0:       if (node.type_ == sg::kConstant) {
ian@0:         // constant value
ian@0:         if (stdx::Chance(g_probability_input_mutation)) {
ian@0:           MutateValue(&node.constant_value_, &mutation_occurred);
ian@0:         }
ian@0:       }
ian@0:     }
ian@0:   }
ian@0:   return true;
ian@0: }
ian@0: 
ian@0: bool Grammar::MutationModifyConnections(sg::Graph& graph) const {
ian@0:   // sanity check
ian@0:   if (boost::num_edges(graph) < 1) {
ian@0:     throw std::runtime_error("sc::Grammar::MutationModifyConnections - graph has no connections");
ian@0:   }
ian@0:   bx::GaussianGenerator gaussian = bx::MakeGaussianGenerator(0, 0.125);
ian@0:   bool mutation_occurred = false;
ian@0:   while (!mutation_occurred) {
ian@0:     sg::EdgeIterator edge;
ian@0:     sg::EdgeIterator edge_end;
ian@0:     for (boost::tie(edge, edge_end) = boost::edges(graph);
ian@0:          edge != edge_end;
ian@0:          ++edge) {
ian@0:       if (stdx::Chance(g_probability_connection_mutation)) {
ian@0:         sg::Connection& connection = graph[*edge];
ian@0:         const sg::Node& target = graph[boost::target(*edge, graph)];
ian@0:         const sc::Argument& argument = GetCommandArgument(target.id_,
ian@0:                                                           connection.input_);
ian@0:         if (!argument.fixed_range_) {
ian@0:           // mutate weight
ian@0:           MutateValue(&connection.weight_,
ian@0:                       &mutation_occurred,
ian@0:                       g_minimum_connection_weight);
ian@0:           // special command inputs and modifier command input arguments 
ian@0:           // have offsets set to zero
ian@0:           if ((target.type_ != sg::kSpecial) && (argument.name_ != "in")) {
ian@0:             MutateValue(&connection.offset_, &mutation_occurred,
ian@0:                         0.0, 1.0 - connection.weight_);
ian@0:           }
ian@0:         }
ian@0:       }
ian@0:     }    
ian@0:   }
ian@0:   return true;
ian@0: }
ian@0:   
ian@0: const std::vector<sc::Argument>& Grammar::CommandArguments(int command) const {
ian@0:   return commands_[command].Arguments();
ian@0: }
ian@0: 
ian@0: bool Grammar::MutationReplaceCommand(sg::Graph& graph) const {
ian@0:   // sanity check
ian@0:   if (boost::num_vertices(graph) <= 1) {
ian@0:     throw std::runtime_error("sc::Grammar::MutationReplaceCommand - graph has too few nodes");
ian@0:   }
ian@0:   sg::Vertex node_to_replace;
ian@0:   sg::Node* node_info;
ian@0:   // find command to replace
ian@0:   do {
ian@0:     node_to_replace = boost::random_vertex(graph, bx::RandomEngine());
ian@0:     node_info = &graph[node_to_replace];
ian@0:   } while (node_info->type_ != sg::kCommand);
ian@0:   int old_id = node_info->id_;
ian@0:   // generate new command id
ian@0:   int new_id;
ian@0:   int number_of_commands = static_cast<int>(commands_.size());
ian@0:   do {
ian@0:     // new command must match old output and mode
ian@0:     new_id = stdx::Random(number_of_commands);
ian@0:   } while (new_id != old_id
ian@0:            && commands_[new_id].Output() != commands_[old_id].Output()
ian@0:            && commands_[new_id].Mode() != commands_[old_id].Mode());
ian@0:   // new command info
ian@0:   const std::vector<sc::Argument>& arguments = CommandArguments(new_id);
ian@0:   std::size_t number_of_arguments = commands_[new_id].Arguments().size();
ian@0:   // remove invalid parameters
ian@0:   // removing an in edge invalidates the iterators, so we need to restart the
ian@0:   // search each time an edge is removed
ian@0:   sg::InEdgeIterator edge;
ian@0:   sg::InEdgeIterator edge_end;
ian@0:   bool do_it_again;
ian@0:   do {
ian@0:     do_it_again = false;
ian@0:     for (boost::tie(edge, edge_end) = boost::in_edges(node_to_replace, graph);
ian@0:          edge != edge_end;
ian@0:          ++edge) {
ian@0:       int input = graph[*edge].input_;
ian@0:       // remove input tree if it's for an extraneous parameter
ian@0:       // or if the argument is a constant
ian@0:       if (input >= number_of_arguments
ian@0:           || arguments[input].scaling_mode_ == sc::Argument::kConstant) {
ian@0:         RemoveSubTree(*edge, graph);
ian@0:         do_it_again = true;
ian@0:         // break out of for loop
ian@0:         break;
ian@0:       }
ian@0:     }
ian@0:   } while (do_it_again);
ian@0:   // now invalid parameters have been removed, validate the rest
ian@0:   for (boost::tie(edge, edge_end) = boost::in_edges(node_to_replace, graph);
ian@0:        edge != edge_end;
ian@0:        ++edge) {
ian@0:     // if the new argument is fixed range then correct the connection weight
ian@0:     int input = graph[*edge].input_;
ian@0:     if (arguments[input].fixed_range_) {
ian@0:       GenerateWeightAndOffset(arguments[input],
ian@0:                               node_info->rate_, 
ian@0:                               &graph[*edge]);
ian@0:     }
ian@0:   }
ian@0:   // apply new command id
ian@0:   node_info->id_ = new_id;
ian@0:   return true;
ian@0: }
ian@0:   
ian@0: int Grammar::GetCommandInputID(int command) const {
ian@0:   const std::vector<sc::Argument>& arguments = commands_[command].Arguments();
ian@0:   for (std::size_t i = 0, size = arguments.size(); i < size; i++) {
ian@0:     if (arguments[i].name_ == "in") {
ian@0:       return static_cast<int>(i);
ian@0:     }
ian@0:   }
ian@0:   return -1;
ian@0: }
ian@0:   
ian@0: const Argument& Grammar::GetCommandArgument(int command_id,
ian@0:                                             int argument_id) const {
ian@0:   return commands_[command_id].Arguments()[argument_id];
ian@0: }
ian@0: 
ian@0: bool Grammar::MutationInsertCommand(sg::Graph& graph) const {
ian@0:   // sanity check
ian@0:   if (boost::num_vertices(graph) == 0) {
ian@0:     throw std::runtime_error("sc::Grammar::MutationInsertCommand - graph is empty");
ian@0:   }
ian@0:   // pick a random edge as insertion point
ian@0:   sg::Edge edge_to_replace;
ian@0:   sg::Vertex source_command;
ian@0:   sg::NodeType source_type;
ian@0:   do {
ian@0:     edge_to_replace = boost::random_edge(graph, bx::RandomEngine());
ian@0:     source_command = boost::source(edge_to_replace, graph);
ian@0:     source_type = graph[source_command].type_;
ian@0:   } while (source_type != sg::kCommand);
ian@0:   // store target connection info
ian@0:   sg::Vertex target_command = boost::target(edge_to_replace, graph);
ian@0:   sg::Connection target_connection = graph[edge_to_replace];
ian@0:   // make the new command
ian@0:   const sg::Node& source_node = graph[source_command];
ian@0:   sg::CommandRate rate = source_node.rate_;
ian@0:   sg::Vertex new_command = CreateCommand(graph, rate, 0, true, false);
ian@0:   // remove the existing connection
ian@0:   boost::remove_edge(source_command, target_command, graph);
ian@0:   // connect the new command to the source
ian@0:   sg::Connection source_connection(GetCommandInputID(graph[new_command].id_));
ian@0:   // generate weighting for new connection
ian@0:   double weight = stdx::RandomCoefficient();
ian@0:   if (rate == sg::kAudioRate) {
ian@0:     weight *= weight;
ian@0:   }
ian@0:   source_connection.weight_ = weight;
ian@0:   boost::add_edge(source_command, new_command, source_connection, graph);
ian@0:   // connect new command to the target, use old connection weighting
ian@0:   boost::add_edge(new_command, target_command, target_connection, graph);
ian@0:   // success!
ian@0:   return true;
ian@0: }
ian@0: 
ian@0: } // sc namespace