BoolBuffer.hpp

/*--------------------------------------------------------------------------------------------
Copyright (c) 2019, NDEVR LLC
tyler.parke@ndevr.org
  __    __   ____     _____ __     __  _______
 |  \  |  | |  __ \  |  ___|\ \   / / |   __  \
 |   \ |  | | |  \ \ | |___  \ \ / /  |  |__)  |
 |  . \|  | | |__/ / | |___   \ V /   |   _   /
 |  |\    |_|_____/__|_____|___\_/____|  | \  \
 |__| \__________________________________|  \__\
 
Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants 
Licensee a limited, non-exclusive, non-transferable, royalty-free license 
(without the right to sublicense) to use the API solely for the purpose of 
Licensee's internal development efforts to develop applications for which 
the API was provided.
 
The above copyright notice and this permission notice shall be included in all 
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
 
Library: Base
File: BoolBuffer
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/ObjectAllocator.h>
#include <NDEVR/BitReference.h>
#include <NDEVR/BitIterator.h>
namespace NDEVR
{
    #define bitset_wrd(pos) ((pos) >> 3)
    #define bitset_idx(pos) ((pos) & 7)
    #define bitmaskt(nbits,type) ((nbits) ? ~(type)0 >> (sizeof(type)*8-(nbits)): (type)0)
    #define bitmask(nbits) cast<uint01>(bitmaskt(nbits,uint32_t))

    template<class t_index_type>
    class BufferAllocator<bool, 0, true, t_index_type, false>
    {
    public:
        typedef ObjectAllocator<bool, true, t_index_type> allocator;
        using index_type = t_index_type;
 
        explicit BufferAllocator()
            : m_buffer(nullptr)
            , m_filled_size(0)
            , m_allocated_size(0)
        {}
 
        BufferAllocator(BufferAllocator&& allocator) noexcept
            : m_buffer(nullptr)
            , m_filled_size(0)
            , m_allocated_size(0)
        {
            std::swap(allocator.m_buffer, m_buffer);
            std::swap(allocator.m_filled_size, m_filled_size);
            std::swap(allocator.m_allocated_size, m_allocated_size);
        }
        ~BufferAllocator()
        {
            if (m_allocated_size != 0)
                free(m_buffer);
        }
        template<bool t_managed>
        void createSpace(t_index_type size)
        {
            m_filled_size += size;
            allocationSizeCheck<t_managed>();
        }
        template<bool t_managed>
        void createSpace(t_index_type location, t_index_type size)
        {
            createSpace<t_managed>(size);
            bitmove(begin() + location + size, begin() + location, m_filled_size - (size + location));
        }
        void addLast()
        {
            createSpace<false>(1);
        }
        void removeLast()
        {
            m_filled_size--;
        }
        void addIndex()
        {
            createSpace<false>(1);
        }
        void addIndex(t_index_type location)
        {
            lib_assert(location <= m_filled_size, "Out of bounds add all");
            createSpace<false>(1);
            bitmove(begin() + location + 1, begin() + location, (m_filled_size - location - 1));
        }
        void removeIndex(t_index_type location)
        {
            lib_assert(location <= m_filled_size, "Out of bounds add all");
            bitmove(begin() + location, begin() + location + 1, (m_filled_size - location));
            m_filled_size--;
        }
        sint04 compare(const BufferAllocator& allocator) const
        {
            t_index_type min_size = bitset_wrd(getMin(allocator.filledSize(), filledSize()));
            sint04 cmp_value = cast<sint04>(memcmp(m_buffer, allocator.m_buffer, min_size));
            return cmp_value;
        }
        sint04 compare(const BufferAllocator& allocator, t_index_type start, t_index_type end) const
        {
            sint04 cmp_value = memcmp(&(m_buffer[start]), &(allocator.m_buffer[start]), getMin(allocator.filledSize(), filledSize(), end));
            return cmp_value;
        }
        void swap(t_index_type index_a, t_index_type index_b)
        {
            std::swap(m_buffer[index_a], m_buffer[index_b]);
        }
        void clear()
        {
            m_filled_size = 0;
        }
        void setSize(t_index_type size)
        {
            m_filled_size = size;
            allocationSizeCheck<false>();
        }
        BitReference get(t_index_type index)
        {
            lib_assert(index < m_filled_size, "Array out of bounds");
            return BitReference(m_buffer[bitset_wrd(index)], bitset_idx(index));
        }
        bool get(t_index_type index) const
        {
            lib_assert(index < m_filled_size, "Array out of bounds");
            return m_buffer[bitset_wrd(index)][bitset_idx(index)];
        }
        BitIterator begin()
        {
            return BitIterator(m_buffer, 0);
        }
        const ConstBitIterator begin() const
        {
            return ConstBitIterator(m_buffer, 0);
        }
        BitIterator begin(t_index_type index) const
        {
            return BitIterator(m_buffer, cast<sint04>(index));
        }
 
        t_index_type capacity() const
        {
            return m_allocated_size;
        }
        BitIterator end()
        {
            return BitIterator(m_buffer, m_filled_size);
        }
        ConstBitIterator end() const
        {
            return ConstBitIterator(m_buffer, m_filled_size);
        }
        BitIterator end(t_index_type index)
        {
            return BitIterator(m_buffer, m_filled_size - index);
        }
 
        BitFlag* ptr()
        {
            return m_buffer;
        }
 
        const BitFlag* ptr() const
        {
            return m_buffer;
        }
        t_index_type memSize() const
        {
            if (m_filled_size == 0)
                return 0;
            return bitset_wrd(m_filled_size - 1) + 1;
        }
        void setAll(const bool& object, t_index_type offset, t_index_type size)
        {
            if (size == 0) 
                return;
 
            t_index_type first_word = bitset_wrd(offset);
            t_index_type last_word = bitset_wrd(offset + size - 1);
            t_index_type foffset = bitset_idx(offset);
            t_index_type loffset = bitset_idx(offset + size - 1);
 
            if (first_word == last_word)
            {
                uint01 mask = bitmask(size) << foffset;
                if(object)
                    m_buffer[first_word] |= BitFlag(mask);
                else
                    m_buffer[first_word] &= BitFlag(~mask);
            }
            else
            {
                // Set first word
                if (object)
                    m_buffer[first_word] |= BitFlag(~bitmask(foffset));
                else
                    m_buffer[first_word] &= BitFlag(bitmask(foffset));
                memset(m_buffer + first_word + 1, object ? 0xFF : 0, last_word - (first_word + 1));
                
                if (object)
                    m_buffer[last_word] |= BitFlag(bitmask(loffset + 1));
                else
                    m_buffer[last_word] &= BitFlag(~bitmask(loffset + 1));
            }
#ifdef _DEBUG
            for (uint04 i = 0; i < size; i++)
                lib_assert(get(i + offset) == object, "Bad optimized set");
#endif
        }
        template<bool is_primitive>
        void setAll(const bool* src, t_index_type offset, t_index_type size)
        {
            for (t_index_type i = 0; i < size; i++)
            {
                get(i + offset) = src[i];
            }
        }
 
        template<bool is_primitive>
        void setAll(const BufferAllocator& allocator, t_index_type offset, t_index_type other_offset, t_index_type size)
        {
            if(bitset_idx(offset) == 0 && bitset_idx(other_offset) == 0)//if we are memory aligned
            {
                t_index_type new_size = bitset_wrd(size);
                t_index_type new_offset = bitset_wrd(offset);
                t_index_type new_other_offset = bitset_wrd(other_offset);
                memmove(m_buffer + new_offset, allocator.m_buffer + new_other_offset, new_size);
                for (t_index_type i = 8 * new_size; i < size; i++)
                {
                    get(i + offset) = allocator.get(i + other_offset);
                }
            }
            for (t_index_type i = 0; i < size; i++)
            {
                get(i + offset) = allocator.get(i + other_offset);
            }
        }
        template<class t_other_allocator>
        void setAllFromSource(const t_other_allocator& allocator, t_index_type offset, t_index_type other_offset, t_index_type size)
        {
            for (t_index_type i = 0; i < size; i++)
                get(i + offset) = allocator.get(i + other_offset);
        }
        template<bool is_primitive>
        void setAll(ConstBitIterator iterator, uint04 offset, uint04 size)
        {
            BitReference ref = get(offset);
            for (t_index_type i = 0; i < size; i++)
            {
                get(i + offset) = iterator;
                iterator++;
            }
        }
        template<bool t_managed>
        inline void allocationSizeCheck()
        {
            if ((t_managed && m_filled_size > m_allocated_size) || m_filled_size == m_allocated_size + 1)//We only 1, assume more to come shortly and allocate more space than required
            {
                lib_assert(cast<uint08>((t_managed ? m_filled_size : m_allocated_size) * 3) / 2 < cast<uint08>(Constant<uint04>::Max), "Buffer overflow");
                resizeSpace(cast<t_index_type>(cast<uint08>((t_managed ? m_filled_size : m_allocated_size) * 3) / 2) + 1);
            }
            else if (m_filled_size > m_allocated_size) //We added more than 1, increase buffer only once for compaction
            {
                resizeSpace(m_filled_size);
            }
        }
        void removeAllIndex(t_index_type start, t_index_type end)
        {
            if (end == m_filled_size)
            {
                m_filled_size = start;
            }
            else
            {
                bitmove(begin() + start, begin() + end, (m_filled_size - end));
                m_filled_size -= (end - start);
            }
        }
 
        t_index_type filledSize() const
        {
            return m_filled_size;
        }
        t_index_type count(const bool& value) const
        {
            uint04 count = 0;
            for (uint04 i = 0; i < m_filled_size; i++)
            {
                if (get(i) == value)
                    ++count;
            }
            return count;
            //return value ? numSet() : filledSize() - numSet();
        }
        template<class t_comparable_type>
        bool contains(const t_comparable_type& value, t_index_type start, t_index_type size) const
        {
            bool bool_val = value;
            t_index_type end = start + size;
            // First partial byte (unaligned prefix)
            t_index_type byte_start = (start + 7) & ~7;
            for (t_index_type i = start; i < byte_start && i < end; ++i)
            {
                if (get(i) == bool_val)
                    return true;
            }
 
            // Last partial byte (unaligned suffix)
            t_index_type byte_end = end & ~7;
            for (t_index_type i = byte_end; i < end; ++i)
            {
                if (get(i) == bool_val)
                    return true;
            }
            // Full byte-aligned segment
            t_index_type byte_begin = byte_start / 8;
            t_index_type byte_finish = byte_end / 8;
            constexpr BitFlag off(false);
            constexpr BitFlag on(true);
            if (bool_val)
            {
                for (t_index_type i = byte_begin; i < byte_finish; ++i)
                {
                    if (m_buffer[i] != off)
                        return true;
                }
            }
            else
            {
                for (t_index_type i = byte_begin; i < byte_finish; ++i)
                {
                    if (m_buffer[i] != on)
                        return true;
                }
            }
            return false;
        }
        inline BufferAllocator& operator=(BufferAllocator&& value) noexcept
        {
            std::swap(value.m_buffer, m_buffer);
            std::swap(value.m_filled_size, m_filled_size);
            std::swap(value.m_allocated_size, m_allocated_size);
            return *this;
        }
    
        inline void resizeSpace(t_index_type new_size)
        {
            t_index_type byte_size = new_size == 0 ? 0 : bitset_wrd(new_size - 1) + 1;
            if (new_size == 0)
            {
                if (m_allocated_size != 0)
                    free(m_buffer);
                m_buffer = nullptr;
            }
            else
            {
                if (m_allocated_size == 0)
                    m_buffer = cast<BitFlag*>(malloc(byte_size));
                else
                    m_buffer = cast<BitFlag*>(realloc(m_buffer, byte_size));
                lib_assert(m_buffer != nullptr, "Unable to allocate buffer");
            }
            m_allocated_size = 8 * byte_size;
        }
            
    public:
        t_index_type numSet() const
        {
            static const t_index_type BitsSetTable256[256] =
            {
                #   define NDV_B2(n) n,     n+1,     n+1,     n+2
                #   define NDV_B4(n) NDV_B2(n), NDV_B2(n+1), NDV_B2(n+1), NDV_B2(n+2)
                #   define NDV_B6(n) NDV_B4(n), NDV_B4(n+1), NDV_B4(n+1), NDV_B4(n+2)
                NDV_B6(0), NDV_B6(1), NDV_B6(1), NDV_B6(2)
            };
            t_index_type flag_size = bitset_wrd(filledSize());
            t_index_type num_set = 0;
            uint01* mask = new uint01(1 << (filledSize() + 1)) - 1;
            flag_size = flag_size ^ ((flag_size ^ filledSize()) & *mask);
            BitFlag k(~*mask);
            for (t_index_type i = 0; i < flag_size; i++)
            {
                num_set += BitsSetTable256[m_buffer[i]];
            }
            const uint01 size_mod_8 = bitset_idx(filledSize());
            if (size_mod_8 != 0)
            {
                for (t_index_type i = 0; i < size_mod_8; i++)
                {
                    num_set += m_buffer[flag_size][i] ? 1 : 0;
                }
            }
            return num_set;
        }
        
    protected:
        static void bitmove(BitIterator dst, BitIterator src, t_index_type size)
        {
            if (dst == src)
            {
                return;
            }
            if (dst < src)//prevent overlap
            {
                for (t_index_type i = 0; i < size; i++)
                {
                    *dst = *src;
                    ++dst;
                    ++src;
                }
            }
            else
            {
                for (t_index_type i = size - 1; IsValid(i); i--)
                {
                    *(dst + i) = *(src + i);
                }
            }
        }
        void setFlag(const t_index_type index, const bool value)
        {
            m_buffer[bitset_wrd(index)](index & 7, value);
        }
 
    public:
        void invert()
        {
            const t_index_type byte_size = memSize();
            for (t_index_type i = 0; i < byte_size; i++)
            {
                m_buffer[i] = ~m_buffer[i];
            }
        }
        void inverseAndEquals(const BufferAllocator<bool, 0, true, t_index_type>& buffer)
        {
            lib_assert(memSize() == buffer.memSize(), "Cannot ^= two buffers of different length");
            const t_index_type byte_size = memSize();
            for (t_index_type i = 0; i < byte_size; i++)
                m_buffer[i] &= (~buffer.m_buffer[i]);
        }
        void operator^=(const BufferAllocator<bool, 0, true, t_index_type>& buffer)
        {
            lib_assert(memSize() == buffer.memSize(), "Cannot ^= two buffers of different length");
            const t_index_type byte_size = memSize();
            for (t_index_type i = 0; i < byte_size; i++)
                m_buffer[i] ^= buffer.m_buffer[i];
        }
        void operator|=(const BufferAllocator<bool, 0, true, t_index_type>& buffer)
        {
            lib_assert(memSize() == buffer.memSize(), "Cannot |= two buffers of different length");
            const t_index_type byte_size = memSize();
            for (t_index_type i = 0; i < byte_size; i++)
                m_buffer[i] |= buffer.m_buffer[i];
        }
        void operator&=(const BufferAllocator<bool, 0, true, t_index_type>& buffer)
        {
            lib_assert(memSize() == buffer.memSize(), "Cannot &= two buffers of different length");
            const t_index_type byte_size = memSize();
            for (t_index_type i = 0; i < byte_size; i++)
                m_buffer[i] &= buffer.m_buffer[i];
        }
    protected:
        BitFlag* m_buffer;
        t_index_type  m_filled_size;
        t_index_type  m_allocated_size;
    };
#undef bitset_wrd
#undef bitset_idx
#undef bitmaskt
#undef bitmask
}