<commit_before>// -*- mode: c++; coding: utf-8; -*-

// state_space.cc - State space

// Copyright (C) 2013 <NAME>

// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice (including the next
// paragraph) shall be included in all copies or substantial portions of the
// Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

#include <iostream>
#include <algorithm>
#include <ctgmath>
#include <functional>
#include <numeric>

#include <boost/range/irange.hpp>

#include "state_space.hh"
#include "util.hh"

namespace esf {

using std::accumulate;
using std::copy;
using std::multiplies;
using std::partial_sum;
using std::sort;
using std::transform;
using boost::irange;

namespace {
State GenerateState(Index idx, Index ndeme, Index ngene);
Index GenerateIndex(State::iterator begin, State::iterator end);
};


Index StateSpace::StateToIndex(Init init, State state) {
  auto ndeme = init.size();
  Index sum = 0, mult = 1;
  State::iterator begin = state.begin();
  for (Index i = 0; i < ndeme; ++i, begin += ndeme) {
    sum += mult * GenerateIndex(begin, begin + ndeme);
    mult *= Binomial(i + ndeme, i + 1);
  }
  return sum;
}

State StateSpace::IndexToState(Init init, Index idx) {
  auto ndeme = init.size();
  IndexList dim(ndeme);
  transform(init.begin(), init.end() - 1, dim.begin(),
            [ndeme](Index i) {return Binomial(i + ndeme - 1, i);});
  *(dim.end() - 1) = 1;
  IndexList dim2(ndeme);
  dim2[0] = 1;
  partial_sum(dim.begin(), dim.end() - 1, dim2.begin() + 1, multiplies<Index>());
  State state;
  State substate;
  for (Index i = 0; i < ndeme; ++i) {
    substate = GenerateState((idx / dim2[i]) % dim[i], ndeme, init[i]);
    state.insert(state.end(), substate.begin(), substate.end());
  };
  return state;
}

StateList StateSpace::Neighbors(Init init, Index idx) {
  // Based on incoming states rather than outgoing states.
  auto ndeme = init.size();
  auto deme = 0;
  State state = IndexToState(init, idx);
  State new_state(state.size());
  StateList neighbors;
  for (Index tar = 0; tar < state.size(); ++tar) {
    deme = tar / ndeme;
    for (Index src = ndeme * deme; src < ndeme * (deme + 1); ++src) {
      if (state[src] > 0 && src != tar) {
        copy(state.begin(), state.end(), new_state.begin());
        new_state[src] -= 1;
        new_state[tar] += 1;
        neighbors.push_back(new_state);
      }
    }
  }
  return neighbors;
}<commit_msg>StateSpace::Neighbors return a list of nodes accessible by single migration out of idx.<commit_after>// -*- mode: c++; coding: utf-8; -*-

// state_space.cc - State space

// Copyright (C) 2013 <NAME>

// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice (including the next
// paragraph) shall be included in all copies or substantial portions of the
// Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

#include <iostream>
#include <algorithm>
#include <ctgmath>
#include <functional>
#include <numeric>

#include <boost/range/irange.hpp>

#include "state_space.hh"
#include "util.hh"

namespace esf {

using std::accumulate;
using std::copy;
using std::multiplies;
using std::partial_sum;
using std::sort;
using std::transform;
using boost::irange;

namespace {
State GenerateState(Index idx, Index ndeme, Index ngene);
Index GenerateIndex(State::iterator begin, State::iterator end);
};


Index StateSpace::StateToIndex(Init init, State state) {
  auto ndeme = init.size();
  Index sum = 0, mult = 1;
  State::iterator begin = state.begin();
  for (Index i = 0; i < ndeme; ++i, begin += ndeme) {
    sum += mult * GenerateIndex(begin, begin + ndeme);
    mult *= Binomial(i + ndeme, i + 1);
  }
  return sum;
}

State StateSpace::IndexToState(Init init, Index idx) {
  auto ndeme = init.size();
  IndexList dim(ndeme);
  transform(init.begin(), init.end() - 1, dim.begin(),
            [ndeme](Index i) {return Binomial(i + ndeme - 1, i);});
  *(dim.end() - 1) = 1;
  IndexList dim2(ndeme);
  dim2[0] = 1;
  partial_sum(dim.begin(), dim.end() - 1, dim2.begin() + 1, multiplies<Index>());
  State state;
  State substate;
  for (Index i = 0; i < ndeme; ++i) {
    substate = GenerateState((idx / dim2[i]) % dim[i], ndeme, init[i]);
    state.insert(state.end(), substate.begin(), substate.end());
  };
  return state;
}

StateList StateSpace::Neighbors(Init init, Index idx) {
  // List of nodes accessible from idx by a single emigration.
  auto ndeme = init.size();
  auto deme = 0;
  State state = IndexToState(init, idx);
  State new_state(state.size());
  StateList neighbors;
  for (Index src = 0; src < state.size(); ++src) {
    if (state[src] != 0) {
      deme = src / ndeme;
      for (Index tar = ndeme * deme; tar < ndeme * (deme + 1); ++tar) {
        if (src != tar) {
          copy(state.begin(), state.end(), new_state.begin());
          new_state[src] -= 1;
          new_state[tar] += 1;
          neighbors.push_back(new_state);
        }
      }
    }
  }
  return neighbors;
}
{'fraction_non_alphanumeric': 0.13229804390025385, 'fraction_numerical': 0.008361953113334328, 'mean_word_length': 3.632088520055325, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4695659', 'n_tokens_mistral': 2131, 'n_tokens_neox': 2073, 'n_words': 771}