/*
    mmorph, MULTEXT morphology tool
    Version 2.3, October 1995
    Copyright (c) 1994,1995 ISSCO/SUISSETRA, Geneva, Switzerland
    Dominique Petitpierre, <petitp@divsun.unige.ch>
*/
/*
    bitmap.c

    handle arbitary length bit maps

    Dominique Petitpierre, ISSCO Summer 1994
*/

#include "bitmap.h"
#include "mymalloc.h"

long
next_bit(bitmap, from_position)
s_bitmap   *bitmap;
long        from_position;

{
    register long pos;

    /* TODO skip zero chunks */
    pos = from_position;
    /* there is a sentinel bit at the end of the bitmap */
    while (!TEST_BIT(bitmap->bits[WORD_OFFSET(pos)], pos))
	pos++;
    if (pos < bitmap->size)
	return (pos);
    else
	return (-1);
}

void
unset_bit(bitmap, pos)
s_bitmap   *bitmap;
long        pos;

{
#ifdef DEBUG
    if (pos < 0 || pos > bitmap->size)	/* allow for sentinel */
	fatal_error("bit position is %d, bitmap size=%d", pos, bitmap->size);
#endif
    /* beware: bit position not checked */
    UNSET_BIT(bitmap->bits[WORD_OFFSET(pos)], pos);
}

void
set_bit(bitmap, pos)
s_bitmap   *bitmap;
long        pos;

{
#ifdef DEBUG
    if (pos < 0 || pos > bitmap->size)	/* allow for sentinel */
	fatal_error("bit position is %d, bitmap size=%d", pos, bitmap->size);
#endif
    /* beware: bit position not checked */
    SET_BIT(bitmap->bits[WORD_OFFSET(pos)], pos);
}

int	/* boolean */
test_bit(bitmap, pos)
s_bitmap   *bitmap;
long        pos;

{
#ifdef DEBUG
    if (pos < 0 || pos > bitmap->size)	/* allow for sentinel */
	fatal_error("bit position is %d, bitmap size=%d", pos, bitmap->size);
#endif
    /* beware: bit position not checked */
    return (TEST_BIT(bitmap->bits[WORD_OFFSET(pos)], pos));
}



s_bitmap   *
new_bitmap(size)
long        size;

{
    s_bitmap   *bitmap;

    MY_MALLOC(bitmap, s_bitmap);
    MY_CALLOC(bitmap->bits, size / BITS(WORD_TYPE) + 1, WORD_TYPE);
    bitmap->size = size;
    /* add sentinel bit */
    set_bit(bitmap, size);
    return (bitmap);
}

void
free_bitmap(bitmap)
s_bitmap   *bitmap;

{
    if (bitmap->bits != NULL)
	MY_FREE(bitmap->bits);
    MY_FREE(bitmap);
}

/* return a boolean value */
int
has_unique_bit(word)
WORD_TYPE   word;

{
    /* could be improved by considering the bytes composing the word */
    if (word == NO_BITS)
	return (0);
    else {
	register WORD_TYPE w;

	w = word;
	/* shift until a bit appears in position 1 */
	while (!(w & FIRST_BIT))
	    w >>= 1;
	return (w == FIRST_BIT);
    }
}

int	/* boolean */
set_if_not_set(bitmap, pos)
s_bitmap   *bitmap;
long        pos;

{
#ifdef DEBUG
    if (pos < 0 || pos > bitmap->size)	/* allow for sentinel */
	fatal_error("bit position is %d, bitmap size=%d", pos, bitmap->size);
#endif
    /* beware: bit position not checked */
    if (TEST_BIT(bitmap->bits[WORD_OFFSET(pos)], pos))
	return (0);
    else {
	SET_BIT(bitmap->bits[WORD_OFFSET(pos)], pos);
	return (1);
    }
}

/*
    bitmap equivalent of  b1 & b2
    assume that the sizes are identical
*/
int
test_and(bitmap1, bitmap2)
s_bitmap   *bitmap1;
s_bitmap   *bitmap2;

{
    register WORD_TYPE *bits1;
    register WORD_TYPE *bits2;
    register WORD_TYPE *last_word;

    bits1 = bitmap1->bits;
    bits2 = bitmap2->bits;
    last_word = bitmap1->bits + bitmap1->size / BITS(WORD_TYPE);
    while (bits1 < last_word)
	if (*bits1++ & *bits2++)
	    return (1);
    return (*bits1 & *bits2 & FULL_SET(bitmap1->size & MODULO_MASK)
	    != NO_BITS);
}

void
empty_bitmap(bitmap)
s_bitmap   *bitmap;

{
    register WORD_TYPE *bits;
    register WORD_TYPE *last_word;

    bits = bitmap->bits;
    last_word = bits + bitmap->size / BITS(WORD_TYPE) + 1;
    while (bits < last_word)
	*bits++ = NO_BITS;
    set_bit(bitmap, bitmap->size);	/* sentinel */
}

void
fill_bitmap(bitmap)
s_bitmap   *bitmap;

{
    register WORD_TYPE *bits;
    register WORD_TYPE *last_word;

    bits = bitmap->bits;
    last_word = bits + bitmap->size / BITS(WORD_TYPE) + 1;
    while (bits < last_word)
	*bits++ = ALL_BITS;
}


/*
    bitmap equivalent of  b1 |= b2
    assume that the sizes are identical
*/
void
assign_or(bitmap1, bitmap2)
s_bitmap   *bitmap1;
s_bitmap   *bitmap2;

{
    register WORD_TYPE *bits1;
    register WORD_TYPE *bits2;
    register WORD_TYPE *last_word;

    bits1 = bitmap1->bits;
    bits2 = bitmap2->bits;
    last_word = bits1 + bitmap1->size / BITS(WORD_TYPE) + 1;
    while (bits1 < last_word)
	*bits1++ |= *bits2++;
}


/*
    bitmap equivalent of  b1 &= b2
    assume that the sizes are identical
*/
void
assign_and(bitmap1, bitmap2)
s_bitmap   *bitmap1;
s_bitmap   *bitmap2;

{
    register WORD_TYPE *bits1;
    register WORD_TYPE *bits2;
    register WORD_TYPE *last_word;

    bits1 = bitmap1->bits;
    bits2 = bitmap2->bits;
    last_word = bitmap1->bits + bitmap1->size / BITS(WORD_TYPE) + 1;
    while (bits1 < last_word)
	*bits1++ &= *bits2++;
}

/*
    bitmap equivalent of  b1 = ~ b1
*/
void
negate_bitmap(bitmap)
s_bitmap   *bitmap;

{
    register WORD_TYPE *bits;
    register WORD_TYPE *last_word;

    bits = bitmap->bits;
    last_word = bitmap->bits + bitmap->size / BITS(WORD_TYPE) + 1;
    while (bits < last_word) {
	*bits = ~(*bits);
	bits++;
    }
    /* restore the sentinel bit */
    set_bit(bitmap, bitmap->size);
}