#ifndef SASS_PATHS_H
#define SASS_PATHS_H

#include <vector>

namespace Sass {

  // Returns a list of all possible paths through the given lists.
  //
  // For example, given `[[1, 2], [3, 4], [5, 6]]`, this returns:
  //
  // ```
  // [[1, 3, 5],
  //  [2, 3, 5],
  //  [1, 4, 5],
  //  [2, 4, 5],
  //  [1, 3, 6],
  //  [2, 3, 6],
  //  [1, 4, 6],
  //  [2, 4, 6]]
  // ```
  // 
  // Note: called `paths` in dart-sass
  template <class T>
  sass::vector<sass::vector<T>> permutate(
    const sass::vector<sass::vector<T>>& in)
  {

    size_t L = in.size(), n = 0;

    if (L == 0) return {};
    // Exit early if any entry is empty
    for (size_t i = 0; i < L; i += 1) {
      if (in[i].size() == 0) return {};
    }

    size_t* state = new size_t[L + 1];
    sass::vector<sass::vector<T>> out;

    // First initialize all states for every permutation group
    for (size_t i = 0; i < L; i += 1) {
      state[i] = in[i].size() - 1;
    }
    while (true) {
      sass::vector<T> perm;
      // Create one permutation for state
      for (size_t i = 0; i < L; i += 1) {
        perm.push_back(in.at(i).at(in[i].size() - state[i] - 1));
      }
      // Current group finished
      if (state[n] == 0) {
        // Find position of next decrement
        while (n < L && state[++n] == 0) {}

        if (n == L) {
          out.push_back(perm);
          break;
        }

        state[n] -= 1;

        for (size_t p = 0; p < n; p += 1) {
          state[p] = in[p].size() - 1;
        }

        // Restart from front
        n = 0;

      }
      else {
        state[n] -= 1;
      }
      out.push_back(perm);
    }

    delete[] state;
    return out;
  }
  // EO permutate

  // ToDo: this variant is used in resolveParentSelectors
  // Returns a list of all possible paths through the given lists.
  //
  // For example, given `[[1, 2], [3, 4], [5, 6]]`, this returns:
  //
  // ```
  // [[1, 3, 5],
  //  [1, 3, 6],
  //  [1, 4, 5],
  //  [1, 4, 6],
  //  [2, 3, 5],
  //  [2, 3, 6],
  //  [2, 4, 5],
  //  [2, 4, 6]]
  // ```
  // 
  template <class T>
  sass::vector<sass::vector<T>>
    permutateAlt(const sass::vector<sass::vector<T>>& in) {

    size_t L = in.size();
    size_t n = in.size() - 1;

    if (L == 0) return {};
    // Exit early if any entry is empty
    for (size_t i = 0; i < L; i += 1) {
      if (in[i].size() == 0) return {};
    }

    size_t* state = new size_t[L];
    sass::vector<sass::vector<T>> out;

    // First initialize all states for every permutation group
    for (size_t i = 0; i < L; i += 1) {
      state[i] = in[i].size() - 1;
    }

    while (true) {
      /*
      // std::cerr << "PERM: ";
      for (size_t p = 0; p < L; p++)
      { // std::cerr << state[p] << " "; }
      // std::cerr << "\n";
      */
      sass::vector<T> perm;
      // Create one permutation for state
      for (size_t i = 0; i < L; i += 1) {
        perm.push_back(in.at(i).at(in[i].size() - state[i] - 1));
      }
      // Current group finished
      if (state[n] == 0) {
        // Find position of next decrement
        while (n > 0 && state[--n] == 0) {}

        // Check for end condition
        if (state[n] != 0) {
          // Decrease next on the left side
          state[n] -= 1;
          // Reset all counters to the right
          for (size_t p = n + 1; p < L; p += 1) {
            state[p] = in[p].size() - 1;
          }
          // Restart from end
          n = L - 1;
        }
        else {
          out.push_back(perm);
          break;
        }
      }
      else {
        state[n] -= 1;
      }
      out.push_back(perm);
    }

    delete[] state;
    return out;
  }
  // EO permutateAlt

}

#endif