/* Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#define C_TESTLUCY_TESTBITVECTOR
#define TESTLUCY_USE_SHORT_NAMES
#include "Lucy/Util/ToolSet.h"

#include "Clownfish/TestHarness/TestBatchRunner.h"
#include "Clownfish/TestHarness/TestUtils.h"
#include "Lucy/Test.h"
#include "Lucy/Test/TestUtils.h"
#include "Lucy/Test/Object/TestBitVector.h"

#include <stdlib.h>

TestBitVector*
TestBitVector_new() {
    return (TestBitVector*)Class_Make_Obj(TESTBITVECTOR);
}

static void
test_Set_and_Get(TestBatchRunner *runner) {
    const size_t  three     = 3;
    const size_t  seventeen = 17;
    BitVector    *bit_vec   = BitVec_new(8);

    BitVec_Set(bit_vec, three);
    TEST_TRUE(runner, BitVec_Get_Capacity(bit_vec) < seventeen,
              "set below cap");
    BitVec_Set(bit_vec, seventeen);
    TEST_TRUE(runner, BitVec_Get_Capacity(bit_vec) > seventeen,
              "set above cap causes BitVector to grow");

    size_t i, max;
    for (i = 0, max = BitVec_Get_Capacity(bit_vec); i < max; i++) {
        if (i == three || i == seventeen) {
            TEST_TRUE(runner, BitVec_Get(bit_vec, i), "set/get %u", (unsigned)i);
        }
        else {
            TEST_FALSE(runner, BitVec_Get(bit_vec, i), "get %u", (unsigned)i);
        }
    }
    TEST_FALSE(runner, BitVec_Get(bit_vec, i), "out of range get");

    DECREF(bit_vec);
}

static void
test_Flip(TestBatchRunner *runner) {
    BitVector *bit_vec = BitVec_new(0);

    unsigned i;
    for (i = 0; i <= 20; i++) { BitVec_Flip(bit_vec, i); }
    for (i = 0; i <= 20; i++) {
        TEST_TRUE(runner, BitVec_Get(bit_vec, i), "flip on %u", i);
    }
    TEST_FALSE(runner, BitVec_Get(bit_vec, i), "no flip %u", i);
    for (i = 0; i <= 20; i++) { BitVec_Flip(bit_vec, i); }
    for (i = 0; i <= 20; i++) {
        TEST_FALSE(runner, BitVec_Get(bit_vec, i), "flip off %u", i);
    }
    TEST_FALSE(runner, BitVec_Get(bit_vec, 21), "still no flip %u", i);

    DECREF(bit_vec);
}

static void
test_Flip_Block_ascending(TestBatchRunner *runner) {
    BitVector *bit_vec = BitVec_new(0);

    for (unsigned i = 0; i <= 20; i++) {
        BitVec_Flip_Block(bit_vec, i, 21 - i);
    }

    for (unsigned i = 0; i <= 20; i++) {
        if (i % 2 == 0) {
            TEST_TRUE(runner, BitVec_Get(bit_vec, i),
                      "Flip_Block ascending %u", i);
        }
        else {
            TEST_FALSE(runner, BitVec_Get(bit_vec, i),
                       "Flip_Block ascending %u", i);
        }
    }

    DECREF(bit_vec);
}

static void
test_Flip_Block_descending(TestBatchRunner *runner) {
    BitVector *bit_vec = BitVec_new(0);

    for (int i = 19; i >= 0; i--) {
        BitVec_Flip_Block(bit_vec, 1, (size_t)i);
    }

    for (unsigned i = 0; i <= 20; i++) {
        if (i % 2) {
            TEST_TRUE(runner, BitVec_Get(bit_vec, i),
                      "Flip_Block descending %u", i);
        }
        else {
            TEST_FALSE(runner, BitVec_Get(bit_vec, i),
                       "Flip_Block descending %u", i);
        }
    }

    DECREF(bit_vec);
}

static void
test_Flip_Block_bulk(TestBatchRunner *runner) {
    for (unsigned offset = 0; offset <= 17; offset++) {
        for (unsigned len = 0; len <= 17; len++) {
            int upper = (int)offset + (int)len - 1;
            BitVector *bit_vec = BitVec_new(0);

            BitVec_Flip_Block(bit_vec, offset, len);
            unsigned i;
            for (i = 0; i <= 17; i++) {
                if (i >= offset && (int)i <= upper) {
                    if (!BitVec_Get(bit_vec, i)) { break; }
                }
                else {
                    if (BitVec_Get(bit_vec, i)) { break; }
                }
            }
            TEST_UINT_EQ(runner, i, 18, "Flip_Block(%u, %u)", offset, len);

            DECREF(bit_vec);
        }
    }
}

static void
test_Mimic(TestBatchRunner *runner) {
    for (unsigned foo = 0; foo <= 17; foo++) {
        for (unsigned bar = 0; bar <= 17; bar++) {
            BitVector *foo_vec = BitVec_new(0);
            BitVector *bar_vec = BitVec_new(0);

            BitVec_Set(foo_vec, foo);
            BitVec_Set(bar_vec, bar);
            BitVec_Mimic(foo_vec, (Obj*)bar_vec);

            unsigned i;
            for (i = 0; i <= 17; i++) {
                if (BitVec_Get(foo_vec, i) && i != bar) { break; }
            }
            TEST_UINT_EQ(runner, i, 18, "Mimic(%u, %u)", foo, bar);

            DECREF(foo_vec);
            DECREF(bar_vec);
        }
    }
}

static BitVector*
S_create_set(int set_num) {
    unsigned nums_1[] = { 1, 2, 3, 10, 20, 30, 0 };
    unsigned nums_2[] = { 2, 3, 4, 5, 6, 7, 8, 9, 10,
                     25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 0
                   };
    unsigned *nums = set_num == 1 ? nums_1 : nums_2;
    BitVector *bit_vec = BitVec_new(31);
    for (unsigned i = 0; nums[i] != 0; i++) {
        BitVec_Set(bit_vec, nums[i]);
    }
    return bit_vec;
}

#define OP_OR 1
#define OP_XOR 2
#define OP_AND 3
#define OP_AND_NOT 4
static unsigned
S_verify_logical_op(BitVector *bit_vec, BitVector *set_1, BitVector *set_2,
                    int op) {
    unsigned i;

    for (i = 0; i < 50; i++) {
        bool wanted;

        switch (op) {
            case OP_OR:
                wanted = BitVec_Get(set_1, i) || BitVec_Get(set_2, i);
                break;
            case OP_XOR:
                wanted = (!BitVec_Get(set_1, i)) != (!BitVec_Get(set_2, i));
                break;
            case OP_AND:
                wanted = BitVec_Get(set_1, i) && BitVec_Get(set_2, i);
                break;
            case OP_AND_NOT:
                wanted = BitVec_Get(set_1, i) && (!BitVec_Get(set_2, i));
                break;
            default:
                wanted = false;
                THROW(ERR, "unknown op: %d", op);
        }

        if (BitVec_Get(bit_vec, i) != wanted) { break; }
    }

    return i;
}

static void
test_Or(TestBatchRunner *runner) {
    BitVector *smaller = S_create_set(1);
    BitVector *larger  = S_create_set(2);
    BitVector *set_1   = S_create_set(1);
    BitVector *set_2   = S_create_set(2);

    BitVec_Or(smaller, set_2);
    TEST_UINT_EQ(runner, S_verify_logical_op(smaller, set_1, set_2, OP_OR),
                 50, "OR with self smaller than other");
    BitVec_Or(larger, set_1);
    TEST_UINT_EQ(runner, S_verify_logical_op(larger, set_1, set_2, OP_OR),
                 50, "OR with other smaller than self");

    DECREF(smaller);
    DECREF(larger);
    DECREF(set_1);
    DECREF(set_2);
}

static void
test_Xor(TestBatchRunner *runner) {
    BitVector *smaller = S_create_set(1);
    BitVector *larger  = S_create_set(2);
    BitVector *set_1   = S_create_set(1);
    BitVector *set_2   = S_create_set(2);

    BitVec_Xor(smaller, set_2);
    TEST_UINT_EQ(runner, S_verify_logical_op(smaller, set_1, set_2, OP_XOR),
                 50, "XOR with self smaller than other");
    BitVec_Xor(larger, set_1);
    TEST_UINT_EQ(runner, S_verify_logical_op(larger, set_1, set_2, OP_XOR),
                 50, "XOR with other smaller than self");

    DECREF(smaller);
    DECREF(larger);
    DECREF(set_1);
    DECREF(set_2);
}

static void
test_And(TestBatchRunner *runner) {
    BitVector *smaller = S_create_set(1);
    BitVector *larger  = S_create_set(2);
    BitVector *set_1   = S_create_set(1);
    BitVector *set_2   = S_create_set(2);

    BitVec_And(smaller, set_2);
    TEST_UINT_EQ(runner, S_verify_logical_op(smaller, set_1, set_2, OP_AND),
                 50, "AND with self smaller than other");
    BitVec_And(larger, set_1);
    TEST_UINT_EQ(runner, S_verify_logical_op(larger, set_1, set_2, OP_AND),
                 50, "AND with other smaller than self");

    DECREF(smaller);
    DECREF(larger);
    DECREF(set_1);
    DECREF(set_2);
}

static void
test_And_Not(TestBatchRunner *runner) {
    BitVector *smaller = S_create_set(1);
    BitVector *larger  = S_create_set(2);
    BitVector *set_1   = S_create_set(1);
    BitVector *set_2   = S_create_set(2);

    BitVec_And_Not(smaller, set_2);
    TEST_UINT_EQ(runner,
                 S_verify_logical_op(smaller, set_1, set_2, OP_AND_NOT),
                 50, "AND_NOT with self smaller than other");
    BitVec_And_Not(larger, set_1);
    TEST_UINT_EQ(runner,
                 S_verify_logical_op(larger, set_2, set_1, OP_AND_NOT),
                 50, "AND_NOT with other smaller than self");

    DECREF(smaller);
    DECREF(larger);
    DECREF(set_1);
    DECREF(set_2);
}

static void
test_Count(TestBatchRunner *runner) {
    unsigned shuffled[64];
    BitVector *bit_vec = BitVec_new(64);

    for (unsigned i = 0; i < 64; i++) { shuffled[i] = i; }
    for (unsigned i = 0; i < 64; i++) {
        unsigned shuffle_pos = (unsigned)rand() % 64;
        unsigned temp = shuffled[shuffle_pos];
        shuffled[shuffle_pos] = shuffled[i];
        shuffled[i] = temp;
    }
    unsigned i;
    for (i = 0; i < 64; i++) {
        BitVec_Set(bit_vec, shuffled[i]);
        if (BitVec_Count(bit_vec) != (uint32_t)(i + 1)) { break; }
    }
    TEST_UINT_EQ(runner, i, 64, "Count() returns the right number of bits");

    DECREF(bit_vec);
}

static void
test_Next_Hit(TestBatchRunner *runner) {
    for (int i = 24; i <= 33; i++) {
        BitVector *bit_vec = BitVec_new(64);
        BitVec_Set(bit_vec, (size_t)i);
        TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, 0), i,
                    "Next_Hit for 0 is %d", i);
        TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, 1), i,
                    "Next_Hit for 1 is %d", i);
        for (int probe = 15; probe <= i; probe++) {
            TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, (size_t)probe), i,
                        "Next_Hit for %d is %d", probe, i);
        }
        for (int probe = i + 1; probe <= i + 9; probe++) {
            TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, (size_t)probe), -1,
                        "no Next_Hit for %d when max is %d", probe, i);
        }
        TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, INT32_MAX), -1,
                    "no Next_Hit for INT32_MAX when max is %d", i);
        DECREF(bit_vec);
    }
}

static void
test_Clear_All(TestBatchRunner *runner) {
    BitVector *bit_vec = BitVec_new(64);
    BitVec_Flip_Block(bit_vec, 0, 63);
    BitVec_Clear_All(bit_vec);
    TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, 0), -1, "Clear_All");
    DECREF(bit_vec);
}

static void
test_Clone(TestBatchRunner *runner) {
    BitVector *self = BitVec_new(30);
    BitVector *twin;

    BitVec_Set(self, 2);
    BitVec_Set(self, 3);
    BitVec_Set(self, 10);
    BitVec_Set(self, 20);

    twin = BitVec_Clone(self);
    size_t i;
    for (i = 0; i < 50; i++) {
        if (BitVec_Get(self, i) != BitVec_Get(twin, i)) { break; }
    }
    TEST_UINT_EQ(runner, i, 50, "Clone");
    TEST_UINT_EQ(runner, BitVec_Count(twin), 4, "clone Count");

    DECREF(self);
    DECREF(twin);
}

static int
S_compare_u64s(const void *va, const void *vb) {
    uint64_t a = *(uint64_t*)va;
    uint64_t b = *(uint64_t*)vb;
    return a == b ? 0 : a < b ? -1 : 1;
}

static void
test_To_Array(TestBatchRunner *runner) {
    uint64_t  *source_ints = TestUtils_random_u64s(NULL, 20, 0, 200);
    BitVector *bit_vec = BitVec_new(0);
    I32Array  *array;
    unsigned   num_unique = 0;

    // Unique the random ints.
    qsort(source_ints, 20, sizeof(uint64_t), S_compare_u64s);
    for (unsigned i = 0; i < 19; i++) {
        if (source_ints[i] != source_ints[i + 1]) {
            source_ints[num_unique] = source_ints[i];
            num_unique++;
        }
    }

    // Set bits.
    for (unsigned i = 0; i < num_unique; i++) {
        BitVec_Set(bit_vec, (size_t)source_ints[i]);
    }

    // Create the array and compare it to the source.
    array = BitVec_To_Array(bit_vec);
    unsigned i;
    for (i = 0; i < num_unique; i++) {
        if (I32Arr_Get(array, (size_t)i) != (int32_t)source_ints[i]) { break; }
    }
    TEST_UINT_EQ(runner, i, num_unique, "To_Array (%u == %u)", i,
                 num_unique);

    DECREF(array);
    DECREF(bit_vec);
    FREEMEM(source_ints);
}


// Valgrind only - detect off-by-one error.
static void
test_off_by_one_error() {
    for (unsigned cap = 5; cap <= 24; cap++) {
        BitVector *bit_vec = BitVec_new(cap);
        BitVec_Set(bit_vec, cap - 2);
        DECREF(bit_vec);
    }
}

void
TestBitVector_Run_IMP(TestBitVector *self, TestBatchRunner *runner) {
    TestBatchRunner_Plan(runner, (TestBatch*)self, 1039);
    test_Set_and_Get(runner);
    test_Flip(runner);
    test_Flip_Block_ascending(runner);
    test_Flip_Block_descending(runner);
    test_Flip_Block_bulk(runner);
    test_Mimic(runner);
    test_Or(runner);
    test_Xor(runner);
    test_And(runner);
    test_And_Not(runner);
    test_Count(runner);
    test_Next_Hit(runner);
    test_Clear_All(runner);
    test_Clone(runner);
    test_To_Array(runner);
    test_off_by_one_error();
}