/* This file is part of GNU Pies.
   Copyright (C) 2008-2019 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;         /* Number of rows (== number of mapped elements) */
  size_t rowlen;        /* Length of a row in words */
  unsigned r[1];        /* Data rows */
};

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;
}

/* Return size of a depmap row in bytes */
static inline size_t
depmap_row_size (pies_depmap_t dpm)
{
  return dpm->rowlen * sizeof (unsigned);
}

pies_depmap_t
depmap_copy (pies_depmap_t dpm)
{
  pies_depmap_t copy = depmap_alloc (dpm->nrows);
  memcpy (copy->r, dpm->r, dpm->nrows * depmap_row_size (dpm));
  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);
}

/* Remove nth row and column from the map */
void
depmap_remove (pies_depmap_t dmap, size_t n)
{
  if (n < dmap->nrows - 1)
    {
      size_t i, j;

      /* Remove nth row */
      memmove (depmap_rowptr (dmap, n), depmap_rowptr (dmap, n + 1),
	       (dmap->nrows - n - 1) * depmap_row_size (dmap));
      /* Renumber all columns j >= n: j = j - 1 */
      for (i = 0; i < dmap->nrows; i++)
	for (j = n; j < dmap->nrows - 1; j++)
	  (depmap_isset (dmap, i, j + 1) ? depmap_set : depmap_clear)
	    (dmap, i, j);
    }
  dmap->nrows--;
}