permutation.h

Go to the documentation of this file.

/*
 *  This file is a part of TiledArray.
 *  Copyright (C) 2013  Virginia Tech
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#ifndef TILEDARRAY_PERMUTATION_H__INCLUDED
#define TILEDARRAY_PERMUTATION_H__INCLUDED

#include <TiledArray/error.h>
#include <TiledArray/type_traits.h>
#include <TiledArray/utility.h>
#include <array>
#include <numeric>

namespace TiledArray {

  // Forward declarations
  class Permutation;
  bool operator==(const Permutation&, const Permutation&);
  std::ostream& operator<<(std::ostream&, const Permutation&);
  template <typename T, std::size_t N>
  inline std::array<T,N> operator*(const Permutation&, const std::array<T, N>&);
  template <typename T, std::size_t N>
  inline std::array<T,N>& operator*=(std::array<T,N>&, const Permutation&);
  template <typename T, typename A>
  inline std::vector<T> operator*(const Permutation&, const std::vector<T, A>&);
  template <typename T, typename A>
  inline std::vector<T, A>& operator*=(std::vector<T, A>&, const Permutation&);
  template <typename T>
  inline std::vector<T> operator*(const Permutation&, const T* MADNESS_RESTRICT const);

  namespace detail {


    template <typename Perm, typename Arg, typename Result>
    inline void permute_array(const Perm& perm, const Arg& arg, Result& result) {
      TA_ASSERT(size(result) == size(arg));
      const unsigned int n = size(arg);
      for(unsigned int i = 0u; i < n; ++i) {
        const typename Perm::index_type pi = perm[i];
        TA_ASSERT(i < size(arg));
        TA_ASSERT(pi < size(result));
        result[pi] = arg[i];
      }
    }
  } // namespace detail



  class Permutation {
  public:
    typedef Permutation Permutation_;
    typedef unsigned int index_type;
    typedef std::vector<index_type>::const_iterator const_iterator;

  private:

    std::vector<index_type> p_;

    template <typename InIter>
    bool valid_permutation(InIter first, InIter last) {
      bool result = true;
      using diff_type = typename std::iterator_traits<InIter>::difference_type;
      const diff_type n = std::distance(first, last);
      TA_ASSERT(n >= 0);
      for(; first != last; ++first) {
        const diff_type value = *first;
        result = result && value >= 0 && (value < n) && (std::count(first, last, *first) == 1ul);
      }
      return result;
    }

    // Used to select the correct constructor based on input template types
    struct Enabler { };

  public:

    Permutation() = default; // constructs an invalid Permutation
    Permutation(const Permutation&) = default;
    Permutation(Permutation&&) = default;
    ~Permutation() = default;
    Permutation& operator=(const Permutation&) = default;
    Permutation& operator=(Permutation&& other) = default;


    template <typename InIter,
        typename std::enable_if<detail::is_input_iterator<InIter>::value>::type* = nullptr>
    Permutation(InIter first, InIter last) :
        p_(first, last)
    {
      TA_ASSERT( valid_permutation(first, last) );
    }


    template <typename Integer>
    explicit Permutation(const std::vector<Integer>& a) :
        Permutation(a.begin(), a.end())
    {
    }


    explicit Permutation(std::vector<index_type>&& a) :
        p_(std::move(a))
    {
      TA_ASSERT( valid_permutation(p_.begin(), p_.end()) );
    }


    template <typename Integer,
              typename std::enable_if<std::is_integral<Integer>::value>::type* = nullptr>
    explicit Permutation(std::initializer_list<Integer> list) :
        Permutation(list.begin(), list.end())
    { }


    index_type dim() const { return p_.size(); }


    const_iterator begin() const { return p_.begin(); }


    const_iterator cbegin() const { return p_.cbegin(); }


    const_iterator end() const { return p_.end(); }


    const_iterator cend() const { return p_.cend(); }


    index_type operator[](unsigned int i) const { return p_[i]; }


    std::vector<std::vector<index_type> > cycles() const {

      std::vector<std::vector<index_type>> result;

      std::vector<bool> placed_in_cycle(p_.size(), false);

      // 1. for each i compute its orbit
      // 2. if the orbit is longer than 1, sort and add to the list of cycles
      for(index_type i=0; i!= p_.size(); ++i) {
        if (not placed_in_cycle[i]) {
          std::vector<index_type> cycle(1,i);
          placed_in_cycle[i] = true;

          index_type next_i = p_[i];
          while (next_i != i) {
            cycle.push_back(next_i);
            placed_in_cycle[next_i] = true;
            next_i = p_[next_i];
          }

          if (cycle.size() != 1) {
            std::sort(cycle.begin(), cycle.end());
            result.emplace_back(cycle);
          }

        } // this i already in a cycle
      } // loop over i

      return result;
    }


    static Permutation identity(const unsigned int dim) {
      Permutation result;
      result.p_.reserve(dim);
      for(unsigned int i = 0u; i < dim; ++i)
        result.p_.emplace_back(i);
      return result;
    }


    Permutation identity() const { return identity(p_.size()); }


    Permutation mult(const Permutation& other) const {
      const unsigned int n = p_.size();
      TA_ASSERT(n == other.p_.size());
      Permutation result;
      result.p_.reserve(n);

      for(unsigned int i = 0u; i < n; ++i) {
        const index_type p_i = p_[i];
        const index_type result_i = other.p_[p_i];
        result.p_.emplace_back(result_i);
      }

      return result;
    }


    Permutation inv() const {
      const index_type n = p_.size();
      Permutation result;
      result.p_.resize(n, 0ul);
      for(index_type i = 0ul; i < n; ++i) {
        const index_type pi = p_[i];
        result.p_[pi] = i;
      }
      return result;
    }


    Permutation pow(int n) const {
      // Initialize the algorithm inputs
      int power;
      Permutation value;
      if(n < 0) {
        value = inv();
        power = -n;
      } else {
        value = *this;
        power = n;
      }

      Permutation result = identity(p_.size());

      // Compute the power of value with the exponentiation by squaring.
      while(power) {
          if(power & 1)
            result = result.mult(value);
          value = value.mult(value);
          power >>= 1;
      }

      return result;
    }


    operator bool() const { return ! p_.empty(); }


    bool operator!() const { return p_.empty(); }


    const std::vector<index_type>& data() const { return p_; }


    template <typename Archive>
    void serialize(Archive& ar) {
      ar & p_;
    }

  }; // class Permutation


  inline bool operator==(const Permutation& p1, const Permutation& p2) {
    return (p1.dim() == p2.dim())
        && std::equal(p1.data().begin(), p1.data().end(), p2.data().begin());
  }


  inline bool operator!=(const Permutation& p1, const Permutation& p2) {
    return ! operator==(p1, p2);
  }


  inline bool operator<(const Permutation& p1, const Permutation& p2) {
    return std::lexicographical_compare(p1.data().begin(), p1.data().end(),
        p2.data().begin(), p2.data().end());
  }


  inline std::ostream& operator<<(std::ostream& output, const Permutation& p) {
    std::size_t n = p.dim();
    output << "{";
    for (unsigned int dim = 0; dim < n - 1; ++dim)
      output << dim << "->" << p.data()[dim] << ", ";
    output << n - 1 << "->" << p.data()[n - 1] << "}";
    return output;
  }



  inline Permutation operator -(const Permutation& perm) {
    return perm.inv();
  }


  inline Permutation operator*(const Permutation& p1, const Permutation& p2) {
    return p1.mult(p2);
  }


  inline Permutation& operator*=(Permutation& p1, const Permutation& p2) {
    return (p1 = p1 * p2);
  }


  inline Permutation operator^(const Permutation& perm, int n) {
    return perm.pow(n);
  }


  template <typename T, std::size_t N>
  inline std::array<T,N> operator*(const Permutation& perm, const std::array<T, N>& a) {
    TA_ASSERT(perm.dim() == a.size());
    std::array<T,N> result;
    detail::permute_array(perm, a, result);
    return result;
  }


  template <typename T, std::size_t N>
  inline std::array<T,N>& operator*=(std::array<T,N>& a, const Permutation& perm) {
    TA_ASSERT(perm.dim() == a.size());
    const std::array<T,N> temp = a;
    detail::permute_array(perm, temp, a);
    return a;
  }


  template <typename T, typename A>
  inline std::vector<T> operator*(const Permutation& perm, const std::vector<T, A>& v) {
    TA_ASSERT(perm.dim() == v.size());
    std::vector<T> result(perm.dim());
    detail::permute_array(perm, v, result);
    return result;
  }


  template <typename T, typename A>
  inline std::vector<T, A>& operator*=(std::vector<T, A>& v, const Permutation& perm) {
    const std::vector<T, A> temp = v;
    detail::permute_array(perm, temp, v);
    return v;
  }


  template <typename T>
  inline std::vector<T> operator*(const Permutation& perm, const T* MADNESS_RESTRICT const ptr) {
    const unsigned int n = perm.dim();
    std::vector<T> result(n);
    for(unsigned int i = 0u; i < n; ++i) {
      const typename Permutation::index_type perm_i = perm[i];
      const T ptr_i = ptr[i];
      result[perm_i] = ptr_i;
    }
    return result;
  }

} // namespace TiledArray

#endif // TILEDARRAY_PERMUTATION_H__INCLUED