bitvector.hpp

Go to the documentation of this file.

#ifndef GENESIS_UTILS_MATH_BITVECTOR_H_
#define GENESIS_UTILS_MATH_BITVECTOR_H_

/*
    Genesis - A toolkit for working with phylogenetic data.
    Copyright (C) 2014-2020 Lucas Czech and HITS gGmbH

    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/>.

    Contact:
    Lucas Czech <lucas.czech@h-its.org>
    Exelixis Lab, Heidelberg Institute for Theoretical Studies
    Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
*/

#include <array>
#include <cassert>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <vector>

namespace genesis {
namespace utils {

// =================================================================================================
//     Bitvector
// =================================================================================================

class Bitvector
{
public:

    // ---------------------------------------------------------
    //     Typedefs, Enums, Constants
    // ---------------------------------------------------------

    using IntType = uint64_t;
    static const size_t IntSize = sizeof(IntType) * 8;

    // ---------------------------------------------------------
    //     Constructor and Rule of Five
    // ---------------------------------------------------------

    Bitvector() = default;

    Bitvector( size_t size, bool initial_value = false)
        : size_(size)
    {
        // reserve enough bits, and init them.
        data_.resize( (size / IntSize) + (size % IntSize == 0 ? 0 : 1) );
        set_all(initial_value);
    }

    Bitvector( size_t size, std::initializer_list<size_t> list)
        : Bitvector(size, false)
    {
        for (size_t e : list) {
            set(e);
        }
    }

    Bitvector( std::string const& values );

    Bitvector( Bitvector const& other, size_t max_size );

    ~Bitvector() = default;

    Bitvector(Bitvector const&) = default;
    Bitvector(Bitvector&&)      = default;

    Bitvector& operator= (Bitvector const&) = default;
    Bitvector& operator= (Bitvector&&)      = default;

    // ---------------------------------------------------------
    //     Single Bit Functions
    // ---------------------------------------------------------

    inline bool operator [] (size_t index) const {
        assert( index / IntSize < data_.size() );
        assert( index % IntSize < bit_mask_.size() );
        return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
    }

    inline bool get (size_t index) const
    {
        if (index >= size_) {
            throw std::out_of_range(
                "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
                std::to_string(size())
            );
        }

        assert( index / IntSize < data_.size() );
        assert( index % IntSize < bit_mask_.size() );
        return static_cast<bool> (data_[index / IntSize] & bit_mask_[index % IntSize]);
    }

    inline void set (size_t index)
    {
        if (index >= size_) {
            throw std::out_of_range(
                "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
                std::to_string(size())
            );
        }

        assert( index / IntSize < data_.size() );
        assert( index % IntSize < bit_mask_.size() );
        data_[index / IntSize] |= bit_mask_[index % IntSize];
    }

    inline void unset (size_t index)
    {
        if (index >= size_) {
            throw std::out_of_range(
                "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
                std::to_string(size())
            );
        }

        assert( index / IntSize < data_.size() );
        assert( index % IntSize < bit_mask_.size() );
        data_[index / IntSize] &= ~(bit_mask_[index % IntSize]);
    }

    inline void set (size_t index, bool value)
    {
        if (value) {
            set(index);
        } else {
            unset(index);
        }
    }

    inline void flip (size_t index)
    {
        if (index >= size_) {
            throw std::out_of_range(
                "Cannot access element " + std::to_string(index) + " in Bitvector of size " +
                std::to_string(size())
            );
        }

        assert( index / IntSize < data_.size() );
        assert( index % IntSize < bit_mask_.size() );
        data_[index / IntSize] ^= bit_mask_[index % IntSize];
    }

    // ---------------------------------------------------------
    //     Operators
    // ---------------------------------------------------------

    Bitvector& operator &= (Bitvector const& rhs);
    Bitvector& operator |= (Bitvector const& rhs);
    Bitvector& operator ^= (Bitvector const& rhs);
    Bitvector  operator ~  () const;

    friend Bitvector operator & (Bitvector const& lhs, Bitvector const& rhs);
    friend Bitvector operator | (Bitvector const& lhs, Bitvector const& rhs);
    friend Bitvector operator ^ (Bitvector const& lhs, Bitvector const& rhs);

    bool operator == (const Bitvector &other) const;
    bool operator != (const Bitvector &other) const;

    // ---------------------------------------------------------
    //     Other Functions
    // ---------------------------------------------------------

    inline size_t size() const
    {
        return size_;
    }

    size_t count() const;

    size_t hash()  const;

    IntType x_hash() const;

    void negate();

    void normalize();

    void set_all(const bool value = false);

    std::string dump() const;
    std::string dump_int(IntType x) const;

    // ---------------------------------------------------------
    //     Internal Members
    // ---------------------------------------------------------

private:

    void unset_padding_();

    static const IntType all_0_;
    static const IntType all_1_;

    static const std::array<IntType, IntSize> bit_mask_;

    static const std::array<IntType, IntSize> ones_mask_;

    static const std::array<IntType, 4> count_mask_;

    // ---------------------------------------------------------
    //     Data Members
    // ---------------------------------------------------------

    size_t               size_ = 0;
    std::vector<IntType> data_;
};

// =============================================================================
//     Hashing
// =============================================================================

struct BitvectorHash
{
    std::size_t operator() ( genesis::utils::Bitvector const& value ) const
    {
        return value.hash();
    }
};

struct BitvectorXhash
{
    std::size_t operator() ( genesis::utils::Bitvector const& value ) const
    {
        return static_cast<std::size_t>( value.x_hash() );
    }
};

} // namespace utils
} // namespace genesis

// =============================================================================
//     Namespace std extension
// =============================================================================

namespace std {

template<>
struct hash<genesis::utils::Bitvector>
{
    std::size_t operator() ( genesis::utils::Bitvector const& value ) const
    {
        return value.hash();
    }
};

} // namespace std

#endif // include guard