BitMask.h

/*
 * ░▒▓ APPARATUS ▓▒░
 * 
 * File: BitMask.h
 * Created: Friday, 23rd October 2020 7:00:48 pm
 * Author: Vladislav Dmitrievich Turbanov (vladislav@turbanov.ru)
 * ───────────────────────────────────────────────────────────────────
 * Last Modified: Friday, 26th March 2021 3:32:07 pm
 * Modified By: Vladislav Dmitrievich Turbanov (vladislav@turbanov.ru)
 * ───────────────────────────────────────────────────────────────────
 * 
 * The Apparatus source code is for your internal usage only.
 * Redistribution of this file is strictly prohibited.
 * 
 * Community forums: https://talk.turbanov.ru
 * 
 * Copyright 2020 - 2021, SP Vladislav Dmitrievich Turbanov
 * Made in Russia, Moscow City, Chekhov City
 */
 
#pragma once
 
#include <algorithm>
#include <limits>
#include <ostream>
#include <typeinfo>
#include <vector>
 
#include "CoreMinimal.h"
 
#include "BitMask.generated.h"
 
USTRUCT(BlueprintType)
struct APPARATUSRUNTIME_API FBitMask
{
    GENERATED_BODY()
 
  private:
    typedef uint64 GroupType;
 
    static const int32 GroupSizeBits = sizeof(GroupType) * 8;
 
    static const int32 GroupShift = 6;
 
    static const int32 GroupBitIndexMask = GroupSizeBits - 1;
 
    static const FBitMask Zero;
 
    UPROPERTY(VisibleAnywhere, BlueprintReadOnly, Category = "Bit Mask",
              Meta = (AllowPrivateAccess = "true"))
    int32 Count = 0;
 
    UPROPERTY(VisibleAnywhere, Category = "Bit Mask",
              Meta = (AllowPrivateAccess = "true"))
    TArray<uint64> BitGroups;
 
    FORCEINLINE GroupType GetBitGroup(int32 index) const
    {
        checkf(index >= 0, TEXT("An index can't be negative: %d"), index);
        if (index >= BitGroups.Num())
            return 0;
        return BitGroups[index];
    }
 
    friend class StaticConstructor;
 
    struct StaticConstructor
    {
        FORCEINLINE StaticConstructor()
        {
            for (size_t i = 0; i < bitsCountLUTSize; ++i)
            {
                int32 c = 0;
                for (int32 j = 0; j < 8; ++j)
                {
                    if (((i >> j) & 1) != 0)
                        ++c;
                }
                bitsCountLUT[i] = c;
            }
        }
    };
 
    static StaticConstructor staticConstructor;
 
    static const int32 bitsCountLUTSize = 256;
 
    static int32 bitsCountLUT[bitsCountLUTSize];
 
    FORCEINLINE static int32 GetOneBitsCount(GroupType bg)
    {
        return bitsCountLUT[0xff & bg] + bitsCountLUT[0xff & (bg >> 8)] +
               bitsCountLUT[0xff & (bg >> 16)] +
               bitsCountLUT[0xff & (bg >> 24)] +
               bitsCountLUT[0xff & (bg >> 32)] +
               bitsCountLUT[0xff & (bg >> 40)] +
               bitsCountLUT[0xff & (bg >> 48)] +
               bitsCountLUT[0xff & (bg >> 56)];
    }
 
    FORCEINLINE bool FastAt(const int32 Index) const {
        checkf(Index >= 0, TEXT("An index must be non-negative: %d"),
                Index);
 
        checkf(Index < Count, 
            TEXT("FastAt can work only with indexes less than Count: %d >= %d"), Index, Count);
 
        const GroupType bg = BitGroups[Index >> GroupShift];
        return (bg & (((GroupType)1) << (Index & GroupBitIndexMask))) !=
               (GroupType)0;
    }
 
    friend uint32 GetTypeHash(const FBitMask &bm);
 
  public:
    FORCEINLINE int32 Num() const { return Count; }
 
    FORCEINLINE int32 GetCount() const { return Count; }
 
    FORCEINLINE FBitMask() {}
 
    FORCEINLINE FBitMask(const int32 Capacity) { EnsureBitGroups(Capacity); }
 
    FORCEINLINE bool operator[](const int32 Index) const { return At(Index); }
 
    FORCEINLINE bool At(const int32 Index) const
    {
        checkf(Index >= 0, TEXT("An index must be non-negative: %d"),
                Index);
 
        if (Index >= Count)
            return false;
 
        return FastAt(Index);
    }
 
    FORCEINLINE void Set(const int32 Index, const bool value)
    {
        checkf(Index >= 0, TEXT("An index must be non-negative: %d"),
                Index);
 
        auto gi = Index >> GroupShift;
 
        if (value)
        {
            if (Index >= Count)
            {
                EnsureBitGroups(Index);
                Count = Index + 1;
            }
            BitGroups[gi] |= (((GroupType)1) << (Index & GroupBitIndexMask));
        }
        else
        {
            if (gi < BitGroups.Num())
                BitGroups[gi] &=
                    ~(((GroupType)1) << (Index & GroupBitIndexMask));
        }
    }
 
    FORCEINLINE void Set(const FBitMask &BitMask)
    {
        BitGroups = BitMask.BitGroups;
        Count = BitMask.Count;
    }
 
    FORCEINLINE FBitMask &operator=(const FBitMask &BitMask)
    {
        Set(BitMask);
        return *this;
    }
 
    int32 DifferencesCount(const FBitMask &BitMask) const;
 
    int32 InclusionsCount(const FBitMask &BitMask) const;
 
    FORCEINLINE bool Includes(const FBitMask &BitMask) const
    {
        for (int32 gi = 0; gi < BitMask.BitGroups.Num(); ++gi)
        {
            const GroupType bitGroup      = GetBitGroup(gi);
            const GroupType otherBitGroup = BitMask.BitGroups[gi];
 
            const GroupType masked = otherBitGroup & bitGroup;
            if (masked != otherBitGroup)
                return false;
        }
        return true;
    }
 
    bool IncludesPartially(const FBitMask &BitMask) const
    {
        int32 Size = FMath::Min(BitGroups.Num(), BitMask.BitGroups.Num());
        if (Size == 0) return false;
        for (int32 gi = 0; gi < Size; ++gi)
        {
            const GroupType bitGroup      = BitGroups[gi];
            const GroupType otherBitGroup = BitMask.BitGroups[gi];
 
            const GroupType masked = otherBitGroup & bitGroup;
            if (masked != (GroupType)0)
                return true;
        }
        return false;
    }
 
    bool Contains(const bool bit) const;
 
    struct Iterator
    {
        int32 index = -1;
 
        const FBitMask &owner;
 
        FORCEINLINE Iterator(const FBitMask &o, int32 i = 0) : owner(o)
        {
            this->index = i;
        }
 
      public:
        FORCEINLINE bool operator*() const { return owner.At(index); }
 
        FORCEINLINE bool next() { return (++index) < owner.Count; }
 
        FORCEINLINE bool operator==(const Iterator &i) const
        {
            return &owner == &i.owner && index == i.index;
        }
 
        FORCEINLINE bool operator!=(const Iterator &i) const
        {
            return &owner != &i.owner || index != i.index;
        }
    };
 
    friend Iterator;
 
    FORCEINLINE Iterator begin() { return Iterator(*this); }
 
    FORCEINLINE Iterator end() { return Iterator(*this, Count); }
 
    int32 IndexOf(const bool bit) const;
 
    FORCEINLINE void EnsureBitGroupsCount(int32 Groups)
    {
        BitGroups.Reserve(Groups);
 
        while (BitGroups.Num() < Groups)
            BitGroups.Add(0);
    }
 
    FORCEINLINE void EnsureBitGroups(const int32 index)
    {
        auto gi = index >> GroupShift;
        EnsureBitGroupsCount(gi + 1);
    }
 
    friend std::ostream &operator<<(std::ostream &Str, const FBitMask &v);
    friend bool operator==(const FBitMask &a, const FBitMask &b);
    friend bool operator!=(const FBitMask &a, const FBitMask &b);
 
    FORCEINLINE int32 Max() const { return BitGroups.Max() << GroupShift; }
 
    FORCEINLINE void Reserve(const int32 Capacity)
    {
        BitGroups.Reserve(Capacity >> GroupShift);
    }
 
    void Add(const bool Bit);
 
    FORCEINLINE void Empty(const int32 Slack = 0)
    {
        checkf(Slack >= 0, TEXT("A Slack must be non-negative: %d"), Slack);
        if (Count == 0)
            return;
        BitGroups.Empty(Slack >> GroupShift);
        Count = 0;
    }
 
    FORCEINLINE void Reset(const int32 NewSize = 0)
    {
        checkf(NewSize >= 0, TEXT("A NewSize must be non-negative: %d"), NewSize);
        if (Count == 0)
            return;
        BitGroups.Reset(NewSize >> GroupShift);
        Count = 0;
    }
 
    FORCEINLINE void CopyTo(bool *Array, int32 ArrayIndex) const
    {
        for (int32 i = 0; i < Count; ++i)
        {
            Array[ArrayIndex + i] = FastAt(i);
        }
    }
 
    void Insert(const int32 Index, const bool Bit);
 
    void Remove(const bool Bit);
 
    void RemoveAt(const int32 Index);
 
    FORCEINLINE void Erase(const int32 Index)
    {
        checkf(Index >= 0 && Index < Count,
                TEXT("An index is out of range: %d"), Index);
 
        if (Index == --Count)
        {
            this->Set(Index, false);
        }
        else
        {
            for (auto s = Index; s < Count; ++s)
            {
                this->Set(s, this->At(s + 1));
            }
        }
    }
 
    FORCEINLINE void CopyTo(TArray<bool> &array, const int32 index = 0)
    {
        for (int32 i = 0; i < Count; ++i)
        {
            array[index + i] = this->FastAt(i);
        }
    }
 
    FORCEINLINE FBitMask &AndWith(const FBitMask &mask)
    {
        int32 Size = FMath::Min(BitGroups.Num(), mask.BitGroups.Num());
        EnsureBitGroupsCount(Size);
 
        for (int32 i = 0; i < Size; ++i)
        {
            BitGroups[i] &= mask.BitGroups[i];
        }
 
        this->Count = FMath::Min(this->Count, mask.Count);
 
        return *this;
    }
 
    FORCEINLINE FBitMask &OrWith(const FBitMask &mask)
    {
        int32 Size = FMath::Max(BitGroups.Num(), mask.BitGroups.Num());
        EnsureBitGroupsCount(Size);
 
        for (int32 i = 0; i < mask.BitGroups.Num(); ++i)
        {
            BitGroups[i] |= mask.BitGroups[i];
        }
 
        this->Count = FMath::Max(this->Count, mask.Count);
 
        return *this;
    }
 
    FORCEINLINE FString ToString() const
    {
        FString str;
        for (int32 i = 0; i < Count; ++i)
        {
            auto b = FastAt(i);
            str += b ? TEXT("1") : TEXT("0");
        }
        return str;
    }
 
    friend FBitMask operator&(const FBitMask &a, const FBitMask &b);
    friend FBitMask operator|(const FBitMask &a, const FBitMask &b);
}; // struct FBitMask
 
FORCEINLINE bool operator==(const FBitMask &a, const FBitMask &b)
{
    if (std::addressof(a) == std::addressof(b))
        return true;
 
    const auto count = FMath::Max(a.BitGroups.Num(), b.BitGroups.Num());
    for (int32 gi = 0; gi < count; ++gi)
    {
        if (a.GetBitGroup(gi) != b.GetBitGroup(gi))
            return false;
    }
    return true;
}
 
FORCEINLINE bool operator!=(const FBitMask &a, const FBitMask &b)
{
    if (std::addressof(a) == std::addressof(b))
        return false;
 
    const auto count = FMath::Max(a.BitGroups.Num(), b.BitGroups.Num());
    for (int32 gi = 0; gi < count; ++gi)
    {
        if (a.GetBitGroup(gi) != b.GetBitGroup(gi))
            return true;
    }
    return false;
}
 
FORCEINLINE FBitMask operator&(const FBitMask &a, const FBitMask &b)
{
    auto count = FMath::Min(a.BitGroups.Num(), b.BitGroups.Num());
    auto r = FBitMask();
    r.EnsureBitGroupsCount(count);
    for (int32 i = 0; i < count; ++i)
    {
        r.BitGroups[i] = a.BitGroups[i] & b.BitGroups[i];
    }
    r.Count = FMath::Min(a.Count, b.Count);
    return r;
}
 
FORCEINLINE FBitMask operator|(const FBitMask &a, const FBitMask &b)
{
    auto count = FMath::Max(a.BitGroups.Num(), b.BitGroups.Num());
    auto r = FBitMask();
    r.EnsureBitGroupsCount(count);
    for (int32 i = 0; i < count; ++i)
    {
        r.BitGroups[i] = a.GetBitGroup(i) | b.GetBitGroup(i);
    }
    r.Count = FMath::Max(a.Count, b.Count);
    return r;
}
 
FORCEINLINE uint32 GetTypeHash(const FBitMask &bm)
{
    auto hashCode = 1799407316;
    hashCode = hashCode * -1521134295 + bm.Count;
    for (auto bg : bm.BitGroups)
    {
        hashCode = hashCode * -1521134295 + (int32)(bg >> 32);
        hashCode = hashCode * -1521134295 + (int32)(bg & 0xFFFFFFFF);
    }
    return hashCode;
}