/*
 * Copyright (C) 2020 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include <wtf/Bitmap.h>

namespace TestWebKitAPI {

constexpr size_t size = 128;
constexpr size_t smallSize = 9;
constexpr size_t zeroSize = 0;

static constexpr bool expectedBits1[size] = {
    false, false, true,  false,  false, false, false, false,
    false, false, false, false,  false, false, false, true,
    false, true,  false, false,  false, false, true,  false,
    false, false, true,  false,  false, false, true,  true,
    true,  false, false, false,  false, true,  false, false,
    true,  false, false, false,  false, true,  false, true,
    false, false, false, false,  false, true,  true,  false,
    false, true,  false, false,  false, true,  true,  true,
    false, false, true,  false,  true,  false, false, false,
    false, false, true,  false,  true,  false, false, true,
    true,  false, false, false,  true,  false, true,  false,
    false, false, false, false,  true,  false, true,  true,
    false, false, false, false,  true,  true,  false, false,
    false, true,  false, false,  true,  true,  false, true,
    false, true,  false, false,  true,  true,  true,  false,
    false, false, true,  false,  true,  true,  true,  true,
};

static constexpr bool expectedBits2[size] = {
    false, true,  false, true,   false, false, false, false,
    false, false, false, true,   false, false, false, true,
    false, false, false, true,   false, false, true,  false,
    false, false, false, true,   false, false, true,  true,
    true,  false, false, true,   false, true,  false, false,
    false, false, false, true,   false, true,  false, true,
    false, false, false, true,   false, true,  true,  false,
    false, false, true,  true,   false, true,  true,  true,
    false, true,  false, true,   true,  false, false, false,
    false, true,  false, true,   true,  false, false, true,
    false, false, false, true,   true,  false, true,  false,
    false, false, true,  true,   true,  false, true,  true,
    true,  false, false, true,   true,  true,  false, false,
    false, false, true,  true,   true,  true,  false, true,
    true,  false, false, true,   true,  true,  true,  false,
    false, true,  false, true,   true,  true,  true,  true,
};

static constexpr bool expectedSmallBits1[smallSize] = {
    false, true, true,  false,  true,  false, false, true,
    true,
};

static constexpr bool expectedSmallBits2[smallSize] = {
    true,  true, false, false,  false, false, true,  true,
    false,
};

constexpr size_t countBits(const bool boolArray[], size_t size)
{
    size_t result = 0;
    for (size_t i = 0; i < size; ++i) {
        if (boolArray[i])
            result++;
    }
    return result;
}

constexpr size_t expectedNumberOfSetBits1 = countBits(expectedBits1, size);
constexpr size_t expectedNumberOfSetBits2 = countBits(expectedBits2, size);

#define DECLARE_BITMAPS_FOR_TEST() \
    Bitmap<size, WordType> bitmapZeroes; \
    Bitmap<size, WordType> bitmap1; /* Will hold values specified in expectedBits1. */ \
    Bitmap<size, WordType> bitmap2; /* Will hold values specified in expectedBits2. */ \
    Bitmap<size, WordType> bitmap2Clone; /* Same as bitmap2. */ \
    Bitmap<size, WordType> bitmapOnes; \
    Bitmap<smallSize, WordType> smallBitmapZeroes; \
    Bitmap<smallSize, WordType> smallBitmapOnes; \
    Bitmap<smallSize, WordType> smallBitmap1; /* Will hold values specified in expectedSmallBits1. */ \
    Bitmap<smallSize, WordType> smallBitmap2; /* Will hold values specified in expectedSmallBits2. */ \

#define DECLARE_AND_INIT_BITMAPS_FOR_TEST() \
    DECLARE_BITMAPS_FOR_TEST() \
    for (size_t i = 0; i < size; ++i) { \
        bitmap1.set(i, expectedBits1[i]); \
        bitmap2.set(i, expectedBits2[i]); \
        bitmap2Clone.set(i, expectedBits2[i]); \
        bitmapOnes.set(i); \
    } \
    for (size_t i = 0; i < smallSize; ++i) { \
        smallBitmap1.set(i, expectedSmallBits1[i]); \
        smallBitmap2.set(i, expectedSmallBits2[i]); \
        smallBitmapOnes.set(i); \
    }

template<typename WordType>
void testBitmapSize()
{
    DECLARE_BITMAPS_FOR_TEST();

    auto verifySize = [=] (auto& bitmap, size_t expectedSize, size_t notExpectedSize) {
        EXPECT_EQ(bitmap.size(), expectedSize);
        EXPECT_NE(bitmap.size(), notExpectedSize);
    };

    verifySize(bitmapZeroes, size, smallSize);
    verifySize(bitmap1, size, smallSize);
    verifySize(bitmap2, size, smallSize);
    verifySize(bitmap2Clone, size, smallSize);
    verifySize(bitmapOnes, size, smallSize);
    verifySize(smallBitmapZeroes, smallSize, size);
    verifySize(smallBitmapOnes, smallSize, size);
}

template<typename WordType>
void testBitmapConstructedEmpty()
{
    DECLARE_BITMAPS_FOR_TEST();

    // Verify that the default constructor initializes all bits to 0.
    auto verifyIsEmpty = [=] (const auto& bitmap) {
        EXPECT_TRUE(bitmap.isEmpty());
        EXPECT_EQ(bitmap.count(), zeroSize);
        for (size_t i = 0; i < bitmap.size(); ++i)
            EXPECT_FALSE(bitmap.get(i));
    };

    verifyIsEmpty(bitmapZeroes);
    verifyIsEmpty(bitmap1);
    verifyIsEmpty(bitmap2);
    verifyIsEmpty(bitmap2Clone);
    verifyIsEmpty(bitmapOnes);
    verifyIsEmpty(smallBitmapZeroes);
    verifyIsEmpty(smallBitmapOnes);
}

template<typename WordType>
void testBitmapSetGet()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    auto verifyIsEmpty = [=] (const auto& bitmap) {
        EXPECT_TRUE(bitmap.isEmpty());
        EXPECT_EQ(bitmap.count(), zeroSize);
        for (size_t i = 0; i < bitmap.size(); ++i)
            EXPECT_FALSE(bitmap.get(i));
    };

    for (size_t i = 0; i < size; ++i)
        EXPECT_EQ(bitmap1.get(i), expectedBits1[i]);

    for (size_t i = 0; i < size; ++i) {
        EXPECT_EQ(bitmap2.get(i), expectedBits2[i]);
        EXPECT_EQ(bitmap2Clone.get(i), expectedBits2[i]);
    }
    for (size_t i = 0; i < size; ++i)
        EXPECT_EQ(bitmap2.get(i), bitmap2Clone.get(i));

    for (size_t i = 0; i < size; ++i)
        EXPECT_TRUE(bitmapOnes.get(i));

    for (size_t i = 0; i < smallSize; ++i)
        EXPECT_TRUE(smallBitmapOnes.get(i));

    // Verify that there is no out of bounds write from the above set operations.
    verifyIsEmpty(bitmapZeroes);
    verifyIsEmpty(smallBitmapZeroes);
}

template<typename WordType>
void testBitmapTestAndSet()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    ASSERT_FALSE(bitmap1.isFull());
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.testAndSet(i), expectedBits1[i]);
    ASSERT_TRUE(bitmap1.isFull());

    ASSERT_FALSE(smallBitmapZeroes.isFull());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    for (size_t i = 0; i < smallSize; ++i)
        ASSERT_FALSE(smallBitmapZeroes.testAndSet(i));
    ASSERT_TRUE(smallBitmapZeroes.isFull());
}

template<typename WordType>
void testBitmapTestAndClear()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    ASSERT_FALSE(bitmap1.isEmpty());
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.testAndClear(i), expectedBits1[i]);
    ASSERT_TRUE(bitmap1.isEmpty());

    ASSERT_FALSE(smallBitmapOnes.isEmpty());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    for (size_t i = 0; i < smallSize; ++i)
        ASSERT_TRUE(smallBitmapOnes.testAndClear(i));
    ASSERT_TRUE(smallBitmapOnes.isEmpty());
}

template<typename WordType>
void testBitmapConcurrentTestAndSet()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    // FIXME: the following does not test the concurrent part. It only ensures that
    // the TestAndSet part of the operation is working.
    ASSERT_FALSE(bitmap1.isFull());
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.testAndSet(i), expectedBits1[i]);
    ASSERT_TRUE(bitmap1.isFull());

    ASSERT_FALSE(smallBitmapZeroes.isFull());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    for (size_t i = 0; i < smallSize; ++i)
        ASSERT_FALSE(smallBitmapZeroes.testAndSet(i));
    ASSERT_TRUE(smallBitmapZeroes.isFull());
}

template<typename WordType>
void testBitmapConcurrentTestAndClear()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    // FIXME: the following does not test the concurrent part. It only ensures that
    // the TestAndClear part of the operation is working.
    ASSERT_FALSE(bitmap1.isEmpty());
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.testAndClear(i), expectedBits1[i]);
    ASSERT_TRUE(bitmap1.isEmpty());

    ASSERT_FALSE(smallBitmapOnes.isEmpty());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    for (size_t i = 0; i < smallSize; ++i)
        ASSERT_TRUE(smallBitmapOnes.testAndClear(i));
    ASSERT_TRUE(smallBitmapOnes.isEmpty());
}

template<typename WordType>
void testBitmapClear()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    ASSERT_TRUE(bitmapOnes.isFull());
    for (size_t i = 0; i < size; ++i) {
        if (!expectedBits1[i])
            bitmapOnes.clear(i);
    }
    ASSERT_EQ(bitmapOnes, bitmap1);
}

template<typename WordType>
void testBitmapClearAll()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    auto verifyIsEmpty = [=] (const auto& bitmap) {
        EXPECT_TRUE(bitmap.isEmpty());
        EXPECT_EQ(bitmap.count(), zeroSize);
        for (size_t i = 0; i < bitmap.size(); ++i)
            EXPECT_FALSE(bitmap.get(i));
    };

    auto verifyIsFull = [=] (const auto& bitmap) {
        EXPECT_TRUE(bitmap.isFull());
        for (size_t i = 0; i < bitmap.size(); ++i)
            EXPECT_TRUE(bitmap.get(i));
    };

    EXPECT_FALSE(bitmap1.isEmpty());
    bitmap1.clearAll();
    verifyIsEmpty(bitmap1);
    verifyIsFull(bitmapOnes);
    verifyIsFull(smallBitmapOnes);

    EXPECT_FALSE(bitmap2.isEmpty());
    bitmap2.clearAll();
    verifyIsEmpty(bitmap1);
    verifyIsEmpty(bitmap2);
    verifyIsFull(bitmapOnes);
    verifyIsFull(smallBitmapOnes);

    EXPECT_FALSE(bitmap2Clone.isEmpty());
    bitmap2Clone.clearAll();
    verifyIsEmpty(bitmap1);
    verifyIsEmpty(bitmap2);
    verifyIsEmpty(bitmap2Clone);
    verifyIsFull(bitmapOnes);
    verifyIsFull(smallBitmapOnes);
}

template<typename WordType>
void testBitmapInvert()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    auto verifyInvert = [=] (auto& bitmap) {
        ASSERT_TRUE(bitmap.isFull());
        ASSERT_FALSE(bitmap.isEmpty());
        bitmap.invert();
        ASSERT_FALSE(bitmap.isFull());
        ASSERT_TRUE(bitmap.isEmpty());
        bitmap.invert();
        ASSERT_TRUE(bitmap.isFull());
        ASSERT_FALSE(bitmap.isEmpty());
    };

    verifyInvert(bitmapOnes);
    verifyInvert(smallBitmapOnes);

    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
    bitmap1.invert();
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.get(i), !expectedBits1[i]);
    bitmap1.invert();
    for (size_t i = 0; i < size; ++i)
        ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
}

template<typename WordType>
void testBitmapFindRunOfZeros()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    const int64_t bitmap1RunsOfZeros[15] = {
        0, 0, 0, 3, 3,
        3, 3, 3, 3, 3,
        3, 3, 3, -1, -1
    };

    const int64_t bitmap2RunsOfZeros[15] = {
        0, 0, 4, 4, 4,
        4, 4, 4, -1, -1,
        -1, -1, -1, -1, -1,
    };

    Bitmap<smallSize, WordType> smallTemp;
    smallTemp.set(1, true); // bits low to high are: 0100 0000 0

    const int64_t smallTempRunsOfZeros[15] = {
        0, 0, 2, 2, 2,
        2, 2, 2, -1, -1,
        -1, -1, -1, -1, -1
    };

    for (size_t runLength = 0; runLength < 15; ++runLength) {
        ASSERT_EQ(bitmapZeroes.findRunOfZeros(runLength), 0ll);
        ASSERT_EQ(bitmap1.findRunOfZeros(runLength), bitmap1RunsOfZeros[runLength]);
        ASSERT_EQ(bitmap2.findRunOfZeros(runLength), bitmap2RunsOfZeros[runLength]);
        ASSERT_EQ(bitmapOnes.findRunOfZeros(runLength), -1ll);

        if (runLength <= smallSize)
            ASSERT_EQ(smallBitmapZeroes.findRunOfZeros(runLength), 0ll);
        else
            ASSERT_EQ(smallBitmapZeroes.findRunOfZeros(runLength), -1ll);

        ASSERT_EQ(smallBitmapOnes.findRunOfZeros(runLength), -1ll);

        ASSERT_EQ(smallTemp.findRunOfZeros(runLength), smallTempRunsOfZeros[runLength]);
    }
}

template<typename WordType>
void testBitmapCount()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    EXPECT_EQ(bitmapZeroes.count(), zeroSize);
    EXPECT_EQ(bitmap1.count(), expectedNumberOfSetBits1);
    EXPECT_EQ(bitmap2.count(), expectedNumberOfSetBits2);
    EXPECT_EQ(bitmap2Clone.count(), expectedNumberOfSetBits2);
    EXPECT_EQ(bitmapOnes.count(), size);
    EXPECT_EQ(smallBitmapZeroes.count(), zeroSize);
    EXPECT_EQ(smallBitmapOnes.count(), smallSize);
}

template<typename WordType>
void testBitmapIsEmpty()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    EXPECT_TRUE(bitmapZeroes.isEmpty());
    EXPECT_FALSE(bitmap1.isEmpty());
    EXPECT_FALSE(bitmap2.isEmpty());
    EXPECT_FALSE(bitmap2Clone.isEmpty());
    EXPECT_FALSE(bitmapOnes.isEmpty());
    EXPECT_TRUE(smallBitmapZeroes.isEmpty());
    EXPECT_FALSE(smallBitmapOnes.isEmpty());

    auto verifyIsEmpty = [=] (const auto& bitmap) {
        EXPECT_TRUE(bitmap.isEmpty());
        EXPECT_EQ(bitmap.count(), zeroSize);
        for (size_t i = 0; i < bitmap.size(); ++i)
            EXPECT_FALSE(bitmap.get(i));
    };

    verifyIsEmpty(bitmapZeroes);
    verifyIsEmpty(smallBitmapZeroes);
}

template<typename WordType>
void testBitmapIsFull()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    EXPECT_FALSE(bitmapZeroes.isFull());
    EXPECT_FALSE(bitmap1.isFull());
    EXPECT_FALSE(bitmap2.isFull());
    EXPECT_FALSE(bitmap2Clone.isFull());
    EXPECT_TRUE(bitmapOnes.isFull());
    EXPECT_FALSE(smallBitmapZeroes.isFull());
    EXPECT_TRUE(smallBitmapOnes.isFull());

    auto verifyIsFull = [=] (auto& bitmap) {
        EXPECT_TRUE(bitmap.isFull());
        for (size_t i = 0; i < bitmap.size(); ++i)
            EXPECT_TRUE(bitmap.get(i));
    };

    verifyIsFull(bitmapOnes);
    verifyIsFull(smallBitmapOnes);
}

template<typename WordType>
void testBitmapMerge()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    ASSERT_TRUE(bitmapZeroes.isEmpty());
    ASSERT_EQ(bitmap2, bitmap2Clone);
    bitmap2.merge(bitmapZeroes);
    ASSERT_EQ(bitmap2, bitmap2Clone);
    
    ASSERT_NE(bitmap1, bitmap2);
    ASSERT_NE(bitmap1, bitmap2Clone);
    ASSERT_EQ(bitmap2, bitmap2Clone);
    bitmap2Clone.merge(bitmap1);
    ASSERT_NE(bitmap2, bitmap2Clone);
    for (size_t i = 0; i < size; ++i) {
        bool expectedBit = expectedBits2[i] | expectedBits1[i];
        ASSERT_EQ(bitmap2Clone.get(i), expectedBit);
    }

    ASSERT_TRUE(bitmapOnes.isFull());
    ASSERT_TRUE(bitmapZeroes.isEmpty());
    bitmapOnes.merge(bitmapZeroes);
    ASSERT_TRUE(bitmapOnes.isFull());
    ASSERT_TRUE(bitmapZeroes.isEmpty());

    bitmapZeroes.merge(bitmap1);
    ASSERT_EQ(bitmapZeroes, bitmap1);

    bitmap1.merge(bitmapOnes);
    ASSERT_EQ(bitmap1, bitmapOnes);

    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    smallBitmapZeroes.merge(smallBitmapOnes);
    ASSERT_FALSE(smallBitmapZeroes.isEmpty());
    ASSERT_TRUE(smallBitmapZeroes.isFull());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    
    smallBitmapZeroes.clearAll();
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    smallBitmapOnes.merge(smallBitmapZeroes);
    ASSERT_TRUE(smallBitmapOnes.isFull());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
}

template<typename WordType>
void testBitmapFilter()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    ASSERT_TRUE(bitmapOnes.isFull());
    ASSERT_EQ(bitmap2, bitmap2Clone);
    bitmap2.filter(bitmapOnes);
    ASSERT_EQ(bitmap2, bitmap2Clone);
    
    ASSERT_NE(bitmap1, bitmap2);
    ASSERT_NE(bitmap1, bitmap2Clone);
    ASSERT_EQ(bitmap2, bitmap2Clone);
    bitmap2Clone.filter(bitmap1);
    ASSERT_NE(bitmap2, bitmap2Clone);
    for (size_t i = 0; i < size; ++i) {
        bool expectedBit = expectedBits2[i] & expectedBits1[i];
        ASSERT_EQ(bitmap2Clone.get(i), expectedBit);
    }

    ASSERT_TRUE(bitmapZeroes.isEmpty());
    bitmap2.filter(bitmapZeroes);
    ASSERT_EQ(bitmap2, bitmapZeroes);

    ASSERT_TRUE(bitmapZeroes.isEmpty());
    bitmapZeroes.filter(bitmap1);
    ASSERT_TRUE(bitmapZeroes.isEmpty());

    ASSERT_TRUE(bitmapOnes.isFull());
    bitmapOnes.filter(bitmap1);
    ASSERT_EQ(bitmapOnes, bitmap1);

    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    smallBitmapZeroes.filter(smallBitmapOnes);
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    ASSERT_FALSE(smallBitmapZeroes.isFull());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    
    smallBitmapOnes.filter(smallBitmapZeroes);
    ASSERT_FALSE(smallBitmapOnes.isFull());
    ASSERT_TRUE(smallBitmapOnes.isEmpty());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
}

template<typename WordType>
void testBitmapExclude()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    ASSERT_TRUE(bitmapZeroes.isEmpty());
    ASSERT_EQ(bitmap2, bitmap2Clone);
    bitmap2.exclude(bitmapZeroes);
    ASSERT_EQ(bitmap2, bitmap2Clone);
    
    ASSERT_NE(bitmap1, bitmap2);
    ASSERT_NE(bitmap1, bitmap2Clone);
    ASSERT_EQ(bitmap2, bitmap2Clone);
    bitmap2Clone.exclude(bitmap1);
    ASSERT_NE(bitmap2, bitmap2Clone);
    for (size_t i = 0; i < size; ++i) {
        bool expectedBit = expectedBits2[i] & !expectedBits1[i];
        ASSERT_EQ(bitmap2Clone.get(i), expectedBit);
    }

    ASSERT_TRUE(bitmapZeroes.isEmpty());
    ASSERT_TRUE(bitmapOnes.isFull());
    bitmap2.exclude(bitmapOnes);
    ASSERT_EQ(bitmap2, bitmapZeroes);

    ASSERT_TRUE(bitmapOnes.isFull());
    bitmapOnes.exclude(bitmap1);
    bitmap1.invert();
    ASSERT_EQ(bitmapOnes, bitmap1);

    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    smallBitmapZeroes.exclude(smallBitmapOnes);
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    ASSERT_FALSE(smallBitmapZeroes.isFull());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    
    smallBitmapOnes.exclude(smallBitmapZeroes);
    ASSERT_TRUE(smallBitmapOnes.isFull());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());

    smallBitmapOnes.exclude(smallBitmapOnes);
    ASSERT_FALSE(smallBitmapOnes.isFull());
    ASSERT_TRUE(smallBitmapOnes.isEmpty());
}

template<typename WordType>
void testBitmapConcurrentFilter()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    // FIXME: the following does not test the concurrent part. It only ensures that
    // the Filter part of the operation is working.
    ASSERT_TRUE(bitmapOnes.isFull());
    ASSERT_EQ(bitmap2, bitmap2Clone);
    bitmap2.concurrentFilter(bitmapOnes);
    ASSERT_EQ(bitmap2, bitmap2Clone);
    
    ASSERT_NE(bitmap1, bitmap2);
    ASSERT_NE(bitmap1, bitmap2Clone);
    ASSERT_EQ(bitmap2, bitmap2Clone);
    bitmap2Clone.concurrentFilter(bitmap1);
    ASSERT_NE(bitmap2, bitmap2Clone);
    for (size_t i = 0; i < size; ++i) {
        bool expectedBit = expectedBits2[i] & expectedBits1[i];
        ASSERT_EQ(bitmap2Clone.get(i), expectedBit);
    }

    ASSERT_TRUE(bitmapZeroes.isEmpty());
    bitmap2.concurrentFilter(bitmapZeroes);
    ASSERT_EQ(bitmap2, bitmapZeroes);

    ASSERT_TRUE(bitmapZeroes.isEmpty());
    bitmapZeroes.concurrentFilter(bitmap1);
    ASSERT_TRUE(bitmapZeroes.isEmpty());

    ASSERT_TRUE(bitmapOnes.isFull());
    bitmapOnes.concurrentFilter(bitmap1);
    ASSERT_EQ(bitmapOnes, bitmap1);

    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    smallBitmapZeroes.concurrentFilter(smallBitmapOnes);
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    ASSERT_FALSE(smallBitmapZeroes.isFull());
    ASSERT_TRUE(smallBitmapOnes.isFull());
    
    smallBitmapOnes.concurrentFilter(smallBitmapZeroes);
    ASSERT_FALSE(smallBitmapOnes.isFull());
    ASSERT_TRUE(smallBitmapOnes.isEmpty());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
}

template<typename WordType>
void testBitmapSubsumes()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    ASSERT_TRUE(bitmapZeroes.isEmpty());
    ASSERT_TRUE(bitmapOnes.isFull());
    ASSERT_EQ(bitmap2, bitmap2Clone);

    ASSERT_TRUE(bitmapZeroes.subsumes(bitmapZeroes));
    ASSERT_FALSE(bitmapZeroes.subsumes(bitmap1));
    ASSERT_FALSE(bitmapZeroes.subsumes(bitmap2));
    ASSERT_FALSE(bitmapZeroes.subsumes(bitmap2Clone));
    ASSERT_FALSE(bitmapZeroes.subsumes(bitmapOnes));

    ASSERT_TRUE(bitmap1.subsumes(bitmapZeroes));
    ASSERT_TRUE(bitmap1.subsumes(bitmap1));
    ASSERT_FALSE(bitmap1.subsumes(bitmap2));
    ASSERT_FALSE(bitmap1.subsumes(bitmap2Clone));
    ASSERT_FALSE(bitmap1.subsumes(bitmapOnes));

    ASSERT_TRUE(bitmap2.subsumes(bitmapZeroes));
    ASSERT_FALSE(bitmap2.subsumes(bitmap1));
    ASSERT_TRUE(bitmap2.subsumes(bitmap2));
    ASSERT_TRUE(bitmap2.subsumes(bitmap2Clone));
    ASSERT_FALSE(bitmap2.subsumes(bitmapOnes));

    ASSERT_TRUE(bitmap2Clone.subsumes(bitmapZeroes));
    ASSERT_FALSE(bitmap2Clone.subsumes(bitmap1));
    ASSERT_TRUE(bitmap2Clone.subsumes(bitmap2));
    ASSERT_TRUE(bitmap2Clone.subsumes(bitmap2Clone));
    ASSERT_FALSE(bitmap2Clone.subsumes(bitmapOnes));

    ASSERT_TRUE(bitmapOnes.subsumes(bitmapZeroes));
    ASSERT_TRUE(bitmapOnes.subsumes(bitmap1));
    ASSERT_TRUE(bitmapOnes.subsumes(bitmap2));
    ASSERT_TRUE(bitmapOnes.subsumes(bitmap2Clone));
    ASSERT_TRUE(bitmapOnes.subsumes(bitmapOnes));

    ASSERT_TRUE(smallBitmapOnes.subsumes(smallBitmapOnes));
    ASSERT_TRUE(smallBitmapOnes.subsumes(smallBitmapZeroes));

    ASSERT_FALSE(smallBitmapZeroes.subsumes(smallBitmapOnes));
    ASSERT_TRUE(smallBitmapZeroes.subsumes(smallBitmapZeroes));
}

template<typename WordType>
void testBitmapForEachSetBit()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    size_t count = 0;
    ASSERT_TRUE(bitmapZeroes.isEmpty());
    bitmapZeroes.forEachSetBit([&] (size_t i) {
        constexpr bool notReached = false;
        ASSERT_TRUE(notReached);
        count++;
    });
    ASSERT_EQ(count, zeroSize);

    count = 0;
    bitmap1.forEachSetBit([&] (size_t i) {
        ASSERT_TRUE(bitmap1.get(i));
        ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
        count++;
    });
    ASSERT_EQ(count, expectedNumberOfSetBits1);

    count = 0;
    ASSERT_TRUE(bitmapOnes.isFull());
    bitmapOnes.forEachSetBit([&] (size_t i) {
        ASSERT_TRUE(bitmapOnes.get(i));
        count++;
    });
    ASSERT_EQ(count, size);

    count = 0;
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    smallBitmapZeroes.forEachSetBit([&] (size_t i) {
        constexpr bool notReached = false;
        ASSERT_TRUE(notReached);
        count++;
    });
    ASSERT_EQ(count, zeroSize);

    count = 0;
    ASSERT_TRUE(smallBitmapOnes.isFull());
    smallBitmapOnes.forEachSetBit([&] (size_t i) {
        ASSERT_TRUE(smallBitmapOnes.get(i));
        count++;
    });
    ASSERT_EQ(count, smallSize);
}

template<typename WordType>
void testBitmapFindBit()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    auto findExpectedBit = [=] (auto expectedBits, size_t startIndex, bool value) -> size_t {
        for (auto index = startIndex; index < size; ++index) {
            if (expectedBits[index] == value)
                return index;
        }
        return startIndex;
    };
    
    for (size_t i = 1, lastIndex = 1; i < size; lastIndex = i, i += lastIndex) {
        ASSERT_EQ(bitmap1.findBit(i, true), findExpectedBit(expectedBits1, i, true));
        ASSERT_EQ(bitmap1.findBit(i, false), findExpectedBit(expectedBits1, i, false));
        ASSERT_EQ(bitmap2.findBit(i, true), findExpectedBit(expectedBits2, i, true));
        ASSERT_EQ(bitmap2.findBit(i, false), findExpectedBit(expectedBits2, i, false));

        ASSERT_EQ(bitmap2.findBit(i, true), bitmap2Clone.findBit(i, true));
        ASSERT_EQ(bitmap2.findBit(i, false), bitmap2Clone.findBit(i, false));
    }

    ASSERT_EQ(bitmapZeroes.findBit(0, false), zeroSize);
    ASSERT_EQ(bitmapZeroes.findBit(10, false), static_cast<size_t>(10));
    ASSERT_EQ(bitmapZeroes.findBit(size - 1, false), size-1);
    ASSERT_EQ(bitmapZeroes.findBit(size, false), size);
    ASSERT_EQ(bitmapZeroes.findBit(size + 1, false), size);

    ASSERT_EQ(bitmapZeroes.findBit(0, true), size);
    ASSERT_EQ(bitmapZeroes.findBit(10, true), size);
    ASSERT_EQ(bitmapZeroes.findBit(size - 1, true), size);
    ASSERT_EQ(bitmapZeroes.findBit(size, true), size);
    ASSERT_EQ(bitmapZeroes.findBit(size + 1, true), size);

    ASSERT_EQ(bitmapOnes.findBit(0, false), size);
    ASSERT_EQ(bitmapOnes.findBit(10, false), size);
    ASSERT_EQ(bitmapOnes.findBit(size - 1, false), size);
    ASSERT_EQ(bitmapOnes.findBit(size, false), size);
    ASSERT_EQ(bitmapOnes.findBit(size + 1, false), size);

    ASSERT_EQ(bitmapOnes.findBit(0, true), zeroSize);
    ASSERT_EQ(bitmapOnes.findBit(10, true), static_cast<size_t>(10));
    ASSERT_EQ(bitmapOnes.findBit(size - 1, true), size-1);
    ASSERT_EQ(bitmapOnes.findBit(size, true), size);
    ASSERT_EQ(bitmapOnes.findBit(size + 1, true), size);
}

template<typename WordType>
void testBitmapIteration()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    auto computeSetBitsCount = [=] (auto& bitmap) -> size_t {
        size_t count = 0;
        for (auto bitIndex : bitmap) {
            UNUSED_PARAM(bitIndex);
            count++;
        }
        return count;
    };

    EXPECT_EQ(computeSetBitsCount(bitmapZeroes), zeroSize);
    EXPECT_EQ(computeSetBitsCount(bitmap1), expectedNumberOfSetBits1);
    EXPECT_EQ(computeSetBitsCount(bitmap2), expectedNumberOfSetBits2);
    EXPECT_EQ(computeSetBitsCount(bitmap2Clone), expectedNumberOfSetBits2);
    EXPECT_EQ(computeSetBitsCount(bitmapOnes), size);
    EXPECT_EQ(computeSetBitsCount(smallBitmapZeroes), zeroSize);
    EXPECT_EQ(computeSetBitsCount(smallBitmapOnes), smallSize);

    auto verifySetBits = [=] (auto& bitmap, auto& expectedBits) {
        for (auto bitIndex : bitmap) {
            EXPECT_TRUE(bitmap.get(bitIndex));
            EXPECT_EQ(bitmap.get(bitIndex), expectedBits[bitIndex]);
        }
    };

    verifySetBits(bitmap1, expectedBits1);
    verifySetBits(bitmap2, expectedBits2);
    verifySetBits(bitmap2Clone, expectedBits2);

    auto verifyBitsAllSet = [=] (auto& bitmap) {
        size_t lastBitIndex = 0;
        for (auto bitIndex : bitmap) {
            EXPECT_TRUE(bitmap.get(bitIndex));
            if (bitIndex)
                EXPECT_EQ(bitIndex, lastBitIndex + 1);
            lastBitIndex = bitIndex;
        }
    };

    verifyBitsAllSet(bitmapOnes);
    verifyBitsAllSet(smallBitmapOnes);
}

template<typename WordType>
void testBitmapMergeAndClear()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    Bitmap<size, WordType> temp;
    Bitmap<size, WordType> savedBitmap1;

    ASSERT_FALSE(bitmap2.isEmpty());

    savedBitmap1.merge(bitmap1);
    ASSERT_EQ(savedBitmap1, bitmap1);
    
    ASSERT_NE(bitmap1, bitmap2);
    ASSERT_NE(bitmap1, bitmap2Clone);
    ASSERT_EQ(bitmap2Clone, bitmap2);
    bitmap1.mergeAndClear(bitmap2Clone);
    ASSERT_NE(bitmap1, bitmap2);
    ASSERT_NE(bitmap1, savedBitmap1);
    ASSERT_TRUE(bitmap2Clone.isEmpty());
    for (size_t i = 0; i < size; ++i) {
        bool expectedBit = expectedBits1[i] | expectedBits2[i];
        ASSERT_EQ(bitmap1.get(i), expectedBit);
    }

    bitmap2Clone.merge(bitmap2); // restore bitmap2Clone
    ASSERT_EQ(bitmap2Clone, bitmap2);

    ASSERT_TRUE(temp.isEmpty());
    temp.mergeAndClear(bitmap2Clone);
    ASSERT_FALSE(temp.isEmpty());
    ASSERT_EQ(temp, bitmap2);
    ASSERT_TRUE(bitmap2Clone.isEmpty());

    Bitmap<size, WordType> savedBitmapOnes;
    savedBitmapOnes.merge(bitmapOnes);

    temp.clearAll();
    ASSERT_TRUE(temp.isEmpty());
    ASSERT_FALSE(temp.isFull());
    ASSERT_FALSE(bitmapOnes.isEmpty());
    ASSERT_TRUE(bitmapOnes.isFull());
    temp.mergeAndClear(bitmapOnes);
    ASSERT_FALSE(temp.isEmpty());
    ASSERT_TRUE(temp.isFull());
    ASSERT_TRUE(bitmapOnes.isEmpty());
    ASSERT_FALSE(bitmapOnes.isFull());

    bitmap2Clone.merge(bitmap2); // restore bitmap2Clone
    ASSERT_EQ(bitmap2Clone, bitmap2);
    bitmapOnes.merge(savedBitmapOnes); // restore bitmapOnes
    ASSERT_TRUE(bitmapOnes.isFull());

    ASSERT_TRUE(temp.isFull());
    temp.mergeAndClear(bitmap2Clone);
    ASSERT_TRUE(temp.isFull());
    ASSERT_EQ(temp, bitmapOnes);
    ASSERT_TRUE(bitmap2Clone.isEmpty());

    Bitmap<smallSize, WordType> smallTemp;

    smallTemp.merge(smallBitmapOnes);
    ASSERT_TRUE(smallTemp.isFull());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    smallTemp.mergeAndClear(smallBitmapZeroes);
    ASSERT_TRUE(smallTemp.isFull());
    ASSERT_FALSE(smallTemp.isEmpty());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());

    smallTemp.clearAll();
    ASSERT_TRUE(smallBitmapOnes.isFull());
    ASSERT_TRUE(smallTemp.isEmpty());
    smallTemp.mergeAndClear(smallBitmapOnes);
    ASSERT_TRUE(smallTemp.isFull());
    ASSERT_TRUE(smallBitmapOnes.isEmpty());
}

template<typename WordType>
void testBitmapSetAndClear()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    Bitmap<size, WordType> temp;
    Bitmap<size, WordType> savedBitmap1;

    ASSERT_FALSE(bitmap2.isEmpty());

    savedBitmap1.merge(bitmap1);
    ASSERT_EQ(savedBitmap1, bitmap1);
    
    ASSERT_NE(bitmap1, bitmap2);
    ASSERT_NE(bitmap1, bitmap2Clone);
    ASSERT_EQ(bitmap2Clone, bitmap2);
    bitmap1.setAndClear(bitmap2Clone);
    ASSERT_EQ(bitmap1, bitmap2);
    ASSERT_NE(bitmap1, savedBitmap1);
    ASSERT_TRUE(bitmap2Clone.isEmpty());

    bitmap2Clone.merge(bitmap2); // restore bitmap2Clone
    ASSERT_EQ(bitmap2Clone, bitmap2);

    ASSERT_TRUE(temp.isEmpty());
    temp.setAndClear(bitmap2Clone);
    ASSERT_FALSE(temp.isEmpty());
    ASSERT_EQ(temp, bitmap2);
    ASSERT_TRUE(bitmap2Clone.isEmpty());

    temp.clearAll();
    ASSERT_TRUE(temp.isEmpty());
    ASSERT_FALSE(temp.isFull());
    ASSERT_FALSE(bitmapOnes.isEmpty());
    ASSERT_TRUE(bitmapOnes.isFull());
    temp.setAndClear(bitmapOnes);
    ASSERT_FALSE(temp.isEmpty());
    ASSERT_TRUE(temp.isFull());
    ASSERT_TRUE(bitmapOnes.isEmpty());
    ASSERT_FALSE(bitmapOnes.isFull());

    bitmap2Clone.merge(bitmap2); // restore bitmap2Clone
    ASSERT_EQ(bitmap2Clone, bitmap2);

    ASSERT_TRUE(temp.isFull());
    temp.setAndClear(bitmap2Clone);
    ASSERT_FALSE(temp.isFull());
    ASSERT_EQ(temp, bitmap2);
    ASSERT_TRUE(bitmap2Clone.isEmpty());

    Bitmap<smallSize, WordType> smallTemp;

    smallTemp.merge(smallBitmapOnes);
    ASSERT_TRUE(smallTemp.isFull());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    smallTemp.setAndClear(smallBitmapZeroes);
    ASSERT_TRUE(smallTemp.isEmpty());
    ASSERT_TRUE(smallBitmapZeroes.isEmpty());
    
    ASSERT_TRUE(smallBitmapOnes.isFull());
    ASSERT_TRUE(smallTemp.isEmpty());
    smallTemp.setAndClear(smallBitmapOnes);
    ASSERT_TRUE(smallTemp.isFull());
    ASSERT_TRUE(smallBitmapOnes.isEmpty());
}

template<typename Bitmap>
void testBitmapSetEachNthBitImpl(size_t size, size_t wordSize, const Bitmap& zeroes, const Bitmap& ones)
{
    Bitmap temp;

    EXPECT_TRUE(temp == zeroes);
    temp.setEachNthBit(1);
    EXPECT_TRUE(temp == ones);

    size_t nValues[] = { 1, 2, wordSize / 2, wordSize - 1, wordSize, size / 2, size - 1, size };
    size_t nValuesCount = sizeof(nValues) / sizeof(nValues[0]);

    size_t startEndValues[] = { 0, 1, 2, wordSize / 2, wordSize - 1, wordSize, size / 2, size - 1, size };
    constexpr size_t numberOfStartEndValues = sizeof(startEndValues) / sizeof(startEndValues[0]);

    for (size_t start = 0; start < numberOfStartEndValues; ++start) {
        for (size_t end = start; end < numberOfStartEndValues; ++end) {
            size_t startIndex = startEndValues[start];
            size_t endIndex = startEndValues[end];
            if (endIndex < startIndex)
                continue;
            if (startIndex > size)
                continue;
            if (endIndex > size)
                continue;

            for (size_t j = 0; j < nValuesCount; ++j) {
                size_t n = nValues[j];
                temp.clearAll();
                temp.setEachNthBit(n, startIndex, endIndex);

                for (size_t i = 0; i < startIndex; ++i)
                    EXPECT_FALSE(temp.get(i));

                size_t count = 0;
                for (size_t i = startIndex; i < endIndex; ++i) {
                    bool expected = !count;
                    EXPECT_TRUE(temp.get(i) == expected);
                    count++;
                    count = count % n;
                }

                for (size_t i = endIndex; i < size; ++i)
                    EXPECT_FALSE(temp.get(i));
            }
        }
    }
}

template<typename WordType>
void testBitmapSetEachNthBit()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
    constexpr size_t wordSize = sizeof(WordType) * 8;
    testBitmapSetEachNthBitImpl(size, wordSize, bitmapZeroes, bitmapOnes);
    testBitmapSetEachNthBitImpl(smallSize, wordSize, smallBitmapZeroes, smallBitmapOnes);
}

template<typename WordType>
void testBitmapOperatorEqual()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    EXPECT_TRUE(bitmapZeroes == bitmapZeroes);
    EXPECT_FALSE(bitmapZeroes == bitmap1);
    EXPECT_TRUE(bitmap1 == bitmap1);
    EXPECT_FALSE(bitmap1 == bitmap2);
    EXPECT_FALSE(bitmap1 == bitmap2Clone);
    EXPECT_TRUE(bitmap2 == bitmap2Clone);
    EXPECT_FALSE(bitmapOnes == bitmap1);
    EXPECT_FALSE(smallBitmapZeroes == smallBitmapOnes);
}

template<typename WordType>
void testBitmapOperatorNotEqual()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    EXPECT_FALSE(bitmapZeroes != bitmapZeroes);
    EXPECT_TRUE(bitmapZeroes != bitmap1);
    EXPECT_FALSE(bitmap1 != bitmap1);
    EXPECT_TRUE(bitmap1 != bitmap2);
    EXPECT_TRUE(bitmap1 != bitmap2Clone);
    EXPECT_FALSE(bitmap2 != bitmap2Clone);
    EXPECT_TRUE(bitmapOnes != bitmap1);
    EXPECT_TRUE(smallBitmapZeroes != smallBitmapOnes);
}

template<typename Bitmap>
void testBitmapOperatorAssignmentImpl(const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
{
    Bitmap temp;
    Bitmap temp2;
    EXPECT_TRUE(temp.isEmpty());
    EXPECT_TRUE(temp2.isEmpty());

    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != bitmap1);
    temp = bitmap1;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == bitmap1);

    EXPECT_TRUE(temp != bitmap2);
    temp = bitmap2;
    EXPECT_TRUE(temp == bitmap2);
    EXPECT_TRUE(temp != bitmap1);

    temp.clearAll();
    temp2.clearAll();
    for (size_t i = 0; i < bitmap1.size(); ++i)
        temp.set(i, bitmap1.get(i));

    EXPECT_TRUE(temp == bitmap1);
    EXPECT_TRUE(temp2.isEmpty());
    EXPECT_TRUE(temp2 != bitmap1);
    temp2 = temp;
    EXPECT_TRUE(temp2 == bitmap1);
}

template<typename WordType>
void testBitmapOperatorAssignment()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
    testBitmapOperatorAssignmentImpl(bitmap1, bitmap2, bitmapZeroes, bitmapOnes);
    testBitmapOperatorAssignmentImpl(smallBitmap1, smallBitmap2, smallBitmapZeroes, smallBitmapOnes);
}

template<typename Bitmap>
void testBitmapOperatorBitOrAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
{
    Bitmap temp;
    Bitmap temp1;

    // 0 | 0
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);
    temp |= zeroes;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);

    // 0 | 1
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);
    temp |= ones;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);

    // 1 | 0
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);
    temp |= zeroes;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);

    // 1 | 1
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);
    temp |= ones;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);

    temp = zeroes;
    EXPECT_TRUE(temp.isEmpty());
    EXPECT_TRUE(temp != bitmap1);
    temp |= bitmap1;
    EXPECT_TRUE(temp == bitmap1);

    temp |= bitmap2;
    for (size_t i = 0; i < size; ++i)
        EXPECT_EQ(temp.get(i), bitmap1.get(i) | bitmap2.get(i));

    temp1 = temp;
    EXPECT_TRUE(temp1 == temp);

    temp |= zeroes;
    EXPECT_TRUE(temp == temp1);
    EXPECT_TRUE(temp != zeroes);

    temp |= ones;
    EXPECT_TRUE(temp != temp1);
    EXPECT_TRUE(temp == ones);
}

template<typename WordType>
void testBitmapOperatorBitOrAssignment()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
    testBitmapOperatorBitOrAssignmentImpl(size, bitmap1, bitmap2, bitmapZeroes, bitmapOnes);
    testBitmapOperatorBitOrAssignmentImpl(smallSize, smallBitmap1, smallBitmap2, smallBitmapZeroes, smallBitmapOnes);
}

template<typename Bitmap>
void testBitmapOperatorBitAndAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
{
    Bitmap temp;
    Bitmap temp1;

    // 0 & 0
    temp = zeroes;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);
    temp &= zeroes;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);

    // 0 & 1
    temp = zeroes;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);
    temp &= ones;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);

    // 1 & 0
    temp = ones;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);
    temp &= zeroes;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);

    // 1 & 1
    temp = ones;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);
    temp &= ones;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);

    temp = ones;
    EXPECT_TRUE(temp == ones);
    EXPECT_TRUE(temp != bitmap1);
    temp &= bitmap1;
    EXPECT_TRUE(temp == bitmap1);

    temp &= bitmap2;
    for (size_t i = 0; i < size; ++i)
        EXPECT_EQ(temp.get(i), bitmap1.get(i) & bitmap2.get(i));

    EXPECT_TRUE(!temp.isEmpty());
    temp1 = temp;
    EXPECT_TRUE(temp1 == temp);

    temp &= zeroes;
    EXPECT_TRUE(temp != temp1);
    EXPECT_TRUE(temp == zeroes);

    temp = temp1;
    temp &= ones;
    EXPECT_TRUE(temp == temp1);
    EXPECT_TRUE(temp != ones);
}

template<typename WordType>
void testBitmapOperatorBitAndAssignment()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
    testBitmapOperatorBitAndAssignmentImpl(size, bitmap1, bitmap2, bitmapZeroes, bitmapOnes);
    testBitmapOperatorBitAndAssignmentImpl(smallSize, smallBitmap1, smallBitmap2, smallBitmapZeroes, smallBitmapOnes);
}

template<typename Bitmap>
void testBitmapOperatorBitXorAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
{
    Bitmap temp;
    Bitmap temp1;

    // 0 ^ 0
    temp = zeroes;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);
    temp ^= zeroes;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);

    // 0 ^ 1
    temp = zeroes;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);
    temp ^= ones;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);

    // 1 ^ 0
    temp = ones;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);
    temp ^= zeroes;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);

    // 1 ^ 1
    temp = ones;
    EXPECT_TRUE(temp != zeroes);
    EXPECT_TRUE(temp == ones);
    temp ^= ones;
    EXPECT_TRUE(temp == zeroes);
    EXPECT_TRUE(temp != ones);

    temp.clearAll();
    EXPECT_TRUE(temp.isEmpty());
    EXPECT_TRUE(temp != bitmap1);
    temp ^= bitmap1;
    EXPECT_TRUE(temp == bitmap1);

    temp ^= bitmap2;
    for (size_t i = 0; i < size; ++i)
        EXPECT_EQ(temp.get(i), bitmap1.get(i) ^ bitmap2.get(i));

    temp1 = temp;
    EXPECT_TRUE(temp1 == temp);

    temp ^= zeroes;
    EXPECT_TRUE(temp == temp1);
    EXPECT_TRUE(temp != zeroes);

    temp ^= ones;
    EXPECT_TRUE(temp != temp1);
    EXPECT_TRUE(temp != ones);
    temp1.invert();
    EXPECT_TRUE(temp == temp1);
    EXPECT_TRUE(temp != ones);
}

template<typename WordType>
void testBitmapOperatorBitXorAssignment()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();
    testBitmapOperatorBitXorAssignmentImpl(size, bitmap1, bitmap2, bitmapZeroes, bitmapOnes);
    testBitmapOperatorBitXorAssignmentImpl(smallSize, smallBitmap1, smallBitmap2, smallBitmapZeroes, smallBitmapOnes);
}

template<typename WordType>
void testBitmapHash()
{
    DECLARE_AND_INIT_BITMAPS_FOR_TEST();

    constexpr unsigned wordSize = sizeof(WordType) * 8;
    constexpr size_t words = (size + wordSize - 1) / wordSize;

    auto expectedBitmapZeroesHash = [=] () -> unsigned {
        unsigned result = 0;
        WordType zeroWord = 0;
        for (size_t i = 0; i < words; ++i)
            result ^= IntHash<WordType>::hash(zeroWord);
        return result;
    };

    auto expectedBitmapOnesHash = [=] () -> unsigned {
        unsigned result = 0;
        WordType filledWord = static_cast<WordType>(-1);
        for (size_t i = 0; i < words; ++i)
            result ^= IntHash<WordType>::hash(filledWord);
        return result;
    };

    ASSERT_EQ(bitmapZeroes.hash(), expectedBitmapZeroesHash());
    ASSERT_EQ(bitmapOnes.hash(), expectedBitmapOnesHash());

    auto expectedHash = [=] (auto expectedBits, size_t size) {
        unsigned result = 0;
        for (size_t i = 0; i < size;) {
            WordType word = 0;
            for (size_t j = 0; j < wordSize && i < size; ++i, ++j)
                word |= static_cast<WordType>(!!expectedBits[i]) << j;
            result ^= IntHash<WordType>::hash(word);
        }
        return result;
    };

    ASSERT_EQ(bitmap1.hash(), expectedHash(expectedBits1, size));
    ASSERT_EQ(bitmap2.hash(), expectedHash(expectedBits2, size));

    static constexpr bool expectedSmallBits[smallSize] = {
        true,  false, false, true,  false,  false, false, true,
        true,
    };
    Bitmap<smallSize, WordType> temp1;
    Bitmap<smallSize, WordType> temp2;

    auto initTemp = [&] (auto& bitmap) {
        for (size_t i = 0; i < smallSize; ++i)
            bitmap.set(i, expectedSmallBits[i]);
    };

    initTemp(temp1);
    ASSERT_EQ(temp1.hash(), expectedHash(expectedSmallBits, smallSize));

    temp2.invert();
    initTemp(temp2);
    ASSERT_EQ(temp2.hash(), expectedHash(expectedSmallBits, smallSize));
    ASSERT_EQ(temp2.hash(), temp1.hash());
}

TEST(WTF_Bitmap, Size_uint32_t) { testBitmapSize<uint32_t>(); }
TEST(WTF_Bitmap, ConstructedEmpty_uint32_t) { testBitmapConstructedEmpty<uint32_t>(); }
TEST(WTF_Bitmap, SetGet_uint32_t) { testBitmapSetGet<uint32_t>(); }
TEST(WTF_Bitmap, TestAndSet_uint32_t) { testBitmapTestAndSet<uint32_t>(); }
TEST(WTF_Bitmap, TestAndClear_uint32_t) { testBitmapTestAndClear<uint32_t>(); }
TEST(WTF_Bitmap, ConcurrentTestAndSet_uint32_t) { testBitmapConcurrentTestAndSet<uint32_t>(); }
TEST(WTF_Bitmap, ConcurrentTestAndClear_uint32_t) { testBitmapConcurrentTestAndClear<uint32_t>(); }
TEST(WTF_Bitmap, Clear_uint32_t) { testBitmapClear<uint32_t>(); }
TEST(WTF_Bitmap, ClearAll_uint32_t) { testBitmapClearAll<uint32_t>(); }
TEST(WTF_Bitmap, Invert_uint32_t) { testBitmapInvert<uint32_t>(); }
TEST(WTF_Bitmap, FindRunOfZeros_uint32_t) { testBitmapFindRunOfZeros<uint32_t>(); }
TEST(WTF_Bitmap, Count_uint32_t) { testBitmapCount<uint32_t>(); }
TEST(WTF_Bitmap, IsEmpty_uint32_t) { testBitmapIsEmpty<uint32_t>(); }
TEST(WTF_Bitmap, IsFull_uint32_t) { testBitmapIsFull<uint32_t>(); }
TEST(WTF_Bitmap, Merge_uint32_t) { testBitmapMerge<uint32_t>(); }
TEST(WTF_Bitmap, Filter_uint32_t) { testBitmapFilter<uint32_t>(); }
TEST(WTF_Bitmap, Exclude_uint32_t) { testBitmapExclude<uint32_t>(); }
TEST(WTF_Bitmap, ConcurrentFilter_uint32_t) { testBitmapConcurrentFilter<uint32_t>(); }
TEST(WTF_Bitmap, Subsumes_uint32_t) { testBitmapSubsumes<uint32_t>(); }
TEST(WTF_Bitmap, ForEachSetBit_uint32_t) { testBitmapForEachSetBit<uint32_t>(); }
TEST(WTF_Bitmap, FindBit_uint32_t) { testBitmapFindBit<uint32_t>(); }
TEST(WTF_Bitmap, Iteration_uint32_t) { testBitmapIteration<uint32_t>(); }
TEST(WTF_Bitmap, MergeAndClear_uint32_t) { testBitmapMergeAndClear<uint32_t>(); }
TEST(WTF_Bitmap, SetAndClear_uint32_t) { testBitmapSetAndClear<uint32_t>(); }
TEST(WTF_Bitmap, SetEachNthBit_uint32_t) { testBitmapSetEachNthBit<uint32_t>(); }
TEST(WTF_Bitmap, OperatorEqualAccess_uint32_t) { testBitmapOperatorEqual<uint32_t>(); }
TEST(WTF_Bitmap, OperatorNotEqualAccess_uint32_t) { testBitmapOperatorNotEqual<uint32_t>(); }
TEST(WTF_Bitmap, OperatorAssignment_uint32_t) { testBitmapOperatorAssignment<uint32_t>(); }
TEST(WTF_Bitmap, OperatorBitOrAssignment_uint32_t) { testBitmapOperatorBitOrAssignment<uint32_t>(); }
TEST(WTF_Bitmap, OperatorBitAndAssignment_uint32_t) { testBitmapOperatorBitAndAssignment<uint32_t>(); }
TEST(WTF_Bitmap, OperatorBitXorAssignment_uint32_t) { testBitmapOperatorBitXorAssignment<uint32_t>(); }
TEST(WTF_Bitmap, Hash_uint32_t) { testBitmapHash<uint32_t>(); }

#if CPU(REGISTER64)

TEST(WTF_Bitmap, Size_uint64_t) { testBitmapSize<uint64_t>(); }
TEST(WTF_Bitmap, ConstructedEmpty_uint64_t) { testBitmapConstructedEmpty<uint64_t>(); }
TEST(WTF_Bitmap, SetGet_uint64_t) { testBitmapSetGet<uint64_t>(); }
TEST(WTF_Bitmap, TestAndSet_uint64_t) { testBitmapTestAndSet<uint64_t>(); }
TEST(WTF_Bitmap, TestAndClear_uint64_t) { testBitmapTestAndClear<uint64_t>(); }
TEST(WTF_Bitmap, ConcurrentTestAndSet_uint64_t) { testBitmapConcurrentTestAndSet<uint64_t>(); }
TEST(WTF_Bitmap, ConcurrentTestAndClear_uint64_t) { testBitmapConcurrentTestAndClear<uint64_t>(); }
TEST(WTF_Bitmap, Clear_uint64_t) { testBitmapClear<uint64_t>(); }
TEST(WTF_Bitmap, ClearAll_uint64_t) { testBitmapClearAll<uint64_t>(); }
TEST(WTF_Bitmap, Invert_uint64_t) { testBitmapInvert<uint64_t>(); }
TEST(WTF_Bitmap, FindRunOfZeros_uint64_t) { testBitmapFindRunOfZeros<uint64_t>(); }
TEST(WTF_Bitmap, Count_uint64_t) { testBitmapCount<uint64_t>(); }
TEST(WTF_Bitmap, IsEmpty_uint64_t) { testBitmapIsEmpty<uint64_t>(); }
TEST(WTF_Bitmap, IsFull_uint64_t) { testBitmapIsFull<uint64_t>(); }
TEST(WTF_Bitmap, Merge_uint64_t) { testBitmapMerge<uint64_t>(); }
TEST(WTF_Bitmap, Filter_uint64_t) { testBitmapFilter<uint64_t>(); }
TEST(WTF_Bitmap, Exclude_uint64_t) { testBitmapExclude<uint64_t>(); }
TEST(WTF_Bitmap, ConcurrentFilter_uint64_t) { testBitmapConcurrentFilter<uint64_t>(); }
TEST(WTF_Bitmap, Subsumes_uint64_t) { testBitmapSubsumes<uint64_t>(); }
TEST(WTF_Bitmap, ForEachSetBit_uint64_t) { testBitmapForEachSetBit<uint64_t>(); }
TEST(WTF_Bitmap, FindBit_uint64_t) { testBitmapFindBit<uint64_t>(); }
TEST(WTF_Bitmap, Iteration_uint64_t) { testBitmapIteration<uint64_t>(); }
TEST(WTF_Bitmap, MergeAndClear_uint64_t) { testBitmapMergeAndClear<uint64_t>(); }
TEST(WTF_Bitmap, SetAndClear_uint64_t) { testBitmapSetAndClear<uint64_t>(); }
TEST(WTF_Bitmap, SetEachNthBit_uint64_t) { testBitmapSetEachNthBit<uint64_t>(); }
TEST(WTF_Bitmap, OperatorEqualAccess_uint64_t) { testBitmapOperatorEqual<uint64_t>(); }
TEST(WTF_Bitmap, OperatorNotEqualAccess_uint64_t) { testBitmapOperatorNotEqual<uint64_t>(); }
TEST(WTF_Bitmap, OperatorAssignment_uint64_t) { testBitmapOperatorAssignment<uint64_t>(); }
TEST(WTF_Bitmap, OperatorBitOrAssignment_uint64_t) { testBitmapOperatorBitOrAssignment<uint64_t>(); }
TEST(WTF_Bitmap, OperatorBitAndAssignment_uint64_t) { testBitmapOperatorBitAndAssignment<uint64_t>(); }
TEST(WTF_Bitmap, OperatorBitXorAssignment_uint64_t) { testBitmapOperatorBitXorAssignment<uint64_t>(); }
TEST(WTF_Bitmap, Hash_uint64_t) { testBitmapHash<uint64_t>(); }

#endif // CPU(REGISTER64)

} // namespace TestWebKitAPI