/* This file is part of GNU Pies.
   Copyright (C) 2008-2013, 2016 Sergey Poznyakoff

   GNU Pies is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3, or (at your option)
   any later version.

   GNU Pies is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with GNU Pies.  If not, see <http://www.gnu.org/licenses/>. */

#include "pies.h"

#ifndef CHAR_BIT
# define CHAR_BIT 8
#endif
#define BITS_PER_WORD   (sizeof(unsigned)*CHAR_BIT)

#define WORDSIZE(n)     (((n) + BITS_PER_WORD - 1) / BITS_PER_WORD)
#define SETBIT(x, i)    ((x)[(i)/BITS_PER_WORD] |= (1<<((i) % BITS_PER_WORD)))
#define CLRBIT(x, i)    ((x)[(i)/BITS_PER_WORD] &= ~(1<<((i) % BITS_PER_WORD)))
#define BITISSET(x, i)  (((x)[(i)/BITS_PER_WORD] & (1<<((i) % BITS_PER_WORD))) != 0)

void
TC (unsigned *R, int n)
{
  register int rowsize;
  register unsigned mask;
  register unsigned *rowj;
  register unsigned *rp;
  register unsigned *rend;
  register unsigned *ccol;

  unsigned *relend;
  unsigned *cword;
  unsigned *rowi;

  rowsize = WORDSIZE (n) * sizeof (unsigned);
  relend = (unsigned *) ((char *) R + (n * rowsize));

  cword = R;
  mask = 1;
  rowi = R;
  while (rowi < relend)
    {
      ccol = cword;
      rowj = R;
                
      while (rowj < relend)
	{
	  if (*ccol & mask)
	    {
	      rp = rowi;
	      rend = (unsigned *) ((char *) rowj + rowsize);
                                
	      while (rowj < rend)
		*rowj++ |= *rp++;
	    }
	  else
	    {
	      rowj = (unsigned *) ((char *) rowj + rowsize);
	    }
	  
	  ccol = (unsigned *) ((char *) ccol + rowsize);
	}
                
      mask <<= 1;
      if (mask == 0)
	{
	  mask = 1;
	  cword++;
	}
      rowi = (unsigned *) ((char *) rowi + rowsize);
    }
}

struct pies_depmap
{
  size_t nrows;
  size_t rowlen;
  unsigned r[1];
};
  
pies_depmap_t
depmap_alloc (size_t count)
{
  size_t size = (count + BITS_PER_WORD - 1) / BITS_PER_WORD;
  pies_depmap_t dmap = grecs_zalloc (sizeof (*dmap) - 1 
				     + count * size * sizeof (unsigned));
  dmap->nrows  = count;
  dmap->rowlen = size;
  return dmap;
}

pies_depmap_t
depmap_copy (pies_depmap_t dpm)
{
  pies_depmap_t copy = depmap_alloc (dpm->nrows);
  memcpy (copy->r, dpm->r, dpm->nrows * dpm->rowlen * sizeof (unsigned));
  return copy;
}

static unsigned *
depmap_rowptr (pies_depmap_t dmap, size_t row)
{
  return dmap->r + dmap->rowlen * row;
}

void
depmap_set (pies_depmap_t dmap, size_t row, size_t col)
{
  unsigned *rptr = depmap_rowptr (dmap, row);
  SETBIT (rptr, col);
}

void
depmap_clear (pies_depmap_t dmap, size_t row, size_t col)
{
  unsigned *rptr = depmap_rowptr (dmap, row);
  CLRBIT (rptr, col);
}

int
depmap_isset (pies_depmap_t dmap, size_t row, size_t col)
{
  unsigned *rptr = depmap_rowptr (dmap, row);
  return BITISSET (rptr, col);
}

void
depmap_tc (pies_depmap_t dmap)
{
  TC (dmap->r, dmap->nrows);
}

struct pies_depmap_pos
{
  enum pies_depmap_direction dir;
  size_t coord[2];
};

size_t
depmap_next (pies_depmap_t dmap, pies_depmap_pos_t pos)
{
  for (pos->coord[pos->dir]++; pos->coord[pos->dir] < dmap->nrows;
       pos->coord[pos->dir]++)
    if (depmap_isset (dmap, pos->coord[0], pos->coord[1]))
      break;
  
  return pos->coord[pos->dir] == dmap->nrows ?
             (size_t) -1 : pos->coord[pos->dir];
}

size_t
depmap_first (pies_depmap_t dmap, enum pies_depmap_direction dir,
	      size_t coord, pies_depmap_pos_t *ppos)
{
  pies_depmap_pos_t pos = grecs_malloc (sizeof *pos);
  *ppos = pos;
  pos->dir = dir;
  pos->coord[!pos->dir] = coord;
  pos->coord[pos->dir] = -1;
  return depmap_next (dmap, pos);
}

void
depmap_end (pies_depmap_pos_t pos)
{
  grecs_free (pos);
}

void
depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir,
		  size_t coord)
{
  size_t i;
  
  switch (dir)
    {
    case depmap_row:
      for (i = 0; i < dmap->nrows; i++)
	depmap_clear (dmap, coord, i);
      break;

    case depmap_col:
      for (i = 0; i < dmap->nrows; i++)
	depmap_clear (dmap, i, coord);
    }
}