key.hpp

Go to the documentation of this file.

//  
//       ,---.     ,--,    .---.     ,--,    ,---.    .-. .-. 
//       | .-'   .' .')   / .-. )  .' .'     | .-'    |  \| | 
//       | `-.   |  |(_)  | | |(_) |  |  __  | `-.    |   | | 
//       | .-'   \  \     | | | |  \  \ ( _) | .-'    | |\  | 
//       |  `--.  \  `-.  \ `-' /   \  `-) ) |  `--.  | | |)| 
//       /( __.'   \____\  )---'    )\____/  /( __.'  /(  (_) 
//      (__)              (_)      (__)     (__)     (__)     
//
//  This file is part of ECOGEN.
//
//  ECOGEN is the legal property of its developers, whose names 
//  are listed in the copyright file included with this source 
//  distribution.
//
//  ECOGEN 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.
//  
//  ECOGEN 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 ECOGEN (file LICENSE).  
//  If not, see <http://www.gnu.org/licenses/>.
 
#ifndef INCLUDED_KEY_HPP
#define INCLUDED_KEY_HPP
 
 
#include <array>
#include <iomanip>
#include <cmath>
#include <bitset>
#include "vector.hpp"
 
namespace decomposition
{
 
 
template <int Dim>
struct Key
{
public: // member types
 
    //using value_type = uint_fast64_t;
    using value_type = unsigned long long int;
    using scalar_coordinate_type=int;
 
    using float_type = double;
    template<typename U>
    using vector_type = math::vector<U,Dim>;
    using coordinate_type = vector_type<scalar_coordinate_type>;
    using real_coordinate_type = vector_type<float_type>;
    struct hash_functor
    {
        std::size_t operator()(Key const& n) const noexcept
        {
            return std::hash<value_type>()(n.index_);
        }
    };
 
public:  //static members
 
    static value_type compute_index(const coordinate_type& _c)noexcept {
        value_type idx =split_bits(static_cast<value_type>(_c.x()));
        for(int d=1;d<Dim;++d) 
        {
            idx |=(split_bits(static_cast<value_type>(_c[d])) << d);
        }
        return idx;
    }
 
public: 
    static coordinate_type coordinate(const value_type& code ) noexcept{
        coordinate_type c(0);
        for (int d = 0; d < Dim; ++d) c[d] = static_cast<scalar_coordinate_type>(compress_bits(code >> static_cast<value_type>(d)));
        return c;
    }
 
public: // Ctors
 
    Key() noexcept
    : index_(0) {}
 
    Key(value_type idx) noexcept
    : index_(idx) {}
 
    Key(int x, int y, int z) noexcept
    :Key(coordinate_type({x,y,z})) { }
 
    Key(coordinate_type x) noexcept
    : index_(compute_index(x)) {  }
 
    Key(const Key&) = default;
    Key(Key&&) = default;
    Key& operator=(const Key&) & = default;
    Key& operator=(Key&&) & = default;
 
 
public: //Access 
 
    coordinate_type coordinate()const noexcept {return coordinate(index_);}
    const value_type& index()const noexcept{return index_;}
    value_type& index() noexcept{return index_;}
    const value_type& getIndex()const noexcept {return index_;}
    value_type& getIndex() noexcept{return index_;}
 
    Key neighbor(const coordinate_type& _offset) const noexcept
    {
        const auto c =coordinate()+_offset;
        return Key(c);
    }
    
    Key child(int i) const noexcept
    {
        return (index_<<Dim)| static_cast<value_type>(i);
    }
 
    Key& operator++() noexcept { ++index_;return *this; }
    Key& operator--() noexcept { ++index_;return *this; }
    Key& operator+=(int) noexcept { ++index_; return *this;}
    Key& operator-=(int) noexcept { ++index_; return *this;}
    friend std::ostream& operator<<(std::ostream& os, const Key& _k)
    {
        os<<std::bitset<64>(_k.index_)<<" = "<<_k.index_
                 <<" coord =( "<<_k.coordinate()<<" )";
        return os;
    }
 
 
private: //Static 
 
    template<int nDim =Dim>
    static value_type split_bits(value_type w)
    {
        using tag=std::integral_constant<int,3>*;
        return split_bits_impl(w, tag(0));
    }
    template<int nDim =Dim>
    static value_type compress_bits(value_type w)
    {
        using tag=std::integral_constant<int,3>*;
        return compress_bits_impl(w, tag(0));
    }
 
    static value_type 
    split_bits_impl(value_type w, std::integral_constant<int, 3>*)  
    noexcept
    {
        w &=                0x00000000001fffff; 
        w = (w | w << 32) & 0x001f00000000ffff;  
        w = (w | w << 16) & 0x001f0000ff0000ff;  
        w = (w | w <<  8) & 0x010f00f00f00f00f; 
        w = (w | w <<  4) & 0x10c30c30c30c30c3; 
        w = (w | w <<  2) & 0x1249249249249249;
        return w;
    }
    static scalar_coordinate_type 
    compress_bits_impl(value_type w,std::integral_constant<int, 3>*) noexcept
    {
        w &=                  0x1249249249249249;
        w = (w ^ (w >> 2))  & 0x30c30c30c30c30c3;
        w = (w ^ (w >> 4))  & 0xf00f00f00f00f00f;
        w = (w ^ (w >> 8))  & 0x00ff0000ff0000ff;
        w = (w ^ (w >> 16)) & 0x00ff00000000ffff;
        w = (w ^ (w >> 32)) & 0x00000000001fffff;
        return static_cast<scalar_coordinate_type>(w);
    }
    static value_type 
    split_bits_impl(value_type x, std::integral_constant<int, 2>*)  
    noexcept
    {
        x = (x | (x << 16)) & 0x0000FFFF0000FFFF;
        x = (x | (x << 8))  & 0x00FF00FF00FF00FF;   
        x = (x | (x << 4))  & 0x0F0F0F0F0F0F0F0F; 
        x = (x | (x << 2))  & 0x3333333333333333;
        x = (x | (x << 1))  & 0x5555555555555555;
        return x;
    }
 
    static scalar_coordinate_type 
    compress_bits_impl(value_type w,std::integral_constant<int, 2>*) noexcept
    {
        w &=                  0x5555555555555555;
        w = (w ^ (w >> 1))  & 0x3333333333333333;
        w = (w ^ (w >> 2))  & 0x0f0f0f0f0f0f0f0f;
        w = (w ^ (w >> 4))  & 0x00ff00ff00ff00ff;
        w = (w ^ (w >> 8))  & 0x0000ffff0000ffff;
        w = (w ^ (w >> 16)) & 0x00000000ffffffff;
        return static_cast<scalar_coordinate_type>(w);
    }
 
private:
    value_type index_;
};
 
// binary operators
template<int Dim>
Key<Dim> operator+(int n, Key<Dim> k) noexcept
{ return k+=n;}
 
template<int Dim>
Key<Dim> operator-(int n, Key<Dim> k) noexcept
{ return k-=n; }
 
// relational operators
template<int Dim>
constexpr bool operator==(const Key<Dim>& l, const Key<Dim>& r) noexcept
{ return l.index() == r.index(); }
 
template<int Dim>
constexpr bool operator!=(const Key<Dim>& l, const Key<Dim>& r) noexcept
{ return l.index() != r.index(); }
 
template<int Dim>
constexpr bool operator<(const Key<Dim>& l, const Key<Dim>& r) noexcept
{ return l.index() < r.index(); }
 
template<int Dim>
constexpr bool operator<=(const Key<Dim>& l, const Key<Dim>& r) noexcept
{ return l.index() <= r.index(); }
 
template<int Dim>
constexpr bool operator>(const Key<Dim>& l, const Key<Dim>& r) noexcept
{ return l.index() > r.index(); }
 
template<int Dim>
constexpr bool operator>=(const Key<Dim>& l, const Key<Dim>& r) noexcept
{ return l.index() >= r.index(); }
 
}
 
#endif