stress32.cpp

Go to the documentation of this file.

Go to the SVN repository for this file.

 /*
Copyright(c) 2002-2018 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
 
Licensed 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.
 
For more information please visit:  http://bitmagic.io
*/
 
 
//#define BMSSE2OPT
//#define BMSSE42OPT
//#define BMAVX2OPT
//#define BM_USE_EXPLICIT_TEMP
//#define BM_USE_GCC_BUILD
 
#define BMXORCOMP
#define BM_NONSTANDARD_EXTENTIONS
 
#include <ncbi_pch.hpp>
 
#include <stdio.h>
#include <stdlib.h>
#undef NDEBUG
#include <time.h>
#include <math.h>
#include <string.h>
 
#include <iostream>
#include <iomanip>
#include <utility>
#include <memory>
#include <random>
#include <algorithm>
#include <stdarg.h>  
#include <mutex>
 
#include <util/bitset/ncbi_bitset_alloc.hpp>
#include <util/bitset/ncbi_bitset_util.hpp>
#include <util/bitset/bmxor.h>
#include <util/bitset/bmaggregator.h>
#include <util/bitset/bmutil.h>
#include <util/bitset/bmserial.h>
#include <util/bitset/bmbvimport.h>
#include <util/bitset/bmrandom.h>
#include <util/bitset/bmvmin.h>
#include <util/bitset/bmbmatrix.h>
#include <util/bitset/bmintervals.h>
#include <util/bitset/bmsparsevec.h>
#include <util/bitset/bmsparsevec_algo.h>
#include <util/bitset/bmsparsevec_serial.h>
#include <util/bitset/bmalgo_similarity.h>
#include <util/bitset/bmsparsevec_util.h>
#include <util/bitset/bmsparsevec_compr.h>
#include <util/bitset/bmstrsparsevec.h>
#include <util/bitset/bm3vl.h>
#include <util/bitset/bmtimer.h>
#include <util/bitset/bmtask.h>
#include <util/bitset/bmsparsevec_parallel.h>
#include <util/bitset/bmthreadpool.h>
 
#include <common/test_assert.h>
 
using namespace bm;
using namespace std;
 
#include "rlebtv.h"
#include <util/bitset/encoding.h>
#include <limits.h>
 
#include <util/bitset/bmdbg.h>
#include <vector>
 
bool is_silent = false;
 
#if defined(BMSSE2OPT) || defined(BMSSE42OPT) || defined(BMAVX2OPT) || defined(BMAVX512OPT) || defined(__ARM_NEON__)
#else
# define MEM_DEBUG
#endif
 
#ifdef MEM_DEBUG
 
#include "stacktrace_dbg.h"
#include <unordered_map>
 
 
 
// -------------------------------
// memory profiler: very slow if defined
//
//#define BM_STACK_COLL
 
// NOTE: ARM NEON compilation causes SIGBUS failure (Pi 32-bit)
// (disabled as non-essential)
 
#ifdef BM_STACK_COLL
std::unordered_map<void*, std::string> g_alloc_trace_map;
#endif
std::mutex g_trace_lock;
 
class dbg_block_allocator
{
public:
    static inline size_t na_ = 0;
    static inline size_t nf_ = 0;
 
    static bm::word_t* allocate(size_t n, const void *)
    {
        #ifdef BM_STACK_COLL
        std::string stack_str;
        stack_str.reserve(2048);
        get_stacktrace(stack_str);
        #endif
        g_trace_lock.lock();
        ++na_;
        assert(n);
        bm::word_t* p =
            (bm::word_t*) ::malloc((n+1) * sizeof(bm::word_t));
        if (!p)
        {
            std::cerr << "ERROR Failed allocation!" << endl;
            assert(0);exit(1);
        }
        *p = (bm::word_t)n;
 
        #ifdef BM_STACK_COLL
        g_alloc_trace_map.emplace(p, std::move(stack_str));
        #endif
        g_trace_lock.unlock();
        return ++p;
    }
 
    static void deallocate(bm::word_t* p, size_t n)
    {
        g_trace_lock.lock();
        ++nf_;
        --p;
        if (*p != n)
        {
            printf("Block memory deallocation ERROR! n = %i (expected %i)\n", (int)n, (int)*p);
            assert(0);exit(1);
        }
        ::free(p);
        #ifdef BM_STACK_COLL
        g_alloc_trace_map.erase(p);
        #endif
        g_trace_lock.unlock();
    }
 
    static size_t balance() BMNOEXCEPT { return na_ - nf_; }
};
 
class dbg_ptr_allocator
{
public:
    static inline size_t na_ = 0;
    static inline size_t nf_ = 0;
 
    static void* allocate(size_t n, const void *)
    {
        #ifdef BM_STACK_COLL
        std::string stack_str;
        stack_str.reserve(2048);
        get_stacktrace(stack_str);
        #endif
 
        g_trace_lock.lock();
        ++na_;
        assert(sizeof(size_t) == sizeof(void*));
        void* p = ::malloc((n+1) * sizeof(void*));
        if (!p)
        {
            std::cerr << "ERROR! Failed allocation!" << endl;
            exit(1);
        }
        size_t* s = (size_t*) p;
        *s = n;
 
        #ifdef BM_STACK_COLL
        g_alloc_trace_map.emplace(p, std::move(stack_str));
        #endif
        g_trace_lock.unlock();
 
        return (void*)++s;
    }
 
    static void deallocate(void* p, size_t n)
    {
        g_trace_lock.lock();
        ++nf_;
        size_t* s = (size_t*) p;
        --s;
        if(*s != n)
        {
            printf("Ptr memory deallocation ERROR!\n");
            assert(0);
            exit(1);
        }
        ::free(s);
 
        #ifdef BM_STACK_COLL
        g_alloc_trace_map.erase(s);
        #endif
        g_trace_lock.unlock();
    }
 
    static size_t balance() BMNOEXCEPT { return nf_ - na_; }
 
};
 
 
 
typedef mem_alloc<dbg_block_allocator, dbg_ptr_allocator, alloc_pool<dbg_block_allocator, dbg_ptr_allocator> > dbg_alloc;
 
typedef bm::bvector<dbg_alloc> bvect;
typedef bm::bvector_mini<dbg_block_allocator> bvect_mini;
typedef bm::rs_index<dbg_alloc> rs_ind;
 
#else
 
typedef bm::bvector<> bvect;
typedef bm::bvector_mini<bm::block_allocator> bvect_mini;
typedef bm::rs_index<> rs_ind;
 
 
#endif
 
typedef std::vector<unsigned> ref_vect_type;
 
typedef bm::sparse_vector<unsigned, bvect > sparse_vector_u32;
typedef bm::sparse_vector<int, bvect >      sparse_vector_i32;
typedef bm::sparse_vector<unsigned long long, bvect > sparse_vector_u64;
typedef bm::sparse_vector<signed long long, bvect > sparse_vector_i64;
typedef bm::rsc_sparse_vector<unsigned, sparse_vector_u32> rsc_sparse_vector_u32;
typedef bm::rsc_sparse_vector<int, sparse_vector_i32> rsc_sparse_vector_i32;
typedef bm::rsc_sparse_vector<unsigned long long, sparse_vector_u64> rsc_sparse_vector_u64;
typedef bm::rsc_sparse_vector<signed long long, sparse_vector_i64> rsc_sparse_vector_i64;
 
//const unsigned BITVECT_SIZE = 100000000 * 8;
 
// This this setting program will consume around 150M of RAM
const unsigned BITVECT_SIZE = 100000000 * 2;
 
const unsigned ITERATIONS = 180000;
//const unsigned PROGRESS_PRINT = 2000000;
 
/// Reference (naive) inetrval detector based on population counting
/// and boundaries tests
///
template<typename BV>
bool test_interval(const BV& bv,
                   typename BV::size_type left, typename BV::size_type right)
{
    if (left > right)
        bm::xor_swap(left, right); // make sure left <= right
    bool is_left(0), is_right(0);
    if (left) // check left-1 bit (if exists)
        is_left = bv.test(left - 1);
    if ((is_left == false) && (right < bm::id_max - 1))
        is_right = bv.test(right + 1); // check [...right] range condition
    if (is_left == false && is_right == false)
    {
        typename BV::size_type cnt = bv.count_range(left, right);
        if (cnt == (1 + right - left))
            return true;
    }
    return false;
}
 
 
template<class BV>
void DetailedCompareBVectors(const BV& bv1, const BV& bv2)
{
    bvect::counted_enumerator en1 = bv1.first();
    bvect::counted_enumerator en2 = bv2.first();
    
    for (; en1.valid(); ++en1)
    {
        assert(en2.valid());
        
        bm::id_t i1 = *en1;
        bm::id_t i2 = *en2;
        
        if (i1 != i2)
        {
            unsigned nb1 = unsigned(i1 >>  bm::set_block_shift);
            unsigned nb2 = unsigned(i2 >>  bm::set_block_shift);
            unsigned ii1 = nb1 >> bm::set_array_shift;
            unsigned jj1 = nb1 &  bm::set_array_mask;
            unsigned ii2 = nb2 >> bm::set_array_shift;
            unsigned jj2 = nb2 &  bm::set_array_mask;
 
            std::cerr << "Difference detected at: position="
                      << i1 << " nb=" << nb1
                      << "[" << ii1 << ", " << jj1 << "]"
                      " other position = " << i2 <<
                      " nb=" << nb2
                      << "[" << ii2 << ", " << jj2 << "]"
                      << std::endl;
            std::cerr << " en1.count()=" << en1.count() << " en2.count()=" << en2.count()
                      << std::endl;
            
            exit(1);
            return;
        }
        ++en2;
    } // for
 
    bool eq = bv1.equal(bv2);
    if (!eq)
    {
        cerr << "EQ (1-2) discrepancy! " << endl;
        exit(1);
    }
    int cmp = bv1.compare(bv2);
    if (cmp != 0)
    {
        cerr << "Compare (1-2) discrepancy! " << cmp << endl;
        exit(1);
    }
    cmp = bv2.compare(bv1);
    if (cmp != 0)
    {
        cerr << "Compare (2-1) discrepancy! " << cmp << endl;
        exit(1);
    }
 
    cout << "Detailed compare OK (no difference)." << endl;
}
 
void CheckVectors(bvect_mini &bvect_min, 
                  bvect      &bvect_full,
                  unsigned size,
                  bool     detailed = true);
 
 
extern "C" {
    static
    int bit_decode_func(void* handle_ptr, bm::id_t bit_idx)
    {
        std::vector<bm::id_t>* vp = (std::vector<bm::id_t>*)handle_ptr;
        vp->push_back(bit_idx);
        return 0;
    }
    /*
    static
    int bit_decode_func2(void* handle_ptr, bm::id_t bit_idx)
    {
        if (bit_idx > (65536 * 256))
        {
            throw 1;
        }
        std::vector<bm::id_t>* vp = (std::vector<bm::id_t>*)handle_ptr;
        vp->push_back(bit_idx);
        return 0;
    }
    */
} // extern C
 
 
template<class BV>
void VisitorAllRangeTest(const BV& bv, typename BV::size_type step = 1)
{
    typename BV::size_type left, right, next, i_end;
    bool non_empty = bv.find_range(left, right);
    if (!non_empty)
        return;
    if (left < 65536)
        left = 0;
    if (right < 65536)
        right = 65535;
 
    auto drange = right - left;
    if (!drange)
        drange = 256;
    if (!step)
        step = drange / 100;
    if (!step)
        step = 1;
 
    cout << "... VisitorAllRangeTest() step=" << step << endl;
 
    auto pcnt = 256;
    for (auto i = left; i <= right; i+=step)
    {
        {
            bvect bv_control;
            bm::bit_vistor_copy_functor<bvect> func(bv_control);
            bm::for_each_bit_range(bv, i, right, func);
 
            bvect bv2;
            bv2.copy_range(bv, i, right);
 
            bool eq = bv2.equal(bv_control);
            assert(eq);
        }
        next = bv.get_next(i);
        if (next)
        {
            auto delta = next - i;
            if (delta > 32)
            {
                i += delta / 2;
            }
            else
            if (delta == 1)
            {
                bool f = bm::find_interval_end(bv, next, i_end);
                if (f)
                {
                    delta = i_end - i;
                    if (delta > 4)
                        i += delta / 2;
                }
                else
                {
                    assert(!bv.test(i));
                }
            }
        }
        if (!pcnt)
        {
            if (!is_silent)
                cout << "\r" << i << " / " << right << flush;
            pcnt = 128;
        }
        --pcnt;
 
    } // for i
    cout << endl;
 
    pcnt = 256;
    for (; left <= right; left+=step, --right)
    {
        {
            bvect bv_control;
            bm::bit_vistor_copy_functor<bvect> func(bv_control);
            bm::for_each_bit_range(bv, left, right, func);
 
            bvect bv2;
            bv2.copy_range(bv, left, right);
 
            bool eq = bv2.equal(bv_control);
            assert(eq);
        }
        next = bv.get_next(left);
        if (next)
        {
            auto delta = next - left;
            if (delta > 128)
            {
                left += delta / 2;
            }
            else
            if (delta == 1)
            {
                bool f = bm::find_interval_end(bv, left, i_end);
                if (f)
                {
                    delta = i_end - left;
                    if (delta > 4)
                        left += delta / 2;
                }
            }
        }
        if (!pcnt)
        {
            if (!is_silent)
                cout << "\r" << left << " / " << right << flush;
            pcnt = 128;
        }
        --pcnt;
 
    } // for i
    cout << endl;
}
 
 
void generate_bvector(bvect& bv, unsigned vector_max = 40000000, bool optimize=true);
 
static
unsigned random_minmax(unsigned min, unsigned max)
{
    unsigned r = (unsigned(rand()) << 16u) | unsigned(rand());
    return r % (max-min) + min;
}
 
template<typename BV>
void TestFindDiff(const BV& bv1, BV& bv2)
{
    bool f;
    typename BV::size_type pos, pos_c, pos_l;
    f = bv1.find_first_mismatch(bv2, pos);
    bvect bv_x;
    bv_x.bit_xor(bv1, bv2, bvect::opt_compress);
    if (!f)
    {
        auto a = bv_x.any();
        assert(!a);
        return;
    }
    else // found
    {
        bool f2 = bv1.find_first_mismatch(bv2, pos_l, pos);
        assert(f2 == f);
        assert(pos_l == pos);
        if (pos)
        {
            f2 = bv1.find_first_mismatch(bv2, pos_l, pos-1);
            assert(!f2);
        }
    }
    bool cf = bv_x.find(pos_c);
    assert(f == cf);
    assert(pos == pos_c);
 
    f = bv2.find_first_mismatch(bv1, pos);
    assert(f == cf);
    assert(pos == pos_c);
}
 
 
static
void FillSets(bvect_mini* bvect_min, 
              bvect* bvect_full,
              unsigned min, 
              unsigned max,
              unsigned fill_factor)
{
    unsigned i;
    unsigned id;
 
    //Random filling
    if(fill_factor == 0)
    {
        unsigned n_id = (max - min) / 100;
        printf("random filling : %i\n", n_id);
        for (i = 0; i < n_id; i++)
        {
            id = random_minmax(min, max);
            bvect_min->set_bit(id);
            bvect_full->set_bit(id);
        }
        std::cout << endl;
    }
    else
    {
        printf("fill_factor random filling : factor = %i\n", fill_factor);
 
        for(i = 0; i < fill_factor; i++)
        {
            unsigned k = unsigned(rand()) % 10;
            if (k == 0)
                k+=2;
 
            //Calculate start
            unsigned start = min + (max - min) / (fill_factor * k);
 
            //Randomize start
            start += random_minmax(1, (max - min) / (fill_factor * 10));
 
            if (start > max)
            {
                start = min;
            }
            
            //Calculate end 
            unsigned end = start + (max - start) / (fill_factor *2);
 
            //Randomize end
            end -= random_minmax(1, (max - start) / (fill_factor * 10));
 
            if (end > max )
            {
                end = max;
            }
 
            bvect::bulk_insert_iterator iit = bvect_full->inserter();
 
            if (fill_factor > 1)
            {
                for(; start < end;)
                {
                    unsigned r = unsigned(rand()) % 8;
 
                    if (r > 7)
                    {
                        unsigned inc = unsigned(rand()) % 3;
                        ++inc;
                        unsigned end2 = start + (unsigned)rand() % 1000;
                        if (end2 > end)
                            end2 = end;
                        while (start < end2)
                        {
                            bvect_min->set_bit(start);
                            iit = start;
                            start += inc;
                        }
                        continue;
                    }
 
                    if (r)
                    {
                        bvect_min->set_bit(start);
                        iit = start;
                        ++start;
                    }
                    else
                    {
                        start+=r;
                        bvect_min->set_bit(start);
                        iit = start;
                    }
                }
            }
            else
            {
                unsigned c = unsigned(rand()) % 15;
                if (c == 0)
                    ++c;
                for(; start < end; ++start)
                {
                    bvect_min->set_bit(start);
                    iit = start;
                    if (start % c)
                    {
                        start += c;
                    }
                }
            }
            cout << endl;
 
        }
    }
}
 
//
// Interval filling.
// 111........111111........111111..........11111111.......1111111...
//
 
static
void FillSetsIntervals(bvect_mini* bvect_min, 
              bvect& bvect_full,
              unsigned min, 
              unsigned max,
              unsigned fill_factor,
              bool set_flag=true)
{
 
    while(fill_factor==0)
    {
        fill_factor=(unsigned)rand()%10;
    }
    bvect_full.init();
 
    cout << "Intervals filling. Factor=" 
         <<  fill_factor << endl << endl;
 
    unsigned i, j;
    unsigned factor = 70 * fill_factor;
    for (i = min; i < max; ++i)
    {
        unsigned len, end; 
 
        do
        {
            len = unsigned(rand()) % factor;
            end = i+len;
            
        } while (end >= max);
        if (i < end)
        {
            bvect_full.set_range(i, end-1, set_flag);
            bool all_one_range = bvect_full.is_all_one_range(i, end - 1);
            assert(all_one_range == set_flag);
            bool any_one = bvect_full.any_range(i, end - 1);
            assert(any_one == set_flag);
            bool is_int = bm::is_interval(bvect_full, i, end-1);
            bool is_int_c = test_interval(bvect_full, i, end-1);
            assert(is_int == is_int_c);
            if (is_int)
            {
                bvect::size_type pos;
                bool b = bm::find_interval_end(bvect_full, i, pos);
                assert(b && pos == end-1);
            }
        }
       
        for (j = i; j < end; ++j)
        {
            if (set_flag)
            {
                if (bvect_min)
                    bvect_min->set_bit(j);
                //bvect_full.set_bit(j);
            }
            else
            {
                if (bvect_min)
                    bvect_min->clear_bit(j);
                //bvect_full.clear_bit(j);
            }
 
                           
        } // j
 
        i = end;
        len = unsigned(rand()) % (factor* 10 * bm::gap_max_bits);
        if (len % 2)
        {
            len *= unsigned(rand()) % (factor * 10);
        }
 
        i+=len;
 
        if ( (len % 6) == 0)  
        {
            for(unsigned k=0; k < 1000 && i < max; k+=3,i+=3)
            {
                if (set_flag)
                {
                    if (bvect_min)
                        bvect_min->set_bit(i);
                    bvect_full.set_bit_no_check(i);
                }
                else
                {
                    if (bvect_min)
                        bvect_min->clear_bit(j);
                    bvect_full.clear_bit(j);
                }
            }
        }
    } // for i
 
}
 
static
void FillSetClearIntervals(bvect_mini* bvect_min, 
              bvect* bvect_full,
              unsigned min, 
              unsigned max,
              unsigned fill_factor)
{
    FillSetsIntervals(bvect_min, *bvect_full, min, max, fill_factor, true);
    FillSetsIntervals(bvect_min, *bvect_full, min, max, fill_factor, false);
}
 
static
void FillSetsRandomOne(bvect_mini* bvect_min, 
                       bvect* bvect_full,
                       unsigned min, 
                       unsigned max)
{
    unsigned range = max - min;
    unsigned bit_idx = unsigned(rand()) % range;
    bvect_min->set_bit(bit_idx);
    bvect_full->set_bit(bit_idx);
    std::cout << "Bit_idx=" << bit_idx << endl;
}
 
static
void FillSetsRandom(bvect_mini* bvect_min, 
              bvect* bvect_full,
              unsigned min, 
              unsigned max,
              unsigned fill_factor)
{
    bvect_full->init();
    unsigned diap = max - min;
    unsigned count;
 
    switch (fill_factor)
    {
    case 0:
        count = diap / 1000;
        break;
    case 1:
        count = diap / 255;
        break;
    default:
        count = diap / 10;
        break;
    }
 
    for (unsigned i = 0; i < count; ++i)
    {
        unsigned bn = unsigned(rand()) % count;
        bn += min;
 
        if (bn > max)
        {
            bn = max;
        }
        bvect_min->set_bit(bn);
        bvect_full->set_bit_no_check(bn);
    }
    cout << "Ok" << endl;
 
}
 
static
void FillSetsRegular(bvect_mini* bvect_min,
                     bvect* bvect_full,
              unsigned /*min*/,
              unsigned max,
              unsigned /*fill_factor*/)
{
    bvect::bulk_insert_iterator iit = bvect_full->inserter();
 
    unsigned step = (unsigned)rand() % 4;
    if (step < 2) ++step;
    for (unsigned i = 0; i < max; i+=step)
    {
        bvect_min->set_bit(i);
        iit = i;
        //bvect_full->set_bit_no_check(i);
    }
    cout << "Ok" << endl;
}
 
 
 
 
//
//  Quasi random filling with choosing randomizing method.
//
//
static
void FillSetsRandomMethod(bvect_mini* bvect_min, 
                          bvect* bvect_full,
                          unsigned min, 
                          unsigned max,
                          int optimize = 0,
                          int method = -1)
{
    if (method == -1)
    {
        method = rand() % 7;
    }
//method = 2;
    unsigned factor;
    switch (method)
    {
 
    case 0:
        cout << "Random filling: method - FillSets - factor(0)" << endl;
        FillSets(bvect_min, bvect_full, min, max, 0);
        break;
 
    case 1:
        cout << "Random filling: method - FillSets - factor(random)" << endl;
        factor = (unsigned)rand()%3;
        FillSets(bvect_min, bvect_full, min, max, factor?factor:1);
        break;
 
    case 2:
        cout << "Random filling: method - Set-Clear Intervals - factor(random)" << endl;
        factor = (unsigned)rand()%10;
        FillSetClearIntervals(bvect_min, bvect_full, min, max, factor);
        break;
    case 3:
        cout << "Random filling: method - FillRandom - factor(random)" << endl;
        factor = (unsigned)rand()%3;
        FillSetsRandom(bvect_min, bvect_full, min, max, factor?factor:1);
        break;
    case 4:
        cout << "Random set one bit" << endl;
        FillSetsRandomOne(bvect_min, bvect_full, min, max);
        break;
    case 5:
        cout << "Regular pattern filling" << endl;
        FillSetsRegular(bvect_min, bvect_full, min, max, 2);
        break;
    default:
        cout << "Random filling: method - Set Intervals - factor(random)" << endl;
        factor = (unsigned)rand()%10;
        FillSetsIntervals(bvect_min, *bvect_full, min, max, factor);
        break;
 
    } // switch
 
    if (optimize && (method <= 1))
    {
        BM_DECLARE_TEMP_BLOCK(tb)
        bvect_full->optimize(tb);
    }
}
 
static
void print_bv(const bvect& bv)
{
    std::cout << bv.count() << ": ";
    bvect::enumerator en = bv.first();
    for (; en.valid(); ++en)
        std::cout << *en << ", ";
    std::cout << std::endl;
}
 
// reference SHIFT right
static
void ShiftRight(bvect*  bv, unsigned shift)
{
    bvect bv_tmp;
    {
        bvect::bulk_insert_iterator bi = bv_tmp.inserter();
        bvect::enumerator en = bv->first();
        for (; en.valid(); ++en)
        {
            unsigned v = *en;
            unsigned new_v = v + shift;
            if (new_v < v || new_v == bm::id_max) // check overflow
            {}
            else
            {
                bi = new_v;
            }
        }
    }
    bv->swap(bv_tmp);
}
 
// Reference bit insert
static
void BVectorInsert(bvect*  bv, unsigned pos, bool value)
{
    bvect bv_tmp;
    if (pos)
        bv_tmp.copy_range(*bv, 0, pos-1);
    
    {
        bvect::bulk_insert_iterator bi = bv_tmp.inserter();
        bvect::enumerator en = bv->first();
        for (; en.valid(); ++en)
        {
            unsigned v = *en;
            if (v < pos)
                continue;
            unsigned new_v = v + 1;
            if (new_v < v || new_v == bm::id_max) // check overflow
            {}
            else
            {
                bi = new_v;
            }
        }
    }
    bv->swap(bv_tmp);
    bv->set(pos, value);
}
 
// Reference bit erase
static
void BVectorErase(bvect*  bv, unsigned pos)
{
    bvect bv_tmp;
    if (pos)
        bv_tmp.copy_range(*bv, 0, pos-1);
    
    {
        bvect::bulk_insert_iterator bi = bv_tmp.inserter();
        bvect::enumerator en = bv->first();
        en.go_to(pos+1);
        for (; en.valid(); ++en)
        {
            unsigned v = *en;
            assert(v > pos);
            bi = v -1;
        }
    }
    bv->swap(bv_tmp);
}
 
 
 
// do logical operation through serialization
static
unsigned SerializationOperation(bvect*             bv_target,
                                /*const*/ bvect&   bv1,
                                /*const*/ bvect&   bv2,
                                set_operation      op,
                                bool               check_reverse=false)
{
    bvect bv_tmp;
    if (!bv_target)
    {
        bv_target = &bv_tmp;
    }
 
    if (op == set_COUNT_SUB_AB ||
        op == set_COUNT_SUB_BA)
    {
        check_reverse = false;
    }
 
    // serialize input vectors
    bvect::statistics st1_op, st2_op;
 
    BM_DECLARE_TEMP_BLOCK(tb)
    if (!bv1.is_ro())
        bv1.optimize(tb, bvect::opt_compress, &st1_op);
    else
        bv1.calc_stat(&st1_op);
    if (!bv2.is_ro())
        bv2.optimize(tb, bvect::opt_compress, &st2_op);
    else
        bv2.calc_stat(&st2_op);
 
 
   struct bvect::statistics st1, st2;
   bv1.calc_stat(&st1);
   bv2.calc_stat(&st2);
 
 
   if (st1.max_serialize_mem > st1_op.max_serialize_mem)
   {
       cout << "Error: Optimize failed to compute max_serialize_mem" << endl;
       cout << "calc_stat=" << st1.max_serialize_mem << endl;
       cout << "optimize=" << st1_op.max_serialize_mem << endl;
       assert(0);
       exit(1);
   }
   if (st2.max_serialize_mem > st2_op.max_serialize_mem)
   {
       cout << "Error:Optimize failed to compute max_serialize_mem" << endl;
       cout << "calc_stat=" << st2.max_serialize_mem << endl;
       cout << "optimize=" << st2_op.max_serialize_mem << endl;
       assert(0); exit(1);
   }
 
   unsigned char* smem1 = new unsigned char[st1.max_serialize_mem];
   unsigned char* smem2 = new unsigned char[st2.max_serialize_mem];
 
   size_t slen1 = bm::serialize(bv1, smem1, tb);
   size_t slen2 = bm::serialize(bv2, smem2, tb);
 
   if (slen1 > st1.max_serialize_mem || slen2 > st2.max_serialize_mem)
   {
       cout << "Serialization override detected!" << endl;
       exit(1);
   }
 
   operation_deserializer<bvect> od;
 
   auto count = od.deserialize(*bv_target, smem1, nullptr, set_ASSIGN);
   cout << slen1 << " " << slen2 << endl;
   int res = bv1.compare(*bv_target);
   if (res != 0)
   {
       cout << "---------------------------------- " << endl;
       cout << "bv1.count()=" << bv1.count() << endl;
       print_stat(cout, bv1);
       cout << "---------------------------------- " << endl;
       cout << "bv_target.count()=" << bv_target->count() << endl;
       print_stat(cout, *bv_target);
       
       bv_target->bit_xor(bv1);
       cout << "First diff=" << bv_target->get_first() << endl;
       cout << "set_ASSIGN 1 failed!" << endl;
       exit (1);
   }
   cout << "Deserialization ASSIGN into bv1 OK" << endl;
 
   {
       bvect* bv_tmp2 = new bvect();
       bm::deserialize(*bv_tmp2, smem1);
       if (*bv_tmp2 != bv1)
       {
           cout << "Deserialize NOT equal to Operation deserialize!" << endl;
           assert(0); exit(1);
       }
       delete bv_tmp2;
   }
 
 
   cout << "Operation deserialization... " << op << endl;
 
    count = od.deserialize(*bv_target, smem2, 0, op);
    cout << "OK" << endl;
 
    // check if operation was ok
    {
        bvect bv_agg, bv_agg2;
        
        bm::aggregator<bvect> agg;
        agg.set_optimization();
        
        const bvect* agg_list[10];
        const bvect* agg_list2[10];
        agg_list[0] = &bv1;
        agg_list[1] = &bv2;
        agg_list2[0] = &bv2;
 
 
        bool agg_check = false;
 
        bvect bvt(bv1, bm::finalization::READWRITE);
        switch(op)
        {
        case bm::set_OR:
            {
                bvect bvc(bv1, bm::finalization::READWRITE);
                bvc |= bv2;
                bvect bv_merge1(bv1, bm::finalization::READWRITE);
                bvect bv_merge2(bv2, bm::finalization::READWRITE);
                bv_merge1.merge(bv_merge2);
                
                if (bv_merge1 != bvc)
                {
                    cerr << "Merge(OR) check error!" << endl;
                    exit(1);
                }
                // 2-way
                {
                    bvect bvt1;
                    bvt1.bit_or(bv1, bv2, bvect::opt_none);
                    if (bvt1 != bvc)
                    {
                        cerr << "1. OR 2-way check error!" << endl;
                        exit(1);
                    }
                    bvect bvt2;
                    bvt2.bit_or(bv2, bv1, bvect::opt_compress);
                    if (bvt2 != bvc)
                    {
                        cerr << "2. OR 2-way check error!" << endl;
                        exit(1);
                    }
                }
            }
            bvt |= bv2;
            agg.combine_or(bv_agg, agg_list, 2);
            agg_check = true;
            break;
        case bm::set_XOR:
            bvt ^= bv2;
            // 2-way
            {
                bvect bvc(bv1, bm::finalization::READWRITE);
                bvc ^= bv2;
                
                bvect bvt1;
                bvt1.bit_xor(bv1, bv2, bvect::opt_none);
                if (bvt1 != bvc)
                {
                    cerr << "1. XOR 2-way check error!" << endl;
                    cerr << "Run detailed check (1)..." << endl;
                    DetailedCompareBVectors(bvt1, bvc);
 
                    bvect bvt2;
                    bvt2.bit_xor(bv2, bv1, bvect::opt_compress);
                    if (bvt2 != bvc)
                    {
                        cerr << "Reverse XOR 2-way check failed too!" << endl;
                    }
 
                    cerr << "Run detailed check (2)..." << endl;
                    DetailedCompareBVectors(bvt2, bvc);
 
                    exit(1);
                }
                bvect bvt2;
                bvt2.bit_xor(bv2, bv1, bvect::opt_compress);
                if (bvt2 != bvc)
                {
                    cerr << "2. XOR 2-way check error!" << endl;
                    exit(1);
                }
            }
            break;
        case bm::set_AND:
            bvt &= bv2;
            agg.combine_and(bv_agg, agg_list, 2);
            agg.combine_and_sub(bv_agg2, agg_list, 2, 0, 0, false);
            {
                if (bv_agg != bv_agg2)
                {
                    cerr << "Error: Aggregator AND - AND-SUB(0) comparison failed!" << endl;
                    exit(1);
                }
            }
            agg_check = true;
            
            // 2-way
            {
                bvect bvc(bv1, bm::finalization::READWRITE);
                bvc &= bv2;
 
                bvect bv_ro1(bv1, bm::finalization::READONLY);
                bvect bv_ro2(bv2, bm::finalization::READONLY);
 
                bvect bvt1;
                bvt1.bit_and(bv1, bv2, bvect::opt_none);
                if (bvt1 != bvc)
                {
                    cerr << "1. AND 2-way check error!" << endl;
                    //print_bv(bvt1);
                    //cout << "control:" << endl;
                    //print_bv(bvc);
                    assert(0); exit(1);
                }
                bvect bvt11;
                bvt11.bit_and(bv_ro1, bv_ro2, bvect::opt_none);
                if (bvt11 != bvc)
                {
                    cerr << "1.1 AND 2-way check error!" << endl;
                    assert(0); exit(1);
                }
 
                bvect bvt2;
                bvt2.bit_and(bv2, bv1, bvect::opt_compress);
                if (bvt2 != bvc)
                {
                    cerr << "2. AND 2-way check error!" << endl;
                    assert(0);exit(1);
                }
                bvect bvt12;
                bvt12.bit_and(bv_ro1, bv_ro2, bvect::opt_none);
                if (bvt12 != bvc)
                {
                    cerr << "2.1 AND 2-way check error!" << endl;
                    assert(0); exit(1);
                }
            }
            break;
        case bm::set_SUB:
            bvt -= bv2;
            agg.combine_and_sub(bv_agg, agg_list, 1, agg_list2, 1, false);
            {
                bvect bv_h;
                agg.combine_and_sub_horizontal(bv_h, agg_list, 1, agg_list2, 1);
                if (bv_agg != bv_h)
                {
                    cerr << "Error: Aggregator Horz-AND-SUB comparison failed!" << endl;
                    exit(1);
                }
            }
            agg_check = true;
            // 2-way
            {
                bvect bvc1(bv1, bm::finalization::READWRITE);
                bvect bvc2(bv2, bm::finalization::READWRITE);
                bvc1 -= bv2;
                bvc2 -= bv1;
                
                bvect bvt1;
                bvt1.bit_sub(bv1, bv2, bvect::opt_compress);
                if (bvt1 != bvc1)
                {
                    DetailedCompareBVectors(bvt1, bvc1);
                    cerr << "1. SUB 2-way check error!" << endl;
                    exit(1);
                }
                bvect bvt2;
                bvt2.bit_sub(bv2, bv1, bvect::opt_compress);
                if (bvt2 != bvc2)
                {
                    cerr << "2. SUB 2-way check error!" << endl;
                    exit(1);
                }
            }
 
            break;
        default:
            goto no_compare;
        }
        if (bvt.compare(*bv_target) != 0)
        {
            cout << "Direct Serial operation comparison failed!" << endl;
            exit(1);
        }
        if (agg_check && bvt.compare(bv_agg) != 0)
        {
            cerr << "Error: Aggregator operation comparison failed!" << endl;
            exit(1);
        }
 
        no_compare:
        ;
 
    }
/*
    if (op == bm::set_AND || op == bm::set_OR || op == bm::set_XOR || op == bm::set_SUB)
    {
        cout << "3 way operation check... " << op << endl;
        operation_deserializer<bvect>::deserialize(*bv_target,
                                                   bv1,
                                                   smem2,
                                                   0,
                                                   op);
        cout << "OK" << endl;
 
        bvect bvt(bv1);
        switch(op)
        {
        case bm::set_OR:
            bvt |= bv2;
            break;
        case bm::set_XOR:
            bvt ^= bv2;
            break;
        case bm::set_AND:
            bvt &= bv2;
            break;
        case bm::set_SUB:
            bvt -= bv2;
            break;
        default:
            goto no_compare2;
        }
        if (bvt.compare(*bv_target) != 0)
        {
            cout << "3-way Serial operation comparison failed!" << endl;
            exit(1);
        }
        no_compare2:
        ;
    }
*/
 
   if (check_reverse)
   {
        cout << "Reverse check... " << endl;
        bvect bv_tmp2(BM_GAP);
        od.deserialize(bv_tmp2, smem2, 0, set_ASSIGN);
        res = bv_tmp2.compare(bv2);
        if (res != 0)
        {
            cout << "set_ASSIGN failed 2! " << endl;
            exit(1);
        }
        if (bv_tmp2 != bv2)
        {
            cout << "set_ASSIGN failed 2-1! " << endl;
            exit(1);
        }
        cout << "Deserialization assign to bv_tmp2 OK" << endl;
        unsigned count_rev =
        od.deserialize(bv_tmp2, smem1, 0, op);
        if (count != count_rev)
        {
//            print_stat(bv1);
/*
            unsigned c = count_or(bv1, bv2);
            cout << "Correct count=" << c << endl;
 
            c = count_or(bv2, bv1);
            cout << "Correct count=" << c << endl;
 
            bv1 |= bv2;
            cout << "Count3 = " << bv1.count() << endl;;
*/
            //SaveBVector("err1.bv", bv1);
            //SaveBVector("err2.bv", bv2);
 
            
 
            cout << "Operation=" << op << endl;
 
            cout << "Serialization operation reverse check failed"
                 << " count = " << count 
                 << " count rev= " << count_rev
                 << endl;
            cout << "See bvector dumps: err1.bv, err2.bv" << endl;
 
            exit(1);
        }
 
   }
 
   delete [] smem1;
   delete [] smem2;
 
   return count;
}
 
static
void SerializationOperation2Test(bvect*        bv_target,
                                 bvect&        bv1,
                                 bvect&        bv2,
                                 unsigned      predicted_count,
                                 set_operation op_count,
                                 set_operation op_combine)
{
    bv_target->clear(true);
 
    bvect bv_ro1(bv1, bm::finalization::READONLY);
    bvect bv_ro2(bv2, bm::finalization::READONLY);
 
    cout << "Serialization operation count..." << endl;
 
    unsigned scount1 = SerializationOperation(0, 
                                              bv1,
                                              bv2,
                                              op_count,
                                              true //reverse check
                                            );
    cout << "Serialization operation count OK." << endl;
 
 
 
    cout << "Serialization operation. " << endl;
    unsigned scount2 = SerializationOperation(bv_target,
        bv1,
        bv2,
        op_combine);
    scount2 = bv_target->count();
    if (predicted_count != scount2 || scount1 != scount2)
    {
        cout << "Serialization count != predicted" << endl
            << " predicted=" << predicted_count
            << " scount1=" << scount1
            << " scount2=" << scount2
            << endl;
 
        cout << endl << "target:" << endl;
        print_stat(cout, *bv_target);
        cout << endl << endl << "Reference" << endl;
        if (op_combine == set_OR)
        {
            bv1 |= bv2;
            if (bv1 != *bv_target)
            {
                cout << "Comparison OR error!" << endl;
            }
            cout << "OR operation count=" << bv1.count() << endl;
            print_stat(cout, bv1);
        }
        else
            if (op_combine == set_AND)
            {
                bv1 &= bv2;
                print_stat(cout,bv1);
            }
 
        exit(1);
    }
 
    bvect bv_target2;
    unsigned scount3 = SerializationOperation(&bv_target2,
        bv_ro1,
        bv_ro2,
        op_combine);
    scount3 = bv_target2.count();
    assert(scount3 == scount2);
 
    bool eq = bv_target->equal(bv_target2);
    assert(eq);
 
    cout << "OK" << endl;
}
 
static
void print_mv(const bvect_mini &bvect_min, unsigned size)
{
    unsigned i;
    for (i = 0; i < size; ++i)
    {
        bool bflag = bvect_min.is_bit_true(i) != 0;
 
        if (bflag)
            printf("1");
        else
            printf("0");
        if ((i % 31) == 0 && (i != 0))
            printf(".");
    }
 
    printf("\n");
}
 
static
void print_gap(const gap_vector& gap_vect, unsigned /*size*/)
{
    const gap_word_t *buf = gap_vect.get_buf();
    unsigned len = gap_length(buf);
    printf("[%i:]", *buf++ & 1);
 
    for (unsigned i = 1; i < len; ++i)
    {
        printf("%i,", *buf++);
    }
 
    printf("\n");
}
 
 
static
void CheckGAPMin(const gap_vector& gapv, const bvect_mini& bvect_min, unsigned len)
{
    int last_bit = -1;
    for (unsigned i = 0; i < len; ++i)
    {
        int bit1 = (gapv.is_bit_true(i) == 1);
        int bit2 = (bvect_min.is_bit_true(i) != 0);
        if (bit1 != bit2)
        {
            cout << "Bit comparison failed. " << "Bit N=" << i << endl;
            assert(0);
            exit(1);
        }
        if (bvect_min.is_bit_true(i))
        {
            last_bit = (int)i;
        }
    }
    unsigned glast;
    bool found = gapv.get_last(&glast);
    if (!found && last_bit != -1)
    {
        cout << "Gap last search failed. " << "Bit=" << last_bit << endl;
        assert(0);
        exit(1);
    }
 
    if (found && last_bit == -1)
    {
        cout << "Gap last search ok but should failed. " << "Bit=" <<
             glast << endl;
        assert(0);
        exit(1);
    }
 
    if (last_bit != (int)glast)
    {
        if (!found && last_bit == -1)
        {}
        else
        {
            cout << "Gap last search discrepancy:" << " found Bit=" <<
                 glast << " last=" << last_bit << endl;
            assert(0);
            exit(1);
        }
    }
}
 
static
void CheckIntervals(const bvect& bv, unsigned /*max_bit*/)
{
    unsigned cnt0 = count_intervals(bv);
    unsigned cnt1 = 1;
    //bool bit_prev = bv.test(0);
 
    unsigned cnt2 = 0;
    bvect::enumerator en = bv.first();
    if (!en.valid())
    {
        cnt2 = 1;
    }
    else
    {
        if (*en > 0)
            ++cnt2;
        unsigned prev = *en;
        for (++en; en.valid(); ++en)
        {
            if (++prev == *en)
            {
            }
            else
            {
                cnt2 += 2;
                prev = *en;
            }
        }
        cnt2 += 2;
    }
/*
    for (unsigned i = 1; i < max_bit; ++i)
    {
        bool bit = bv.test(i);
        cnt1 += bit_prev ^ bit;
        bit_prev = bit;
    }
*/
    if (cnt0 != cnt2)
    {
        cout << "CheckIntervals error. " << "bm count=" << cnt0
             << " Control = " << cnt1 << endl;
        exit(1);
    }
}
 
template<class T> void CheckCountGapRange(const T& vect,
                                       unsigned left,
                                       unsigned right,
                                       unsigned* block_count_arr=0)
{
    unsigned cnt1 = vect.count_range(left, right, block_count_arr);
    unsigned cnt2 = 0;
    for (unsigned i = left; i <= right; ++i)
    {
        if (vect.test(i))
        {
            ++cnt2;
        }
    }
    if (cnt1 != cnt2)
    {
        cout << "Bitcount range failed!" << "left=" << left
             << " right=" << right << endl
             << "count_range()=" << cnt1
             << " check=" << cnt2;
        exit(1);
    }
}
 
template<typename T>
bool FindRank(const T& bv, bm::id_t rank, bm::id_t from, bm::id_t& pos)
{
    assert(rank);
    bool res = false;
    
    typename T::enumerator en = bv.get_enumerator(from);
    
    typename T::enumerator en2 = bv.get_enumerator(from);
    if (rank > 1)
        en2.skip_to_rank(rank);
    if (!en.valid())
        return false;
    for (; en.valid(); ++en)
    {
        rank -= en.valid();
        if (rank == 0)
        {
            pos = *en;
            res = true;
            break;
        }
    } // for en
    
    bm::id_t pos2 = *en2;
    if (pos != pos2)
    {
        cerr << "FindRank enumerator::skip() failed: "
        << "pos=" << pos << " skip()pos=" << pos2
        << " from=" << from
        << endl;
        assert(0);
        exit(1);
    }
    
    return res;
}
 
inline
void CheckRangeCopy(const bvect& bv, unsigned from, unsigned to)
{
    bm::id_t f1, l1, f2, l2;
    
    bvect bv_cp(bv, from, to);
    bvect bv_cp2(bv, to, from); // swapped interval copy is legal
 
    bvect bv_control;
    bv_control.set_range(from, to);
 
    bv_control &= bv;
    
    int res = bv_control.compare(bv_cp);
    if (res != 0)
    {
        bool found1 =  bv_cp.find_range(f1, l1);
        bool found2 =  bv_control.find_range(f2, l2);
        
        bvect bv_cp3(bv, from, to);
        
        cerr << "Error: bvector<>::range_copy() failed. from=" << from << " to=" << to << endl;
        if (found1)
            cerr << " range copy from=" << f1 << " to=" << l1 << endl;
        if (found2)
            cerr << " control    from=" << f2 << " to=" << l2 << endl;
        exit(1);
    }
 
    int res2 = bv_control.compare(bv_cp2);
    if (res2 != 0)
    {
        bool found1 = bv_cp2.find_range(f1, l1);
        bool found2 = bv_control.find_range(f2, l2);
 
        cerr << "Error: reversed bvector<>::range_copy() failed. from=" << from << " to=" << to << endl;
        if (found1)
            cerr << " range copy from=" << f1 << " to=" << l1 << endl;
        if (found2)
            cerr << " control    from=" << f2 << " to=" << l2 << endl;
        exit(1);
    }
 
    bool found1 =  bv_cp.find_range(f1, l1);
    bool found2 =  bv_control.find_range(f2, l2);
    if (found1 != found2)
    {
        cerr << "Error: Dynamic range integrity check." << endl;
        exit(1);
    }
    if (found1)
    {
        if (f1 != f2 || l1 != l2)
        {
            cerr << "Error: bvector<>::range_copy() failed (dynamic range check). from=" << from << " to=" << to << endl;
            cerr << " range copy from=" << f1 << " to=" << l1 << endl;
            cerr << " control    from=" << f2 << " to=" << l2 << endl;
            exit(1);
        }
    }
 
}
 
 
template<class T>
void CheckCountRange(const T& vect, const bvect::rs_index_type& bc_arr,
                                       unsigned left, 
                                       unsigned right)
{
    unsigned cnt1 = vect.count_range(left, right);
    unsigned cnt2 = 0;
 
    typename T::enumerator en = vect.get_enumerator(left);
    for (; en.valid(); ++en)
    {
        if (*en > right)
            break;
        cnt2 += en.valid();
    }
    if (cnt1 != cnt2)
    {
        cout << "2. Bitcount range failed!" << "left=" << left
             << " right=" << right << endl
             << "count_range()=" << cnt1 
             << " check=" << cnt2;
        exit(1);
    }
    
    CheckRangeCopy(vect, left, right);
    
//    bvect::rs_index_type bc_arr;
//    vect.build_rs_index(&bc_arr);
    
    // run a cycle to check count_to()
    //
    //for (unsigned i = 0; i <= right; ++i)
    {
        if (left > right)
            swap(left, right);
 
        unsigned cnt_to_r = vect.count_to(right, bc_arr);
        cnt1 = vect.count_range(left, right, bc_arr);
        unsigned cnt_to_l = left ? vect.count_to(left - 1, bc_arr) : 0;
        cnt2 = cnt_to_r - cnt_to_l;
        if (cnt1 != cnt2)
        {
            cout << "Bitcount range TO failed!" << " left=" << left
                 << " right=" << right << endl
                 << " count_range()=" << cnt1
                 << " check=" << cnt2;
            assert(0); exit(1);
        }
        
        bm::id_t range = 1 + right - left;
        if (cnt1 > range)
        {
            cerr << "Impossible count_range detected!" << endl;
            cerr << " range = " << range << endl;
            cerr << " cnt1  = " << cnt1 << endl;
            cerr << " left  = " << left << endl;
            cerr << " right = " << right << endl;
            cnt1 = vect.count_range(left, right, bc_arr);
            cerr << " cnt1  = " << cnt1 << endl;
            assert(0); exit(1);
        }
        
        
        if (cnt1) // check if we can reverse the search (rank)
        {
            unsigned pos, pos1;
            pos = pos1 = 0;
            bool rf = vect.find_rank(cnt1, left, pos);
            bool rf1 = vect.find_rank(cnt1, left, pos1, bc_arr);
            if (!rf || !rf1)
            {
                cerr << "1. find_rank() failed!" << " left=" << left
                     << " right=" << right
                     << " count_range()=" << cnt1
                     << " pos=" << pos
                     << " pos1=" << pos1
                     << " range=" << range
                     << endl;
                
                unsigned pos2;
                bool rf2 = FindRank(vect, cnt1, left, pos2);
                if (!rf2)
                {
                    cerr << "Debug FindRank failed!" << endl;
                }
                else
                {
                    cerr << " rank=" << pos2 << endl;
                }
                
                cerr << "detailed bug search..." << endl;
                for (unsigned k = 1; k <= cnt1; ++k)
                {
                    rf = vect.find_rank(k, left, pos);
                    rf2 = FindRank(vect, k, left, pos2);
                    if (rf != rf2 || pos != pos2)
                    {
                        rf = vect.find_rank(k, left, pos);
                        
                        cerr << "Failed for rank=" << k << endl;
                        cerr << rf << " " << rf2 << endl;
                        cerr << "pos = " << pos << " pos2 = " << pos2 << endl;
                        assert(0); exit(1);
                    }
                }
                assert(0); exit(1);
            }
            assert(pos == pos1);
            
            if (left > 0)
            {
                unsigned pos3;
                T bv1(vect, left, bm::id_max-1);
                std::unique_ptr<bvect::rs_index_type> bc_arr2(new bvect::rs_index_type);
                bv1.build_rs_index(bc_arr2.get());
 
                bool rf3 = bv1.select(cnt1, pos3, *bc_arr2);
                assert(rf3 == rf);
                assert(pos == pos3);
            }
            
            if (right != pos)
            {
                unsigned pos2;
                bool rf2 = FindRank(vect, cnt1, left, pos2);
                assert(rf2);
                // check if we found zero-tail
                //auto cnt3 = vect.count_range(pos+1, right, block_count_arr);
                if (pos2 != pos)
                {
                    rf = vect.find_rank(cnt1, left, pos);
                    cout << "2. find_rank() check failed! \n" << "left=" << left
                         << " right=" << right
                         << " count_range()=" << cnt1
                         << " pos=" << pos
                         << " rank = " << pos2
                         << endl;
                    assert(0); exit(1);
                }
            }
        }
    }
}
 
static
unsigned BitCountChange(unsigned word)
{
    unsigned count = 1;
    unsigned bit_prev = word & 1;
    word >>= 1;
    for (unsigned i = 1; i < 32; ++i)
    {
        unsigned bit = word & 1;
        count += bit ^ bit_prev;
        bit_prev = bit;
        word >>= 1;
    }
    return count;
}
 
static
void DetailedCheckVectors(const bvect      &bv1,
                          const bvect      &bv2)
{
    bvect::enumerator en1 = bv1.first();
    bvect::enumerator en2 = bv2.first();
    
    while (en1.valid())
    {
        if (!en2.valid())
        {
            cout << "Second vector - invalid enumerator at:" << *en1;
            return;
        }
        if (*en1 != *en2)
        {
            cout << "Discrepancy at bit position: " << *en1;
            cout << " second vector is at:" << *en2;
            return;
        }
        ++en1;
        ++en2;
    }
    cout << "Detailed check OK" << endl; // Hmmm... Why?
}
 
static
void DetailedCheckVectors(const bvect_mini &bvect_min, 
                          const bvect      &bvect_full,
                          unsigned size)
{
    cout << "Detailed check" << endl;
 
    //bvect_full.stat();
 
    // detailed bit by bit comparison. Paranoia check.
 
    unsigned i;
    for (i = 0; i < size; ++i)
    {
        bool bv_m_flag = bvect_min.is_bit_true(i) != 0; 
        bool bv_f_flag = bvect_full.get_bit(i) != 0;
 
        if (bv_m_flag != bv_f_flag)
        {
            printf("Bit %u is non conformant. vect_min=%i vect_full=%i\n",
                i, (int)bv_m_flag, (int)bv_f_flag);
 
            cout << "Non-conformant block number is: " << unsigned(i >>  bm::set_block_shift) << endl;
            assert(0); exit(1);
        }
    }
    
    printf("\n detailed check ok.\n");
 
}
 
static
void CompareEnumerators(const bvect::enumerator& en1, const bvect::enumerator& en2)
{
    if (!en1.valid() && !en2.valid())
        return;
    bool fsm_equal = en1.compare_state(en2);
    if (!fsm_equal)
    {
        cerr << "Enumerators FSM comparison failed" << endl;
        exit(1);
    }
}
 
// find last set bit by scan (not optimal)
//
static
bool FindLastBit(const bvect& bv, bm::id_t& last_pos)
{
    bvect::enumerator en = bv.first();
    if (!en.valid())
        return false;
    for (; en.valid(); ++en)
    {
        last_pos = *en;
    }
    return true;
}
 
 
 
template<class BV>
void IntervalsCheck(const BV& bv)
{
    cout << " ... IntervalsCheck" << endl;
    BV bv_inv(bv);
    bv_inv.invert();
 
    typename BV::size_type intervals = bm::count_intervals(bv);
    typename BV::size_type intervals_c = 1;
 
    typename BV::enumerator en1 = bv.get_enumerator(0);
    typename BV::enumerator en2 = bv_inv.get_enumerator(0);
 
    while (en1.valid())
    {
        typename BV::size_type from = *en1;
        typename BV::size_type to = *en2;
        assert(from != to);
 
        bool all_one, any_one;
        bool is_int, is_int_c;
        if (to == bm::id_max)
        {
            all_one = bv.is_all_one_range(from, to-1);
            assert(all_one);
            any_one = bv.any_range(from, to-1);
            assert(any_one);
            is_int = bm::is_interval(bv, from, to-1);
            is_int_c = test_interval(bv, from, to-1);
            assert(is_int == is_int_c);
            {
                bvect::size_type pos;
                bool b = bm::find_interval_end(bv, from, pos);
                assert(b == is_int);
                if (b)
                {
                    assert(pos == to-1);
                }
            }
            if (is_int)
            {
                bvect::size_type pos;
                bool b = bm::find_interval_start(bv, from, pos);
                assert(b && pos == from);
                b = bm::find_interval_start(bv, to-1, pos);
                assert(b && pos == from);
            }
 
            break;
        }
        else
        {
            all_one = bv.is_all_one_range(from, to);
            assert(!all_one);
            any_one = bv.any_range(from, to);
            auto cnt = bv.count_range(from, to);
            if (any_one)
            {
                assert(cnt);
            }
            else
            {
                assert(!cnt);
            }
            is_int = bm::is_interval(bv, from, to);
            is_int_c = test_interval(bv, from, to);
            assert(is_int == is_int_c);
            if (is_int)
            {
                bvect::size_type pos;
                bool b = bm::find_interval_end(bv, from, pos);
                assert(b == is_int);
                if (b)
                {
                    assert(pos == to);
                }
                b = bm::find_interval_start(bv, from, pos);
                assert(b && pos == from);
                pos = 0xDEADBEEF;
                b = bm::find_interval_start(bv, to, pos);
                assert(b && pos == from);
            }
 
        }
 
 
        if (to == bm::id_max)
        {}
        else
        {
            ++intervals_c;
        }
        if (to < from)
        {
            --from;
            assert(!bv.test(to));
            all_one = bv.is_all_one_range(from, to);
            assert(!all_one);
            any_one = bv.any_range(from, to);
            assert(!any_one);
            typename BV::size_type cnt = bv.count_range(to, from);
            assert(!cnt);
            is_int = bm::is_interval(bv, from, to);
            is_int_c = test_interval(bv, from, to);
            assert(is_int == is_int_c);
            if (is_int)
            {
                bvect::size_type pos;
                bool b = bm::find_interval_end(bv, from, pos);
                assert(b == is_int);
                if (b)
                {
                    assert(pos == to);
                }
                b = bm::find_interval_start(bv, from, pos);
                assert(b && pos == from);
                pos = 0xDEADBEEF;
                b = bm::find_interval_start(bv, to, pos);
                assert(b && pos == from);
            }
 
            en2.go_to(from+1);
            if (!en2.valid())
                break;
        }
        else
        {
            --to;
            assert(bv.test(to));
            all_one = bv.is_all_one_range(from, to);
            assert(all_one);
            any_one = bv.any_range(from, to);
            assert(any_one);
            typename BV::size_type cnt = bv.count_range(from, to);
            assert(cnt == (to - from + 1));
            is_int = bm::is_interval(bv, from, to);
            is_int_c = test_interval(bv, from, to);
            assert(is_int == is_int_c);
            if (is_int)
            {
                bvect::size_type pos;
                bool b = bm::find_interval_end(bv, from, pos);
                assert(b == is_int);
                if (b)
                {
                    assert(pos == to);
                }
                b = bm::find_interval_start(bv, from, pos);
                assert(b && pos == from);
                pos = 0xDEADBEEF;
                b = bm::find_interval_start(bv, to, pos);
                assert(b && pos == from);
            }
 
            en1.go_to(to+1);
        }
 
    } // while
    if (intervals != intervals_c)
    {
        typename BV::size_type diff;
        diff = std::max(intervals, intervals_c) - std::min(intervals, intervals_c);
        if (diff > 1)
        {
            cerr << "Intervals difference:" << diff << endl;
            assert(0);
            exit(1);
        }
    }
}
 
template<class BV>
void interval_copy_range(BV& bv, const BV& bv_src,
                         typename BV::size_type from, typename BV::size_type to)
{
    bv.clear();
 
    if (from > to)
        bm::xor_swap(from, to);
 
    bm::interval_enumerator<bvect> ien(bv_src, from, false);
    while (ien.valid())
    {
        auto st = ien.start();
        assert(st >= from);
        if (st > to)
            break;
        auto end = ien.end();
        if (end > to)
            end = to;
 
        assert(st <= end);
        bv.set_range(st, end);
        if (!ien.advance())
            break;
    } // while
}
 
template<typename BV>
void IntervalsEnumeratorCheck(const BV& bv, bool report)
{
    if (report)
        cout << "..IntervalsEnumeratorCheck()" << flush;
    bvect::allocator_pool_type pool;
 
    typename BV::size_type f, l, m;
    auto b = bv.find_range(f, l);
    if (!b)
    {
        assert(bv.count() == 0);
        return;
    }
    m = l - f;
    if (!m)
        m = l;
 
    bool eq;
    if (report)
        cout << "1 " << flush;
    // Full vector
    {
        bvect bv2; bvect bv2_c;
        bvect::mem_pool_guard g1(pool, bv2);
        bvect::mem_pool_guard g2(pool, bv2_c);
 
        bv2_c.copy_range(bv, 0, bm::id_max-1);
 
        interval_copy_range(bv2, bv, 0, bm::id_max - 1);
        eq = bv2.equal(bv2_c);
        assert(eq);
    }
    if (report)
        cout << "2 " << flush;
    // 0 -> frist
    {
        bvect bv2; bvect bv2_c;
        bvect::mem_pool_guard g1(pool, bv2);
        bvect::mem_pool_guard g2(pool, bv2_c);
 
        bv2_c.copy_range(bv, 0, l);
 
        interval_copy_range(bv2, bv, 0, l);
        eq = bv2.equal(bv2_c);
        assert(eq);
    }
 
    if (report)
        cout << "3 " << flush;
    // [first..last]
    {
        bvect bv2; bvect bv2_c;
        bvect::mem_pool_guard g1(pool, bv2);
        bvect::mem_pool_guard g2(pool, bv2_c);
 
        bv2_c.copy_range(bv, f, l);
 
        interval_copy_range(bv2, bv, f, l);
        eq = bv2.equal(bv2_c);
        assert(eq);
    }
    if (report)
        cout << "4 " << flush;
    // [last..]
    {
        bvect bv2; bvect bv2_c;
        bvect::mem_pool_guard g1(pool, bv2);
        bvect::mem_pool_guard g2(pool, bv2_c);
 
        bv2_c.copy_range(bv, l, bm::id_max-1);
 
        interval_copy_range(bv2, bv, l, bm::id_max - 1);
        eq = bv2.equal(bv2_c);
        assert(eq);
    }
    if (report)
        cout << "5 " << flush;
    // [mid..last]
    {
        bvect bv2; bvect bv2_c;
        bvect::mem_pool_guard g1(pool, bv2);
        bvect::mem_pool_guard g2(pool, bv2_c);
 
        bv2_c.copy_range(bv, m, l);
 
        interval_copy_range(bv2, bv, m, l);
        eq = bv2.equal(bv2_c);
        assert(eq);
    }
    if (report)
        cout << "6 " << flush;
    // [first..mid]
    {
        bvect bv2; bvect bv2_c;
        bvect::mem_pool_guard g1(pool, bv2);
        bvect::mem_pool_guard g2(pool, bv2_c);
 
        bv2_c.copy_range(bv, f, m);
 
        interval_copy_range(bv2, bv, f, m);
        eq = bv2.equal(bv2_c);
        assert(eq);
    }
    if (report)
        cout << endl;
}
 
 
 
 
// vectors comparison check
 
void CheckVectors(bvect_mini &bvect_min, 
                  bvect      &bvect_full,
                  unsigned size,
                  bool     detailed)
{
    cout << "\nVectors checking...bits to compare = " << size << endl;
 
    cout << "Bitcount summary : ";
    unsigned min_count = bvect_min.bit_count();
    cout << " minvector count = " << min_count;
    unsigned count = bvect_full.count();
    unsigned full_count = bvect_full.recalc_count();
    cout << " fullvector re-count = " << full_count << endl;
    
    if (min_count != full_count)
    {
        cout << "fullvector count = " << count << endl;
        cout << "Count comparison failed !!!!" << endl;
        print_stat(cout, bvect_full);
        DetailedCheckVectors(bvect_min, bvect_full, size);
        assert(0);
        exit(1);  
    } 
 
    if (full_count)
    {
        bool any = bvect_full.any();
        if (!any)
        {
            cout << "Anycheck failed!" << endl;
            exit(1);
        }
    }
 
    // find_last check
    {
        bm::id_t pos1 = 0;
        bm::id_t pos2 = 0;
        bool last_found1 = FindLastBit(bvect_full, pos1);
        bool last_found2 = bvect_full.find_reverse(pos2);
        
        assert(last_found1 == last_found2);
        if (last_found1)
        {
            assert(pos1 == pos2);
        }
    }
 
    IntervalsCheck(bvect_full);
    IntervalsEnumeratorCheck(bvect_full, true);
    
    if (!detailed)
        return;
    
    // get_next comparison
    cout << "Positive bits comparison..." << flush;
    unsigned nb_min = bvect_min.get_first();
    unsigned nb_ful = bvect_full.get_first();
 
    bvect::counted_enumerator en = bvect_full.first();
    unsigned nb_en = *en;
    bvect::enumerator en1 = bvect_full.get_enumerator(*en);
    if (nb_min != nb_ful)
    {
         cout << "!!!! First bit comparison failed. Full id = " 
              << nb_ful << " Min id = " << nb_min 
              << endl;
 
         bool bit_f = bvect_full.get_bit(nb_ful);
         cout << "Full vector'd bit #" << nb_ful << "is:" 
              << bit_f << endl;
 
         bool bit_m = (bvect_min.is_bit_true(nb_min) == 1);
         cout << "Min vector'd bit #" << nb_min << "is:" 
              << bit_m << endl;
 
 
         print_stat(cout,bvect_full);
 
         DetailedCheckVectors(bvect_min, bvect_full, size);
 
         exit(1);
    }
    CompareEnumerators(en, en1);
 
    if (full_count)
    {
       unsigned bit_count = 1;
       unsigned en_prev = nb_en;
 
       do
       {
           nb_min = bvect_min.get_next(nb_min);
           if (nb_min == 0)
           {
               break;
           }
 
           en_prev = nb_en;
           ++en;
           ++en1;
           CompareEnumerators(en, en1);
 
           if ((bit_count % 10 == 0) || (bit_count % 128 == 0))
           {
                bvect::enumerator en2 = bvect_full.get_enumerator(*en);
                CompareEnumerators(en, en2);
           }
 
           nb_en = *en;
           ++bit_count;
 
           if (nb_en != nb_min)
           {
               nb_ful = bvect_full.get_next(en_prev);
               cout << "!!!!! next bit comparison failed. Full id = " 
                    << nb_ful << " Min id = " << nb_min 
                    << " Enumerator = " << nb_en
                    << endl;
 
     //          bvect_full.stat();
 
     //          DetailedCheckVectors(bvect_min, bvect_full, size);
 
               exit(1);
           }
       } while (en.valid());
       if (bit_count != min_count)
       {
           cout << " Bit count failed."  
                << " min = " << min_count 
                << " bit = " << bit_count 
                << endl;
           exit(1);
       }
    }
 
    cout << "OK" << endl;
 
    return;
}
 
static
void DynamicMatrixTest()
{
    cout << "---------------------------- DynamicMatrixTest() test" << endl;
    
    {
        bm::dynamic_heap_matrix<unsigned, bvect::allocator_type> matr(0, 0);
        matr.resize(3, bm::set_sub_array_size);
        matr.set_zero();
        
        {
            unsigned* r = matr.row(1);
            for (unsigned i = 0; i < matr.cols(); ++i)
            {
                r[i] = i;
            }
        }
        
        matr.resize(matr.rows()+1, matr.cols());
        {
            unsigned* r = matr.row(3);
            for (unsigned i = 0; i < matr.cols(); ++i)
            {
                r[i] = i;
            }
        }
 
        {
            const unsigned* r = matr.row(1);
            for (unsigned i = 0; i < matr.cols(); ++i)
            {
                assert(r[i] == i);
            }
        }
    }
    {
        bm::dynamic_heap_matrix<unsigned, bvect::allocator_type> matr(3, 3);
        matr.init();
        matr.set_zero();
 
        matr.set(0, 0, 10);
        matr.set(1, 1, 100);
        matr.set(2, 2, 200);
 
        matr.set(1, 0, 1);
        matr.set(2, 0, 2);
        matr.set(2, 1, 21);
 
        assert(matr.get(0, 0) == 10);
        assert(matr.get(1, 1) == 100);
        assert(matr.get(2, 2) == 200);
 
 
        matr.replicate_triange();
 
        assert(matr.get(0, 1) == 1);
        assert(matr.get(0, 2) == 2);
        assert(matr.get(1, 2) == 21);
 
 
 
        bm::id64_t s;
        matr.sum(s, 0);
        assert(s == 13);
 
    }
 
    
    cout << "---------------------------- DynamicMatrixTest() test OK" << endl;
}
 
static
void RSIndexTest()
{
    cout << "---------------------------- RSIndexTest() test" << endl;
 
    {
        rs_ind rsi;
        
        rsi.resize(bm::set_sub_array_size*5);
        rsi.resize_effective_super_blocks(3);
        
        rsi.set_super_block(0, 1);
        rsi.set_super_block(1, 2);
        rsi.set_super_block(2, 3);
        rsi.set_null_super_block(3);
        rsi.set_full_super_block(4);
 
        auto sb_size = rsi.super_block_size();
        assert(sb_size == 5);
        
        auto rc = rsi.get_super_block_count(0);
        assert(rc == 1);
        rc = rsi.get_super_block_count(1);
        assert(rc == 2);
        rc = rsi.get_super_block_count(2);
        assert(rc == 3);
        rc = rsi.get_super_block_count(256);
        assert(rc == 0);
 
 
        auto bc = rsi.get_super_block_rcount(0);
        assert(bc == 1);
        bc = rsi.get_super_block_rcount(1);
        assert(bc == 3);
        bc = rsi.get_super_block_rcount(2);
        assert(bc == 6);
        
        unsigned i = rsi.find_super_block(1);
        assert(i == 0);
        i = rsi.find_super_block(2);
        assert(i == 1);
        i = rsi.find_super_block(3);
        assert(i == 1);
        i = rsi.find_super_block(4);
        assert(i == 2);
        i = rsi.find_super_block(200);
        assert(i == 4);
/*
        i = rsi.find_super_block(bm::id_max);
        assert(i == 5);
*/
    }
    
    {
        unsigned bcount[bm::set_sub_array_size];
        bm::id64_t sub_count1[bm::set_sub_array_size];
        bm::id64_t sub_count2[bm::set_sub_array_size];
        for (unsigned i = 0; i < bm::set_sub_array_size; ++i)
        {
            bcount[i] = 0; sub_count1[i] = sub_count2[i] = 0;
        } // for
        bcount[0] = 1;
        bcount[255] = 2;
        
        sub_count1[0] = 1;          // sub-range 0
        sub_count1[255] = 0;        // sub-3
        sub_count2[0] = 1 << 16;    // sub-2
        sub_count2[255] = 1 << 16;  // sub 2,3
 
        
        rs_ind rsi;
        // -----------------------------------------
        rsi.resize(bm::set_sub_array_size*4);
        rsi.resize_effective_super_blocks(2);
        rsi.set_total(bm::set_sub_array_size*4);
        
        
        rsi.set_null_super_block(0);
        auto tcnt = rsi.count();
        assert(tcnt == 0);
        rsi.register_super_block(1, &bcount[0], &sub_count1[0]);
        tcnt = rsi.count();
        assert(tcnt == 3);
        rsi.register_super_block(2, &bcount[0], &sub_count2[0]);
        tcnt = rsi.count();
        assert(tcnt == 6);
        rsi.set_full_super_block(3);
        tcnt = rsi.count();
        assert(tcnt == 6 + bm::set_sub_array_size * 65536);
 
        unsigned i = rsi.find_super_block(1);
        assert(i == 1);
        i = rsi.find_super_block(3);
        assert(i == 1);
        i = rsi.find_super_block(4);
        assert(i == 2);
        i = rsi.find_super_block(400);
        assert(i == 3);
//        i = rsi.find_super_block(bm::id_max);
//        assert(i == rsi.super_block_size());
        
        unsigned bc;
        rs_ind::size_type rbc;
        for (unsigned nb = 0; nb < bm::set_sub_array_size; ++nb)
        {
            bc = rsi.count(nb);
            assert(bc == 0);
            rbc = rsi.rcount(nb);
            assert(!rbc);
        }
        bc = rsi.count(bm::set_sub_array_size);
        assert(bc == 1);
        rbc = rsi.rcount(bm::set_sub_array_size);
        assert(rbc == 1);
        
        bc = rsi.count(bm::set_sub_array_size+1);
        assert(bc == 0);
        rbc = rsi.rcount(bm::set_sub_array_size+1);
        assert(rbc == 1);
 
        bc = rsi.count(bm::set_sub_array_size + 255);
        assert(bc == 2);
        rbc = rsi.rcount(bm::set_sub_array_size + 255);
        assert(rbc == 3);
 
        bc = rsi.count(bm::set_sub_array_size*3);
        assert(bc == 65536);
        rbc = rsi.rcount(bm::set_sub_array_size*3);
        assert(rbc == 65536+6);
        rbc = rsi.rcount(bm::set_sub_array_size*3 + 1);
        assert(rbc == 65536+6 + 65536);
        
        
        // ==========================
        {
            auto nb = rsi.find(1);
            assert(nb == 256);
            
            nb = rsi.find(2);
            assert(nb == bm::set_sub_array_size+255);
            nb = rsi.find(3);
            assert(nb == bm::set_sub_array_size+255);
 
            nb = rsi.find(4);
            assert(nb == bm::set_sub_array_size+255+1);
 
            nb = rsi.find(65536);
            assert(nb == 3*bm::set_sub_array_size+0);
            nb = rsi.find(65536*2);
            assert(nb == 3*bm::set_sub_array_size+1);
            nb = rsi.find(65536*3);
            assert(nb == 3*bm::set_sub_array_size+2);
        }
        // ==========================
 
        {
            bool b;
            rs_ind::size_type rank;
            rs_ind::block_idx_type nb;
            bm::gap_word_t sub_range;
 
            rank = 1;
            b = rsi.find(&rank, &nb, &sub_range);
            assert(b);
            assert(nb == 256);
            assert(sub_range == 0);
            assert(rank == 1);
 
            rank = 2;
            b = rsi.find(&rank, &nb, &sub_range);
            assert(b);
            assert(nb == bm::set_sub_array_size+255);
            assert(sub_range == bm::rs3_border1 + 1);
            assert(rank == 1);
 
            rank = 3;
            b = rsi.find(&rank, &nb, &sub_range);
            assert(b);
            assert(nb == bm::set_sub_array_size+255);
            assert(sub_range == bm::rs3_border1 + 1);
            assert(rank == 2);
 
            rank = 4;
            b = rsi.find(&rank, &nb, &sub_range);
            assert(b);
            assert(nb == bm::set_sub_array_size+255+1);
            assert(sub_range == bm::rs3_border0 + 1);
            assert(rank == 1);
 
            rank = 5;
            b = rsi.find(&rank, &nb, &sub_range);
            assert(b);
            assert(nb == bm::set_sub_array_size+256+255);
            assert(sub_range == bm::rs3_border0 + 1);
            assert(rank == 1);
 
            rank = 6;
            b = rsi.find(&rank, &nb, &sub_range);
            assert(b);
            assert(nb == bm::set_sub_array_size+256+255);
            assert(sub_range == bm::rs3_border1 + 1);
            assert(rank == 1);
 
            rank = 65536;
            b = rsi.find(&rank, &nb, &sub_range);
            assert(b);
            assert(nb == 3*bm::set_sub_array_size+0);
            assert(sub_range == bm::rs3_border1 + 1);
            assert(rank == 65536 - 6 - bm::rs3_border1 - 1);
 
            rank = 65536 + 7;
            b = rsi.find(&rank, &nb, &sub_range);
            assert(b);
            assert(nb == 3*bm::set_sub_array_size+1);
            assert(sub_range == 0);
            assert(rank == 1);
 
            rank = bm::id_max;
            b = rsi.find(&rank, &nb, &sub_range);
            assert(!b);
 
 
        }
 
    }
    
 
    cout << "---------------------------- RSIndexTest() test OK" << endl;
}
 
 
static
void ClearAllTest()
{
    bvect     bvect_full;
 
    for (unsigned i = 0; i < 100000; ++i)
    {
        bvect_full.set_bit(i);
    }
    BM_DECLARE_TEMP_BLOCK(tb)
    bvect_full.optimize(tb);
    bvect_full.clear();
 
    print_stat(cout, bvect_full);
 
    unsigned count = bvect_full.count();
    assert(count == 0);
    print_stat(cout, bvect_full);
}
 
static
void WordCmpTest()
{
    cout << "---------------------------- WordCmp test" << endl;
 
    for (int i = 0; i < 10000000; ++i)
    {
        unsigned w1 = unsigned(rand());
        unsigned w2 = unsigned(rand());
        int res = wordcmp0(w1, w2);
        int res2 = wordcmp(w1, w2);
        if (res != res2)
        {
            printf("WordCmp failed !\n");
            exit(1);
        }
 
        res = wordcmp0((unsigned)0U, (unsigned)w2);
        res2 = wordcmp((unsigned)0U, (unsigned)w2);
 
        if (res != res2)
        {
            printf("WordCmp 0 test failed !\n");
            exit(1);
        }
 
        res = wordcmp0((unsigned)~0U, (unsigned)w2);
        res2 = wordcmp((unsigned)~0U, (unsigned)w2);
 
        if (res != res2)
        {
            printf("WordCmp ~0 test failed !\n");
            exit(1);
        }
 
        res = wordcmp0((unsigned)w2, (unsigned)0);
        res2 = wordcmp((unsigned)w2, (unsigned)0);
 
        if (res != res2)
        {
            printf("WordCmp 0-2 test failed !\n");
            exit(1);
        }
 
    }
 
    cout << "Ok." << endl;
}
 
 
static
void TestBlockCountChange()
{
    cout << "---------------------------- CountChange test" << endl;
 
#ifdef VECT_BLOCK_CHANGE
 
    unsigned i, c, cc;
    bm::word_t BM_VECT_ALIGN blk[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
 
    for (i = 0; i < bm::set_block_size; ++i)
        blk[i] = 0;
    
    c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
    cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
    assert(c == 1);
    assert(c == cc);
 
    blk[0] = 1;
    c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
    cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
    assert(c == 2);
    assert(c == cc);
 
    blk[0] = 0xFF;
    c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
    cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
    assert(c == 2);
    assert(c == cc);
 
    blk[0] = ~0u;
    c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
    cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
    assert(c == 2);
    assert(c == cc);
 
    blk[0] = blk[1] = blk[2] = blk[3] = 2;
    c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
    cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
    assert(c == cc);
    
    blk[4] = blk[5] = blk[6] = blk[7] = 2;
    c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
    cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
    assert(c == cc);
 
    {
    for (i = 0; i < bm::set_block_size; ++i)
        blk[i] = 2;
 
    c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
    cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
    assert(c == cc);
    }
    
    {
    for (i = 0; i < bm::set_block_size; ++i)
        blk[i] = 1u << 31;
 
    c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
    cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
    assert(c == cc);
    }
 
    {
    for (i = 0; i < bm::set_block_size; ++i)
        blk[i] = ~0u << 30;
 
    c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
    cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
    assert(c == cc);
    }
 
    cout << "Block change stress..." << endl;
    {
    std::chrono::time_point<std::chrono::steady_clock> s;
    std::chrono::time_point<std::chrono::steady_clock> f;
    s = std::chrono::steady_clock::now();
 
    
        unsigned k_max = (1u << 31) / 4;
        for (unsigned k = 0; k <= k_max; ++k)
        {
            for (i = 0; i < bm::set_block_size; ++i)
                blk[i] = k;
            c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
            cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
            assert(c == cc);
            
            if (k % 100000 == 0)
            {
                f = std::chrono::steady_clock::now();
                auto diff = f - s;
                auto d = std::chrono::duration <double, std::milli> (diff).count();
 
                if (!is_silent)
                    cout << "\r" << k << " / " << k_max << " (" << d << "ms)" << flush;
                
                s = std::chrono::steady_clock::now();
            }
        } // for k
    }
    cout << endl;
 
#endif
 
    
    cout << "---------------------------- CountChange test OK" << endl;
}
 
 
inline
bm::id64_t bit_block_calc_xor_change_digest(
                        const bm::word_t*  block,
                        const bm::word_t*  xor_block,
                        block_waves_xor_descr&  x_descr,
                        bm::xor_complement_match& match_type)
{
    unsigned gc, bc;
    unsigned c_gc, c_bc;
    bm::compute_s_block_descr(block, x_descr, &gc, &bc);
    bm::bit_block_change_bc(block, &c_gc, &c_bc);
    assert(gc == c_gc);
    assert(bc == c_bc);
 
    block_xor_match_descr xmd;
    bm::id64_t d64 = bm::calc_block_digest0(block);
 
    xor_scanner<bvect> xs;
    xs.compute_s_block_stats(block);
    xs.compute_xor_complexity_descr(block, d64, xor_block, x_descr, xmd);
    match_type = xmd.match_type;
    return xmd.xor_d64;
}
 
static
void Check_XOR_Product(const bm::word_t*  block,
                       const bm::word_t*  xor_block,
                       bm::id64_t         digest)
{
    assert(digest);
 
    bm::word_t BM_VECT_ALIGN t_blk1[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
    bm::word_t BM_VECT_ALIGN t_blk2[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
 
    bm::bit_block_xor(t_blk1, block, xor_block, digest);
    bm::bit_block_xor(t_blk2, t_blk1, xor_block, digest);
 
    unsigned cnt = bm::bit_block_xor_count(block, t_blk2);
    assert(cnt == 0); // identically restored
}
 
 
static
void TestBlockCountXORChange()
{
    cout << "---------------------------- TestBlockCountXORChange() test" << endl;
    unsigned i;
    bm::id64_t d64;
    bm::block_waves_xor_descr x_descr;
    unsigned gc, bc;
 
    {
        bm::block_match_chain<unsigned> bmc;
        bmc.nb=100;
        bmc.chain_size = 56;
        bmc.ref_idx[0]=1024;
        bmc.xor_d64[0]=~0ULL;
 
        bm::block_match_chain<unsigned> bmc2;
        bmc2 = bmc;
        assert(bmc2.nb==100);
        assert(bmc2.chain_size == 56);
        assert(bmc2.ref_idx[0]==1024);
    }
 
    {
        bm::word_t BM_VECT_ALIGN blk[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
        bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
        for (unsigned k = 0; k < bm::block_waves; ++k)
        {
            assert(x_descr.sb_bc[k] == 0);
        } // for
        assert(bc == 0);
        assert(gc == 1);
 
        blk[bm::set_block_digest_wave_size] = 1;
        bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
        assert(x_descr.sb_bc[0] == 0);
        assert(x_descr.sb_bc[1] == 1);
        assert(x_descr.sb_gc[0] == 1);
        assert(x_descr.sb_gc[1] == 2);
        assert(bc == 1);
        assert(gc == 3);
 
        blk[bm::set_block_digest_wave_size-1] = 1u << 31;
        bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
        assert(x_descr.sb_bc[0] == 1);
        assert(x_descr.sb_bc[1] == 1);
        assert(x_descr.sb_gc[0] == 2);
        assert(x_descr.sb_gc[1] == 2 || x_descr.sb_gc[1] == 1);
        assert(bc == 2);
        assert(gc == 3);
 
 
        blk[bm::set_block_digest_wave_size-1] = 0;
        blk[bm::set_block_digest_wave_size] = 0;
 
 
 
        blk[0] = 1;
        bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
        assert(x_descr.sb_bc[0] == 1);
        assert(x_descr.sb_gc[0] == 2);
        for (unsigned k = 1; k < bm::block_waves; ++k)
        {
            assert(x_descr.sb_bc[k] == 0);
        } // for
        assert(bc == 1);
        assert(gc == 2);
 
 
 
        blk[0] = 1 | (1 << 1);
        bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
        assert(x_descr.sb_bc[0] == 2);
        assert(x_descr.sb_gc[0] == 2);
        for (unsigned k = 1; k < bm::block_waves; ++k)
        {
            assert(x_descr.sb_bc[k] == 0);
            assert(x_descr.sb_gc[k] == 0);
        } // for
        assert(bc == 2);
        assert(gc == 2);
 
        blk[bm::set_block_size-1] = 1 | (1 << 1);
        bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
        assert(x_descr.sb_bc[0] == 2);
        assert(x_descr.sb_gc[0] == 2);
        assert(x_descr.sb_bc[bm::block_waves-1] == 2);
        assert(x_descr.sb_gc[bm::block_waves-1] == 3 || x_descr.sb_gc[bm::block_waves-1] == 2);
        for (unsigned k = 1; k < bm::block_waves-1; ++k)
        {
            assert(x_descr.sb_bc[k] == 0);
            assert(x_descr.sb_gc[k] == 0);
        } // for
 
        blk[0] = 0;
        bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
        assert(x_descr.sb_bc[bm::block_waves-1] == 2);
        assert(x_descr.sb_gc[bm::block_waves-1] == 3 || x_descr.sb_gc[bm::block_waves-1] == 2);
        for (unsigned k = 0; k < bm::block_waves-1; ++k)
        {
            assert(x_descr.sb_bc[k] == 0);
            if (k == 0)
            {
                assert(x_descr.sb_gc[k] == 1);
            }
        } // for
 
    }
 
    // test match vector search/refine
    //
    {
        typedef
        bm::heap_vector<bm::block_xor_match_descr, bvect::allocator_type, true>
            xor_matches_vector_type;
        typedef
        bm::heap_vector<bm::match_pair, bvect::allocator_type, true>
            m_pairs_vector_type;
        xor_matches_vector_type xm_vect;
        m_pairs_vector_type pm_vect;
        {
            block_xor_match_descr xmd;
            xmd.match_type = e_xor_match_BC; xmd.ref_idx = 10; xmd.xor_d64 = 1ull;
            xm_vect.push_back(xmd);
        }
        auto cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 10, (1ull << 1), e_xor_match_BC);
        assert(!cnt);
        assert(pm_vect.size()==0);
        cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 11, (1ull << 1), e_xor_match_BC);
        assert(cnt == 1);
        assert(pm_vect.size()==1);
        bm::match_pair mp = pm_vect[0];
        assert(mp.ref_idx == 10);
        assert(pm_vect[0].xor_d64 == 1ull);
        cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 11, (1ull << 1), e_xor_match_iBC);
        assert(cnt == 0);
/*
        int brate = bm::check_pair_vect_vbr(pm_vect, 255);
        assert(brate == 1);
        brate = bm::check_pair_vect_vbr(pm_vect, 65535);
        assert(brate == 2);
        brate = bm::check_pair_vect_vbr(pm_vect, 65536);
        assert(brate == 0);
*/
 
        {
            block_xor_match_descr xmd;
            xmd.match_type = e_xor_match_BC; xmd.ref_idx = 20; xmd.xor_d64 = 3ull;
            xm_vect.push_back(xmd);
        }
        cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 11, (1ull << 1), e_xor_match_BC);
        assert(cnt == 1);
        mp = pm_vect[0];
        assert(pm_vect[0].ref_idx == 20);
        assert(mp.xor_d64 == 1ull);
 
        {
            xm_vect.resize(0);
            block_xor_match_descr xmd;
            xmd.match_type = e_xor_match_BC; xmd.ref_idx = 20; xmd.xor_d64 = 3ull;
            xm_vect.push_back(xmd);
            xmd.match_type = e_xor_match_BC; xmd.ref_idx = 25; xmd.xor_d64 = 3ull << 60;
            xm_vect.push_back(xmd);
        }
        cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 11, (1ull << 1), e_xor_match_BC);
        assert(cnt == 2);
        mp = pm_vect[0];
        assert(pm_vect[0].ref_idx == 20);
        assert(mp.xor_d64 == 1ull);
        mp = pm_vect[1];
        assert(mp.ref_idx == 25);
        assert(mp.xor_d64 == 3ull << 60);
 
    }
 
    {
        bm::xor_complement_match match_type;
        bm::word_t BM_VECT_ALIGN blk[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
        bm::word_t BM_VECT_ALIGN blk_xor[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
 
        for (i = 0; i < bm::set_block_size; ++i)
            blk[i] = blk_xor[i] = 0;
 
        d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
        assert(d64 == ~0ull);
        assert(match_type == bm::e_xor_match_GC);
        for (unsigned k = 0; k < bm::block_waves; ++k)
        {
            assert(x_descr.sb_gc[k] == 1 || (k && x_descr.sb_gc[k] == 0));
            assert(x_descr.sb_xor_gc[k] == 1 || (k && x_descr.sb_xor_gc[k] == 0));
        } // for k
 
        blk[0] = 1;
        d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
        assert(!d64);
        assert(match_type == bm::e_no_xor_match);
 
        assert(x_descr.sb_gc[0] == 2);
        assert(x_descr.sb_xor_gc[0] == 2);
        for (unsigned k = 1; k < bm::block_waves; ++k)
        {
            assert(x_descr.sb_gc[k] == 1 || (k && x_descr.sb_gc[k] == 0));
            assert(x_descr.sb_xor_gc[k] == 1 || (k && x_descr.sb_xor_gc[k] == 0));
        } // for k
 
        // ----------------------------
        blk[0] = 1 | (1<<1) | (1<<2); blk_xor[0] = (1 << 1);
        d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
        assert(d64);
        assert(x_descr.sb_bc[0] == 3);
        assert(x_descr.sb_xor_bc[0] == 2);
        assert(match_type == bm::e_xor_match_BC);
 
 
        // ----------------------------
        blk[0] = 1; blk_xor[0] = 1;
        d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
        cout << x_descr.sb_xor_gc[0] << endl;
        assert(x_descr.sb_gc[0] == 2);
        assert(match_type == bm::e_xor_match_BC);
        // next assert hides non-critical discrepancy between SIMD versions
        assert(x_descr.sb_xor_gc[0] == 1 || x_descr.sb_xor_gc[0] == 0);
        assert(d64 == 1ull);
        for (unsigned k = 1; k < bm::block_waves; ++k)
        {
            assert(x_descr.sb_gc[k] == 1 || (k && x_descr.sb_gc[k] == 0));
            assert(x_descr.sb_xor_gc[k] == 1 || (k && x_descr.sb_xor_gc[k] == 0));
        } // for k
 
        Check_XOR_Product(blk, blk_xor, d64);
 
        blk[0] = (1 << 10) | (1 << 12) | (1 << 14) | ( 1 << 16) | (1 << 18) | (1<<19);
        blk_xor[0] = (1 << 11) | (1 << 13) | (1 << 15) | (1 << 17);
        unsigned off = (60 * bm::set_block_digest_wave_size);
        blk[off] = (1 << 10) | (1 << 12);
 
        d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
        assert(x_descr.sb_gc[0] == 11);
        assert(x_descr.sb_xor_gc[0] == 3);
        assert((d64 & 1));
        assert(match_type == bm::e_xor_match_GC);
 
        Check_XOR_Product(blk, blk_xor, d64);
 
        for (unsigned k = 1; k < bm::block_waves; ++k)
        {
            if (k!= 60)
            {
                assert(x_descr.sb_gc[k] == 0);
                assert(x_descr.sb_xor_gc[k] == 0);
            }
            else
            {
                assert(x_descr.sb_gc[60] == 4);
                assert(x_descr.sb_xor_gc[60] == 4);
            }
        } // for k
 
        blk_xor[off] = (1 << 10) | (1 << 11) | (1 << 12);
        d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
        assert(x_descr.sb_gc[0] == 11);
        assert(x_descr.sb_xor_gc[0] == 3);
        assert((d64 & 1) && (d64 & (1ull << 60)));
        assert(match_type == bm::e_xor_match_GC);
 
        for (unsigned k = 1; k < bm::block_waves; ++k)
        {
            if (k!= 60)
            {
                assert(x_descr.sb_gc[k] == 0);
                assert(x_descr.sb_xor_gc[k] == 0);
            }
            else
            {
                assert(x_descr.sb_gc[60] == 4);
                assert(x_descr.sb_xor_gc[60] == 2);
            }
        } // for k
 
        Check_XOR_Product(blk, blk_xor, d64);
 
    }
 
    cout << "---------------------------- TestBlockCountXORChange() test OK" << endl;
}
 
 
/*!
   \brief Converts bit block to GAP.
   \param dest - Destinatio GAP buffer.
   \param src - Source bitblock buffer.
   \param bits - Number of bits to convert.
   \param dest_len - length of the dest. buffer.
   \return  New length of GAP block or 0 if conversion failed
   (insufficicent space).
 
   @ingroup gapfunc
*/
template<typename T>
unsigned bit_convert_to_gap(T*  dest,
                            const unsigned*  src,
                            bm::id_t bits,
                            unsigned dest_len)
{
    T*  pcurr = dest;
    T*  end = dest + dest_len;
    unsigned bitval = (*src) & 1u;
    *pcurr = (T)bitval;
 
    ++pcurr;
    *pcurr = 0;
    unsigned bit_idx = 0;
    unsigned bitval_next;
 
    unsigned val = *src;
 
    do
    {
        // We can fast pace if *src == 0 or *src = 0xffffffff
 
        while (val == 0 || val == 0xffffffff)
        {
           bitval_next = val ? 1 : 0;
           if (bitval != bitval_next)
           {
               *pcurr++ = (T)(bit_idx-1);
               assert((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
               if (pcurr >= end)
               {
                   return 0; // OUT of memory
               }
               bitval = bitval_next;
           }
           bit_idx += unsigned(sizeof(*src) * 8);
           if (bit_idx >= bits)
           {
               goto complete;
           }
           ++src;
           val = *src;
        }
 
        unsigned mask = 1;
        while (mask)
        {
            // Now plane bitshifting. TODO: Optimization wanted.
 
            bitval_next = val & mask ? 1 : 0;
            if (bitval != bitval_next)
            {
                *pcurr++ = (T)(bit_idx-1);
                assert((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
                bitval = bitval_next;
                if (pcurr >= end)
                    return 0; // OUT of memory
            }
            mask <<= 1;
            ++bit_idx;
        } // while mask
 
        if (bit_idx >= bits)
            goto complete;
 
        ++src;
        val = *src;
 
    } while(1);
 
complete:
    *pcurr = (T)(bit_idx-1);
    unsigned len = (unsigned)(pcurr - dest);
    *dest = (T)((*dest & 7) + (len << 3));
    return len;
}
 
/*
static
void TestGAP_XOR()
{
   cout << "---------------------------- TestGAP_XOR()" << endl;
 
    unsigned gc, bc;
    {
       gap_vector gapv1(0);
       gap_vector gapv2(0);
       gap_word_t* gap_buf1 = gapv1.get_buf();
       gap_word_t* gap_buf2 = gapv2.get_buf();
 
 
        gap_operation_dry_xor(gap_buf1, gap_buf2, gc, bc);
        assert(bc == 0);
        assert(gc == 1);
 
        gapv1.set_bit(256);
        gapv2.set_bit(256);
 
        gap_operation_dry_xor(gap_buf1, gap_buf2, gc, bc);
        assert(bc == 0);
        assert(gc == 1);
 
        gapv1.set_bit(258);
        gapv2.set_bit(257);
        gapv1.set_bit(259);
        gapv1.set_bit(260);
 
        gap_operation_dry_xor(gap_buf1, gap_buf2, gc, bc);
        assert(bc == 4);
        assert(gc == 3);
 
    }
 
   cout << "---------------------------- TestGAP_XOR() - end" << endl;
}*/
 
static
void TestBlockToGAP()
{
    cout << "---------------------------- TestBlockToGAP" << endl;
    
    unsigned i;
    bm::word_t BM_VECT_ALIGN blk[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
 
    for (i = 0; i < bm::set_block_size; ++i)
        blk[i] = 0;
    
    {
       gap_vector gapv1(0);
       gap_vector gapv2(0);
       gap_word_t* gap_buf1 = gapv1.get_buf();
       *gap_buf1 = 0;
       unsigned len1 = bit_convert_to_gap(gap_buf1, blk, bm::gap_max_bits, bm::gap_max_buff_len);
       gap_word_t* gap_buf2 = gapv2.get_buf();
       unsigned len2 = bm::bit_to_gap(gap_buf2, blk, bm::gap_max_buff_len);
       print_gap(gapv2, 100);
       assert(len1 == len2);
       int cmp = bm::gapcmp(gap_buf1, gap_buf2);
       assert(cmp == 0);
 
       unsigned pos;
       bool f = bm::gap_find_first_diff(gap_buf1, gap_buf2, &pos);
       assert(!f);
    }
 
    unsigned test_arr[] = { 1, 2, 3, (~0u << 4), ~0u, (~0u >> 1), (~0u >> 2) };
    unsigned arr_size = sizeof(test_arr)/sizeof(test_arr[0]);
    for (unsigned k = 0; k < bm::set_block_size; ++k)
    {
        for (i = 0; i < bm::set_block_size; ++i)
            blk[i] = 0;
        for (i = 0; i < arr_size; ++i)
        {
            blk[k] = test_arr[i];
            
           gap_vector gapv1(0);
           gap_vector gapv2(0);
           gap_word_t* gap_buf1 = gapv1.get_buf();
           *gap_buf1 = 0;
           unsigned len1 = bit_convert_to_gap(gap_buf1, blk, bm::gap_max_bits, bm::gap_max_buff_len);
           print_gap(gapv1, 100);
           gap_word_t* gap_buf2 = gapv2.get_buf();
           unsigned len2 = bm::bit_to_gap(gap_buf2, blk, bm::gap_max_buff_len);
           assert(len1 == len2);
           assert(len1);
           print_gap(gapv2, 100);
           int cmp = bm::gapcmp(gap_buf1, gap_buf2);
           assert(cmp == 0);
 
           unsigned pos;
           bool f = bm::gap_find_first_diff(gap_buf1, gap_buf2, &pos);
           assert(!f);
        }
    } // for k
    
    cout << "Test arr - ok" << endl;
    
    {
       gap_vector gapv1(0);
       gap_vector gapv2(0);
       gap_word_t* gap_buf1 = gapv1.get_buf();
       *gap_buf1 = 0;
       gap_word_t* gap_buf2 = gapv2.get_buf();
       *gap_buf2 = 0;
 
        unsigned mask = 1u;
        for (unsigned k = 0; k < bm::set_block_size; ++k)
        {
            for (i = 0; i < bm::set_block_size; ++i)
                blk[i] = 0;
            
            blk[k] = mask;
            mask <<= 1;
            if (!mask)
                mask = 1u;
            
            *gap_buf1 = 0;
            *gap_buf2 = 0;
            unsigned len1 = bit_convert_to_gap(gap_buf1, blk, bm::gap_max_bits, bm::gap_max_buff_len);
            unsigned len2 = bm::bit_to_gap(gap_buf2, blk, bm::gap_max_buff_len);
            assert(len1);
            assert(len1 == len2);
            if (len1)
            {
               int cmp = bm::gapcmp(gap_buf1, gap_buf2);
               assert(cmp == 0);
 
               unsigned pos;
               bool f = bm::gap_find_first_diff(gap_buf1, gap_buf2, &pos);
               assert(!f);
            }
        }
    }
    
    cout << "mask shift - ok" << endl;
 
    {
       gap_vector gapv1(0);
       gap_vector gapv2(0);
       gap_word_t* gap_buf1 = gapv1.get_buf();
       *gap_buf1 = 0;
       gap_word_t* gap_buf2 = gapv2.get_buf();
       *gap_buf2 = 0;
 
        unsigned max_try = 1000000;
        for (unsigned k = 0; k < max_try; ++k)
        {
            for (i = 0; i < bm::set_block_size; ++i)
                blk[i] = 0;
            
            unsigned idx = (unsigned)rand() % bm::set_block_size;
            blk[idx] |= (unsigned)rand();
            idx = (unsigned)rand() % bm::set_block_size;
            blk[idx] |= (unsigned)rand();
            idx = (unsigned)rand() % bm::set_block_size;
            blk[idx] |= (unsigned)rand();
            idx = (unsigned)rand() % bm::set_block_size;
            blk[idx] |= (unsigned)rand();
 
            idx = (unsigned)rand() % bm::set_block_size;
            blk[idx] |= ~0u;
            idx = (unsigned)rand() % bm::set_block_size;
            blk[idx] |= (~0u << (rand()%31));
 
            *gap_buf1 = 0;
            *gap_buf2 = 0;
            unsigned len1 = bit_convert_to_gap(gap_buf1, blk, bm::gap_max_bits, bm::gap_max_buff_len);
            unsigned len2 = bm::bit_to_gap(gap_buf2, blk, bm::gap_max_buff_len);
            assert(len1);
            assert(len1 == len2);
            if (len1)
            {
               int cmp = bm::gapcmp(gap_buf1, gap_buf2);
               assert(cmp == 0);
               unsigned pos;
               bool f = bm::gap_find_first_diff(gap_buf1, gap_buf2, &pos);
               assert(!f);
            }
        }
    }
 
 
    cout << "---------------------------- TestBlockToGAP  OK" << endl;
 
}
 
 
static
void ShiftRotateTest()
{
    cout << "---------------------------- ShiftRotate test" << endl;
 
    bm::word_t BM_VECT_ALIGN blk0[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
    bm::word_t BM_VECT_ALIGN blk1[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
    unsigned i;
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        blk0[i] = blk1[i] = 1;
    }
 
    bm::bit_block_rotate_left_1(blk0);
    bm::bit_block_rotate_left_1_unr(blk1);
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        if (blk0[i] != 2 || blk0[i] != blk1[i])
        {
            cerr << "Cyclic rotate check failed" << endl;
            exit(1);
        }
    }
 
    bm::bit_block_rotate_left_1(blk0);
    bm::bit_block_rotate_left_1_unr(blk1);
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        if (blk0[i] != 4 || blk0[i] != blk1[i])
        {
            cerr << "Cyclic rotate check failed" << endl;
            exit(1);
        }
    }
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        blk0[i] = blk1[i] = 1u << 31;
    }
    bm::bit_block_rotate_left_1(blk0);
    bm::bit_block_rotate_left_1_unr(blk1);
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        if (blk0[i] != 1 || blk0[i] != blk1[i])
        {
            cerr << "Cyclic rotate check failed" << endl;
            exit(1);
        }
    }
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        blk0[i] = blk1[i] = unsigned(rand());
    }
 
    for (unsigned j = 0; j < bm::set_block_size * 32; ++j)
    {
        bm::bit_block_rotate_left_1(blk0);
        bm::bit_block_rotate_left_1_unr(blk1);
 
        for (i = 0; i < bm::set_block_size; ++i)
        {
            if (blk0[i] != blk1[i])
            {
                cerr << "Stress Cyclic rotate check failed" << endl;
                exit(1);
            }
        }
    }
 
    // SHIFT-R tests
    //
 
    unsigned acc0, acc1;
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        blk0[i] = blk1[i] = 1;
    }
 
    bm::bit_block_shift_r1(blk0, &acc0, 0);
    bm::bit_block_shift_r1_unr(blk1, &acc1, 0);
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        if (blk0[i] != blk1[i])
        {
            cerr << "1. SHIFT-r check failed" << endl;
            assert(0); exit(1);
        }
        assert(blk0[i] == 2);
    }
 
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        blk0[i] = blk1[i] = (1u << 31);
    }
 
    bm::bit_block_shift_r1(blk0, &acc0, 0);
    bm::bit_block_shift_r1_unr(blk1, &acc1, 0);
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        if (blk0[i] != blk1[i])
        {
            cerr << "2. SHIFT-r check failed" << endl;
            exit(1);
        }
    }
 
    for (i = 0; i < bm::set_block_size; ++i)
    {
        blk0[i] = blk1[i] = unsigned(rand());
    }
 
    for (unsigned j = 0; j < bm::set_block_size * 32; ++j)
    {
        bm::bit_block_shift_r1(blk0, &acc0, 0);
        bm::bit_block_shift_r1_unr(blk1, &acc1, 0);
        
        assert(bool(acc0) == bool(acc1));
 
        for (i = 0; i < bm::set_block_size; ++i)
        {
            if (blk0[i] != blk1[i])
            {
                cerr << "Stress SHIFT-r check failed" << endl;
                exit(1);
            }
        }
    }
 
    cout << "---------------------------- ShiftRotate test OK" << endl;
}
 
static
void BlockBitInsertTest()
{
    cout << "---------------------------- BlockBitInsertTest test" << endl;
    
    bm::word_t BM_VECT_ALIGN blk0[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
    bm::word_t BM_VECT_ALIGN blk1[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
    
    unsigned i;
    for (i = 0; i < bm::set_block_size; ++i)
        blk0[i] = blk1[i] = 0;
    
    {
        bm::word_t co = bm::bit_block_insert(blk0, 0, 1);
        assert(co == 0);
        assert(blk0[0]==1u);
        co = bm::bit_block_insert(blk0, 0, 1);
        assert(co == 0);
        assert(blk0[0]==3u);
        
        blk0[bm::set_block_size-1] = ~0u;
        co = bm::bit_block_insert(blk0, 0, 0);
        assert(co == 1);
        assert(blk0[0]==(3u << 1));
        assert(blk0[bm::set_block_size-1] == (~0u << 1));
        
        blk0[0] = ~0u;
        co = bm::bit_block_insert(blk0, 1, 0);
        assert(co == 1);
        assert(blk0[0]==(~0u & ~(1u << 1)));
        assert(blk0[bm::set_block_size-1] == (~0u << 2));
        
        blk0[0] = ~0u;
        co = bm::bit_block_insert(blk0, 31, 0);
        assert(co == 1);
        assert(blk0[0]==(~0u >> 1));
        assert(blk0[1]==3);
        assert(blk0[bm::set_block_size-1] == (~0u << 3));
 
        blk0[0] = 0u;
        co = bm::bit_block_insert(blk0, 31, 1);
        assert(co == 1);
        assert(blk0[0]==(1u << 31));
        assert(blk0[1]==(3u << 1));
        assert(blk0[bm::set_block_size-1] == (~0u << 4));
    }
    
    cout << "bit-insert stress 0..." << endl;
    {
        for (i = 0; i < bm::set_block_size; ++i)
            blk0[i] = blk1[i] = 0;
        
        blk0[0] = 1;
        for (i = 0; i < 65536; ++i)
        {
            bm::word_t co = bm::bit_block_insert(blk0, i, 0);
            assert(co == 0 || i == 65535);
            if (i < 65535)
            {
                unsigned t = bm::test_bit(blk0, i+1);
                assert(t);
            }
            for (unsigned k = 0; k < 65536; ++k)
            {
                if (k != i+1)
                {
                    unsigned t = bm::test_bit(blk0, k);
                    assert(!t);
                }
            } // for k
        } // for i
        for (i = 0; i < bm::set_block_size; ++i)
        {
            if (blk0[i] != blk1[i])
            {
                cerr << "Stress insert(0) failed" << endl;
                exit(1);
            }
        }
    }
    cout << "OK" << endl;
 
    cout << "bit-insert stress 1..." << endl;
    {
        for (i = 0; i < bm::set_block_size; ++i)
            blk0[i] = ~0u;
        
        for (i = 0; i < 65536; ++i)
        {
            bm::word_t co = bm::bit_block_insert(blk0, i, 0);
            assert(co == 1 || i == 65535);
            for (unsigned k = 0; k < 65536; ++k)
            {
                unsigned t = bm::test_bit(blk0, k);
                if (k <= i)
                {
                    assert(!t);
                }
                else
                {
                    assert(t);
                }
            } // for k
        } // for i
        for (i = 0; i < bm::set_block_size; ++i)
        {
            if (blk0[i] != blk1[i])
            {
                cerr << "Stress insert(1) failed" << endl;
                exit(1);
            }
        }
    }
    cout << "OK" << endl;
 
    
    cout << "---------------------------- BlockBitInsertTest test OK" << endl;
}
 
 
static
void BlockBitEraseTest()
{
    cout << "---------------------------- BlockBitEraseTest test" << endl;
    bm::word_t BM_VECT_ALIGN blk0[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
    bm::word_t BM_VECT_ALIGN blk1[bm::set_block_size] BM_VECT_ALIGN_ATTR = { 0 };
 
    bm::bit_block_set(blk0, 0);
    bm::bit_block_set(blk1, 0);
    
    {
        blk0[0] = 1;
        bm::bit_block_erase(blk0, 0, true);
        assert(blk0[0] == 0);
        assert(blk0[bm::set_block_size-1] == (1u << 31u));
        
        blk0[0] = ~0u;
        blk0[1] = 1u;
        blk0[bm::set_block_size-1] = (1u << 31u);
        bm::bit_block_erase(blk0, 0, false);
        assert(blk0[0] == ~0u);
        assert(blk0[1] == 0);
        assert(blk0[bm::set_block_size-1] == (1u << 30u));
        
        bm::bit_block_set(blk0, 0);
        blk0[1] = 15u; // ..01111
        bm::bit_block_erase(blk0, 31, false);
        assert(blk0[1] == 7u); // ..0111
        assert(blk0[0] == 1u << 31u);
 
        bm::bit_block_erase(blk0, 32, false);
        assert(blk0[1] == 3u); // ..011
 
        blk0[1] = 15u; // ..01111
        bm::bit_block_erase(blk0, 33, false);
        assert(blk0[1] == 7); //0b111
    }
    
    {
        bm::bit_block_set(blk0, ~0u);
        bm::word_t acc;
        bm::bit_block_shift_l1_unr(blk0, &acc, true);
        for (unsigned i = 0; i < bm::set_block_size; ++i)
        {
            assert(blk0[i] == ~0u);
        }
        bm::bit_block_erase(blk0, 0, false);
        for (unsigned i = 0; i < bm::set_block_size-1; ++i)
        {
            assert(blk0[i] == ~0u);
        }
        assert(blk0[bm::set_block_size-1] == ((~0u) >> 1) );
 
        bm::bit_block_shift_l1_unr(blk0, &acc, false);
        for (unsigned i = 0; i < bm::set_block_size-1; ++i)
        {
            assert(blk0[i] == ~0u);
        }
        assert(blk0[bm::set_block_size-1] == ((~0u) >> 2) );
        
        bm::bit_block_erase(blk0, 0, true);
        for (unsigned i = 0; i < bm::set_block_size-1; ++i)
        {
            assert(blk0[i] == ~0u);
        }
        assert(blk0[bm::set_block_size-1] == ((~0u >> 3) |  (1u << 31)));
    }
 
    cout << "bit-insert-erase stress 0..." << endl;
    unsigned c = 0;
    {
    bm::bit_block_set(blk0, 0);
    bm::bit_block_set(blk1, 0);
    
    blk0[bm::set_block_size-1] = (1u << 31);
    for (unsigned i = 65535; i != 0; --i)
    {
        unsigned t = bm::test_bit(blk0, i);
        assert(t);
        bm::bit_block_erase(blk0, 0, false);
        unsigned cnt = bm::bit_block_count(blk0);
        {
        auto cnt2 = bm::bit_block_count(blk0, ~0ull);
        assert(cnt2 == cnt);
        auto d = calc_block_digest0(blk0);
        cnt2 = bm::bit_block_count(blk0, d);
        assert(cnt2 == cnt);
        }
 
        c += cnt;
        if (cnt != 1)
        {
            unsigned control = 0;
            for (unsigned k = 0; k < 65536; ++k)
            {
                t = bm::test_bit(blk0, k);
                control += t;
            }
 
            t = bm::test_bit(blk0, i-1);
            assert(t);
            cerr << t << " " << control << endl;
            cerr << "i=" << i << " cnt=" << cnt;
            cerr << " CNT==1 failed!" << endl;
            assert(cnt == 1);
            exit(1);
        }
    } // for i
 
    std::cout << c << endl;
 
    bm::bit_block_set(blk0, 0);
 
    {
    blk0[bm::set_block_size-1] = (1u << 31);
    unsigned j = 0;
    for (unsigned i = 65535; i != 0; --i, ++j)
    {
        unsigned t = bm::test_bit(blk0, i);
        assert(t);
        bm::bit_block_erase(blk0, j, false);
        if (i <= j)
        {
            t = bm::test_bit(blk0, j);
            assert(!t);
            t = bm::test_bit(blk0, i);
            assert(t);
 
            auto cnt = bm::bit_block_count(blk0);
            assert(cnt);
            
            bm::bit_block_erase(blk0, i, false);
            t = bm::test_bit(blk0, i);
            assert(!t);
            cnt = bm::bit_block_count(blk0);
            assert(!cnt);
            {
            auto cnt2 = bm::bit_block_count(blk0, ~0ull);
            assert(cnt == cnt2);
            auto d = calc_block_digest0(blk0);
            cnt2 = bm::bit_block_count(blk0, d);
            assert(cnt2 == cnt);
            }
            break;
        }
        auto cnt = bm::bit_block_count(blk0);
        assert(cnt == 1);
    } // for i
    }
    
    {
        bm::bit_block_set(blk0, 0);
        for (unsigned i = 0; i < 65535; ++i)
        {
            for(unsigned j = i; j < 65535; ++j)
            {
                bm::bit_block_set(blk0, 0);
                unsigned bitcount = j - i + 1;
                assert(i + bitcount < 65536);
                bm::or_bit_block(blk0, i, bitcount);
                if (bitcount == 1)
                {
                    break;
                }
                unsigned bc = bm::bit_block_count(blk0);
                for (unsigned k = i + bitcount/2; k < i+bitcount; ++k)
                {
                    auto t = bm::test_bit(blk0, k);
                    assert(t);
 
                    bm::bit_block_erase(blk0, k, false);
                    
                    unsigned bc2 = bm::bit_block_count(blk0);
                    assert(bc2 == bc-1);
                    {
                    auto cnt2 = bm::bit_block_count(blk0, ~0ull);
                    assert(cnt2 == bc2);
                    auto d = calc_block_digest0(blk0);
                    cnt2 = bm::bit_block_count(blk0, d);
                    assert(cnt2 == bc2);
                    }
                    --bc;
                } // for k
                
            } // for j
        } // for i
    }
 
 
    }
    cout << "ok" << endl;
 
    cout << "---------------------------- BlockBitEraseTest test OK" << endl;
}
 
static
void EmptyBVTest()
{
    cout << "---------------------------- Empty bvector test" << endl;
 
    {
        bvect bv1;
        bvect bv2;
        
        bvect bv3(bv1 & bv2);
        bvect bv4 = (bv1 & bv2);
        
        std::vector< bvect > v;
        v.push_back(bvect());
    }
 
    {
        bvect  bv1;
        bm::id_t cnt = bv1.count_range(0, 10);
        if (cnt)
        {
            cerr << "Failed count_range()" << endl;
            exit(1);
        }
        bool b = bv1.test(0);
        if (b)
        {
            cerr << "Failed test" << endl;
            exit(1);
        }
        
        b = bv1.any();
        if (b)
        {
            cerr << "Failed any" << endl;
            exit(1);
        }
        
        bv1.set_bit(0);
        if (!bv1.any())
        {
            cerr << "Failed set_bit" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        bool b = bv1.set_bit_and(0, false);
        if (bv1.any() || b)
        {
            cerr << "Failed set_bit" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        bv1.set_range(0, 1, false);
        if (bv1.any())
        {
            cerr << "Failed set_range" << endl;
            exit(1);
        }
        bv1.set_range(0, 1, true);
        if (bv1.count()!=2)
        {
            cerr << "Failed set_range(0,1)" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        bv1.clear_bit(0);
        if (bv1.any())
        {
            cerr << "Failed clear_bit" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        bv1.clear();
        if (bv1.any())
        {
            cerr << "Failed clear()" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        bv1.invert();
        if (!bv1.any())
        {
            cerr << "Failed invert()" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        bvect  bv2;
        bv1.swap(bv2);
        if (bv1.any() || bv2.any())
        {
            cerr << "Failed swap()" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        if (bv1.get_first() != 0)
        {
            cerr << "Failed get_first()" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        if (bv1.extract_next(0) != 0)
        {
            cerr << "Failed extract_next()" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        bvect::statistics st;
        bv1.calc_stat(&st);
        if (st.memory_used == 0)
        {
            cerr << "Failed calc_stat()" << endl;
            exit(1);
        }
    }
    {
        bvect  bv1;
        bvect  bv2;
        bvect  bv3;
        bv1.bit_or(bv2);
        if (bv1.any())
        {
            cerr << "Failed bit_or()" << endl;
            exit(1);
        }
        bv2.set_bit(100000000);
        bv1.bit_or(bv2);
        if (!bv1.any())
        {
            cerr << "Failed bit_or()" << endl;
            exit(1);
        }
        bv1.bit_or(bv3);
        if (bv1.count()!=1)
        {
            cerr << "Failed bit_or()" << endl;
            exit(1);
        }
    }
    
    {
        bvect  bv1;
        bvect  bv2;
        bv1.bit_and(bv2);
        if (bv1.any())
        {
            cerr << "Failed bit_and()" << endl;
            exit(1);
        }
        bv2.set_bit(100000000);
        bv1.bit_and(bv2);
        if (bv1.any())
        {
            cerr << "Failed bit_and()" << endl;
            exit(1);
        }
        bv2.bit_and(bv1);
        if (bv2.count()!=0)
        {
            cerr << "Failed bit_and()" << endl;
            exit(1);
        }
    }
    
    {
        bvect  bv1;
        bvect::statistics st1;
        bv1.optimize(0, bvect::opt_compress, &st1);
        if (st1.memory_used == 0)
        {
            cerr << "Failed calc_stat()" << endl;
            exit(1);
        }
        bv1.optimize_gap_size();
    }
    
    {
        bvect  bv1;
        bvect  bv2;
        
        int r = bv1.compare(bv2);
        if (r != 0)
        {
            cerr << "Failed compare()" << endl;
            exit(1);
            
        }
        bv2.set_bit(1000);
        r = bv1.compare(bv2);
        if (r == 0)
        {
            cerr << "Failed compare()" << endl;
            exit(1);
            
        }
        r = bv2.compare(bv1);
        if (r == 0)
        {
            cerr << "Failed compare()" << endl;
            exit(1);
        }
    }
    
    {
        bvect  bv1;
        bvect::enumerator en1 = bv1.first();
        bvect::enumerator en2 = bv1.get_enumerator(65535);
        CompareEnumerators(en1, en2);
        if (en1.valid() || en2.valid())
        {
            cerr << "failed first enumerator" << endl;
            exit(1);
        }
    }
 
    {
        bvect bv1;
        bv1.resize(0);
 
        bv1.invert();
        assert(!bv1.any());
        assert(bv1.size()==0);
    }
    
    cout << "---------------------------- Empty bvector test OK" << endl;
    
}
 
 
 
 
static
void BasicFunctionalityTest()
{
    cout << "---------------------------- Basic functinality test" << endl;
 
    assert(ITERATIONS < BITVECT_SIZE);
 
    bvect_mini     bvect_min(BITVECT_SIZE);
    bvect          bvect_full;
    bvect          bvect_full1;
    bvect::rs_index_type bc_arr;
    bvect::rs_index_type bc_arr1;
 
    printf("\nBasic functionality test.\n");
    
    {
        bvect::rs_index_type rs_idx;
        for (unsigned i = 0; i < ITERATIONS; ++i)
        {
            rs_idx.resize(i);
        }
    }
 
 
    // clear_range with memory de-allocation
    {
        bvect::statistics st;
        bvect bv { 65536, 65538};
        bv.calc_stat(&st);
        assert(st.bit_blocks == 1);
 
        bv.clear_range(65536, 65536+65535);
        bv.calc_stat(&st);
        assert(st.bit_blocks == 0);
 
    }
 
 
    {
        bvect::statistics st;
        bvect bv;
        bv.init(256, false/* NOT allocate secondary structures*/);
        bv.calc_stat(&st);
        assert(st.ptr_sub_blocks == 0);
    }
    {
        bvect::statistics st;
        bvect bv;
        bv.init(256, true/*allocate secondary structures*/);
        bv.calc_stat(&st);
        assert(st.ptr_sub_blocks == 256);
    }
 
    // filling vectors with regular values
    
    cout << "test data generation... " << endl;
    unsigned i;
    for (i = 0; i < ITERATIONS; ++i)
    {
        bvect_min.set_bit(i);
        bvect_full.set_bit(i);
 
        bvect_full.build_rs_index(&bc_arr);
        
        bm::id_t pos1, pos2, pos3, pos4, pos5;
        auto rf1 = FindRank(bvect_full, i+1, 0, pos1);
        auto rf2 = bvect_full.find_rank(i+1, 0, pos2);
        auto rf3 = bvect_full.find_rank(i+1, 0, pos3);
        auto rf4 = bvect_full.select(i+1, pos4, bc_arr);
 
        assert(rf1);
        assert(rf2);
        assert(rf3);
        assert(rf4);
        if (pos1 != pos2 || pos1 != pos3 || pos1 != pos4)
        {
            rf2 = bvect_full.find_rank(i+1, 0, pos2);
            cerr << "1.Rank check error!\n"
                 << " pos1 = " << pos1
                 << " pos2 = " << pos2
                 << " pos3 = " << pos3
                 << " pos4 = " << pos4
                 << endl;
                 ;
            exit(1);
        }
 
        {
            bvect bv_opt(bvect_full);
            bv_opt.optimize();
            bv_opt.build_rs_index(&bc_arr);
            auto rf5 = bv_opt.select(i+1, pos5, bc_arr);
            assert(rf5);
            assert(pos1 == pos5);
        }
 
    }
 
    bvect_full1.set_range(0, ITERATIONS-1);
 
    bvect_full1.build_rs_index(&bc_arr1);
 
    cout << "Rank check 2" << endl;
 
    for (i = 0; i < ITERATIONS; ++i)
    {
        bm::id_t pos1, pos2, pos3, pos4;
        auto rf1 = FindRank(bvect_full1, i+1, 0, pos1);
        auto rf2 = bvect_full1.find_rank(i+1, 0, pos2);
        auto rf3 = bvect_full1.find_rank(i+1, 0, pos3);
        auto rf4 = bvect_full1.select(i+1, pos4, bc_arr1);
        assert(rf1);
        assert(rf2);
        assert(rf3);
        assert(rf4);
        if (pos1 != pos2 || pos1 != pos3 || pos1 != pos4)
        {
            rf2 = bvect_full1.find_rank(i+1, 0, pos2);
            cerr << "2.Rank check error!\n"
                 << " pos1 = " << pos1
                 << " pos2 = " << pos2
                 << " pos3 = " << pos3
                 << " pos4 = " << pos4
                 << endl;
                 ;
            exit(1);
        }
        if (i % 1000 == 0)
        {
            if (!is_silent)
                cout << "\r" << i << " / " << ITERATIONS << flush;
        }
    }
    cout << endl;
 
    bvect::rs_index_type rs_idx_full;
    bvect_full.build_rs_index(&rs_idx_full);
 
    bvect::rs_index_type rs_idx_full1;
    bvect_full1.build_rs_index(&rs_idx_full1);
 
    CheckCountRange(bvect_full, rs_idx_full, 0, ITERATIONS);
    CheckCountRange(bvect_full, rs_idx_full, 10, ITERATIONS+10);
    CheckCountRange(bvect_full1, rs_idx_full1, 0, ITERATIONS);
    CheckCountRange(bvect_full1, rs_idx_full1, ITERATIONS-10, ITERATIONS+10);
    CheckCountRange(bvect_full1, rs_idx_full1, 10, ITERATIONS+10);
 
    if (bvect_full1 != bvect_full)
    {
        cout << "set_range failed!" << endl;
        print_stat(cout,bvect_full1);
        exit(1);
    }
 
    print_stat(cout,bvect_full);
    print_stat(cout,bvect_full1);
 
    // checking the results
    unsigned count_min = 0;
 
    for (i = 0; i < ITERATIONS; ++i)
    {
        if (bvect_min.is_bit_true(i))
            ++count_min;
    }
 
    cout << "Rank check 3" << endl;
    for (i = 0; i < ITERATIONS; ++i)
    {
        CheckCountRange(bvect_full, rs_idx_full, i, ITERATIONS);
        CheckCountRange(bvect_full1, rs_idx_full1, i, ITERATIONS);
    }
 
    cout << "Rank check 4" << endl;
    for (i = ITERATIONS; i > 0; --i)
    {
        CheckCountRange(bvect_full, rs_idx_full, 0, i);
        CheckCountRange(bvect_full1, rs_idx_full1, 0, i);
    }
    
    unsigned count_full = bvect_full.count();
 
    if (count_min == count_full)
    {
        printf("simple count test ok.\n");
    }
    else
    {
        printf("simple count test failed count_min = %i  count_full = %i\n", 
               count_min, count_full);
        exit(1);
    }
 
 
    // detailed vectors verification
 
    CheckVectors(bvect_min, bvect_full, ITERATIONS);
 
    // now clearning
 
    for (i = 0; i < ITERATIONS; i+=2)
    {
        bvect_min.clear_bit(i);
        bvect_full.clear_bit(i);
        bvect_full1.set_range(i, i, false);
    }
 
    CheckVectors(bvect_min, bvect_full, ITERATIONS);
    CheckVectors(bvect_min, bvect_full1, ITERATIONS);
 
    for (i = 0; i < ITERATIONS; ++i)
    {
        bvect_min.clear_bit(i);
    }
    bvect_full.clear();
 
    CheckVectors(bvect_min, bvect_full, ITERATIONS);
 
    cout << "Random step filling" << endl;
 
    for (i = (unsigned)rand()%10; i < ITERATIONS; i+=(unsigned)rand()%10)
    {
        bvect_min.clear_bit(i);
        bvect_full.clear_bit(i);
    }
    
    CheckVectors(bvect_min, bvect_full, ITERATIONS);
 
    bvect bv1;
    bvect bv2;
 
    bv1[10] = true;
    bv1[1000] = true;
 
    bv2[200] = bv2[700] = bv2[500] = true;
 
    bv1.swap(bv2);
 
    if (bv1.count() != 3)
    {
        cout << "Swap test failed!" << endl;
        exit(1);
    }
 
    if (bv2.count() != 2)
    {
        cout << "Swap test failed!" << endl;
        exit(1);
    }
 
    {
        //bm::standard_alloc_pool pool;
        bvect::allocator_pool_type pool;
        bvect bv3, bv4;
        bv3.set_allocator_pool(&pool);
        bv3.set(10, true);
        bv4.set(10, true);
        bv4.set(10, false);
        bv3 &= bv4;
    }
    {
        bvect bv(100);
        bv.set_range(150, 151);
        assert(bv.size() == 152);
        bv.set_bit(160);
        assert(bv.size() == 161);
    }
}
 
 
static
void generate_test_vectors(std::vector<bm::id_t> &v1,
                           std::vector<bm::id_t> &v2,
                           std::vector<bm::id_t> &v3,
                           unsigned vector_max)
{
    bm::id_t j;
    for (j = 0; j < vector_max; j += 2)
        v1.push_back(j);
    for (j = 0; j < vector_max; j += 5)
        v2.push_back(j);
    for (j = 0; j < vector_max; j += 120)
        v3.push_back(j);
}
 
 
static
void BvectorBulkSetTest()
{
    cout << "---------------------------- Bvector BULK set test" << endl;
 
    
    {
        unsigned ids[] = { 0 };
        
        bvect bv1, bv2, bv3;
        {
        bvect::bulk_insert_iterator iit = bv3.inserter();
        for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
        {
            bv1.set(ids[i]);
            iit = ids[i];
        }
        }
        bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
        
        int cmp = bv1.compare(bv2);
        assert(cmp==0);
        cmp = bv1.compare(bv3);
        assert(cmp==0);
        
        bv2.set(0);
        bv2.keep(&ids[0], sizeof(ids)/sizeof(ids[0]));
        assert(bv2.count()==1);
        assert(bv2.test(0));
    }
 
    {
        unsigned ids[] = {65535, bm::id_max };
        unsigned cnt;
        bvect bv2;
        bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
        
        cnt = bv2.count();
        cout << cnt << endl;
 
        assert(cnt == 1);
        assert(bv2.test(ids[0]));
    }
 
    // set bits in FULL vector
    {
        unsigned ids[] = {0, 10, 65535, bm::id_max-1, bm::id_max };
        unsigned cnt;
        bvect bv2;
        bv2.invert();
        struct bvect::statistics st1, st2;
        bv2.calc_stat(&st1);
 
        bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
 
        bv2.calc_stat(&st2);
        assert(st1.bit_blocks == st2.bit_blocks);
        assert(st1.gap_blocks == st2.gap_blocks);
 
        cnt = bv2.count();
        cout << cnt << endl;
 
        assert(cnt == bm::id_max);
    }
 
    // test correct sizing
    {
        unsigned ids[] = {65536 };
        bvect bv1;
        bv1.resize(10);
 
        bv1.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
        assert(bv1.size()==65536+1);
        bv1.keep(&ids[0], sizeof(ids)/sizeof(ids[0]));
        cout << bv1.size() << endl;
        assert(bv1.size()==65536+1);
    }
 
    {
        unsigned ids[] = {65536, 1280000, 65535 };
        bvect bv1, bv2;
 
        for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
            bv1.set(ids[i]);
        
        bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
        int cmp = bv1.compare(bv2);
        assert(cmp==0);
        
        bv2.keep(&ids[0], sizeof(ids)/sizeof(ids[0]));
        cmp = bv1.compare(bv2);
        assert(cmp==0);
    }
 
 
    {
    unsigned ids[] = { 0, 1, 2, 3, 4, 5, 256, 1024, 1028, 256000 };
    
    bvect bv1, bv2;
    for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
        bv1.set(ids[i]);
    bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
    
    DetailedCompareBVectors(bv1, bv2);
 
    int cmp = bv1.compare(bv2);
    assert(cmp==0);
    
    {
        bvect bv_inv;
        bv_inv.flip();
        unsigned keep_cnt = sizeof(ids)/sizeof(ids[0]);
        bv_inv.keep(&ids[0], keep_cnt, bm::BM_SORTED);
        unsigned cnt_inv2 = bv_inv.count();
        assert(cnt_inv2 == keep_cnt);
        for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
        {
            assert(bv_inv.test(ids[i]));
        }
    }
    
    bvect bv3, bv4, bv5;
    bv3.invert();
    bv4.invert();
    bv5.invert();
 
    {
        bvect::bulk_insert_iterator iit = bv5.inserter();
        for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
        {
            bv3.set(ids[i]);
            iit = ids[i];
        }
    }
    bv4.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
    cmp = bv3.compare(bv4);
    assert(cmp==0);
    cmp = bv4.compare(bv3);
    assert(cmp==0);
 
    cmp = bv3.compare(bv5);
    assert(cmp==0);
    }
    
    {
    unsigned vector_max = 4000000;
    std::vector<bm::id_t> v1, v2, v3;
    generate_test_vectors(v1, v2, v3, vector_max);
 
    for (unsigned k = 0; k < 2; ++ k)
    {
        bvect bvu, bvuc;
        bvect bv1, bv2, bv3, bv11;
        bvect bv1c, bv2c, bv3c;
        
        {
        bvect::bulk_insert_iterator iit(bv11);
        for (unsigned i = 0; i < v1.size(); ++i)
        {
            bv1c.set(v1[i]);
            iit = v1[i];
        }
        iit.flush();
        }
        
        for (unsigned i = 0; i < v2.size(); ++i)
            bv2c.set(v2[i]);
        for (unsigned i = 0; i < v3.size(); ++i)
            bv3c.set(v3[i]);
        
        // union of 3 vectors
        bvuc = bv1c;
        bvuc |= bv2c;
        bvuc |= bv3c;
 
        bv1.set(&v1[0], unsigned(v1.size()));
        bv2.set(&v2[0], unsigned(v2.size()));
        bv3.set(&v3[0], unsigned(v3.size()));
 
        // imported union of 3 vectors
        bvu.set(&v1[0], unsigned(v1.size()));
        bvu.set(&v2[0], unsigned(v2.size()));
        bvu.set(&v3[0], unsigned(v3.size()));
 
        cout << bv1.count() << " " << bv1c.count() << endl;
        
        int cmp;
        cmp = bv1c.compare(bv1);
        if (cmp != 0)
        {
            DetailedCompareBVectors(bv1, bv1c);
        }
        assert(cmp==0);
        cmp = bv2c.compare(bv2);
        assert(cmp==0);
        cmp = bv3c.compare(bv3);
        assert(cmp==0);
        cmp = bv1.compare(bv11);
        assert(cmp==0);
 
        cmp = bvuc.compare(bvu);
        assert(cmp == 0);
        
        {
            std::random_device rd;
            std::mt19937 g(rd());
            
            std::shuffle(v1.begin(), v1.end(), g);
            std::shuffle(v2.begin(), v2.end(), g);
            std::shuffle(v3.begin(), v3.end(), g);
        }
    }
    
    
    }
    
    cout << "Bulk bvector<>::set() stress.." << endl;
    {
        unsigned vector_max =40000000;
        unsigned delta_max = 65537;
 
        bvect bv1, bv2;
        bvect bv1c;
        std::vector<bm::id_t> v1;
 
        for (unsigned delta = 1; delta < delta_max; ++delta)
        {
            v1.resize(0);
            bvect::bulk_insert_iterator iit(bv2);
            for (unsigned i = 0; i < vector_max; i+=delta)
            {
                v1.push_back(i);
                iit = i;
            }
            iit.flush();
            
            bv1.set(&v1[0], unsigned(v1.size()));
            bm::combine_or(bv1c, v1.begin(), v1.end());
            
            int cmp = bv1.compare(bv1c);
            if (cmp!=0)
            {
                cerr << "1.Failed bulk set test at delta=" << delta << endl;
                exit(1);
            }
            cmp = bv1.compare(bv2);
            if (cmp!=0)
            {
                cerr << "2.Failed bulk set test at delta=" << delta << endl;
                exit(1);
            }
            
            // test AND/keep
            {
                bvect bv3(bv1);
                bvect bv4;
                bv3.keep(&v1[0], unsigned(v1.size()));
                bv4.set(&v1[0], unsigned(v1.size()));
                cmp = bv3.compare(bv4);
                if (cmp!=0)
                {
                    cerr << "3.Failed keep() test at delta=" << delta << endl;
                    exit(1);
                }
                if (v1.size())
                {
                    bv3.keep(&v1[0], 1);
                    assert(bv3.count()==1);
                    assert(bv3.test(v1[0]));
                }
            }
 
            bv1.clear();
            bv1c.clear();
            bv2.clear();
 
            if (delta % 256 == 0)
            {
                if (!is_silent)
                    cout << "\r" << delta << "/" << delta_max << flush;
            }
            
        } // for delta
        cout << endl;
    }
    
    
    cout << "---------------------------- Bvector BULK set test OK\n" << endl;
}
 
 
 
static
void RankFindTest()
{
    cout << "---------------------------- Find Rank test" << endl;
    
    {
    bvect bv1;
    bv1[30] = true;
    bv1[65534] = true;
 
    bvect::rs_index_type bc_arr1;
    bv1.build_rs_index(&bc_arr1);
 
    bool rf1, rf2, rf3;
    bm::id_t pos, pos1;
    rf1 = bv1.find_rank(1, 20, pos);
    rf3 = bv1.find_rank(1, 20, pos1, bc_arr1);
    assert(rf1);
    assert(rf3);
    assert(pos == 30);
    assert(pos1 == 30);
 
    rf2 = bv1.find_rank(2, 30, pos);
    rf3 = bv1.find_rank(2, 30, pos1, bc_arr1);
    assert(rf2);
    assert(rf3);
    assert(pos == 65534);
    assert(pos1 == 65534);
    }
 
 
    cout << "Test bvector<>::select()" << endl;
    {
        bvect::size_type r(65536*256-1), pos;
 
        bvect bv;
        bv.set_range(0, r);
        bv.optimize();
 
        bvect::rs_index_type rs_idx;
        bv.build_rs_index(&rs_idx);
 
        struct bvect::statistics st;
        bv.calc_stat(&st);
        assert(st.bit_blocks == 0);
        assert(st.gap_blocks == 0);
 
        bvect::size_type i;
        for (i = 0; i <=r; ++i)
        {
            bvect::size_type ri = bv.rank(i, rs_idx);
            assert(ri == (i+1));
            bool f = bv.select(ri, pos, rs_idx);
            assert(f);
            assert(pos == i);
        }
        bool f = bv.select(i+1, pos, rs_idx);
        assert(!f);
    }
    
    cout << "Find Rank test stress 1\n" << endl;
    
    {
        const unsigned max_size = 2000000;
        bvect bv1;
        for (unsigned i = 0; i < max_size;)
        {
            bv1.set(i);
            i += (unsigned)rand()%5;
        }
        bvect::rs_index_type bc_arr1;
        bv1.build_rs_index(&bc_arr1);
 
        
        for (unsigned i = 0; i < max_size; ++i)
        {
            bool rf1, rf3;
            bm::id_t pos, pos1;
            
            rf1 = bv1.find_rank(0, i, pos);
            rf3 = bv1.find_rank(0, i, pos1, bc_arr1);
            assert (rf1 == rf3);
            if (rf1)
            {
                if (pos != pos1)
                {
                    cerr << "Rank cmp test failed! i=" << i
                         << " pos="  << pos
                         << " pos1=" << pos1
                         << endl;
                    exit(1);
                }
            }
            
            rf1 = bv1.find_rank(i, max_size-i, pos);
            rf3 = bv1.find_rank(i, max_size-i, pos1, bc_arr1);
            assert (rf1 == rf3);
            if (rf1)
            {
                if (pos != pos1)
                {
                    cerr << "Rank cmp test failed! i=" << i
                         << " pos="  << pos
                         << " pos1=" << pos1
                         << endl;
                    exit(1);
                }
            }
            if (i % 100 == 0)
                if (!is_silent)
                    cout << "\r" << i << "/" << max_size << flush;
        } // for
        cout << endl;
    }
    
    cout << "---------------------------- Find Rank test OK" << endl;
}
 
static
void BvectorIncTest()
{
    cout << "---------------------------- Bvector inc test" << endl;
    
    {
    bvect bv1;
    bool b;
    
    b = bv1.inc(0);
    assert(!b);
    b = bv1.inc(0);
    assert(b);
    
    b = bv1.inc(10);
    assert(!b);
    b = bv1.inc(10);
    assert(b);
    }
    
    {
    bvect bv1(BM_GAP);
    bool b;
    
    assert(bv1.count()==0);
    
    b = bv1.inc(0);
    assert(!b);
    cout << bv1.count() << endl;
    assert(bv1.count()==1);
    b = bv1.inc(0);
    assert(b);
    assert(bv1.count()==0);
 
    b = bv1.inc(10);
    assert(!b);
    b = bv1.inc(10);
    assert(b);
    }
 
    {
    bvect bv1(BM_GAP);
    bool b;
 
    bv1.flip();
    
    b = bv1.inc(0);
    assert(b);
    b = bv1.inc(0);
    assert(!b);
    
    b = bv1.inc(10);
    assert(b);
    b = bv1.inc(10);
    assert(!b);
    }
 
    cout << "---------------------------- Bvector inc test OK" << endl;
}
 
// -----------------------------------------------------------------------
 
static
void optimize_fill(bvect& bv, bvect::size_type base, unsigned inc,
                   bvect::size_type max_bits = bm::gap_max_bits,
                   bool value = true)
{
    for (bvect::size_type i = 0; i < bm::set_sub_array_size; ++i)
    {
        bvect::size_type base_idx = i * bm::gap_max_bits;
        for (bvect::size_type j = base; j < max_bits; j += inc)
        {
            bv.set(base_idx + j, value);
        } // for j
    } // for i
}
 
static
void OptimizeTest()
{
    cout << "---------------------------- Bvector Optimize test" << endl;
    BM_DECLARE_TEMP_BLOCK(tb)
 
    {
        bvect bv;
        optimize_fill(bv, 0, 1, bm::gap_max_bits, true);
        
        bvect::statistics st1;
        bv.calc_stat(&st1);
        
        assert(st1.bit_blocks == bm::set_sub_array_size);
        assert(st1.gap_blocks == 0);
        assert(st1.ptr_sub_blocks == 1);
        
        bv.optimize(tb, bvect::opt_compress, &st1);
 
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == 0);
        assert(st1.ptr_sub_blocks == 0);
        
        bv.calc_stat(&st1);
        
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == 0);
        assert(st1.ptr_sub_blocks == 0);
    }
 
    {
        bvect::statistics st;
        bvect bv;
        bv.set(10);
        bv.set(65536);
        bv.optimize_range(0, 0, tb, bvect::opt_compress);
        bv.calc_stat(&st);
        assert(st.bit_blocks == 1);
        assert(st.gap_blocks == 1);
        bv.optimize_range(0, bm::id_max, tb, bvect::opt_compress);
        bv.calc_stat(&st);
        assert(st.bit_blocks == 0);
        assert(st.gap_blocks == 2);
    }
 
 
    {
        bvect::statistics st;
 
        bvect bv;
        bv.optimize_range(0, 0, tb, bvect::opt_compress);
        bv.invert();
 
        bv.optimize_range(0, 65536, tb, bvect::opt_compress);
        bv.calc_stat(&st);
        assert(st.bit_blocks == 1);
        assert(st.gap_blocks == 0);
 
        bv.optimize_range(65536, bm::id_max-1, tb, bvect::opt_compress);
        bv.calc_stat(&st);
        assert(st.bit_blocks == 0);
        assert(st.gap_blocks == 1);
 
    }
 
    
    {
        bvect bv;
        optimize_fill(bv, 0, 100, bm::gap_max_bits, true);
        optimize_fill(bv, 0, 100, bm::gap_max_bits, false);
 
        bvect::statistics st1;
        bv.calc_stat(&st1);
        
        assert(st1.bit_blocks == bm::set_sub_array_size);
        assert(st1.gap_blocks == 0);
        assert(st1.ptr_sub_blocks == 1);
        
        bv.optimize(tb, bvect::opt_compress, &st1);
 
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == 0);
        assert(st1.ptr_sub_blocks == 0);
    }
 
 
    {
        bvect bv(BM_GAP);
        optimize_fill(bv, 0, 1, bm::gap_max_bits, true);
        
        bvect::statistics st1;
        bv.calc_stat(&st1);
        
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == bm::set_sub_array_size);
        assert(st1.ptr_sub_blocks == 1);
        
        bv.optimize(tb, bvect::opt_compress, &st1);
 
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == 0);
        assert(st1.ptr_sub_blocks == 0);
        
        bv.calc_stat(&st1);
        
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == 0);
        assert(st1.ptr_sub_blocks == 0);
    }
    
    {
        bvect bv(BM_GAP);
        optimize_fill(bv, 0, 1000, bm::gap_max_bits, true);
        optimize_fill(bv, 0, 1000, bm::gap_max_bits, false);
 
        bvect::statistics st1;
        bv.calc_stat(&st1);
        
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == bm::set_sub_array_size);
        assert(st1.gaps_by_level[0] == 0);
        assert(st1.gaps_by_level[1] == bm::set_sub_array_size);
        assert(st1.ptr_sub_blocks == 1);
        
        bv.optimize(tb, bvect::opt_compress, &st1);
 
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == 0);
        assert(st1.ptr_sub_blocks == 0);
    }
    
    {
        bvect bv(BM_GAP);
        optimize_fill(bv, 0, 1000, bm::gap_max_bits, true);
        optimize_fill(bv, 1, 1, bm::gap_max_bits, false);
 
        bvect::statistics st1;
        bv.calc_stat(&st1);
        
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == bm::set_sub_array_size);
        assert(st1.gaps_by_level[0] == 0);
        assert(st1.gaps_by_level[1] == bm::set_sub_array_size);
        assert(st1.ptr_sub_blocks == 1);
        
        bv.optimize(tb, bvect::opt_compress, &st1);
 
        assert(st1.bit_blocks == 0);
        assert(st1.gap_blocks == bm::set_sub_array_size);
        assert(st1.ptr_sub_blocks == 1);
        assert(st1.gaps_by_level[0] == bm::set_sub_array_size);
        assert(st1.gaps_by_level[1] == 0);
    }
 
 
    cout << "---------------------------- Bvector Optimize test OK" << endl;
}
 
 
// -----------------------------------------------------------------------
 
static
void generate_sparse_bvector(bvect& bv,
                             unsigned min = 0,
                             unsigned max = 40000000,
                             unsigned fill_factor = 65536)
{
    bvect::bulk_insert_iterator iit(bv);
    unsigned ff = fill_factor / 10;
    for (unsigned i = min; i < max; i+= ff)
    {
        //bv.set(i);
        iit = i;
        ff += ff / 2;
        if (ff > fill_factor)
            ff = fill_factor / 10;
    }
    iit.flush();
}
 
 
static
void GenerateShiftTestCollection(std::vector<bvect>* target,
                            unsigned count = 30,
                            unsigned vector_max = 40000000,
                            bool optimize = true)
{
    assert(target);
    bvect bv_common; // sub-vector common for all collection
    generate_sparse_bvector(bv_common, vector_max/10, vector_max, 250000);
    
    unsigned cnt1 = (count / 2);
    
    unsigned i = 0;
    
    for (i = 0; i < cnt1; ++i)
    {
        std::unique_ptr<bvect> bv (new bvect);
        generate_bvector(*bv, vector_max, optimize);
        *bv |= bv_common;
        if (optimize)
            bv->optimize();
        target->push_back(std::move(*bv));
    } // for
    
    unsigned fill_factor = 10;
    for (; i < count; ++i)
    {
        std::unique_ptr<bvect> bv (new bvect);
        
        FillSetsIntervals(0, *bv, vector_max/ 10, vector_max, fill_factor);
        *bv |= bv_common;
 
        target->push_back(std::move(*bv));
    } // for
}
 
 
 
static
void BvectorShiftTest()
{
    cout << "---------------------------- Bvector SHIFT test" << endl;
 
 
    {
    bvect bv;
    
    bv.set(bm::id_max-1);
    bv.shift_right();
    print_bv(bv);
    assert(bv.count()==0);
    }
    
    {
    bvect bv(BM_GAP);
    
    bv.set(bm::id_max-1);
    bv.optimize();
    bv.shift_right();
    assert(bv.count()==0);
    }
    
    {
        bvect bv;
        
        bv.set();
        auto cnt1 = bv.count();
        bv.shift_right();
        auto cnt2 = bv.count();
        assert(cnt1-1 == cnt2);
        bool b = bv.test(0);
        assert(!b);
    }
    {
        bvect bv;
        bv.set();
        bv.set(bm::gap_max_bits * bm::set_sub_array_size, false);
        
        auto cnt1 = bv.count();
        bv.shift_left();
        auto cnt2 = bv.count();
        assert(cnt1-1 == cnt2);
        bool b = bv.test(bm::id_max-1);
        assert(!b);
        b = bv.test(bm::id_max-2);
        assert(b);
        b = bv.test(bm::gap_max_bits * bm::set_sub_array_size);
        assert(b);
        b = bv.test(bm::gap_max_bits * bm::set_sub_array_size - 1);
        assert(!b);
    }
    
    {
        bvect bv;
        
        bv.set();
        auto cnt1 = bv.count();
        bv.shift_left();
        auto cnt2 = bv.count();
        assert(cnt1-1 == cnt2);
        bool b = bv.test(bm::id_max-1);
        assert(!b);
    }
 
 
 
    {
    bvect bv;
 
    bv.set(0);
    bv.set(65535);
    bv.set(bm::id_max-1);
    bvect bv1(bv);
    
    bvect bv2(bm::BM_GAP);
    bv2 = bv;
    bv2.optimize();
 
    ShiftRight(&bv, 1);
    assert(bv.count() == 2);
    assert(bv.test(1));
    assert(bv.test(65536));
 
    bv1.shift_right();
    print_bv(bv1);
    int cmp = bv.compare(bv1);
    assert(cmp == 0);
    
    bv2.shift_right();
    print_bv(bv2);
    cmp = bv.compare(bv2);
    assert(cmp == 0);
    struct bvect::statistics st;
    bv2.calc_stat(&st);
    assert(st.gap_blocks >= 2);
 
    }
    
    {
    bvect bv(BM_GAP);
    struct bvect::statistics st;
    
    for (unsigned i = 0; i < 65536; ++i)
    {
        bv.set(i);
    }
    bv.calc_stat(&st);
    assert(st.gap_blocks == 1);
    
    auto cnt = bv.count();
    bv.shift_right();
    assert(bv.test(0)==0);
    assert(bv.count() == cnt);
    
    bv.calc_stat(&st);
    auto bcnt = st.bit_blocks + st.gap_blocks;
    assert(bcnt == 2);
    assert(st.gap_blocks);
    for (unsigned i = 0+1; i < 65536+1; ++i)
    {
        assert(bv.test(i));
    }
    }
 
 
    {
    cout << " inverted test" << endl;
    bvect bv;
    bv.invert();
    unsigned cnt = bv.count();
    bool carry_over = bv.shift_right();
    assert(carry_over);
    unsigned cnt1 = bv.count();
    assert(cnt1 == cnt - 1);
    assert(bv.test(0)==0);
    assert(bv.test(1)==1);
 
    struct bvect::statistics st;
    bv.calc_stat(&st);
    auto bcnt = st.bit_blocks + st.gap_blocks;
    assert(bcnt == 2);
 
    }
    
    {
    cout << " 3-bit optimized test" << endl;
    bvect bv;
    
    bv.set(0);
    bv.set(65535);
    bv.set(66000);
    bv.optimize();
    bvect bv1(bv);
    ShiftRight(&bv, 1);
    bv1.shift_right();
    int cmp = bv.compare(bv1);
    
    assert(cmp == 0);
    }
 
 
    {
    cout << " carry-over test" << endl;
    bvect bv { 1 };
    bool carry_over = bv.shift_left();
    assert(!carry_over);
    unsigned idx = bv.get_first();
    assert(idx == 0);
    carry_over = bv.shift_left();
    assert(carry_over);
    idx = bv.get_first();
    std::cout << idx << endl;
    assert(idx == 0);
    assert(bv.count()==0);
    }
    
    {
    cout << " 4278190080 test" << endl;
 
    bvect bv { 4278190080 };
    bv.shift_left();
    unsigned idx = bv.get_first();
    assert(idx == 4278190080-1);
    bv.shift_left();
    idx = bv.get_first();
    assert(idx == 4278190080-2);
    }
    
    {
    cout << " 4278190080 (optimized) test" << endl;
    bvect bv { 4278190080 };
    bv.optimize();
    bv.shift_left();
    unsigned idx = bv.get_first();
    assert(idx == 4278190080-1);
    bv.shift_left();
    idx = bv.get_first();
    assert(idx == 4278190080-2);
    }
 
    {
    std::cout << "\nShift-L stress (1 bit shift)..\n" << endl;;
    unsigned start = bm::id_max-1;
    bvect bv;
    bv.set(start);
 
   struct bvect::statistics st;
   bv.calc_stat(&st);
   auto bcnt = st.bit_blocks + st.gap_blocks;
   assert(bcnt == 1);
   
    std::chrono::time_point<std::chrono::steady_clock> s;
    std::chrono::time_point<std::chrono::steady_clock> f;
    
    s = std::chrono::steady_clock::now();
 
    for( ; start; --start)
    {
        bool carry_over = bv.shift_left();
        if (carry_over)
        {
            cout << "CO at " << start << endl;
            assert(bv.count()==0);
            assert(start == bm::id_max-1);
            break;
        }
        /*
        unsigned idx = bv.get_first();
        if(idx != start-1)
        {
            cerr << bv.count() << endl;
            cerr << "Shift-L Failed at idx=" << idx << " != " << start << endl;
            exit(1);
        }
        */
 
        if ((start % (1024 * 1024)) == 0)
        {
            f = std::chrono::steady_clock::now();
            auto diff = f - s;
            auto d = std::chrono::duration <double, std::milli> (diff).count();
            cout << "\r" << start << " (" << d << ") " << flush;
 
            unsigned idx = bv.get_first();
            assert(idx == start-1);
 
            bv.optimize();
 
            bv.calc_stat(&st);
            bcnt = st.bit_blocks + st.gap_blocks;
            assert(bcnt == 1);
 
            s = std::chrono::steady_clock::now();
        }
    }
    cout << "ok.\n";
    }
 
    {
    std::cout << "\nShift-R stress (1 bit shift)..\n" << endl;
    unsigned start = 0;
    bvect bv, bv1(BM_GAP);
    bv.set(start);
    bv1.set(start);
 
   struct bvect::statistics st;
   bv.calc_stat(&st);
   auto bcnt = st.bit_blocks + st.gap_blocks;
   assert(bcnt == 1);
   
    std::chrono::time_point<std::chrono::steady_clock> s;
    std::chrono::time_point<std::chrono::steady_clock> f;
    
    s = std::chrono::steady_clock::now();
 
    while(1)
    {
        bool carry_over = bv.shift_right();
        if (carry_over)
        {
            cout << "CO at " << start << endl;
            assert(bv.count()==0);
            assert(start == bm::id_max-1);
            break;
        }
 
        {
            bv.calc_stat(&st);
            bcnt = st.bit_blocks + st.gap_blocks;
            assert(bcnt == 1);
        }
        carry_over = bv1.shift_right();
        if (carry_over)
        {
            cout << "CO at " << start << endl;
            assert(bv1.count()==0);
            assert(start == bm::id_max-1);
            break;
        }
        // optmization of GAP blocks is not implemented yet
        #if 0
        {
            bv1.calc_stat(&st);
            bcnt = st.bit_blocks + st.gap_blocks;
            assert(bcnt == 1);
        }
        #endif
 
 
        if ((start % (1024 * 1024)) == 0)
        {
            bool eq = bv.equal(bv1);
            assert(eq);
 
            bv1.optimize();
 
            f = std::chrono::steady_clock::now();
            auto diff = f - s;
            auto d = std::chrono::duration <double, std::milli> (diff).count();
 
            cout << "\r" << start << " (" << d << ") " << flush;
 
            unsigned idx = bv.get_first();
            assert(idx-1 == start);
 
            bv.calc_stat(&st);
            bcnt = st.bit_blocks + st.gap_blocks;
            assert(bcnt == 1);
 
            s = std::chrono::steady_clock::now();
        }
        ++start;
    }
    cout << "ok.\n";
    }
 
    {
        std::cout << "\nShift-R stress (large vector shift)..\n" << endl;
        bvect bv;
        generate_bvector(bv);
        bvect bv_control(bv);
        
        unsigned max_shifts = 10000;
        for (unsigned i = 0; i < max_shifts; ++i)
        {
            ShiftRight(&bv_control, 1);
            bv.shift_right();
            int cmp = bv.compare(bv_control);
            assert(cmp==0);
            if ((i % 16) == 0)
            {
                if (!is_silent)
                    cout << "\r" << i << "/" << max_shifts << flush;
            }
        }
    }
    cout << "ok.\n";
 
 
    // stress test for shifting aggregator
    //
    cout << "\nAggregator based SHIT-R tests..." << endl;
    {
        const unsigned int REPEATS = 300;
 
        bvect mask_bv; // mask vector
        mask_bv.init();
        generate_bvector(mask_bv, 75000000, false); // mask is shorter on both ends
 
        std::vector<bvect> bv_coll1;
        GenerateShiftTestCollection(&bv_coll1, 25, 80000000);
        
        {
            bm::aggregator<bvect> agg;
            agg.add(&mask_bv);
            for (unsigned k = 0; k < bv_coll1.size(); ++k)
            {
                agg.add(&bv_coll1[k]);
            }
 
            for (unsigned i = 0; i < REPEATS; ++i)
            {
                bvect bv1(mask_bv);
                for (unsigned k = 0; k < bv_coll1.size(); ++k)
                {
                    bv1.shift_right();
                    bv1 &= bv_coll1[k];
                } // for
                
                bvect bv2;
                agg.set_compute_count(false);
                agg.combine_shift_right_and(bv2);
                int cmp = bv1.compare(bv2);
                if (cmp != 0)
                {
                    cerr << "Shift-R compare failure!" << endl;
                    exit(1);
                }
                bvect bv3;
                agg.set_compute_count(true);
                agg.combine_shift_right_and(bv3);
                assert(!bv3.any());
                auto cnt = agg.count();
                auto cnt_c = bv1.count();
                assert(cnt == cnt_c);
 
            } // for
        }
    }
 
 
    cout << "\n---------------------------- Bvector SHIFT test OK" << endl;
}
 
static
void BvectorInsertTest()
{
    cout << "\n---------------------------- Bvector INSERT test" << endl;
    
    {
        bvect bv { 1, 2, 3 };
        bvect bv_c { 2, 3, 4 };
        bvect bv1(bv);
        bvect bv2(bv); bv2.optimize();
 
        BVectorInsert(&bv, 0, false);
        int cmp = bv.compare(bv_c);
        assert(cmp == 0);
        
        bv1.insert(0, false);
        cmp = bv1.compare(bv_c);
        assert(cmp == 0);
 
        bv2.insert(0, false);
        cmp = bv2.compare(bv_c);
        assert(cmp == 0);
 
       struct bvect::statistics st2;
       bv2.calc_stat(&st2);
       assert(st2.gap_blocks==1);
       assert(st2.bit_blocks==0);
    }
    
    {
        bvect bv { 1, 2, 3 };
        bvect bv_c { 0, 2, 3, 4 };
        bvect bv1(bv);
        bvect bv2(bv); bv2.optimize();
 
        BVectorInsert(&bv, 0, true);
        int cmp = bv.compare(bv_c);
        assert(cmp == 0);
 
        bv1.insert(0, true);
        cmp = bv1.compare(bv_c);
        assert(cmp == 0);
 
        bv2.insert(0, true);
//        print_bv(bv2);
//        print_bv(bv_c);
        cmp = bv2.compare(bv_c);
        assert(cmp == 0);
 
        struct bvect::statistics st2;
        bv2.calc_stat(&st2);
        assert(st2.gap_blocks==1);
        assert(st2.bit_blocks==0);
    }
 
    {
        bvect bv;
        bv.set_range(0, 65535);
        bv.optimize();
        bvect bv_c;
        bv_c.set_range(0, 65536);
 
        bv.insert(1, true);
        int cmp = bv.compare(bv_c);
        assert(cmp == 0);
 
        struct bvect::statistics st;
        bv.calc_stat(&st);
        assert(st.gap_blocks==0);
        assert(st.bit_blocks==1);
 
    }
    
    {
        bvect bv { 1, 20, 65535 };
        bvect bv_c { 1, 20, 65535, 65536 };
        bvect bv1(bv);
        bvect bv2(bv); bv2.optimize();
 
        BVectorInsert(&bv, 65535, true);
        int cmp = bv.compare(bv_c);
        assert(cmp == 0);
 
        bv1.insert(65535, true);
        print_bv(bv1);
        cmp = bv1.compare(bv_c);
        assert(cmp == 0);
 
        bv2.insert(65535, true);
        cmp = bv2.compare(bv_c);
        assert(cmp == 0);
 
        struct bvect::statistics st2;
        bv2.calc_stat(&st2);
        assert(st2.gap_blocks==1);
        assert(st2.bit_blocks==1);
 
    }
    
    // bit-vector insert checks
    {
        bvect bv;
        bv.resize(10);
        bv.insert(120303030, true);
        assert(bv.test(120303030));
        assert(bv.count()==1);
        assert(bv.size() == 120303030+1);
    }
    
    {
        bvect bv { 120303030u, 120303031u };
        bvect bv1(bv);
        BVectorInsert(&bv, 120303031u, true);
        bv1.insert(120303031u, true);
        int cmp = bv1.compare(bv);
        assert(cmp==0);
        bv.optimize();
        bv1.optimize();
        BVectorInsert(&bv, 120303031u, true);
        bv1.insert(120303031u, true);
        cmp = bv1.compare(bv);
        assert(cmp==0);
    }
    
    {
        bvect bv, bv1;
        bv.set(10);
        bv.set_range(1203030u, 1203030u+65535u*10u);
        bv1 = bv;
        BVectorInsert(&bv, 1203030u+10, false);
        bv1.insert(1203030u+10, false);
        int cmp = bv1.compare(bv);
        assert(cmp==0);
    }
 
    {
        std::cout << "INSERT GAP  (random)..\n";
 
        bvect bv(BM_GAP), bv1;
        bv.set(10);
        bv1 = bv;
        bv.optimize();
 
        for (unsigned i = 0; i < 1000; ++i)
        {
            unsigned idx = (unsigned)rand() % 65535;
            unsigned val = (unsigned)rand() & 1;
            bv.insert(idx, val);
            bv1.insert(idx, val);
            int cmp = bv1.compare(bv);
            assert(cmp==0);
 
            struct bvect::statistics st;
            bv.calc_stat(&st);
            assert(st.gap_blocks >= 1);
            assert(st.bit_blocks == 0);
 
            bv.insert(idx, val);
            bv1.insert(idx, val);
            cmp = bv1.compare(bv);
            assert(cmp==0);
 
            bv.calc_stat(&st);
            assert(st.gap_blocks >= 1);
            assert(st.bit_blocks == 0);
        }
    }
 
    
    {
        std::cout << "INSERT stress (large vector insert)..\n";
        bvect bv;
        generate_bvector(bv, 40000000);
        bvect bv_control(bv);
        
        unsigned max_shifts = 10000;
        for (unsigned i = 0; i < max_shifts; ++i)
        {
            bvect bv2(bm::BM_GAP);
            bv2 = bv_control;
            bv2.optimize();
            
            unsigned i_pos = (unsigned)rand()%40000000;