index_list.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_EXPRESSIONS_INDEX_LIST_H__INCLUDED
#define TILEDARRAY_EXPRESSIONS_INDEX_LIST_H__INCLUDED
 
#include <algorithm>
#include <iosfwd>
#include <set>
#include <string>
#include "TiledArray/permutation.h"
#include "TiledArray/util/annotation.h"
 
namespace TiledArray {
namespace expressions {
 
class IndexList;
IndexList operator*(const ::TiledArray::Permutation&, const IndexList&);
void swap(IndexList&, IndexList&);
 
class BipartiteIndexList;
BipartiteIndexList operator*(const ::TiledArray::Permutation&,
                             const BipartiteIndexList&);
void swap(BipartiteIndexList&, BipartiteIndexList&);
 
namespace detail {
 
template <typename InIter1, typename InIter2>
void find_common(InIter1 first1, const InIter1 last1, InIter2 first2,
                 const InIter2 last2, std::pair<InIter1, InIter1>& common1,
                 std::pair<InIter2, InIter2>& common2) {
  common1.first = last1;
  common1.second = last1;
  common2.first = last2;
  common2.second = last2;
 
  // find the first common element in the in the two ranges
  for (; first1 != last1; ++first1) {
    common2.first = std::find(first2, last2, *first1);
    if (common2.first != last2) break;
  }
  common1.first = first1;
  first2 = common2.first;
 
  // find the last common element in the two ranges
  while ((first1 != last1) && (first2 != last2)) {
    if (*first1 != *first2) break;
    ++first1;
    ++first2;
  }
  common1.second = first1;
  common2.second = first2;
}
 
inline Permutation var_perm(const IndexList& l, const IndexList& r);
inline BipartitePermutation var_perm(const BipartiteIndexList& l,
                                     const BipartiteIndexList& r);
 
}  // namespace detail
 
 
class IndexList {
 public:
  using container_type = container::svector<std::string>;
  using const_iterator = typename container_type::const_iterator;
 
  IndexList() : indices_() {}
 
 
  explicit IndexList(const std::string& str) {
    if (!str.empty()) init_(str);
  }
 
 
  template <typename InIter>
  IndexList(InIter first, InIter last) {
    static_assert(TiledArray::detail::is_input_iterator<InIter>::value,
                  "IndexList constructor requires an input iterator");
 
    for (; first != last; ++first)
      indices_.push_back(trim_spaces_(first->begin(), first->end()));
  }
 
 
  IndexList(const container_type& indices)
      : IndexList(indices.begin(), indices.end()) {}
 
  IndexList(const IndexList& other) : indices_(other.indices_) {}
 
  IndexList& operator=(const IndexList& other) {
    indices_ = other.indices_;
 
    return *this;
  }
 
  IndexList& operator=(const std::string& str) {
    init_(str);
    return *this;
  }
 
  IndexList& operator*=(const Permutation& p) {
    TA_ASSERT(p.size() == size());
    indices_ *= p;
    return *this;
  }
 
 
  explicit operator bool() const { return !indices_.empty(); }
 
 
  bool operator!() const { return indices_.empty(); }
 
  const_iterator begin() const { return indices_.begin(); }
 
  const_iterator end() const { return indices_.end(); }
 
  const std::string& at(const std::size_t n) const { return indices_.at(n); }
 
  const std::string& operator[](const std::size_t n) const {
    return indices_[n];
  }
 
  [[deprecated("use IndexList::size()")]] unsigned int dim() const {
    return indices_.size();
  }
 
  unsigned int size() const { return indices_.size(); }
 
  const auto& data() const { return indices_; }
 
  std::string string() const {
    std::string result;
    using std::cbegin;
    auto it = cbegin(indices_);
    if (it == indices_.end()) return result;
 
    for (result = *it++; it != indices_.end(); ++it) {
      result += "," + *it;
    }
 
    return result;
  }
 
  void swap(IndexList& other) { std::swap(indices_, other.indices_); }
 
  auto count(const std::string& x) const {
    return std::count(begin(), end(), x);
  }
 
  auto positions(const std::string& x) const {
    container::svector<std::size_t> rv;
    for (std::size_t i = 0; i < size(); ++i)
      if ((*this)[i] == x) rv.push_back(i);
    return rv;
  }
 
 
  template <typename V,
            typename = std::enable_if_t<TiledArray::detail::is_range_v<V>>>
  Permutation permutation(const V& other) const {
    return detail::var_perm(*this, other);
  }
 
 
  bool is_permutation(const IndexList& other) const {
    if (indices_.size() != other.indices_.size()) return false;
 
    for (const_iterator it = begin(); it != end(); ++it) {
      const_iterator other_it = other.begin();
      for (; other_it != other.end(); ++other_it)
        if (*it == *other_it) break;
      if (other_it == other.end()) return false;
    }
 
    return true;
  }
 
 private:
  void init_(const std::string& str) {
    std::string::const_iterator start = str.begin();
    std::string::const_iterator finish = str.begin();
    for (; finish != str.end(); ++finish) {
      if (*finish == ',') {
        indices_.push_back(trim_spaces_(start, finish));
        start = finish + 1;
      }
    }
    indices_.push_back(trim_spaces_(start, finish));
  }
 
  static std::string trim_spaces_(std::string::const_iterator first,
                                  std::string::const_iterator last) {
    TA_ASSERT(first != last);
    std::string result = "";
    for (; first != last; ++first) {
      TA_ASSERT(valid_char_(*first));
      if (*first != ' ' && *first != '\0') result.append(1, *first);
    }
 
    TA_ASSERT(result.length() != 0);
 
    return result;
  }
 
  template <typename InIter>
  bool unique_(InIter first, InIter last) const {
    for (; first != last; ++first) {
      InIter it2 = first;
      for (++it2; it2 != last; ++it2)
        if (first->compare(*it2) == 0) return false;
    }
 
    return true;
  }
 
  static bool valid_char_(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
           (c >= '0' && c <= '9') || (c == ' ') || (c == ',') || (c == '\0') ||
           (c == '\'') || (c == '_');
  }
 
  friend void swap(IndexList&, IndexList&);
 
  container_type indices_;
 
  friend IndexList operator*(const ::TiledArray::Permutation&,
                             const IndexList&);
 
};  // class IndexList
 
inline void swap(IndexList& v0, IndexList& v1) {
  std::swap(v0.indices_, v1.indices_);
}
 
inline bool operator==(const IndexList& v0, const IndexList& v1) {
  return (v0.size() == v1.size()) &&
         std::equal(v0.begin(), v0.end(), v1.begin());
}
 
inline bool operator!=(const IndexList& v0, const IndexList& v1) {
  return !operator==(v0, v1);
}
 
inline IndexList operator*(const ::TiledArray::Permutation& p,
                           const IndexList& v) {
  TA_ASSERT(p.size() == v.size());
  IndexList result;
  result.indices_ = p * v.indices_;
 
  return result;
}
 
inline std::ostream& operator<<(std::ostream& out, const IndexList& v) {
  out << "(";
  std::size_t d;
  std::size_t n = v.size() - 1;
  for (d = 0; d < n; ++d) {
    out << v[d] << ", ";
  }
  out << v[d];
  out << ")";
  return out;
}
 
 
class BipartiteIndexList {
 private:
  using container_type = typename IndexList::container_type;
 
  using container_pair = std::pair<container_type, container_type>;
 
 public:
  typedef std::string value_type;
 
  typedef const value_type& const_reference;
 
  typedef container_type::const_iterator const_iterator;
 
  typedef std::size_t size_type;
 
  BipartiteIndexList() = default;
 
  explicit BipartiteIndexList(const std::string str)
      : BipartiteIndexList(TiledArray::detail::split_index(str)) {}
 
  BipartiteIndexList(const BipartiteIndexList& other) = default;
 
  BipartiteIndexList& operator=(const BipartiteIndexList& other) = default;
 
  BipartiteIndexList& operator=(const std::string& str) {
    BipartiteIndexList(str).swap(*this);
    return *this;
  }
 
  BipartiteIndexList& operator*=(const Permutation& p) {
    TA_ASSERT(p.size() == size());
    indices_ *= p;
    return *this;
  }
 
  bool operator==(const BipartiteIndexList& other) const {
    return std::tie(second_size_, indices_) ==
           std::tie(other.second_size_, other.indices_);
  }
 
 
  explicit operator bool() const { return !indices_.empty(); }
 
 
  bool operator!() const { return indices_.empty(); }
 
  const_iterator begin() const { return indices_.begin(); }
 
  const_iterator end() const { return indices_.end(); }
 
  const_reference at(const size_type n) const { return indices_.at(n); }
 
  const_reference operator[](const size_type n) const { return indices_[n]; }
 
  auto positions(const std::string& x) const {
    container::svector<std::size_t> rv;
    for (size_type i = 0; i < size(); ++i)
      if ((*this)[i] == x) rv.push_back(i);
    return rv;
  }
 
  size_type count(const std::string& x) const {
    return std::count(begin(), end(), x);
  }
 
  [[deprecated("use BipartiteIndexList::size()")]] size_type dim() const {
    return size();
  }
 
  size_type first_size() const { return size() - second_size(); }
 
  size_type second_size() const { return second_size_; }
 
  IndexList first() const { return IndexList(begin(), begin() + first_size()); }
 
  IndexList second() const { return IndexList(begin() + first_size(), end()); }
 
  size_type size() const { return indices_.size(); }
 
  const auto& data() const { return indices_; }
 
  explicit operator value_type() const;
 
  void swap(BipartiteIndexList& other) noexcept {
    std::swap(second_size_, other.second_size_);
    std::swap(indices_, other.indices_);
  }
 
 
  template <typename V,
            typename = std::enable_if_t<TiledArray::detail::is_range_v<V>>>
  BipartitePermutation permutation(const V& other) const {
    return detail::var_perm(*this, other);
  }
 
 
  bool is_permutation(const BipartiteIndexList& other) const {
    if (other.size() != size()) return false;
    return std::is_permutation(begin(), end(), other.begin());
  }
 
  template <typename OuterType, typename InnerType>
  BipartiteIndexList(OuterType&& outer, InnerType&& inner);
 
 private:
  template <typename First, typename Second>
  explicit BipartiteIndexList(const std::pair<First, Second>& tot_idx)
      : BipartiteIndexList(tot_idx.first, tot_idx.second) {}
 
  size_type second_size_ = 0;
 
  container_type indices_;
 
  friend BipartiteIndexList operator*(const ::TiledArray::Permutation&,
                                      const BipartiteIndexList&);
 
};  // class BipartiteIndexList
 
template <typename T, typename... Args>
auto all_annotations(T&& v, Args&&... args) {
  std::set<std::string> rv;
  if constexpr (sizeof...(Args) > 0) {
    rv = all_annotations(std::forward<Args>(args)...);
  }
  rv.insert(v.begin(), v.end());
  return rv;
}
 
template <typename T, typename... Args>
auto common_annotations(T&& v, Args&&... args) {
  std::set<std::string> rv;
  if constexpr (sizeof...(Args) > 0) {
    rv = common_annotations(std::forward<Args>(args)...);
    // Remove all annotations not found in v
    decltype(rv) buffer(rv);
    for (const auto& x : buffer)
      if (!v.count(x)) rv.erase(x);
  } else {
    // Initialize rv to all annotations in v
    rv.insert(v.begin(), v.end());
  }
  return rv;
}
 
template <typename IndexList_, typename... Args>
auto bound_annotations(const IndexList_& out, Args&&... args) {
  // Get all indices in the input tensors
  auto rv = all_annotations(std::forward<Args>(args)...);
 
  // Remove those found in the output tensor
  decltype(rv) buffer(rv);
  for (const auto& x : buffer)
    if (out.count(x)) rv.erase(x);
  return rv;
}
 
inline void swap(BipartiteIndexList& v0, BipartiteIndexList& v1) {
  v0.swap(v1);
}
 
inline bool operator!=(const BipartiteIndexList& v0,
                       const BipartiteIndexList& v1) {
  return !(v0 == v1);
}
 
inline BipartiteIndexList operator*(const ::TiledArray::Permutation& p,
                                    const BipartiteIndexList& v) {
  TA_ASSERT(p.size() == v.size());
  BipartiteIndexList result(v);
  return result *= p;
}
 
inline std::ostream& operator<<(std::ostream& out,
                                const BipartiteIndexList& v) {
  const std::string str = "(" + static_cast<std::string>(v) + ")";
  return out << str;
}
 
//------------------------------------------------------------------------------
//                             Implementations
//------------------------------------------------------------------------------
 
inline BipartiteIndexList::operator value_type() const {
  value_type result;
  for (size_type i = 0; i < size(); ++i) {
    if (i == first_size())
      result += ";";
    else if (i > 0)
      result += ",";
    result += at(i);
  }
 
  return result;
}
 
template <typename OuterType, typename InnerType>
inline BipartiteIndexList::BipartiteIndexList(OuterType&& outer,
                                              InnerType&& inner)
    : second_size_(inner.size()), indices_(outer.size() + inner.size()) {
  for (size_type i = 0; i < outer.size(); ++i) indices_[i] = outer[i];
  for (size_type i = 0; i < inner.size(); ++i)
    indices_[i + outer.size()] = inner[i];
}
 
namespace detail {
 
inline Permutation var_perm(const IndexList& l, const IndexList& r) {
  using std::size;
  TA_ASSERT(size(l) == size(r));
  container::svector<size_t> a(size(l));
  using std::begin;
  using std::end;
  auto rit = begin(r);
  for (auto it = begin(a); it != end(a); ++it) {
    auto lit = std::find(begin(l), end(l), *rit++);
    TA_ASSERT(lit != end(l));
    *it = std::distance(begin(l), lit);
  }
  return Permutation(std::move(a));
}
 
inline BipartitePermutation var_perm(const BipartiteIndexList& l,
                                     const BipartiteIndexList& r) {
  using std::size;
  TA_ASSERT(size(l) == size(r));
  TA_ASSERT(l.first_size() == r.first_size());
  container::svector<size_t> a(size(l));
  using std::begin;
  using std::end;
  auto rit = begin(r);
  for (auto it = begin(a); it != end(a); ++it) {
    auto lit = std::find(begin(l), end(l), *rit++);
    TA_ASSERT(lit != end(l));
    *it = std::distance(begin(l), lit);
  }
  // Make sure this permutation doesn't mix outer and inner tensors
  if (l.second_size() > 0) {
    auto outer_size = l.first_size();
    for (decltype(outer_size) i = 0; i < outer_size; ++i)
      TA_ASSERT(a[i] < outer_size);
    for (auto i = outer_size; i < a.size(); ++i) TA_ASSERT(a[i] >= outer_size);
  }
  return BipartitePermutation(std::move(a), l.second_size());
}
 
}  // namespace detail
 
 
inline auto inner(const IndexList& p) {
  abort();
  return IndexList{};
}
 
// N.B. can't return ref here due to possible dangling ref when p is bound to
// temporary
inline auto outer(const IndexList& p) { return p; }
 
inline auto inner_size(const IndexList& p) { return 0; }
 
inline auto outer_size(const IndexList& p) { return p.size(); }
 
inline auto inner(const BipartiteIndexList& p) { return p.second(); }
 
inline auto outer(const BipartiteIndexList& p) { return p.first(); }
 
inline auto inner_size(const BipartiteIndexList& p) { return p.second_size(); }
 
inline auto outer_size(const BipartiteIndexList& p) { return p.first_size(); }
 
}  // namespace expressions
 
}  // namespace TiledArray
 
#endif  // TILEDARRAY_EXPRESSIONS_INDEX_LIST_H__INCLUDED