ColorSet.hpp

Go to the documentation of this file.

#ifndef BIFROST_COLORSET_HPP
#define BIFROST_COLORSET_HPP
 
#include "roaring.hh"
 
#include "CompactedDBG.hpp"
#include "TinyBitmap.hpp"
 
template<typename Unitig_data_t> class ColoredCDBG;
template<typename Unitig_data_t> class DataAccessor;
template<typename Unitig_data_t> class DataStorage;
 
class UnitigColors {
 
    //Ensure that UnitigColors::setPtrBmp is always allocated with an 8 bytes alignment
    struct alignas(8) Bitmap { Roaring r; };
 
    template<typename U> friend class ColoredCDBG;
    template<typename U> friend class DataAccessor;
    template<typename U> friend class DataStorage;
 
    public:
 
        typedef pair<UnitigColors, size_t> SharedUnitigColors;
 
        class UnitigColors_const_iterator : public std::iterator<std::forward_iterator_tag, pair<size_t, size_t>> {
 
            friend class UnitigColors;
 
            public:
 
                UnitigColors_const_iterator();
 
                UnitigColors_const_iterator(const UnitigColors_const_iterator& o);
 
                ~UnitigColors_const_iterator();
 
                UnitigColors_const_iterator& operator=(const UnitigColors_const_iterator& o);
 
                inline pair<size_t, size_t> operator*() const {
 
                    return make_pair(ck_id % um_sz, ck_id / um_sz);
                }
 
                inline size_t getKmerPosition() const { return ck_id % um_sz; }
 
                inline size_t getColorID() const { return ck_id / um_sz; }
 
                UnitigColors_const_iterator operator++(int);
 
                UnitigColors_const_iterator& operator++();
 
                UnitigColors_const_iterator& nextColor();
 
                bool operator==(const UnitigColors_const_iterator& o) const;
 
                bool operator!=(const UnitigColors_const_iterator& o) const;
 
            private:
 
                const UnitigColors* cs;
 
                size_t flag;
 
                size_t it_setBits;
                size_t cs_sz;
                size_t um_sz;
 
                size_t start_pos;
                size_t end_pos;
 
                uint64_t ck_id;
 
                const Roaring empty_roar;
 
                TinyBitmap t_bmp;
 
                UnitigColors_const_iterator* it_uc;
                Roaring::const_iterator it_roar;
                TinyBitmap::const_iterator it_t_bmp;
 
                UnitigColors_const_iterator(const UnitigColors* cs_, const size_t start_pos_, const size_t end_pos_,
                                            const size_t len_unitig_km, const bool beg);
 
                inline uint64_t get_ID() const { return ck_id; }
 
                inline bool isInvalid() const {
 
                    return ((ck_id == 0xffffffffffffffff) || (it_setBits == cs_sz));
                }
        };
 
        typedef UnitigColors_const_iterator const_iterator;
 
        UnitigColors();
 
        UnitigColors(const UnitigColors& o); // Copy constructor
 
        UnitigColors(UnitigColors&& o); // Move  constructor
 
        ~UnitigColors();
 
        UnitigColors& operator=(const UnitigColors& o);
 
        UnitigColors& operator=(UnitigColors&& o);
 
        //bool operator==(const UnitigColors& o) const;
        // inline bool operator!=(const UnitigColors& o) const { return !operator==(o);
 
        void clear();
 
        bool isEqual(const UnitigMapBase& um, const UnitigColors& o, const UnitigMapBase& um_o) const;
 
        inline bool isEmpty() const { return (size() == 0); }
 
        void add(const UnitigMapBase& um, const size_t color_id);
 
        void remove(const UnitigMapBase& um, const size_t color_id);
 
        bool contains(const UnitigMapBase& um, const size_t color_id) const;
 
        size_t size(const UnitigMapBase& um) const;
 
        size_t size(const UnitigMapBase& um, const size_t color_id) const;
 
        size_t colorMax(const UnitigMapBase& um) const;
 
        bool write(ostream& stream_out, const bool copy_UnitigColors = true) const;
 
        bool read(istream& stream_in);
 
        size_t getSizeInBytes() const;
 
        const_iterator begin(const UnitigMapBase& um) const;
 
        const_iterator end() const;
 
        bool optimizeFullColors(const UnitigMapBase& um);
 
        uint64_t hash(const size_t seed = 0) const;
 
    private:
 
        UnitigColors(SharedUnitigColors& o);
        UnitigColors(const UnitigColors& o, const SharedUnitigColors* old_ref_uc, const SharedUnitigColors* new_ref_uc);
 
        UnitigColors& operator=(SharedUnitigColors& o);
 
        void add(const size_t color_id);
        bool contains(const size_t color_km_id) const;
 
        inline void releaseMemory(){
 
            const uintptr_t flag = setBits & flagMask;
 
            if (flag == ptrUnitigColors) delete[] getPtrUnitigColors();
            else if (flag == ptrBitmap) delete getPtrBitmap();
            else if (flag == ptrSharedUnitigColors){
 
                SharedUnitigColors* s_uc = getPtrSharedUnitigColors();
 
                if (--(s_uc->second) == 0) s_uc->first.clear();
            }
            else if (flag == localTinyBitmap){
 
                uint16_t* setPtrTinyBmp = getPtrTinyBitmap();
                TinyBitmap t_bmp(&setPtrTinyBmp);
 
                t_bmp.clear();
            }
 
            setBits = localBitVector;
        }
 
        inline void shrinkSize(){
 
            const uintptr_t flag = setBits & flagMask;
 
            if (flag == ptrUnitigColors){
 
                UnitigColors* uc = getPtrUnitigColors();
 
                uc[0].shrinkSize();
                uc[1].shrinkSize();
            }
            else if (flag == ptrBitmap) getPtrBitmap()->r.shrinkToFit();
            else if (flag == localTinyBitmap){
 
                uint16_t* setPtrTinyBmp = getPtrTinyBitmap();
                TinyBitmap t_bmp(&setPtrTinyBmp);
 
                t_bmp.shrinkSize();
 
                setBits = (reinterpret_cast<uintptr_t>(t_bmp.detach()) & pointerMask) | localTinyBitmap;
            }
        }
 
        UnitigColors makeFullColors(const UnitigMapBase& um) const;
        UnitigColors getFullColors(const UnitigMapBase& um) const;
        UnitigColors getNonFullColors(const UnitigMapBase& um, const UnitigColors& full_uc) const;
 
        inline UnitigColors* getFullColorsPtr() {
 
            return (isUnitigColors() ? getPtrUnitigColors() : nullptr);
        }
 
        inline const UnitigColors* getFullColorsPtr() const {
 
            return (isUnitigColors() ? getPtrUnitigColors() : nullptr);
        }
 
        inline bool isBitmap() const { return ((setBits & flagMask) == ptrBitmap); }
        inline bool isTinyBitmap() const { return ((setBits & flagMask) == localTinyBitmap); }
        inline bool isUnitigColors() const { return ((setBits & flagMask) == ptrUnitigColors); }
        inline bool isSharedUnitigColors() const { return ((setBits & flagMask) == ptrSharedUnitigColors); }
 
        size_t size() const;
 
        UnitigColors reverse(const UnitigMapBase& um) const;
 
        const_iterator begin(const size_t start_pos, const size_t end_pos, const size_t len_km_sz) const;
 
        inline Bitmap* getPtrBitmap() const {
 
            return reinterpret_cast<Bitmap*>(setBits & pointerMask);
        }
 
        inline const Bitmap* getConstPtrBitmap() const {
 
            return reinterpret_cast<const Bitmap*>(setBits & pointerMask);
        }
 
        inline uint16_t* getPtrTinyBitmap() const {
 
            return reinterpret_cast<uint16_t*>(setBits & pointerMask);
        }
 
        inline UnitigColors* getPtrUnitigColors() const {
 
            return reinterpret_cast<UnitigColors*>(setBits & pointerMask);
        }
 
        inline const UnitigColors* getConstPtrUnitigColors() const {
 
            return reinterpret_cast<const UnitigColors*>(setBits & pointerMask);
        }
 
        inline SharedUnitigColors* getPtrSharedUnitigColors() const {
 
            return reinterpret_cast<SharedUnitigColors*>(setBits & pointerMask);
        }
 
        inline const SharedUnitigColors* getConstPtrSharedUnitigColors() const {
 
            return reinterpret_cast<const SharedUnitigColors*>(setBits & pointerMask);
        }
 
        static const size_t maxBitVectorIDs; // 64 bits - 3 bits for the color set type = 61
        static const size_t shiftMaskBits; // 3 bits
 
        // asBits and asPointer represent:
        // Flag 0 - A TinyBitmap which can contain up to 65488 uint
        // Flag 1 - A bit vector of 62 bits storing presence/absence of up to 62 integers
        // Flag 2 - A single integer
        // Flag 3 - A pointer to a CRoaring compressed bitmap which can contain up to 2^32 uint
        // Flag 4 - A pointer to an array of 2 UnitigColors:
        //          1 - Contains "full" colors -> color is present on ALL k-mers of the unitig
        //          2 - Contains colors for k-mers if NOT full colors
        // Flag 5 - A pointer to a pair (UnitigColors, size_t) shared by multiple UnitigColors
 
        static const uintptr_t localTinyBitmap; // Flag 0
        static const uintptr_t localBitVector; // Flag 1
        static const uintptr_t localSingleInt; // Flag 2
        static const uintptr_t ptrBitmap; // Flag 3
        static const uintptr_t ptrUnitigColors; // Flag 4
        static const uintptr_t ptrSharedUnitigColors; // Flag 5
 
        static const uintptr_t flagMask; // 0x7 (= 2^shiftMaskBits - 1)
        static const uintptr_t pointerMask; // 0xfffffffffffffff8 (= 2^64 - 1 - flagMask)
 
        uintptr_t setBits;
};
 
struct UnitigColorsHash {
 
    size_t operator()(const UnitigColors& uc) const {
 
        return uc.hash();
    }
};
 
#endif