/* Gridlock
Copyright (c) 2002-2003 by Brian Nenninger. All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

#include "hypergrid.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

hypergrid* hypergrid_create(int dim, int *sizes) {
  hypergrid *gridptr = malloc(sizeof(hypergrid));
  int i;
  int totalcells = 1;
  gridptr->num_dimensions = dim;
  gridptr->dimension_sizes = malloc(dim*sizeof(int));
  for(i=0; i<dim; i++) {
    gridptr->dimension_sizes[i] = sizes[i];
    totalcells *= sizes[i];
  }
  gridptr->num_cells = totalcells;
  gridptr->grid_data = calloc(totalcells, sizeof(gridvalue_t));
  return gridptr;
}

hypergrid* hypergrid_copy(hypergrid *srcgrid) {
  hypergrid *copy = hypergrid_create(srcgrid->num_dimensions, srcgrid->dimension_sizes);
  memcpy(copy->grid_data, srcgrid->grid_data, srcgrid->num_cells*sizeof(gridvalue_t));
  return copy;
}

void hypergrid_free(hypergrid *gridptr) {
  free(gridptr->dimension_sizes);
  free(gridptr->grid_data);
  free(gridptr);
}

int* hypergrid_coords_create(hypergrid *gridptr) {
  int *array = calloc(gridptr->num_dimensions, sizeof(int));
  return array;
}

int* hypergrid_coords_copy(int *coords, int len) {
  int *array = malloc(len*sizeof(int));
  memcpy(array, coords, len*sizeof(int));
  return array;
}

void hypergrid_coords_free(int *coords) {
  free(coords);
}

int hypergrid_coords_isvalid(hypergrid *gridptr, int *coords) {
  int dim = gridptr->num_dimensions;
  int i;
  for(i=0; i<dim; i++) {
    if (coords[i]<0 || coords[i]>=gridptr->dimension_sizes[i]) return 0;
  }
  return 1;
}

int hypergrid_coords_increment(hypergrid *gridptr, int *coords) {
  /* indices are in pseudo-big-endian order, so start incrementing from the last position */
  int ndim = gridptr->num_dimensions;
  int cdim = ndim;
  while (cdim--) {
    ++coords[cdim];
    if (coords[cdim]<gridptr->dimension_sizes[cdim]) {
      /* no overflow, we're done */
      return 1;
    }
    else {
      /* "carry" to next position */
      coords[cdim] = 0;
    }
  }
  /* either coords was the "last" one in the hypergrid or it was invalid */
  return 0;
}

/* "private" method to get the coords into the hypergrid's big 1-d array */
int _compute_coords_index(hypergrid *gridptr, int *coords) {
  int acc = 0;
  int placevalue = 1;
  int i=gridptr->num_dimensions;
  while (i--) {
    /* coords[0] is "most" significant, coords[num_dimensions-1] is least */
    acc += (coords[i]*placevalue);
    placevalue *= gridptr->dimension_sizes[i];
  }
  return acc;
}

gridvalue_t hypergrid_get_value(hypergrid *gridptr, int *coords) {
  int index = _compute_coords_index(gridptr, coords);
  return gridptr->grid_data[index];
}

void hypergrid_set_value(hypergrid *gridptr, int *coords, gridvalue_t value) {
  int index = _compute_coords_index(gridptr, coords);
  gridptr->grid_data[index] = value;
}

int hypergrid_dimension_size(hypergrid *gridptr, int dim) {
  return gridptr->dimension_sizes[dim];
}

/* "private" method used by hypergrid_neighbor_count */
int _count_neighbors(hypergrid *gridptr, int cmpequal, gridvalue_t cmpval, 
                     int baseindex, int dimnum, int placevalue, int wrap) {
  int next_placevalue = placevalue*gridptr->dimension_sizes[dimnum];
  int coord = baseindex / next_placevalue;
  int newindex;
  int count = 0;
  if (dimnum>0) {
    /* do three recursions corresponding to offsetting coordinate by -1, 0, +1 */
    int nextdim = dimnum-1;
    /* check 0 */
    newindex = baseindex;
    count += _count_neighbors(gridptr, cmpequal, cmpval, newindex, nextdim, next_placevalue, wrap);
    /* check -1 */
    newindex = baseindex-placevalue;
    /* if it wraps and the wrap flag is set, adjust index and check */
    if (newindex<0 || (newindex/next_placevalue!=coord)) {
      if (wrap) {
        newindex += next_placevalue;
        count += _count_neighbors(gridptr, cmpequal, cmpval, newindex, nextdim, next_placevalue, wrap);
      }
    }
    else {
      /* in range, always check */
      count += _count_neighbors(gridptr, cmpequal, cmpval, newindex, nextdim, next_placevalue, wrap);
    }
    /* check +1 */
    newindex = baseindex+placevalue;
    /* if it wraps and the wrap flag is set, adjust index and check */
    if ((newindex/next_placevalue!=coord)) {
      if (wrap) {
        newindex -= next_placevalue;
        count += _count_neighbors(gridptr, cmpequal, cmpval, newindex, nextdim, next_placevalue, wrap);
      }
    }
    else {
      /* in range, always check */
      count += _count_neighbors(gridptr, cmpequal, cmpval, newindex, nextdim, next_placevalue, wrap);
    }
    return count;
  }
  else {
    /* if we've hit dimension 0, return value directly */
    /* check 0 */
    gridvalue_t *griddata = gridptr->grid_data;
    newindex = baseindex;
    if ((cmpequal && griddata[newindex]==cmpval) || (!cmpequal && griddata[newindex]!=cmpval)) ++count;
    /* check -1 */
    newindex = baseindex-placevalue;
    /* if it wraps and the wrap flag is set, adjust index and check */
    if (newindex<0 || (newindex/next_placevalue!=coord)) {
      if (wrap) {
        newindex += next_placevalue;
        if ((cmpequal && griddata[newindex]==cmpval) || (!cmpequal && griddata[newindex]!=cmpval)) ++count;
      }
    }
    else {
      /* in range, always check */
      if ((cmpequal && griddata[newindex]==cmpval) || (!cmpequal && griddata[newindex]!=cmpval)) ++count;
    }
    /* check +1 */
    newindex = baseindex+placevalue;
    /* if it wraps and the wrap flag is set, adjust index and check */
    if ((newindex/next_placevalue!=coord)) {
      if (wrap) {
        newindex -= next_placevalue;
        if ((cmpequal && griddata[newindex]==cmpval) || (!cmpequal && griddata[newindex]!=cmpval)) ++count;
      }
    }
    else {
      /* in range, always check */
      if ((cmpequal && griddata[newindex]==cmpval) || (!cmpequal && griddata[newindex]!=cmpval)) ++count;
    }
    return count;
  }
  
}

/* cmpequal: true to count cells equal to cmpval, false to count cells not equal */
/* wrap: true to wrap around edges of grid */
int hypergrid_neighbor_count(hypergrid *gridptr, int *coords, int cmpequal, gridvalue_t cmpval, int wrap) {
  int index = _compute_coords_index(gridptr, coords);
  int count = _count_neighbors(gridptr, cmpequal, cmpval, index, gridptr->num_dimensions-1, 1, wrap);
  /* we may have just counted the center itself */
  if ((cmpequal && gridptr->grid_data[index]==cmpval) || 
      (!cmpequal && gridptr->grid_data[index]!=cmpval)) {
    --count;
  }
  return count;
}

/** Returns the number of cells in the entire grid with value equal to cmpval
*/
int hypergrid_value_count(hypergrid *gridptr, int cmpval) {
  gridvalue_t *values = gridptr->grid_data;
  int ncells = gridptr->num_cells;
  int count=0;
  int i;
  for(i=0; i<ncells; i++) {
    if (values[i]==cmpval) ++count;
  }
  return count;
}

/** Returns true if any cells have a value equal to cmpval
*/
int hypergrid_value_exists(hypergrid *gridptr, int cmpval) {
  gridvalue_t *values = gridptr->grid_data;
  int ncells = gridptr->num_cells;
  int i;
  for(i=0; i<ncells; i++) {
    if (values[i]==cmpval) return 1;
  }
  return 0;
}


/* Returns true if the two hypergrids have equal dimensions */
int hypergrid_equal_dimensions(hypergrid *gridptr1, hypergrid *gridptr2) {
  int nd = gridptr1->num_dimensions;
  return ( (nd==gridptr2->num_dimensions) &&
           (memcmp(gridptr1->dimension_sizes, gridptr2->dimension_sizes, nd*sizeof(int))==0) );
}

/* Returns true if the two hypergrids have equal dimensions and identical values */
int hypergrid_equal(hypergrid *gridptr1, hypergrid *gridptr2) {
  if (!hypergrid_equal_dimensions(gridptr1, gridptr2)) return 0;
  else {
    int nc = gridptr1->num_cells;
    return ( (nc==gridptr2->num_cells) && 
             (memcmp(gridptr1->grid_data, gridptr2->grid_data, nc*sizeof(gridvalue_t))==0) );
  }
}

/* Returns an array of coordinates containing all neighbors of the given coordinate within the
specified distance. The number of neighbors is returned in the count reference parameter.
The returned array must be disposed of by calling hypergrid_coords_list_free. */
int** hypergrid_neighbors(hypergrid *gridptr, int *centercoords, int distance, int *count) {
  /* Extremely inefficient algorith: create a dummy hypergrid whose coordinates represent
  offsets from the given center coordinate. */
  int dim = gridptr->num_dimensions;
  int *sizes = malloc(dim*sizeof(int));
  int mag = 2*distance+1;
  hypergrid *offsetgrid;
  int *offsetcoords;
  int *testcoords = hypergrid_coords_create(gridptr);
  int i;
  int done = 0;
  int **holdingarray;
  int **retarray;
  /* create dummy grid */
  for(i=0; i<dim; i++) sizes[i] = mag;
  offsetgrid = hypergrid_create(dim, sizes);
  free(sizes);
  /* create array large enough to hold all neighbors */
  holdingarray = malloc(offsetgrid->num_cells*sizeof(int *));
  *count = 0;
  /* iterate over offset grid */
  offsetcoords = hypergrid_coords_create(offsetgrid);
  while (!done) {
    /* compute this potential neighbor by applying offset vector */
    for(i=0; i<dim; i++) {
      testcoords[i] = centercoords[i]-distance+offsetcoords[i];
    }
    /* if it's valid, add to the holding array */
    if (hypergrid_coords_isvalid(gridptr, testcoords)) {
      holdingarray[*count] = hypergrid_coords_copy(testcoords, dim);
      (*count)++;
    }
    done = !hypergrid_coords_increment(offsetgrid, offsetcoords);
  }
  /* if we didn't fill the holding array, copy to retarray */
  if (*count != offsetgrid->num_cells) {
    retarray = malloc(*count * sizeof(int *));
    for(i=0; i<*count; i++) {
      retarray[i] = holdingarray[i]; 
    }
    free(holdingarray);
  }
  else {
    /* filled exactly, no need to copy */
    retarray = holdingarray;
  }
  hypergrid_free(offsetgrid);
  hypergrid_coords_free(testcoords);
  hypergrid_coords_free(offsetcoords);
  
  return retarray;
}

void hypergrid_coords_list_free(int **list, int count) {
  int i;
  for(i=0; i<count; i++) {
    hypergrid_coords_free(list[i]);
  }
  free(list);
}

int *array_add(int *arr1, int *arr2, int count) {
  int i;
  int *result = malloc(count*sizeof(int));
  for(i=0; i<count; i++) {
    result[i] = arr1[i]+arr2[i];
  }
  return result;
}

int *array_subtract(int *arr1, int *arr2, int count) {
  int i;
  int *result = malloc(count*sizeof(int));
  for(i=0; i<count; i++) {
    result[i] = arr1[i]-arr2[i];
  }
  return result;
}

void* hypergrid_archive(hypergrid *gridptr, int *size) {
  void *data;
  void *ptr;
  int dimsize = gridptr->num_dimensions*sizeof(gridptr->dimension_sizes[0]);
  int valsize = gridptr->num_cells*sizeof(gridptr->grid_data[0]);
  
  *size = sizeof(gridptr->num_dimensions)+dimsize+sizeof(gridptr->num_cells)+valsize;
  data = malloc(*size);
  ptr = data;

  memmove(ptr, &gridptr->num_dimensions, sizeof(gridptr->num_dimensions));
  ptr += sizeof(gridptr->num_dimensions);
  memmove(ptr, &gridptr->num_cells, sizeof(gridptr->num_cells));
  ptr += sizeof(gridptr->num_cells);

  memmove(ptr, gridptr->dimension_sizes, dimsize);
  ptr += dimsize;
  memmove(ptr, gridptr->grid_data, valsize);
  ptr += valsize;

  return data;
}

hypergrid* hypergrid_unarchive(void *data) {
  hypergrid *gridptr = malloc(sizeof(hypergrid));
  void *ptr = data;
  int dimsize, valsize;

  memmove(&gridptr->num_dimensions, ptr, sizeof(gridptr->num_dimensions));
  ptr += sizeof(gridptr->num_dimensions);
  memmove(&gridptr->num_cells, ptr, sizeof(gridptr->num_cells));
  ptr += sizeof(gridptr->num_cells);

  gridptr->dimension_sizes = malloc(dimsize = gridptr->num_dimensions*sizeof(int));
  gridptr->grid_data = malloc(valsize = gridptr->num_cells*sizeof(gridvalue_t));

  memmove(gridptr->dimension_sizes, ptr, dimsize);
  ptr += dimsize;
  memmove(gridptr->grid_data, ptr, valsize);
  ptr += valsize;
  
  return gridptr;
}


void hypergrid_debug_coords(hypergrid *gridptr,int *coords) {
  int i;
  printf("[");
  for(i=0; i<gridptr->num_dimensions; i++) {
    printf("%4d", coords[i]);
  }
  printf("]\n");
}