bitarray.c

使用具有增量学习的监控式学习方法。包括几个不同的分类算法。

/* Copyright (C) 2001-2002  Mikael Ylikoski
 * See the accompanying file "README" for the full copyright notice */
/**
 * @file
 * Bitarrays.
 *
 * @author  Mikael Ylikoski
 * @date    2001-2002
 */

#include <stdlib.h>
#include "bitarray.h"

#define BITS_PER_INT 32
/* #define BITS_PER_INT sizeof(int) * 8 */

struct bitarray_ {
    int *value;		/**< Values */
    int sov;		/**< Size Of Values */
    int nov;		/**< Number Of bits */
    /*int s1s;*/	/* Maxvalue for counting ones */
    int n1s;		/**< Number of ones */
};


/**
 * Create a new empty bitarray.
 *
 * @param size  initial size of array (number of bits)
 * @return  The array. NULL is returned if memory allocation failed.
 */
bitarray *
bitarray_new (int size) {
    bitarray *a;
    int intsize;

    a = malloc (sizeof(bitarray));
    intsize = size / BITS_PER_INT + ((size % BITS_PER_INT) > 0);
    if (size)
	a->value = calloc (intsize, sizeof(int));
    else
	a->value = NULL;
    a->sov = intsize;
    a->nov = size;
    /*a->s1s = maxones;*/
    a->n1s = 0;

    return a;
}


/**
 * Free an array.
 *
 * @param a  array to free
 */
void
bitarray_free (bitarray *a) {
    if (!a)
	return;
    free (a->value);
    free (a);
}


/**
 * Get the value of a bit.
 *
 * @param a    array to operate on
 * @param pos  position of bit to get value of
 * @return  The value of the bit or -1 if the position is out of bounds.
 */
int
bitarray_get_value (bitarray *a, int pos) {
    if (pos >= a->nov || pos < 0)
	return -1;
    return (a->value[pos / BITS_PER_INT] >> (pos % BITS_PER_INT)) & 1;
}


/**
 * Set the value of a bit.
 *
 * @param a      array to operate on
 * @param pos    position of bit to set
 * @param value  value
 */
void
bitarray_set_value (bitarray *a, int pos, int value) {
    if (value)
	bitarray_set_bit (a, pos);
    else
	bitarray_clear_bit (a, pos);
}


/**
 * Set the value of a bit to one.
 *
 * @param a    array to operate on
 * @param pos  position of bit to set
 */
void
bitarray_set_bit (bitarray *a, int pos) {
    int i, j;

    if (pos < 0)
	return;
    i = pos / BITS_PER_INT;
    j = pos % BITS_PER_INT;
    if (!((a->value[i] >> j) & 1)) {
	a->n1s++;
	a->value[i] |= 1 << j;
    }
}


/**
 * Set the value of a bit to zero.
 *
 * @param a    array to operate on
 * @param pos  position of bit to set
 */
void
bitarray_clear_bit (bitarray *a, int pos) {
    int i, j;

    if (pos < 0)
	return;
    i = pos / BITS_PER_INT;
    j = pos % BITS_PER_INT;
    if ((a->value[i] >> j) & 1) {
	a->n1s--;
	a->value[i] &= ~(1 << j);
    }
}


/**
 * Return the first position with a zero.
 *
 * @param a  array to operate on
 * @return  The position or -1 if all positions are ones.
 */
int
bitarray_first_zero (bitarray *a) {
    int i, j, k;

    if (a->n1s == a->nov)
	return -1;

    for (i = 0; i < a->sov; i++) {
	k = ~a->value[i];
	if (k != 0)
	    for (j = 0; j < BITS_PER_INT; j++) {
		if (k & 1)
		    return i * BITS_PER_INT + j;
		k >>= 1;
	    }
	}

    /* assert (0) */
    return -1;
}


/**
 * Return a random position with a zero.
 *
 * @param a  array to operate on
 * @return  The position or -1 if all positions are ones.
 */
int
bitarray_random_zero (bitarray *a) {
    int i, j, k, l, m;

    if (a->n1s == a->nov)
	return -1;

    k = 1 + rand () * (double)(a->nov - a->n1s) / (RAND_MAX + 1.0);

    for (l = i = 0; i < a->sov; i++) {
	m = ~a->value[i];
	for (j = 0; j < BITS_PER_INT; j++) {
	    l += m & 1;
	    if (l == k)
		return i * BITS_PER_INT + j;
	    m >>= 1;
	}
    }

    /* assert (0) */
    return -1;
}