// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2013 Christian Seiler <christian@iwakd.de>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

#ifndef EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H
#define EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H

// IWYU pragma: private
#include "../InternalHeaderCheck.h"

namespace Eigen {

namespace internal {

namespace group_theory {

/** \internal
 * \file CXX11/src/TensorSymmetry/util/TemplateGroupTheory.h
 * This file contains C++ templates that implement group theory algorithms.
 *
 * The algorithms allow for a compile-time analysis of finite groups.
 *
 * Currently only Dimino's algorithm is implemented, which returns a list
 * of all elements in a group given a set of (possibly redundant) generators.
 * (One could also do that with the so-called orbital algorithm, but that
 * is much more expensive and usually has no advantages.)
 */

/**********************************************************************
 *                "Ok kid, here is where it gets complicated."
 *                         - Amelia Pond in the "Doctor Who" episode
 *                           "The Big Bang"
 *
 * Dimino's algorithm
 * ==================
 *
 * The following is Dimino's algorithm in sequential form:
 *
 * Input: identity element, list of generators, equality check,
 *        multiplication operation
 * Output: list of group elements
 *
 * 1. add identity element
 * 2. remove identities from list of generators
 * 3. add all powers of first generator that aren't the
 *    identity element
 * 4. go through all remaining generators:
 *        a. if generator is already in the list of elements
 *                -> do nothing
 *        b. otherwise
 *                i.   remember current # of elements
 *                     (i.e. the size of the current subgroup)
 *                ii.  add all current elements (which includes
 *                     the identity) each multiplied from right
 *                     with the current generator to the group
 *                iii. add all remaining cosets that are generated
 *                     by products of the new generator with itself
 *                     and all other generators seen so far
 *
 * In functional form, this is implemented as a long set of recursive
 * templates that have a complicated relationship.
 *
 * The main interface for Dimino's algorithm is the template
 * enumerate_group_elements. All lists are implemented as variadic
 * type_list<typename...> and numeric_list<typename = int, int...>
 * templates.
 *
 * 'Calling' templates is usually done via typedefs.
 *
 * This algorithm is an extended version of the basic version. The
 * extension consists in the fact that each group element has a set
 * of flags associated with it. Multiplication of two group elements
 * with each other results in a group element whose flags are the
 * XOR of the flags of the previous elements. Each time the algorithm
 * notices that a group element it just calculated is already in the
 * list of current elements, the flags of both will be compared and
 * added to the so-called 'global flags' of the group.
 *
 * The rationale behind this extension is that this allows not only
 * for the description of symmetries between tensor indices, but
 * also allows for the description of hermiticity, antisymmetry and
 * antihermiticity. Negation and conjugation each are specific bit
 * in the flags value and if two different ways to reach a group
 * element lead to two different flags, this poses a constraint on
 * the allowed values of the resulting tensor. For example, if a
 * group element is reach both with and without the conjugation
 * flags, it is clear that the resulting tensor has to be real.
 *
 * Note that this flag mechanism is quite generic and may have other
 * uses beyond tensor properties.
 *
 * IMPORTANT:
 *     This algorithm assumes the group to be finite. If you try to
 *     run it with a group that's infinite, the algorithm will only
 *     terminate once you hit a compiler limit (max template depth).
 *     Also note that trying to use this implementation to create a
 *     very large group will probably either make you hit the same
 *     limit, cause the compiler to segfault or at the very least
 *     take a *really* long time (hours, days, weeks - sic!) to
 *     compile. It is not recommended to plug in more than 4
 *     generators, unless they are independent of each other.
 */

/** \internal
 *
 * \class strip_identities
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Cleanse a list of group elements of the identity element
 *
 * This template is used to make a first pass through all initial
 * generators of Dimino's algorithm and remove the identity
 * elements.
 *
 * \sa enumerate_group_elements
 */
template <template <typename, typename> class Equality, typename id, typename L>
struct strip_identities;

template <template <typename, typename> class Equality, typename id, typename t, typename... ts>
struct strip_identities<Equality, id, type_list<t, ts...>> {
  typedef std::conditional_t<
      Equality<id, t>::value, typename strip_identities<Equality, id, type_list<ts...>>::type,
      typename concat<type_list<t>, typename strip_identities<Equality, id, type_list<ts...>>::type>::type>
      type;
  constexpr static int global_flags =
      Equality<id, t>::global_flags | strip_identities<Equality, id, type_list<ts...>>::global_flags;
};

template <template <typename, typename> class Equality, typename id EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, ts)>
struct strip_identities<Equality, id, type_list<EIGEN_TPL_PP_SPEC_HACK_USE(ts)>> {
  typedef type_list<> type;
  constexpr static int global_flags = 0;
};

/** \internal
 *
 * \class dimino_first_step_elements_helper
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Recursive template that adds powers of the first generator to the list of group elements
 *
 * This template calls itself recursively to add powers of the first
 * generator to the list of group elements. It stops if it reaches
 * the identity element again.
 *
 * \sa enumerate_group_elements, dimino_first_step_elements
 */
template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename g, typename current_element, typename elements,
          bool dont_add_current_element  // = false
          >
struct dimino_first_step_elements_helper
#ifndef EIGEN_PARSED_BY_DOXYGEN
    :  // recursive inheritance is too difficult for Doxygen
       public dimino_first_step_elements_helper<Multiply, Equality, id, g, typename Multiply<current_element, g>::type,
                                                typename concat<elements, type_list<current_element>>::type,
                                                Equality<typename Multiply<current_element, g>::type, id>::value> {
};

template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename g, typename current_element, typename elements>
struct dimino_first_step_elements_helper<Multiply, Equality, id, g, current_element, elements, true>
#endif  // EIGEN_PARSED_BY_DOXYGEN
{
  typedef elements type;
  constexpr static int global_flags = Equality<current_element, id>::global_flags;
};

/** \internal
 *
 * \class dimino_first_step_elements
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Add all powers of the first generator to the list of group elements
 *
 * This template takes the first non-identity generator and generates the initial
 * list of elements which consists of all powers of that generator. For a group
 * with just one generated, it would be enumerated after this.
 *
 * \sa enumerate_group_elements
 */
template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename generators>
struct dimino_first_step_elements {
  typedef typename get<0, generators>::type first_generator;
  typedef typename skip<1, generators>::type next_generators;
  typedef type_list<first_generator> generators_done;

  typedef dimino_first_step_elements_helper<Multiply, Equality, id, first_generator, first_generator, type_list<id>,
                                            false>
      helper;
  typedef typename helper::type type;
  constexpr static int global_flags = helper::global_flags;
};

/** \internal
 *
 * \class dimino_get_coset_elements
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Generate all elements of a specific coset
 *
 * This template generates all the elements of a specific coset by
 * multiplying all elements in the given subgroup with the new
 * coset representative. Note that the first element of the
 * subgroup is always the identity element, so the first element of
 * the result of this template is going to be the coset
 * representative itself.
 *
 * Note that this template accepts an additional boolean parameter
 * that specifies whether to actually generate the coset (true) or
 * just return an empty list (false).
 *
 * \sa enumerate_group_elements, dimino_add_cosets_for_rep
 */
template <template <typename, typename> class Multiply, typename sub_group_elements, typename new_coset_rep,
          bool generate_coset  // = true
          >
struct dimino_get_coset_elements {
  typedef typename apply_op_from_right<Multiply, new_coset_rep, sub_group_elements>::type type;
};

template <template <typename, typename> class Multiply, typename sub_group_elements, typename new_coset_rep>
struct dimino_get_coset_elements<Multiply, sub_group_elements, new_coset_rep, false> {
  typedef type_list<> type;
};

/** \internal
 *
 * \class dimino_add_cosets_for_rep
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Recursive template for adding coset spaces
 *
 * This template multiplies the coset representative with a generator
 * from the list of previous generators. If the new element is not in
 * the group already, it adds the corresponding coset. Finally it
 * proceeds to call itself with the next generator from the list.
 *
 * \sa enumerate_group_elements, dimino_add_all_coset_spaces
 */
template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename sub_group_elements, typename elements, typename generators, typename rep_element, int sub_group_size>
struct dimino_add_cosets_for_rep;

template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename sub_group_elements, typename elements, typename g, typename... gs, typename rep_element,
          int sub_group_size>
struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, type_list<g, gs...>, rep_element,
                                 sub_group_size> {
  typedef typename Multiply<rep_element, g>::type new_coset_rep;
  typedef contained_in_list_gf<Equality, new_coset_rep, elements> _cil;
  constexpr static bool add_coset = !_cil::value;

  typedef
      typename dimino_get_coset_elements<Multiply, sub_group_elements, new_coset_rep, add_coset>::type coset_elements;

  typedef dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements,
                                    typename concat<elements, coset_elements>::type, type_list<gs...>, rep_element,
                                    sub_group_size>
      _helper;

  typedef typename _helper::type type;
  constexpr static int global_flags = _cil::global_flags | _helper::global_flags;

  /* Note that we don't have to update global flags here, since
   * we will only add these elements if they are not part of
   * the group already. But that only happens if the coset rep
   * is not already in the group, so the check for the coset rep
   * will catch this.
   */
};

template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename sub_group_elements, typename elements EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, empty),
          typename rep_element, int sub_group_size>
struct dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements,
                                 type_list<EIGEN_TPL_PP_SPEC_HACK_USE(empty)>, rep_element, sub_group_size> {
  typedef elements type;
  constexpr static int global_flags = 0;
};

/** \internal
 *
 * \class dimino_add_all_coset_spaces
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Recursive template for adding all coset spaces for a new generator
 *
 * This template tries to go through the list of generators (with
 * the help of the dimino_add_cosets_for_rep template) as long as
 * it still finds elements that are not part of the group and add
 * the corresponding cosets.
 *
 * \sa enumerate_group_elements, dimino_add_cosets_for_rep
 */
template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename sub_group_elements, typename elements, typename generators, int sub_group_size, int rep_pos,
          bool stop_condition  // = false
          >
struct dimino_add_all_coset_spaces {
  typedef typename get<rep_pos, elements>::type rep_element;
  typedef dimino_add_cosets_for_rep<Multiply, Equality, id, sub_group_elements, elements, generators, rep_element,
                                    sub_group_elements::count>
      _ac4r;
  typedef typename _ac4r::type new_elements;

  constexpr static int new_rep_pos = rep_pos + sub_group_elements::count;
  constexpr static bool new_stop_condition = new_rep_pos >= new_elements::count;

  typedef dimino_add_all_coset_spaces<Multiply, Equality, id, sub_group_elements, new_elements, generators,
                                      sub_group_size, new_rep_pos, new_stop_condition>
      _helper;

  typedef typename _helper::type type;
  constexpr static int global_flags = _helper::global_flags | _ac4r::global_flags;
};

template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename sub_group_elements, typename elements, typename generators, int sub_group_size, int rep_pos>
struct dimino_add_all_coset_spaces<Multiply, Equality, id, sub_group_elements, elements, generators, sub_group_size,
                                   rep_pos, true> {
  typedef elements type;
  constexpr static int global_flags = 0;
};

/** \internal
 *
 * \class dimino_add_generator
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Enlarge the group by adding a new generator.
 *
 * It accepts a boolean parameter that determines if the generator is redundant,
 * i.e. was already seen in the group. In that case, it reduces to a no-op.
 *
 * \sa enumerate_group_elements, dimino_add_all_coset_spaces
 */
template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename elements, typename generators_done, typename current_generator,
          bool redundant  // = false
          >
struct dimino_add_generator {
  /* this template is only called if the generator is not redundant
   * => all elements of the group multiplied with the new generator
   *    are going to be new elements of the most trivial coset space
   */
  typedef typename apply_op_from_right<Multiply, current_generator, elements>::type multiplied_elements;
  typedef typename concat<elements, multiplied_elements>::type new_elements;

  constexpr static int rep_pos = elements::count;

  typedef dimino_add_all_coset_spaces<
      Multiply, Equality, id,
      elements,  // elements of previous subgroup
      new_elements, typename concat<generators_done, type_list<current_generator>>::type,
      elements::count,  // size of previous subgroup
      rep_pos,
      false  // don't stop (because rep_pos >= new_elements::count is always false at this point)
      >
      _helper;
  typedef typename _helper::type type;
  constexpr static int global_flags = _helper::global_flags;
};

template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename elements, typename generators_done, typename current_generator>
struct dimino_add_generator<Multiply, Equality, id, elements, generators_done, current_generator, true> {
  // redundant case
  typedef elements type;
  constexpr static int global_flags = 0;
};

/** \internal
 *
 * \class dimino_add_remaining_generators
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Recursive template that adds all remaining generators to a group
 *
 * Loop through the list of generators that remain and successively
 * add them to the group.
 *
 * \sa enumerate_group_elements, dimino_add_generator
 */
template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename generators_done, typename remaining_generators, typename elements>
struct dimino_add_remaining_generators {
  typedef typename get<0, remaining_generators>::type first_generator;
  typedef typename skip<1, remaining_generators>::type next_generators;

  typedef contained_in_list_gf<Equality, first_generator, elements> _cil;

  typedef dimino_add_generator<Multiply, Equality, id, elements, generators_done, first_generator, _cil::value> _helper;

  typedef typename _helper::type new_elements;

  typedef dimino_add_remaining_generators<Multiply, Equality, id,
                                          typename concat<generators_done, type_list<first_generator>>::type,
                                          next_generators, new_elements>
      _next_iter;

  typedef typename _next_iter::type type;
  constexpr static int global_flags = _cil::global_flags | _helper::global_flags | _next_iter::global_flags;
};

template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename generators_done, typename elements>
struct dimino_add_remaining_generators<Multiply, Equality, id, generators_done, type_list<>, elements> {
  typedef elements type;
  constexpr static int global_flags = 0;
};

/** \internal
 *
 * \class enumerate_group_elements_noid
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Helper template that implements group element enumeration
 *
 * This is a helper template that implements the actual enumeration
 * of group elements. This has been split so that the list of
 * generators can be cleansed of the identity element before
 * performing the actual operation.
 *
 * \sa enumerate_group_elements
 */
template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename generators, int initial_global_flags = 0>
struct enumerate_group_elements_noid {
  typedef dimino_first_step_elements<Multiply, Equality, id, generators> first_step;
  typedef typename first_step::type first_step_elements;

  typedef dimino_add_remaining_generators<Multiply, Equality, id, typename first_step::generators_done,
                                          typename first_step::next_generators,  // remaining_generators
                                          typename first_step::type              // first_step elements
                                          >
      _helper;

  typedef typename _helper::type type;
  constexpr static int global_flags = initial_global_flags | first_step::global_flags | _helper::global_flags;
};

// in case when no generators are specified
template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          int initial_global_flags>
struct enumerate_group_elements_noid<Multiply, Equality, id, type_list<>, initial_global_flags> {
  typedef type_list<id> type;
  constexpr static int global_flags = initial_global_flags;
};

/** \internal
 *
 * \class enumerate_group_elements
 * \ingroup CXX11_TensorSymmetry_Module
 *
 * \brief Enumerate all elements in a finite group
 *
 * This template enumerates all elements in a finite group. It accepts
 * the following template parameters:
 *
 * \tparam Multiply      The multiplication operation that multiplies two group elements
 *                       with each other.
 * \tparam Equality      The equality check operation that checks if two group elements
 *                       are equal to another.
 * \tparam id            The identity element
 * \tparam Generators_   A list of (possibly redundant) generators of the group
 */
template <template <typename, typename> class Multiply, template <typename, typename> class Equality, typename id,
          typename Generators_>
struct enumerate_group_elements
    : public enumerate_group_elements_noid<Multiply, Equality, id,
                                           typename strip_identities<Equality, id, Generators_>::type,
                                           strip_identities<Equality, id, Generators_>::global_flags> {};

}  // end namespace group_theory

}  // end namespace internal

}  // end namespace Eigen

#endif  // EIGEN_CXX11_TENSORSYMMETRY_TEMPLATEGROUPTHEORY_H

/*
 * kate: space-indent on; indent-width 2; mixedindent off; indent-mode cstyle;
 */