/***********************************************

 !!!! DO NOT EDIT THIS FILE !!!!

 This file was auto-generated by Build.PL from
 lib/KinoSearch/Util/BitVector.pm

 See KinoSearch::Docs::DevGuide for details.

 ***********************************************/

#line 283 "lib/KinoSearch/Util/BitVector.pm"

#include "KinoSearchUtilBitVector.h"

static unsigned char bitmasks[] = { 
    0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80,
};

BitVector*
Kino_BitVec_new(U32 capacity) {
    BitVector *bit_vec;
    Kino_New(0, bit_vec, 1, BitVector);
    bit_vec->capacity = 0;
    bit_vec->bits = NULL;
    Kino_BitVec_grow(bit_vec, capacity);
    return bit_vec;
}

BitVector*
Kino_BitVec_clone(BitVector *bit_vec) {
    BitVector *evil_twin;
    U32 byte_size;

    Kino_New(0, evil_twin, 1, BitVector);
    byte_size = ceil(bit_vec->capacity / 8.0);
    evil_twin->bits 
        = (unsigned char*)Kino_savepvn((char*)bit_vec->bits, byte_size);
    evil_twin->capacity = bit_vec->capacity;

    return evil_twin;
}

void
Kino_BitVec_grow(BitVector *bit_vec, U32 capacity) {
    U32 byte_size;
    U32 old_capacity;

    /* derive size in bytes from size in bits */
    byte_size = ceil(capacity / 8.0);

    if (capacity > bit_vec->capacity && bit_vec->bits != NULL) {
        U32 old_byte_size;
        old_byte_size = ceil(bit_vec->capacity / 8.0);

        Kino_Renew(bit_vec->bits, byte_size, unsigned char);
        /* zero out all new bits, since Renew doesn't guarantee they're 0 */
        old_capacity      = bit_vec->capacity;
        bit_vec->capacity = capacity;
        Kino_BitVec_bulk_clear(bit_vec, old_capacity, capacity - 1);

        /* shouldn't be necessary, but Valgrind reports an error without it */
        if (byte_size > old_byte_size) {
            memset( (bit_vec->bits + old_byte_size), 0x00, 
                (byte_size - old_byte_size) );
        }
    }
    else if (bit_vec->bits == NULL) {
        Kino_Newz(0, bit_vec->bits, byte_size, unsigned char);
        bit_vec->capacity = capacity;
    }
}

void 
Kino_BitVec_shrink(BitVector *bit_vec, U32 capacity) {
    U32 byte_size;
    
    if (capacity >= bit_vec->capacity)
        return;

    /* derive size in bytes from size in bits */
    byte_size = ceil(capacity / 8.0);
    Kino_Renew(bit_vec->bits, byte_size, unsigned char);
    bit_vec->capacity = capacity;
}

void 
Kino_BitVec_set(BitVector *bit_vec, U32 num) {
    if (num >= bit_vec->capacity)
        Kino_BitVec_grow(bit_vec, num + 1);
    bit_vec->bits[ (num >> 3) ]  |= bitmasks[num & 0x7];
}

void 
Kino_BitVec_clear(BitVector *bit_vec, U32 num) {
    if (num >= bit_vec->capacity)
        Kino_BitVec_grow(bit_vec, num + 1);

    bit_vec->bits[ (num >> 3) ] &= ~(bitmasks[num & 0x7]);
}


void
Kino_BitVec_bulk_set(BitVector *bit_vec, U32 first, U32 last) {
    unsigned char *ptr;
    U32   num_bytes;

    /* detect range errors */
    if (first > last) {
        Kino_confess("bitvec range error: %d %d %d", first, last, 
            bit_vec->capacity);
    }

    /* grow the bits if necessary */
    if (last >= bit_vec->capacity) {
        Kino_BitVec_grow(bit_vec, last);
    }

    /* set partial bytes */
    while (first % 8 != 0 && first <= last) {
        Kino_BitVec_set(bit_vec, first++);
    }
    while (last % 8 != 0 && last >= first) {
        Kino_BitVec_set(bit_vec, last--);
    }
    Kino_BitVec_set(bit_vec, last);

    /* mass set whole bytes */
    if (last > first) {
        ptr = bit_vec->bits + (first >> 3);
        num_bytes = (last - first) >> 3;
        memset(ptr, 0xff, num_bytes);
    }
}

void
Kino_BitVec_bulk_clear(BitVector *bit_vec, U32 first, U32 last) {
    unsigned char *ptr;
    U32   num_bytes;

    /* detect range errors */
    if (first > last) {
        Kino_confess("bitvec range error: %d %d %d", first, last, 
            bit_vec->capacity);
    }

    /* grow the bits if necessary */
    if (last >= bit_vec->capacity) {
        Kino_BitVec_grow(bit_vec, last);
    }

    /* clear partial bytes */
    while (first % 8 != 0 && first <= last) {
        Kino_BitVec_clear(bit_vec, first++);
    }
    while (last % 8 != 0 && last >= first) {
        Kino_BitVec_clear(bit_vec, last--);
    }
    Kino_BitVec_clear(bit_vec, last);

    /* mass clear whole bytes */
    if (last > first) {
        ptr       = bit_vec->bits + (first >> 3);
        num_bytes = (last - first) >> 3;
        memset(ptr, 0, num_bytes);
    }
}

bool
Kino_BitVec_get(BitVector *bit_vec, U32 num) {
    if (num >= bit_vec->capacity) return 0;
    return (bit_vec->bits[ (num >> 3) ] & bitmasks[num & 0x7]) != 0;
}

U32
Kino_BitVec_next_set_bit(BitVector *bit_vec, U32 num) {
    U32   outval;
    unsigned char *bits_ptr;
    unsigned char *end_ptr;
    int i;
    U32 byte_size;

    if (num >= bit_vec->capacity) {
        return KINO_BITVEC_SENTINEL;
    }

    outval = KINO_BITVEC_SENTINEL;

    bits_ptr  = bit_vec->bits + (num >> 3) ;
    byte_size = ceil(bit_vec->capacity / 8.0);
    end_ptr   = bit_vec->bits + byte_size;

    while (outval == KINO_BITVEC_SENTINEL) {
        if (*bits_ptr != 0) {
            /* check each num in represented in this byte */
            outval = (bits_ptr - bit_vec->bits) * 8;
            for (i = 0; i < 8; i++) {
                if (Kino_BitVec_get(bit_vec, outval) == 1) {
                    if (outval < bit_vec->capacity && outval >= num) {
                        return outval;
                    }
                }
                outval++;
            }
            /* nothing valid, so reset the sentinel */
            outval = KINO_BITVEC_SENTINEL;
        }
        if (++bits_ptr >= end_ptr)
            break;
    }
    /* nothing valid, so return a sentinel */
    return KINO_BITVEC_SENTINEL;
}

U32
Kino_BitVec_next_clear_bit(BitVector *bit_vec, U32 num) {
    U32   outval;
    unsigned char *bits_ptr;
    unsigned char *end_ptr;
    int i;

    if (num >= bit_vec->capacity) {
        return num;
    }

    outval = KINO_BITVEC_SENTINEL;

    bits_ptr = bit_vec->bits + (num >> 3) ;
    end_ptr  = bit_vec->bits + (bit_vec->capacity >> 3);

    while (outval == KINO_BITVEC_SENTINEL) {
        if (*bits_ptr != 0xFF) {
            /* check each num in represented in this byte */
            outval = (bits_ptr - bit_vec->bits) * 8;
            for (i = 0; i < 8; i++) {
                if (Kino_BitVec_get(bit_vec, outval) == 0) {
                    if (outval < bit_vec->capacity && outval >= num) {
                        return outval;
                    }
                }
                outval++;
            }
            /* nothing valid, so reset the sentinel */
            outval = KINO_BITVEC_SENTINEL;
        }
        if (++bits_ptr >= end_ptr)
            break;
    }
    /* didn't find clear bits in the set, so return 1 larger than the max */
    return bit_vec->capacity;
}

void
Kino_BitVec_logical_and(BitVector *bit_vec, BitVector *other) {
    U32 num = 0;
    while (1) {  
        num = Kino_BitVec_next_set_bit(bit_vec, num);
        if (num == KINO_BITVEC_SENTINEL)
            break;
        if ( !Kino_BitVec_get(other, num) ) 
            Kino_BitVec_clear(bit_vec, num);
        num++;
    }
}

const U32 BYTE_COUNTS[256] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

U32 Kino_BitVec_count(BitVector *bit_vec) {
    U32 count = 0;
    U32 byte_size = ceil(bit_vec->capacity / 8.0);
    unsigned char *ptr = bit_vec->bits;
    unsigned char *limit = ptr + byte_size;

    for( ; ptr < limit; ptr++) {
        count += BYTE_COUNTS[*ptr];
    }

    return count;
}

AV*  
Kino_BitVec_to_array(BitVector* bit_vec) {
    U32  num = 0;
    AV  *out_av;

    out_av = newAV();
    while (1) {  
        num = Kino_BitVec_next_set_bit(bit_vec, num);
        if (num == KINO_BITVEC_SENTINEL)
            break;
        av_push( out_av, newSViv(num) );
        num++;
    }
    return out_av;
}

void
Kino_BitVec_destroy(BitVector* bit_vec) {
    Kino_Safefree(bit_vec->bits);
    Kino_Safefree(bit_vec);
}