/*
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 Sdkbf_ucharH
DAMAGE.
*/



/**	@file	dkbf.c	Bit field and bit matrix module.
*/



#include "dk.h"
#include "dkmem.h"
/**	Inside the dkbf module.
*/
#define DK_BF_C 1
#include "dkbf.h"


#line 52 "dkbf.ctr"




/**	Abbreviation.
*/
typedef unsigned char *dkbf_ucptr;

/**	Abbreviation.
*/
typedef unsigned char dkbf_uchar;



/**	Masks to access single bits in a byte.
*/
static
unsigned char 
the_bits[] = {
  0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
};



dk_bitfield_t *
dkbf_open DK_P1(size_t, bits)
{
  dk_bitfield_t *back = NULL;
  size_t bytes;
  if(bits) {
    bytes = (bits / 8) + 1;
    back = dk_new(dk_bitfield_t,1);
    if(back) {
      back->data = NULL;
      back->bits = bits;
      back->data = dk_new(dkbf_uchar,bytes);
      if(back->data) {
	DK_MEMRES((back->data),bytes) ;
      } else {
	dk_delete(back);
	back = NULL;
      }
    }
  }
  return back;
}



void
dkbf_matrix_close DK_P1(dk_bitmatrix_t *,m)
{
  unsigned char *ptr, **pptr;
  size_t i;
  
  if(m) {
    if(m->data) {
      pptr = m->data;
      for(i = 0; i < m->c; i++) {
        ptr = *pptr;
	dk_delete(ptr);
        pptr++;
      }
      pptr = m->data;
      dk_delete(pptr);
    } m->data = NULL;
    m->c = 0; m->r = 0;
    dk_delete(m);
  } 
}



dk_bitmatrix_t *
dkbf_matrix_open DK_P2(size_t,c, size_t,r)
{
  dk_bitmatrix_t *back = NULL;
  size_t bytes_per_row = 0, i = 0;
  int ok;
  unsigned char **pptr;
  
  ok = 0;
  if((c > 0) && (r > 0)) {
    back = dk_new(dk_bitmatrix_t,1);
    if(back) {
      back->data = NULL;
      back->c = 0; back->r = 0;
      bytes_per_row = 1 + c / 8;
      back->data = dk_new(dkbf_ucptr,r);
      if(back->data) {
        pptr = back->data;
	for(i = 0; i < r; i++) { *(pptr++) = NULL; }
	pptr = back->data;
	ok = 1;
	for(i = 0; i < r; i++) {
	  *pptr = dk_new(dkbf_uchar,bytes_per_row);
	  if(!(*pptr)) { ok = 0; }
	  pptr++;
	}
	back->c = c; back->r = r;
      }
      if(!ok) {
        dkbf_matrix_close(back); back = NULL;
      }
    }
  } 
  return back;
}



void
dkbf_matrix_set DK_P4(dk_bitmatrix_t *,bm, size_t,x, size_t,y, int,v)
{
  size_t i1, i2;
  unsigned char *ptr;
  if(bm) {
    if((x < bm->c) && (y < bm->r)) {
      ptr = (bm->data)[y];
      i1 = x / 8;
      i2 = x % 8;
      if(v) {
        ptr[i1] |= the_bits[i2];
      } else {
        ptr[i1] &= (~(the_bits[i2]));
      }
    }
  }
}



int
dkbf_matrix_get DK_P3(dk_bitmatrix_t *,bm, size_t,x, size_t,y)
{
  int back = 0;
  unsigned char *ptr;
  size_t i1, i2;
  if(bm) {
    if((x < bm->c) && (y < bm->r)) {
      ptr = (bm->data)[y];
      i1 = x / 8;
      i2 = x % 8;
      if(ptr[i1] & the_bits[i2]) {
        back = 1;
      }
    }
  }
  return back;
}



void
dkbf_matrix_reset DK_P1(dk_bitmatrix_t *,bm)
{
  size_t i, j, jmax;
  unsigned char *ptr, **pptr;
  if(bm) {
    pptr = bm->data;
    jmax = 1 + (bm->c) / 8;
    for(i = 0; i < bm->r; i++) {
      ptr = *(pptr++);
      for(j = 0; j < jmax; j++) { *(ptr++) = 0x00; }
    }
  }
}



/*	Not optimized yet.

	Expand a graph way matrix.

	An entry set by dkbf_matrix_set(bm, x, y, 1)
	sets the bit in row y and column x. This means
	there is a directed edge from graph node y to
	graph node x.

	Graph way expansion means, if there is no direct
	way from y to x we have to check, whether there
	is a node j with (direct or indirect) ways
	from y to j and from j to x.
	We have to run several passes, we can stop after
	we have not found any new changes in a pass.
*/
int
dkbf_matrix_expand DK_P1(dk_bitmatrix_t *,bm)
{
  int back = 0;
  int must_continue = 0;
  int cc;
  size_t x, y, j;
  if(bm) {
    if(bm->r == bm->c) {
      back = 1;
      cc = 1;
      while(cc) {
        cc = 0;
	for(y = 0; y < bm->r; y++) {
	  for(x = 0; x < bm->c; x++) {
	    if(!dkbf_matrix_get(bm, x, y)) {
	      must_continue = 1;
	      for(j = 0; ((j < bm->r) && (must_continue)); j++) {
	        if(dkbf_matrix_get(bm, j, y)) {
		  if(dkbf_matrix_get(bm, x, j)) {
		    dkbf_matrix_set(bm, x, y, 1);
		    cc = 1; must_continue = 0;
		  }
		}
	      }
	    }
	  }
	}
      }
    }
  }
  return back;
}



void
dkbf_close DK_P1(dk_bitfield_t *, bf)
{
  char *ptr;
  
  if(bf) {
    ptr = (char *)(bf->data);
    if(ptr) { dk_delete(ptr); }
    bf->data = NULL; bf->bits = 0;
    dk_delete(bf);
  } 
}



void
dkbf_set DK_P3(dk_bitfield_t *, bf, size_t, bit, int, val)
{
  size_t i1, i2;
  if(bf) {
    if((bf->bits) > bit) {
      i1 = bit / 8;
      i2 = bit % 8;
      if(val) {
	(bf->data)[i1] |= the_bits[i2];
      } else {
	(bf->data)[i2] &= (~(the_bits[i2]));
      }
    }
  }
}



void
dkbf_reset DK_P1(dk_bitfield_t *,bf)
{
  size_t bytes, i;
  unsigned char *ptr;
  if(bf) {
    ptr = bf->data;
    bytes = 1 + (bf->bits) / 8;
    for(i = 0; i < bytes; i++) { *(ptr++) = 0x00; }
  }
}



int
dkbf_get DK_P2(dk_bitfield_t *, bf, size_t, bit)
{
  int back = 0;
  size_t i1, i2;
  if(bf) {
    if((bf->bits) > bit) {
      i1 = bit / 8;
      i2 = bit % 8;
      if( ( (bf->data)[i1] ) & (the_bits[i2]) ) {
	back = 1;
      }
    }
  }
  return back;
}


