bit_array.h

Go to the documentation of this file.

// Evo C++ Library
/* Copyright 2019 Justin Crowell
Distributed under the BSD 2-Clause License -- see included file LICENSE.txt for details.
*/

#pragma once
#ifndef INCL_evo_bit_array_h
#define INCL_evo_bit_array_h

#include "bits.h"
#include "impl/iter.h"
#include "impl/str.h"

namespace evo {


template<class TParent>
class BitArraySubsetT {
public:
    typedef BitArraySubsetT<TParent> ThisType;  
    typedef TParent Parent;                     
    typedef typename TParent::Size  Size;       
    typedef typename TParent::Value Value;      

    BitArraySubsetT() : parent_rd_(NULL), parent_wr_(NULL), offset_(0), bitsize_(0) {
    }

    BitArraySubsetT(const Parent& parent) : parent_rd_(&parent), parent_wr_(NULL), offset_(0), bitsize_(parent.bitsize_) {
    }

    BitArraySubsetT(Parent& parent) : parent_rd_(&parent), parent_wr_(&parent), offset_(0), bitsize_(parent.bitsize_) {
    }

    BitArraySubsetT(const Parent& parent, Size pos, Size count=ALL) {
        set(parent, pos, count);
    }

    BitArraySubsetT(Parent& parent, Size pos, Size count=ALL) {
        set(parent, pos, count);
    }

    BitArraySubsetT(const ThisType& src) : parent_rd_(src.parent_rd_), parent_wr_(src.parent_wr_), offset_(src.offset_), bitsize_(src.bitsize_) {
    }

#if defined(EVO_CPP11)

    BitArraySubsetT(ThisType&& src) {
        ::memcpy(this, &src, sizeof(ThisType));
        ::memset(&src, 0, sizeof(ThisType));
    }

    ThisType& operator=(ThisType&& src) {
        ::memcpy(this, &src, sizeof(ThisType));
        ::memset(&src, 0, sizeof(ThisType));
        return *this;
    }
#endif

    // SET

    ThisType& operator=(const ThisType& src) {
        parent_rd_ = src.parent_rd_;
        parent_wr_ = src.parent_wr_;
        offset_ = src.offset_;
        bitsize_ = src.bitsize_;
        return *this;
    }

    ThisType& operator=(const Parent& parent) {
        parent_rd_ = &parent;
        parent_wr_ = NULL;
        offset_  = 0;
        bitsize_ = parent.size();
        return *this;
    }

    ThisType& operator=(Parent& parent) {
        parent_rd_ = parent_wr_ = &parent;
        offset_  = 0;
        bitsize_ = parent.size();
        return *this;
    }

    ThisType& set() {
        parent_rd_ = parent_wr_ = NULL;
        offset_  = 0;
        bitsize_ = 0;
        return *this;
    }

    ThisType& set(const ThisType& src, Size pos=0, Size count=ALL) {
        parent_rd_ = src.parent_rd_;
        parent_wr_ = src.parent_wr_;
        offset_ = src.offset_ + pos;
        if (offset_ > src.bitsize_) {
            offset_ = src.bitsize_;
            bitsize_ = 0;
        } else {
            bitsize_ = src.bitsize_ - offset_;
            if (bitsize_ > count)
                bitsize_ = count;
        }
        return *this;
    }

    ThisType& set(const Parent& parent, Size pos=0, Size count=ALL) {
        parent_rd_ = &parent;
        parent_wr_ = NULL;
        offset_ = pos;
        if (offset_ > parent.bitsize_) {
            offset_ = parent.bitsize_;
            bitsize_ = 0;
        } else {
            bitsize_ = parent.bitsize_ - offset_;
            if (bitsize_ > count)
                bitsize_ = count;
        }
        return *this;
    }

    ThisType& set(Parent& parent, Size pos=0, Size count=ALL) {
        parent_rd_ = parent_wr_ = &parent;
        offset_ = pos;
        if (offset_ > parent.bitsize_) {
            offset_ = parent.bitsize_;
            bitsize_ = 0;
        } else {
            bitsize_ = parent.bitsize_ - offset_;
            if (bitsize_ > count)
                bitsize_ = count;
        }
        return *this;
    }

    // INFO

    bool null() const {
        return (parent_rd_ == NULL);
    }

    bool empty() const {
        return (bitsize_ == 0);
    }

    Size size() const {
        return bitsize_;
    }

    Size offset() const {
        return offset_;
    }

    bool readonly() const {
        return (parent_wr_ == NULL);
    }

    const Parent* parent() const {
        return parent_rd_;
    }

    Parent* parent_nonconst() {
        return parent_wr_;
    }

    // BITS

    bool operator[](Size pos) const {
        return (parent_rd_ != NULL && pos < bitsize_ && Bits<Value,Size>::array_get(parent_rd_->data_, parent_rd_->bitsize_, offset_ + pos));
    }

    Size countbits(bool value=true) const {
        if (parent_rd_ == NULL)
            return 0;
        if (value)
            return Bits<Value,Size>::array_countbits(parent_rd_->data_, parent_rd_->bitsize_, offset_, bitsize_);
        return bitsize_ - Bits<Value,Size>::array_countbits(parent_rd_->data_, parent_rd_->bitsize_, offset_, bitsize_);
    }

    Size checkall() const {
        return (parent_rd_ == NULL || Bits<Value,Size>::array_checkall(parent_rd_->data_, parent_rd_->bitsize_, offset_, bitsize_));
    }

    bool checkany() const {
        return (parent_rd_ != NULL && Bits<Value,Size>::array_checkany(parent_rd_->data_, parent_rd_->bitsize_, offset_, bitsize_));
    }

    bool getbit(Size pos) const {
        return (parent_rd_ != NULL && pos < bitsize_ && Bits<Value,Size>::array_get(parent_rd_->data_, parent_rd_->bitsize_, offset_ + pos));
    }

    bool setbit(Size pos, bool value=true) {
        return (parent_wr_ != NULL && pos < bitsize_ && Bits<Value,Size>::array_set(parent_wr_->data_, parent_wr_->bitsize_, offset_ + pos, value));
    }

    Size setbits(Size pos=0, Size count=ALL, bool value=true) {
        if (parent_wr_ != NULL && pos < bitsize_) {
            const Size maxcount = bitsize_ - pos;
            if (count > maxcount)
                count = maxcount;
            return Bits<Value,Size>::array_set_multi(parent_wr_->data_, parent_wr_->bitsize_, offset_ + pos, count, value);
        }
        return 0;
    }

    bool clearbit(Size pos) {
        return (parent_wr_ != NULL && pos < bitsize_ && Bits<Value,Size>::array_set(parent_wr_->data_, parent_wr_->bitsize_, offset_ + pos, false));
    }

    Size clearbits(Size pos=0, Size count=ALL) const {
        if (parent_wr_ != NULL && pos < bitsize_) {
            const Size maxcount = bitsize_ - pos;
            if (count > maxcount)
                count = maxcount;
            return Bits<Value,Size>::array_set_multi(parent_wr_->data_, parent_wr_->bitsize_, offset_ + pos, count, false);
        }
        return 0;
    }

    bool togglebit(Size pos) {
        return (parent_wr_ != NULL && pos < bitsize_ && Bits<Value,Size>::array_toggle(parent_wr_->data_, parent_wr_->bitsize_, offset_ + pos));
    }

    Size togglebits(Size pos=0, uint count=ALL) {
        if (parent_wr_ != NULL && pos < bitsize_) {
            const Size maxcount = bitsize_ - pos;
            if (count > maxcount)
                count = maxcount;
            return Bits<Value,Size>::array_toggle_multi(parent_wr_->data_, parent_wr_->bitsize_, offset_ + pos, count);
        }
        return 0;
    }

    template<class U>
    bool store(Size pos, Size count, U value) {
        const Size maxcount = bitsize_ - pos;
        if (count > maxcount)
            count = maxcount;
        return (parent_wr_ != NULL && pos < bitsize_ && Bits<Value,Size>::array_store(parent_wr_->data_, parent_wr_->bitsize_, offset_ + pos, count, value));
    }

    template<class U EVO_ONCPP11(=ulong)>
    U extractl(Size pos=0, Size count=ALL) const {
        if (parent_rd_ != NULL && pos < bitsize_) {
            const Size maxcount = bitsize_ - pos;
            if (count > maxcount)
                count = maxcount;
            return Bits<Value,Size>::template array_extractl<U>(parent_rd_->data_, parent_rd_->bitsize_, offset_ + pos, count);
        }
        return 0;
    }

    template<class U EVO_ONCPP11(=ulong)>
    U extractr(Size pos=0, Size count=ALL) const {
        if (parent_rd_ != NULL && pos < bitsize_) {
            const Size maxcount = bitsize_ - pos;
            if (count > maxcount)
                count = maxcount;
            return Bits<Value,Size>::template array_extractr<U>(parent_rd_->data_, parent_rd_->bitsize_, offset_ + pos, count);
        }
        return 0;
    }

    template<class U>
    bool format(U& out, int base=fBIN) {
        if (bitsize_ > 0) {
            assert( parent_rd_ != NULL );
            const char* digits;
            if (base >= 100) {
                base -= 100;
                digits = "0123456789abcdefghijklmnopqrstuvwxyz";
            } else
                digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

            int bits_per_digit;
            switch (base) {
                case 2:  bits_per_digit = 1; break;
                case 4:  bits_per_digit = 2; break;
                case 8:  bits_per_digit = 3; break;
                case 16: bits_per_digit = 4; break;
                case 32: bits_per_digit = 5; break;
                default: return false;
            }

            typename U::Out& outstream = out.write_out();
            typename U::Out::Size available = 0;

            Size outsize = (bitsize_ + bits_per_digit - 1) / bits_per_digit; // round up
            char* outbuf = outstream.write_direct_multi(available, outsize);
            if (outbuf == NULL)
                return false;

            char* outbuf_start = outbuf;
            char* outbuf_end   = outbuf + available;
            char* outbuf_write;
            char* outbuf_next;
            Size outsize_lastwrite = outsize;
            Size digit_count;

            const Value* parent_data    = parent_rd_->data_;    // local copy of data pointer
            const Size   parent_bitsize = offset_ + bitsize_;   // use reduced parent bitsize to exclude ending partial digit bits from extractr()

            // Use extractr() to extract and format bits
            const uint digits_per_ulong = IntegerT<ulong>::BITS / bits_per_digit;
            const uint bits_per_ulong   = digits_per_ulong * bits_per_digit;
            ulong num;
            outbuf_end -= digits_per_ulong;
            for (Size p=offset_; outsize > 0; p += bits_per_ulong) {
                if (outbuf > outbuf_end) {
                    // No room, flush buffer
                    outbuf_start = outbuf = outstream.write_direct_flush(available, (ulong)(outbuf - outbuf_start), outsize);
                    if (outbuf == NULL)
                        return false;
                    outbuf_end = outbuf + available - digits_per_ulong;
                    outsize_lastwrite = outsize;
                }

                if (outsize < digits_per_ulong)
                    digit_count = outsize;
                else
                    digit_count = digits_per_ulong;
                num = Bits<Value,Size>::template array_extractr<ulong>(parent_data, parent_bitsize, p, digit_count * bits_per_digit);

                // Format chunk
                outbuf_next = outbuf_write = outbuf + digit_count;
                for (; num != 0; num /= (Value)base)
                    *--outbuf_write = digits[num % base];
                while (outbuf_write > outbuf)
                    *--outbuf_write = '0';
                outsize -= digit_count;
                outbuf = outbuf_next;
            }

            assert( outsize_lastwrite >= outsize );
            outstream.write_direct_finish(outsize_lastwrite - outsize);
        }
        return true;
    }

    // COMPARE

    bool operator==(const ThisType& data) const {
        bool result;
        if (this == &data)
            result = true;
        else if (parent_rd_ == NULL)
            result = (data.parent_rd_ == NULL);
        else if (data.parent_rd_ == NULL || bitsize_ != data.bitsize_)
            result = false;
        else if (bitsize_ == 0)
            result = true;
        else {
            const Size   this_index   = offset_ / Bits<Value,Size>::BITS;
            const Size   this_offset  = offset_ - (this_index * Bits<Value,Size>::BITS);
            const Value* this_ptr     = parent_rd_->data_ + this_index;
            const Size   other_index  = data.offset_ / Bits<Value,Size>::BITS;
            const Size   other_offset = data.offset_ - (other_index * Bits<Value,Size>::BITS);
            Size count = bitsize_;
            Value maskval;
            if (this_offset == other_offset) {
                // Easier to compare with same offsets
                const Value* other_ptr = data.parent_rd_->data_ + other_index;

                // Leading partial chunk
                if (this_offset > 0) {
                    maskval = Bits<Value,Size>::ALLBITS >> this_offset;
                    if ((*this_ptr & maskval) != (*other_ptr & maskval))
                        return false;
                    count -= (Bits<Value, Size>::BITS - this_offset);
                    ++this_ptr;
                    ++other_ptr;
                }

                // Compare full chunks
                while (count >= Bits<Value, Size>::BITS) {
                    count -= Bits<Value, Size>::BITS;
                    if (*this_ptr != *other_ptr)
                        return false;
                    ++this_ptr;
                    ++other_ptr;
                }

                // Compare trailing partial chunk
                if (count > 0) {
                    maskval = ~(Bits<Value,Size>::ALLBITS >> count);
                    if ((*this_ptr & maskval) != (*other_ptr & maskval))
                        return false;
                }
            } else {
                // Trickier to compare with different offsets, use array_extractl() for other data
                const Value* other_ptr   = data.parent_rd_->data_;
                const Size other_bitsize = data.parent_rd_->bitsize_;
                Size       other_pos     = data.offset_;

                // Leading partial chunk
                if (this_offset > 0) {
                    maskval = Bits<Value,Size>::ALLBITS >> this_offset;
                    if ( (*this_ptr & maskval) != Bits<Value,Size>::template array_extractr<Value>(other_ptr, other_bitsize, other_pos, (Bits<Value,Size>::BITS - this_offset)) )
                        return false;
                    ++this_ptr;
                    const Size bits = Bits<Value, Size>::BITS - this_offset;
                    count -= bits;
                    other_pos += bits;
                }

                // Compare full chunks
                while (count >= Bits<Value, Size>::BITS) {
                    count -= Bits<Value, Size>::BITS;
                    if (*this_ptr != Bits<Value,Size>::template array_extractl<Value>(other_ptr, other_bitsize, other_pos, Bits<Value,Size>::BITS))
                        return false;
                    ++this_ptr;
                    other_pos += Bits<Value, Size>::BITS;
                }

                // Compare trailing partial chunk
                if (count > 0) {
                    maskval = ~(Bits<Value,Size>::ALLBITS >> count);
                    if ((*this_ptr & maskval) != Bits<Value,Size>::template array_extractl<Value>(other_ptr, other_bitsize, other_pos, count))
                        return false;
                }
            }
            result = true;
        }
        return result;
    }

    bool operator!=(const ThisType& data) const {
        return !operator==(data);
    }

private:
    const Parent* parent_rd_;   // reads
    Parent* parent_wr_;         // writes
    Size offset_;
    Size bitsize_;
};


template<class T=ulong,class TSize=SizeT>
class BitArrayT {
public:
    EVO_CONTAINER_TYPE;                         
    typedef BitArrayT<T,TSize> ThisType;        
    typedef BitArraySubsetT<ThisType> Subset;   
    typedef TSize Size;                         
    typedef T     Value;                        

    // Iterator support types
    struct IterKey {
        Size offset;
        typename Bits<T,Size>::IterState state;
    };
    typedef Size IterItem;
    typedef typename IteratorFw<ThisType>::Const Iter;    

    BitArrayT() : data_(NULL), size_(0), bitsize_(0) {
    }

    BitArrayT(Size bitsize) : data_(NULL), size_(0), bitsize_(0) {
        resize(bitsize);
    }

    BitArrayT(const ThisType& src) {
        if (src.size_ > 0) {
            data_ = (Value*)::malloc((size_t)src.size_ * sizeof(Value));
            memcpy(data_, src.data_, src.size_ * sizeof(Value));
        } else
            data_ = src.data_;
        size_    = src.size_;
        bitsize_ = src.bitsize_;
    }

    BitArrayT(const ThisType& src, Size pos, Size count=ALL) : data_(NULL), size_(0), bitsize_(0) {
        if (count > src.bitsize_)
            count = src.bitsize_;
        if (count > 0) {
            resize(count);
            Bits<T,TSize>::array_copy(data_, bitsize_, src.data_, src.bitsize_, pos, count);
        }
    }

    BitArrayT(const Subset& subset, Size pos=0, Size count=ALL) : data_(NULL), size_(0), bitsize_(0) {
        const ThisType* parent = subset.parent();
        if (parent != NULL) {
            const Size subset_bitsize = subset.size();
            if (count > subset_bitsize)
                count = subset_bitsize;
            if (count > 0) {
                resize(count);
                Bits<T,TSize>::array_copy(data_, bitsize_, parent->data_, subset_bitsize, subset.offset() + pos, count);
            }
        }
    }

    ~BitArrayT() {
        if (size_ > 0)
            ::free(data_);
    }

#if defined(EVO_CPP11)

    BitArrayT(std::initializer_list<uint32> init) : BitArrayT() {
        const Size ITEM_BITS = sizeof(uint32) * 8;
        assert( init.size() < IntegerT<Size>::MAX / ITEM_BITS );
        resize((Size)init.size() * ITEM_BITS);
        Size offset = 0;
        for (auto num : init) {
            store(offset, ITEM_BITS, num);
            offset += ITEM_BITS;
        }
    }

    BitArrayT(ThisType&& src) {
        ::memcpy(this, &src, sizeof(ThisType));
        ::memset(&src, 0, sizeof(ThisType));
    }

    ThisType& operator=(ThisType&& src) {
        resize(0);
        ::memcpy(this, &src, sizeof(ThisType));
        ::memset(&src, 0, sizeof(ThisType));
        return *this;
    }
#endif

    const ThisType& asconst() const {
        return *this;
    }

    // SET

    ThisType& operator=(const ThisType& src) {
        return set(src);
    }

    ThisType& clear() {
        if (size_ > 0) {
            ::free(data_);
            data_ = EVO_PEMPTY;
            size_ = 0;
            bitsize_ = 0;
        }
        return *this;
    }

    ThisType& set() {
        if (size_ > 0) {
            ::free(data_);
            size_ = 0;
            bitsize_ = 0;
        }
        data_ = NULL;
        return *this;
    }

    ThisType& set(const ThisType& src) {
        if (this != &src) {
            if (src.size_ > 0) {
                const size_t size_bytes = (size_t)src.size_ * sizeof(Value);
                if (size_ == src.size_) {
                    // Same positive size
                    memcpy(data_, src.data_, size_bytes);
                } else {
                    // New positive size
                    if (size_ > 0)
                        ::free(data_);
                    size_ = src.size_;
                    data_ = (Value*)::malloc(size_bytes);
                    memcpy(data_, src.data_, size_bytes);
                }
                bitsize_ = src.bitsize_;
            } else {
                // Null/Empty
                if (size_ > 0) {
                    ::free(data_);
                    size_ = 0;
                }
                bitsize_ = 0;
                data_ = (src.data_ == NULL ? NULL : EVO_PEMPTY);
            }
        }
        return *this;
    }

    ThisType& set(const Subset& src) {
        const ThisType* src_parent = src.parent();
        if (this == src_parent) {
            Bits<T,Size>::array_shiftl(data_, bitsize_, src.offset());
            resize(src.size());
        } else if (src_parent == NULL) {
            set();
        } else {
            const Size src_size = src.size();
            resize(src_size);
            Bits<T,TSize>::array_copy(data_, bitsize_, src_parent->data_, src_size);
        }
        return *this;
    }

    ThisType& setempty() {
        if (size_ > 0) {
            ::free(data_);
            size_ = 0;
            bitsize_ = 0;
        }
        data_ = EVO_PEMPTY;
        return *this;
    }

    // INFO

    bool null() const {
        return (data_ == NULL);
    }

    bool empty() const {
        return (bitsize_ == 0);
    }

    Size size() const {
        return bitsize_;
    }

    bool shared() const {
        return false;
    }

    const Value* data() const {
        return data_;
    }

    bool operator[](Size pos) const {
        return Bits<T,Size>::array_get(data_, bitsize_, pos);
    }

    ulong hash(ulong seed=0) const {
        return DataHash<T>::hash(data_, size_, seed);
    }

    // BITS

    Iter cbegin() const
        { return Iter(*this); }

    Iter cend() const
        { return Iter(); }

    Iter begin() const
        { return Iter(*this); }

    Iter end() const
        { return Iter(); }

    Size countbits(bool value=true) const {
        if (value)
            return Bits<T,Size>::array_countbits(data_, bitsize_);
        return bitsize_ - Bits<T,Size>::array_countbits(data_, bitsize_);
    }

    bool checkall() const {
        return Bits<T,Size>::array_checkall(data_, bitsize_);
    }

    bool checkany() const {
        return Bits<T,Size>::array_checkany(data_, bitsize_);
    }

    bool getbit(Size pos) const {
        return Bits<T,Size>::array_get(data_, bitsize_, pos);
    }

    bool setbit(Size pos, bool value=true) {
        return Bits<T,Size>::array_set(data_, bitsize_, pos, value);
    }

    Size setbits(Size pos=0, Size count=ALL, bool value=true) {
        return Bits<T,Size>::array_set_multi(data_, bitsize_, pos, count, value);
    }

    bool clearbit(Size pos) {
        return Bits<T,Size>::array_set(data_, bitsize_, pos, false);
    }

    Size clearbits(Size pos=0, Size count=ALL) const {
        return Bits<T,Size>::array_set_multi(data_, bitsize_, pos, count, false);
    }

    bool togglebit(Size pos) {
        return Bits<T,Size>::array_toggle(data_, bitsize_, pos);
    }

    Size togglebits(Size pos=0, uint count=ALL) {
        return Bits<T,Size>::array_toggle_multi(data_, bitsize_, pos, count);
    }

    template<class U>
    bool store(Size pos, Size count, U value) {
        return Bits<T,Size>::array_store(data_, bitsize_, pos, count, value);
    }

    template<class U EVO_ONCPP11(=uint32)>
    U extractl(Size pos=0, Size count=ALL) const {
        return Bits<T,Size>::template array_extractl<U>(data_, bitsize_, pos, count);
    }

    template<class U EVO_ONCPP11(=uint32)>
    U extractr(Size pos=0, Size count=ALL) const {
        return Bits<T,Size>::template array_extractr<U>(data_, bitsize_, pos, count);
    }

    ThisType& shiftl(uint count) {
        Bits<T,Size>::array_shiftl(data_, bitsize_, count);
        return *this;
    }

    ThisType& shiftr(uint count) {
        Bits<T,Size>::array_shiftr(data_, bitsize_, count);
        return *this;
    }

    Size load(const char* str, Size size, int base=2) {
        // Use T or ulong, whichever is larger
        typedef typename StaticIf<(sizeof(T) > sizeof(ulong)), T, ulong>::Type TNum;

        int bits_per_digit;
        switch (base) {
            case 2:  bits_per_digit = 1; break;
            case 4:  bits_per_digit = 2; break;
            case 8:  bits_per_digit = 3; break;
            case 16: bits_per_digit = 4; break;
            case 32: bits_per_digit = 5; break;
            default: return 0;
        }

        uchar ch;
        while (size > 0 && ((ch=str[size-1]) == ' ' || ch == '\t'))
            --size;
        const char* end = str + size;
        while (str < end && ((ch=*str) == ' ' || ch == '\t'))
            ++str;
        if (str >= end)
            return 0;

        size = (Size)(end - str) * bits_per_digit; // size is now in bits
        resize(size);

        uint bits = 0;
        TNum num  = 0;
        T* p = data_;
        for (; str < end; ++str) {
            ch = *str;
            if (ch >= '0' && ch <= '9')
                ch -= '0';
            else if (ch >= 'A' && ch <= 'V')
                ch = ch - 'A' + 10;
            else if (ch >= 'a' && ch <= 'v')
                ch = ch - 'a' + 10;
            else
                return 0; // not a digit
            if (ch >= base)
                return 0;

            bits += bits_per_digit;
            if (bits == Bits<T, Size>::BITS) {
                // No overflow
                *p = T((num * (uint)base) + ch);
                ++p;
                num = 0;
                bits = 0;
            } else if (bits > Bits<T,Size>::BITS) {
                // Protect from overflow from extra bits
                const uint shift = Bits<T,Size>::BITS - (bits - bits_per_digit);
                bits -= Bits<T,Size>::BITS;
                *p = T(num << shift) | (T(ch) >> bits);
                ++p;
                num = T(ch) & ~(Bits<T,Size>::ALLBITS << bits);
            } else {
                num *= (uint)base;
                num += ch;
            }
        }

        if (bits > 0)
            *p = T(num) << (Bits<T,Size>::BITS - bits);
        return size;
    }

    template<class U>
    bool format(U& out, int base=fBIN) {
        if (bitsize_ > 0) {
            const char* digits;
            if (base >= 100) {
                base -= 100;
                digits = "0123456789abcdefghijklmnopqrstuvwxyz";
            } else
                digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

            int bits_per_digit;
            switch (base) {
                case 2:  bits_per_digit = 1; break;
                case 4:  bits_per_digit = 2; break;
                case 8:  bits_per_digit = 3; break;
                case 16: bits_per_digit = 4; break;
                case 32: bits_per_digit = 5; break;
                default: return false;
            }

            typename U::Out& outstream = out.write_out();
            typename U::Out::Size available = 0;

            Size outsize = (bitsize_ + bits_per_digit - 1) / bits_per_digit; // round up
            char* outbuf = outstream.write_direct_multi(available, outsize);
            if (outbuf == NULL)
                return false;

            char* outbuf_start = outbuf;
            char* outbuf_end   = outbuf + available;
            char* outbuf_write;
            char* outbuf_next;
            Size outsize_lastwrite = outsize, digit_count;

            if (Bits<T,Size>::BITS % bits_per_digit != 0) {
                // Use extractr() when bits per digit is not a multiple of bits per chunk
                const uint digits_per_ulong = IntegerT<ulong>::BITS / bits_per_digit;
                const uint bits_per_ulong   = digits_per_ulong * bits_per_digit;
                ulong num;
                outbuf_end -= digits_per_ulong;
                for (Size p=0; outsize > 0; p += bits_per_ulong) {
                    digit_count = (outsize > digits_per_ulong ? digits_per_ulong : outsize);
                    num = Bits<T,Size>::template array_extractr<ulong>(data_, bitsize_, p, digit_count * bits_per_digit);
                    if (outbuf >= outbuf_end) {
                        // No room, flush buffer
                        outbuf_start = outbuf = outstream.write_direct_flush(available, (ulong)(outbuf - outbuf_start), outsize);
                        if (outbuf == NULL)
                            return false;
                        outbuf_end = outbuf + available - digits_per_ulong;
                        outsize_lastwrite = outsize;
                    }

                    // Format chunk
                    outbuf_next = outbuf_write = outbuf + digit_count;
                    for (; num != 0; num /= (T)base)
                        *--outbuf_write = digits[num % base];
                    while (outbuf_write > outbuf)
                        *--outbuf_write = '0';
                    outsize -= digit_count;
                    outbuf = outbuf_next;
                }
            } else {
                // Easier when bits per digit is a multiple of bits per chunk
                const uint digits_per_chunk = Bits<T,Size>::BITS / bits_per_digit;
                const T* p = data_;
                const T* p_end_rndup = data_ + ((bitsize_ + Bits<T,Size>::BITS - 1) / Bits<T,Size>::BITS);  // includes partial chunk at end
                const T* p_end       = data_ + (bitsize_ / Bits<T,Size>::BITS);                             // not including partial chunk at end
                T num;

                while (outsize > 0) {
                    if (outsize < digits_per_chunk)
                        digit_count = outsize;
                    else
                        digit_count = digits_per_chunk;

                    outbuf_next = outbuf + digit_count;
                    if (outbuf_next > outbuf_end && outbuf > outbuf_start) {
                        // No room, flush buffer
                        outbuf_start = outbuf = outstream.write_direct_flush(available, (ulong)(outbuf - outbuf_start), outsize);
                        if (outbuf == NULL)
                            return false;
                        outbuf_end  = outbuf + available;
                        outbuf_next = outbuf + digit_count;
                        outsize_lastwrite = outsize;
                    }

                    // Format chunk
                    outbuf_write = outbuf_next;
                    if (p < p_end_rndup) {
                        num = *p;
                        if (p == p_end)
                            num >>= Bits<T,Size>::BITS - (outsize * bits_per_digit);
                        for (; num != 0; num /= (T)base)
                            *--outbuf_write = digits[num % base];
                        ++p;
                    }
                    while (outbuf_write > outbuf)
                        *--outbuf_write = '0';
                    assert( outbuf_next > outbuf );
                    outsize -= digit_count;
                    outbuf = outbuf_next;
                }
            }

            assert( outsize_lastwrite >= outsize );
            outstream.write_direct_finish(outsize_lastwrite - outsize);
        }
        return true;
    }

    // COMPARE

    bool operator==(const ThisType& data) const {
        bool result;
        if (this == &data)
            result = true;
        else if (data_ == NULL)
            result = (data.data_ == NULL);
        else if (data.data_ == NULL || size_ != data.size_)
            result = false;
        else
            result = DataEqual<T>::equal(data_, data.data_, data.size_);
        return result;
    }

    bool operator!=(const ThisType& data) const {
        bool result;
        if (this == &data)
            result = false;
        else if (data_ == NULL)
            result = (data.data_ != NULL);
        else if (data.data_ == NULL || size_ != data.size_)
            result = true;
        else
            result = !DataEqual<T>::equal(data_, data.data_, data.size_);
        return result;
    }

    ThisType& unshare() {
        return *this;
    }

    ThisType& resize(Size bitsize) {
        Size size = Bits<T,Size>::array_size(bitsize);
        if (size == 0) {
            // Null/Empty
            if (size_ > 0) {
                ::free(data_);
                data_ = EVO_PEMPTY;
                size_ = 0;
                bitsize_ = 0;
            }
        } else if (size_ != size) {
            // New positive size
            assert( size > 0 );
            const size_t size_bytes = (size_t)size * sizeof(Value);
            if (size_ > 0) {
                // Preserve existing items
                Value* const old_data = data_;
                data_ = (Value*)::malloc(size_bytes);

                const size_t save_size_bytes = (size_ < size ? size_ : size) * sizeof(Value);
                memcpy(data_, old_data, save_size_bytes);
                if (size_bytes > save_size_bytes)
                    memset((char*)data_ + save_size_bytes, 0, size_bytes - save_size_bytes);

                size_ = size;
                ::free(old_data);
            } else {
                // New array
                data_ = (T*)::malloc(size_bytes);
                memset(data_, 0, size_bytes);
            }
            size_ = size;
            bitsize_ = bitsize;
        } else {
            // Same array size
            if (bitsize < bitsize_) {
                // Clear removed bits
                const T mask = (Bits<T,Size>::RBIT << (bitsize_ - bitsize)) - 1;
                data_[size_ - 1] &= ~mask;
            }
            bitsize_ = bitsize;
        }
        return *this;
    }

    ThisType& resize_pow2(Size bitsize) {
        if (bitsize > 0)
            bitsize = size_pow2(bitsize);
        resize(bitsize);
        return *this;
    }

    // INTERNAL

    // Iterator support methods
    void iterInitMutable() { }
    const IterItem* iterFirst(IterKey& key) const {
        const IterItem* result;
        if (bitsize_ > 0) {
            key.offset = Bits<T,Size>::array_iter(key.state, data_, bitsize_);
            if (key.offset == NONE)
                result = NULL;
            else
                result = (const IterItem*)&key.offset;
        } else {
            key.offset = END;
            result = NULL;
        }
        return result;
    }
    const IterItem* iterNext(IterKey& key) const {
        const IterItem* result = NULL;
        if (key.offset != END) {
            key.offset = Bits<T,Size>::array_iternext(key.state);
            if (key.offset == NONE)
                result = NULL;
            else
                result = (const IterItem*)&key.offset;
        }
        return result;
    }
private:
    T*   data_;
    Size size_;
    Size bitsize_;

    template<class> friend class BitArraySubsetT;
};


template<class T>
inline bool operator==(const BitArraySubsetT< BitArrayT<T> >& a, const BitArrayT<T>& b) {
    return (a == BitArraySubsetT< BitArrayT<T> >(b));
}

template<class T>
inline bool operator!=(const BitArraySubsetT< BitArrayT<T> >& a, const BitArrayT<T>& b) {
    return !(a == BitArraySubsetT< BitArrayT<T> >(b));
}


typedef BitArrayT<> BitArray;                       
typedef BitArraySubsetT<BitArray> BitArraySubset;   


}
#endif