lexicographic.h

Go to the documentation of this file.

#ifndef TPCC_LEXICOGRAPHIC_H
#define TPCC_LEXICOGRAPHIC_H
 
#include <tpcc/element.h>
 
namespace TPCC
{
 
enum boundaries
{
  both,
  none,
  periodic
};
template <int n, int k, boundaries bnd = both, typename Bint = unsigned int,
          typename Sint = unsigned short, typename Tint = unsigned char>
class Lexicographic
{
  std::array<Sint, n> dimensions;
  std::array<Bint, binomial(n, k)> block_sizes;
 
  std::array<Bint, binomial(n, k)> block_sizes_bnd;
 
public:
  static constexpr Tint order() { return n; }
 
  static constexpr Tint cell_dimension() { return k; }
 
  typedef Bint global_index_t;
  typedef Sint fiber_index_t;
  typedef Tint dimension_index_t;
 
  typedef Element<n, k, Sint, Tint> value_type;
 
  constexpr Lexicographic(const std::array<Sint, n>& d)
    : dimensions(d)
  {
    Combinations<n, k> combinations;
    for (Tint i = 0; i < binomial(n, k); ++i)
    {
      Bint p = 1;
      auto combination = combinations[i];
      for (Tint j = 0; j < k; ++j)
        p *= dimensions[n - 1 - combination.in(j)];
      for (Tint j = 0; j < n - k; ++j)
        switch (bnd)
        {
          case both:
            p *= dimensions[n - 1 - combination.out(j)] + 1;
            break;
          case none:
            p *= dimensions[n - 1 - combination.out(j)] - 1;
            break;
          default: // perioridic
            p *= dimensions[n - 1 - combination.out(j)];
            break;
        }
      block_sizes_bnd[i] = p;
    }
    for (Tint i = 0; i < binomial(n, k); ++i)
    {
      Bint p = 1;
      auto combination = combinations[i];
      for (Tint j = 0; j < k; ++j)
        p *= dimensions[n - 1 - combination.in(j)];
      for (Tint j = 0; j < n - k; ++j)
        p *= dimensions[n - 1 - combination.out(j)] + 1;
      block_sizes[i] = p;
    }
  }
 
  constexpr Bint size() const
  {
    Bint sum = 0;
    for (unsigned int i = 0; i < block_sizes.size(); ++i)
      sum += block_sizes_bnd[i];
    return sum;
  }
 
  constexpr Bint block_size(Tint block) const { return block_sizes[block]; }
 
  constexpr Sint fiber_dimension(Tint i) const { return dimensions[i]; }
 
  value_type operator[](Bint index) const;
 
  Bint index_in_slice(const value_type& e) const
  {
    Bint result = 0, factor = 1;
    for (Tint i = 0; i < k; ++i)
    {
      Sint fdim = dimensions[e.along_direction(i)];
      result += e.along_coordinate(i) * factor;
      factor *= fdim;
    }
    return result;
  }
 
  Bint index(const value_type& e) const;
 
  template <boundaries bndT = bnd>
  constexpr Lexicographic<n, k - 1, bndT, Bint, Sint, Tint> boundary() const
  {
    return Lexicographic<n, k - 1, bndT, Bint, Sint, Tint>{ dimensions };
  }
};
 
template <int n, int k, boundaries bnd, typename Bint, typename Sint, typename Tint>
Element<n, k, Sint, Tint> Lexicographic<n, k, bnd, Bint, Sint, Tint>::operator[](Bint index) const
{
  unsigned int b = 0;
  while (b < block_sizes.size())
  {
    if (index < block_sizes[b])
      break;
    index -= block_sizes[b];
    ++b;
  }
 
  if (b == block_sizes.size())
    throw(b);
 
  Combinations<n, k> combinations;
  auto combination = combinations[b];
 
  std::array<Sint, n> coordinates;
  for (int i = 0; i < k; ++i)
  {
    Sint fdim = dimensions[n - 1 - combination.in(i)];
    coordinates[n - 1 - combination.in(i)] = index % fdim;
    index /= fdim;
  }
  for (int i = 0; i < n - k; ++i)
  {
    Sint fdim = 1 + dimensions[n - 1 - combination.out(i)];
    coordinates[n - 1 - combination.out(i)] = index % fdim;
    index /= fdim;
  }
  return Element<n, k, Sint, Tint>{ combination, coordinates };
}
 
template <int n, int k, boundaries bnd, typename Bint, typename Sint, typename Tint>
Bint Lexicographic<n, k, bnd, Bint, Sint, Tint>::index(const value_type& e) const
{
  Bint ci = e.direction_index();
  Bint result = 0;
  for (unsigned int i = 0; i < ci; ++i)
    result += block_sizes_bnd[i];
 
  Bint factor = 1;
  for (Tint i = 0; i < k; ++i)
  {
    Sint fdim = dimensions[e.along_direction(i)];
    result += e.along_coordinate(i) * factor;
    factor *= fdim;
  }
  for (unsigned int i = 0; i < n - k; ++i)
  {
    Tint fdim = 1 + dimensions[e.across_direction(i)];
 
    if (bnd == periodic)
      fdim -= 1;
    else if (bnd == none)
      fdim -= 2;
 
    Bint cross_coord = e.across_coordinate(i);
    // std::cout << "fdim " << e.across_direction(i) << " " << fdim << " " << e.across_coordinate(i)
    // << std::endl;
    assert((cross_coord != 0 && cross_coord != fdim + 1) || bnd != none);
    if (cross_coord == fdim && bnd == periodic)
      cross_coord = 0;
    else if (bnd == none)
      --cross_coord;
 
    result += cross_coord * factor;
    factor *= fdim;
  }
  return result;
}
 
} // namespace TPCC
 
#endif