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

#import "DCHypergrid.h"
#import "DCHypergridPositionEnumerator.h"
#import "CocoaAdditions.h"

@implementation DCHypergrid

-(id)initWithNumberOfDimensions:(int)numdim sizes:(int *)sizes {
  self = [super init];
  if (self) {
    _cgrid = hypergrid_create(numdim, sizes);
  }
  return self;
}

-(id)initWithCHypergrid:(hypergrid *)gridptr {
  self = [super init];
  if (self) {
    _cgrid = hypergrid_copy(gridptr);
  }
  return self;
}

-(id)copy {
  return [[DCHypergrid alloc] initWithCHypergrid:_cgrid];
}

-(void)copyValuesToGrid:(DCHypergrid *)gridCopy {
  memcpy([gridCopy cHypergrid]->grid_data, [self cHypergrid]->grid_data, [self numberOfCells]*sizeof(gridvalue_t));
}

-(int)numberOfDimensions {
  return _cgrid->num_dimensions;
}

-(int)numberOfCells {
  return _cgrid->num_cells;
}

-(gridvalue_t)valueAtPosition:(DCHypergridPosition *)coords {
  // optimization for 2 dimensions, used in Gridlock to optimize game evaluations
  if (_cgrid->num_dimensions==2) {
    int index = coords->_data[0]*_cgrid->dimension_sizes[1] + coords->_data[1];
    return _cgrid->grid_data[index];
  }
  return hypergrid_get_value(_cgrid, [coords cArray]);
}

-(gridvalue_t)valueAtCoordinateArray:(int *)array {
  // optimization for 2 dimensions, used in Gridlock to optimize game evaluations
  if (_cgrid->num_dimensions==2) {
    int index = array[0]*_cgrid->dimension_sizes[1] + array[1];
    return _cgrid->grid_data[index];
  }
  return hypergrid_get_value(_cgrid, array);
}

-(id)setValue:(gridvalue_t)value atPosition:(DCHypergridPosition *)coords {
  hypergrid_set_value(_cgrid, [coords cArray], value);
  return self;
}

-(id)setValue:(gridvalue_t)value atCoordinateArray:(int *)array {
  hypergrid_set_value(_cgrid, array, value);
  return self;
}

-(void)setValue:(gridvalue_t)value atPositions:(NSArray *)positions {
  int i;
  for(i=[positions count]-1; i>=0; i--) {
    id pos = [positions objectAtIndex:i];
    hypergrid_set_value(_cgrid, [pos cArray], value);
  }
}

-(BOOL)isValidPosition:(DCHypergridPosition *)position {
  return hypergrid_coords_isvalid(_cgrid, [position cArray]);
}

-(BOOL)isValidCoordinateArray:(int *)array {
  return hypergrid_coords_isvalid(_cgrid, array);
}


-(int)sizeOfDimension:(int)dim {
  return hypergrid_dimension_size(_cgrid, dim);
}

-(int)nonzeroNeighborsOfPosition:(DCHypergridPosition *)coords {
  return hypergrid_neighbor_count(_cgrid, [coords cArray], 0, 0, 1);
}

-(int)nonzeroNeighborsOfPosition:(DCHypergridPosition *)coords wrapping:(BOOL)wrap {
  return hypergrid_neighbor_count(_cgrid, [coords cArray], 0, 0, wrap);
}

-(int)numberOfNeighborsOfPosition:(DCHypergridPosition *)pos withValue:(int)value {
  return hypergrid_neighbor_count(_cgrid, [pos cArray], 1, value, 0);
}

-(int)numberOfCellsWithValue:(int)value {
  return hypergrid_value_count(_cgrid, value);
}

-(BOOL)hasCellWithValue:(int)value {
  return (hypergrid_value_exists(_cgrid, value)!=0);
}

-(BOOL)isEqualToHypergrid:(DCHypergrid *)cmp {
  return hypergrid_equal([self cHypergrid], [cmp cHypergrid]);
}

-(NSArray *)neighborsOfPosition:(DCHypergridPosition *)coords distance:(int)dist {
  NSMutableArray *array;
  int dim = [self numberOfDimensions];

  if (dim==2) {
    int dr, dc;
    int r=[coords row], c=[coords column];
    // max neighbors = (2*dist+1)^2 = 4d^2+4d+1 = 4d(d+1)+1
    array = [NSMutableArray arrayWithCapacity:4*dist*(dist+1)+1];
    for(dr=-dist; dr<=dist; dr++) {
      int newr = r+dr;
      for(dc=-dist; dc<=dist; dc++) {
        int newc = c+dc;
        if ([self isValidRow:newr column:newc]) {
          [array addObject:[DCHypergridPosition positionWithRow:newr column:newc]];
        }
      }
    }
  }
  else {
    int **neighborlist;
    int count;
    int i;
    array = [NSMutableArray array];
    neighborlist = hypergrid_neighbors([self cHypergrid], [coords cArray], dist, &count);
    for(i=0; i<count; i++) {
      DCHypergridPosition *neighbor = [DCHypergridPosition positionWithSize:dim data:neighborlist[i]];
      [array addObject:neighbor];
    }
    hypergrid_coords_list_free(neighborlist, count);
  }
  
  return array;
}

-(NSEnumerator *)positionEnumerator {
  return [[[DCHypergridPositionEnumerator alloc] initWithHypergrid:self] autorelease];
}

-(NSEnumerator *)enumeratorForPositionsWithValue:(int)value {
  return [[[DCHypergridPositionEnumeratorForValue alloc] initWithHypergrid:self targetValue:value] autorelease];
}

-(DCHypergridPosition *)positionWithValue:(int)value {
  int * _coords = (int *)calloc(_cgrid->num_dimensions, sizeof(int));
  DCHypergridPosition *position = nil;
  if (hypergrid_get_value(_cgrid, _coords)==value) {
    position = [DCHypergridPosition positionWithSize:_cgrid->num_dimensions data:_coords];
  }
  while (!position && hypergrid_coords_increment(_cgrid, _coords)) {
    if (hypergrid_get_value(_cgrid, _coords)==value) {
      position = [DCHypergridPosition positionWithSize:_cgrid->num_dimensions data:_coords];
    }
  }
  free(_coords);
  return position;
}

-(NSArray *)allPositionsWithValue:(int)value {
  return [[self enumeratorForPositionsWithValue:value] allObjects];
}

-(void)addPositionsToGroup:(NSMutableSet *)group withValue:(int)pnum startingFromPosition:(id)pos onlyOrthoganal:(BOOL)ortho {
  // this only works for 2d grids currently
  static int orthoDeltas[] = {+1,0, -1,0, 0,+1, 0,-1};
  static int diagDeltas[]  = {+1,+1, +1,0, +1,-1, 0,+1, 0,-1, -1,+1, -1,0, -1,-1};

  [group addObject:pos];

  int *deltas = (ortho) ? orthoDeltas : diagDeltas;
  int numd = (ortho) ? 4 : 8;
  int r=[pos row], c=[pos column];
  int i;
  for(i=0; i<numd; i++) {
    int dr = deltas[2*i];
    int dc = deltas[2*i+1];
    id nextpos = [DCHypergridPosition positionWithRow:r+dr column:c+dc];
    if ([self isValidPosition:nextpos] && [self valueAtPosition:nextpos]==pnum && ![group containsObject:nextpos]) {
      [self addPositionsToGroup:group withValue:pnum startingFromPosition:nextpos onlyOrthoganal:ortho];
    }
  }
}

-(NSArray *)connectedGroupsWithValue:(int)value onlyOrthoganal:(BOOL)ortho {
  // returned array is sorted by ascending size of groups
  NSMutableArray *allGroups = [NSMutableArray array];
  NSMutableSet *positionsInGroups = [[[NSMutableSet alloc] init] autorelease];
  NSEnumerator *pe = [self enumeratorForPositionsWithValue:value];
  id pos;
  while(pos=[pe nextObject]) {
    if (![positionsInGroups containsObject:pos]) {
      NSMutableSet *group = [[[NSMutableSet alloc] init] autorelease];
      [self addPositionsToGroup:group withValue:value startingFromPosition:pos onlyOrthoganal:ortho];
      [positionsInGroups addObjectsFromArray:[group allObjects]];
      [allGroups addObject:group];
    }
  }
  [allGroups sortArrayByCount_];
  return allGroups;
}

-(hypergrid *)cHypergrid {
  return _cgrid;
}

-(void)dealloc {
  if (_cgrid) hypergrid_free(_cgrid);
  [super dealloc];
}

-(id)propertyList{
  NSMutableDictionary *dict = [NSMutableDictionary dictionary];
  NSMutableArray *dimsizes = [NSMutableArray array];
  NSMutableArray *values = [NSMutableArray array];
  NSEnumerator *pe = [self positionEnumerator];
  id pos;
  int i;
  
  for(i=0; i<[self numberOfDimensions]; i++) {
    [dimsizes addObject:[NSNumber numberWithInt:[self sizeOfDimension:i]]];
  }
  [dict setObject:[dimsizes componentsJoinedByString:@" "] forKey:@"dimensions"];

  while(pos=[pe nextObject]) {
    [values addObject:[NSNumber numberWithInt:[self valueAtPosition:pos]]];
  }
  [dict setObject:[values componentsJoinedByString:@" "] forKey:@"values"];
  
  return dict;
}
-(id)initFromPropertyList:(id)plist {
  NSArray *dimArray = [[plist objectForKey:@"dimensions"] componentsSeparatedByString:@" "];
  NSArray *valArray = [[plist objectForKey:@"values"] componentsSeparatedByString:@" "];
  
  int *dims = malloc([dimArray count]*sizeof(int));
  int i;
  for(i=0; i<[dimArray count]; i++) {
    dims[i] = [[dimArray objectAtIndex:i] intValue];
  }
  [self initWithNumberOfDimensions:[dimArray count] sizes:dims];
  free(dims);
  {
    NSEnumerator *pe = [self positionEnumerator];
    NSEnumerator *ve = [valArray objectEnumerator];
    id pos;
    id val;
    while ((pos=[pe nextObject]) && (val=[ve nextObject])) {
      [self setValue:[val intValue] atPosition:pos];
    }
  }
  return self;
}


// convenience methods for 2d grids

-(id)initWithRows:(int)r columns:(int)c {
  int sizes[] = {r,c};
  return [self initWithNumberOfDimensions:2 sizes:sizes];
}

+(id)gridWithRows:(int)r columns:(int)c {
  return [[[self alloc] initWithRows:r columns:c] autorelease];
}

-(int)valueAtRow:(int)r column:(int)c {
  int coords[] = {r,c};
  return [self valueAtCoordinateArray:coords];
}

-(void)setValue:(int)value atRow:(int)r column:(int)c {
  int coords[] = {r,c};
  [self setValue:value atCoordinateArray:coords];
}

-(BOOL)isValidRow:(int)r column:(int)c {
  int coords[] = {r,c};
  return [self isValidCoordinateArray:coords];
}

-(int)numberOfRows {
  return [self sizeOfDimension:0];
}

-(int)numberOfColumns {
  return [self sizeOfDimension:1];
}


@end