/*
Copyright (c) 2000-2010, Dirk Krause
All rights reserved.

Redistribution and use in source and binary forms,
with or without modification, are permitted provided
that the following conditions are met:

* Redistributions of source code must retain the above
  copyright notice, this list of conditions and the
  following disclaimer.
* Redistributions in binary form must reproduce the above 
  opyright notice, this list of conditions and the following
  disclaimer in the documentation and/or other materials
  provided with the distribution.
* Neither the name of the Dirk Krause nor the names of
  contributors may be used to endorse or promote
  products derived from this software without specific
  prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED.
IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
DAMAGE.
*/

/**	@file dkbf.h Bit field and bit matrix operations.

Example 1: Setting and requesting bits in a field.
@code
	int i;
	dk_bitfield_t *bf;
	bf = dkbf_open(3210);
	if(bf) {
	  for(i = 0; i < 3210; i++) {
	    if(i % 2) {
	      dkbf_set(bf, i);
	    }
	  }
	  for(i = 0; i < 3210; i++) {
	    if(dkbf_get(bf, i)) {
	      printf("Bit %04d is set.\n");
	    } else {
	      printf("Bit %04d is not set.\n");
	    }
	  }
	  dkbf_close(bf);
	}
@endcode

Example 2: Given is a graph with 4 nodes A, B, C and D.
There is a directed edge from A to B, and a directed edge
from B to C. Is there a path from A to C and a path from
A to D?
@code
	dk_bitmatrix_t *bm;
	bm = dkbf_matrix_open(4, 4);
	if(bm) {
	  dkbf_matrix_set(0, 1); // A (0) to B (1)
	  dkbf_matrix_set(1, 2); // B (1) to C (2)
	  dkbf_matrix_expand(bm);
	  if(dkbf_matrix_get(0, 2)) {
	    printf("There is a directed path from A to C.\n");
	  } else {
	    printf("There is no directed path from A to C.\n");
	  }
	  if(dkbf_matrix_get(0, 3)) {
	    printf("There is a directed path from A to D.\n");
	  } else {
	    printf("There is no directed path from A to D.\n");
	  }
	  dkbf_matrix_close(bm);
	}
@endcode
*/

#ifndef DK_BF_INCLUDED
/** Flag: dkbf.h already included. */
#define DK_BF_INCLUDED 1

#include <dk.h>
#include <dktypes.h>

#if defined(EXTERN)
#undef EXTERN
#endif
#ifndef DK_BF_C
#if !DK_HAVE_PROTOTYPES
#define EXTERN extern
#else
#define EXTERN /* nix */
#endif
#else
#define EXTERN /* nix */
#endif

#if defined(__cplusplus)
extern "C" {
#endif



/**	Create a bit field.
	The bit field structure is created in dynamically allocated memory.
	Use dkbf_close() to close the bit field and release the memory
	after usage.
	@param	n	Number of bits in the field.
	@return	Pointer to new bit field structure on success, NULL on error.
*/
EXTERN
dk_bitfield_t *dkbf_open DK_PR((size_t n));



/**	Close bit field created by dkbf_open() and release the memory.
	@param	f	Pointer to bit field structure.
*/
EXTERN
void dkbf_close DK_PR((dk_bitfield_t *f));



/**	Set or reset a bit.
	@param	f	Pointer to bit field structure.
	@param	n	Number of bit to set/reset.
	@param	v	Flag to set the bit (v!=0) or reset the bit (v=0).
*/
EXTERN
void dkbf_set DK_PR((dk_bitfield_t *f, size_t n, int v));



/**	Get bit value.
	@param	f	Pointer to bit field structure.
	@param	n	Number of the bit to get.
	@return	Flag whether the bit is set or not.
*/
EXTERN
int dkbf_get DK_PR((dk_bitfield_t *f, size_t n));



/**	Reset a bit field (reset all bits).
	@param	f	Pointer to bit field structure.
*/
EXTERN
void dkbf_reset DK_PR((dk_bitfield_t *f));



/**	Create a bit matrix.
	The bit matrix is created in dynamically allocated memory.
	Call dkbf_matrix_close() to destroy the bit matrix and release
	the memory after usage.
	@param	c	Number of columns in the matrix.
	@param	r	Number of rows in the bit matrix.
	@return	Pointer to the new bit matrix structure on success,
			NULL on error.
*/
EXTERN
dk_bitmatrix_t *dkbf_matrix_open DK_PR((size_t c, size_t r));



/**	Destroy bit matrix created by dkbf_matrix_open() and release memory.
	@param	m	Pointer to bit matrix structure to close.
*/
EXTERN
void dkbf_matrix_close DK_PR((dk_bitmatrix_t *m));



/**	Set or reset bit in matrix.
	@param	m	Pointer to bit matrix structure.
	@param	x	X-position (column) of the bit.
	@param	y	Y-position (row) of the bit.
	@param	v	Flag to indicate whether to set (v!=0) or reset (v=0)
			the bit.
*/
EXTERN
void dkbf_matrix_set DK_PR((dk_bitmatrix_t *m, size_t x, size_t y, int v));



/**	Get bit from matrix.
	@param	m	Pointer to bit matrix structure.
	@param	x	X-position (column) of the bit.
	@param	y	Y-position (row) of the bit.
	@return	Flag indicating whether the bit is set.
*/
EXTERN
int dkbf_matrix_get DK_PR((dk_bitmatrix_t *m, size_t x, size_t y));



/**	Reset all bits in the matrix.
	@param	m	Pointer to bit matrix structure.
*/
EXTERN
void dkbf_matrix_reset DK_PR((dk_bitmatrix_t *m));



/**	Expand a bit matrix.
	To find indirect followers in a graph containing N nodes
	create a square bit matrix having N rows and N columns.
	For each directed edge from node i to node j set the bit in
	column i, row j by calling dkbf_matrix_set(m, j, i, 1);
	After calling dkbf_matrix_expand(m); you can use
	dkbf_matrix_get(m, v, u) to check whether or not there is any
	(direct or indirect) connection from node u to node v.
	@param	m	Pointer to bit matrix structure.
	@return	Flag to indicate success.
*/
EXTERN
int dkbf_matrix_expand DK_PR((dk_bitmatrix_t *m));

#if defined(__cplusplus)
}
#endif

#endif
/* DK_BF_INCLUDED */