/* 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 "CheckersGame.h"

static NSArray* _averagesOfPositionsWithPosition(NSArray *positions, DCHypergridPosition *basepos) {
  if ([positions count]==0) return nil;
  else {
    int r = [basepos row];
    int c = [basepos column];
    NSMutableArray *array = [NSMutableArray array];
    NSEnumerator *pe = [positions objectEnumerator];
    id pos;
    while (pos=[pe nextObject]) {
      [array addObject:[DCHypergridPosition positionWithRow:(r+[pos row])/2
                                                     column:(c+[pos column])/2]];
    }
    return array;
  }
}

@implementation CheckersGame

-(void)reset {
  [super reset];
  [self setGrid:[DCHypergrid gridWithRows:[[[self configurationInfo] objectForKey:@"rows"] intValue]
                                  columns:[[[self configurationInfo] objectForKey:@"cols"] intValue]]];
  {
    int rows = [self numberOfRows];
    int cols = [self numberOfColumns];
    int r,c;
    // set alternate cells, leaving the two middle rows empty
    for(r=0; r<rows/2-1; r++) {
      for(c=0; c<cols; c++) {
        if ((r+c)%2==0) {
          [self setValue:1 atRow:r column:c];
          [self setValue:2 atRow:rows-1-r column:cols-1-c];
        }
      }
    }
  }
}

-(int)rowIncrementForCurrentPlayer {
  return (playerNumber==1) ? 1 : -1;
}

-(int)rowIncrementForPlayer:(int)pnum {
  return (pnum==1) ? 1 : -1;
}

-(int)ownerOfPosition:(DCHypergridPosition *)pos {
  int value = [self valueAtPosition:pos];
  return abs(value);
}

-(BOOL)isKingAtPosition:(DCHypergridPosition *)pos {
  int value = [self valueAtPosition:pos];
  return (value<0);
}

-(int)numberOfRegularPiecesForPlayer:(int)pnum {
  return [[self grid] numberOfCellsWithValue:pnum];
}
-(int)numberOfKingsForPlayer:(int)pnum {
  return [[self grid] numberOfCellsWithValue:-pnum];
}


-(NSArray *)validJumpsForPlayer:(int)pnum fromPosition:(DCHypergridPosition *)pos isKing:(BOOL)king startPosition:(DCHypergridPosition *)startPosition{
  int oppnum = [self playerNumberMovingAfterPlayer:pnum];
  int dr = [self rowIncrementForPlayer:pnum];
  int rchecks = (king) ? 2 : 1;
  int row = [pos row];
  int col = [pos column];
  int i;
  NSMutableArray *jumpPositions = nil; 
  // look left and right, and backwards if a king
  for(i=0; i<rchecks; i++) {
    int r1 = (i==0) ? row+dr : row-dr;
    int r2 = (i==0) ? row+2*dr : row-2*dr;
    int dc;
    for(dc=-1; dc<=1; dc+=2) {
      int c1 = col+dc;
      int c2 = col+2*dc;
      id pos1 = [DCHypergridPosition positionWithRow:r1 column:c1];
      id pos2 = [DCHypergridPosition positionWithRow:r2 column:c2];
      // pos1 must have opponent, pos2 must be empty or be the position the move started from
      if ([self isPositionValid:pos2] && [self ownerOfPosition:pos1]==oppnum && ([self valueAtPosition:pos2]==0 || [pos2 isEqual:startPosition])) {
        if (!jumpPositions) jumpPositions = [NSMutableArray array];
        [jumpPositions addObject:pos2];
      }
    }
  }
  return jumpPositions;
}

-(NSArray *)validSingleMovesForPlayer:(int)pnum fromPosition:(DCHypergridPosition *)pos isKing:(BOOL)king {
  int dr = [self rowIncrementForPlayer:pnum];
  int rchecks = (king) ? 2 : 1;
  int row = [pos row];
  int col = [pos column];
  NSMutableArray *positions = nil;
  int i;
  // look left and right, and backwards if a king
  for(i=0; i<rchecks; i++) {
    int r = (i==0) ? row+dr : row-dr;
    int dc;
    for(dc=-1; dc<=1; dc+=2) {
      int c = col+dc;
      id pos = [DCHypergridPosition positionWithRow:r column:c];
      if ([self isPositionValid:pos] && [self ownerOfPosition:pos]==0) {
        if (!positions) positions = [NSMutableArray array];
        [positions addObject:pos];
      }
    }
  }
  return positions;
}

-(DCHypergridPosition *)positionJumpedForPlayer:(int)pnum
                                   fromPosition:(DCHypergridPosition *)pos1
                                     toPosition:(DCHypergridPosition *)pos2
                                         isKing:(BOOL)king
                                  startPosition:(DCHypergridPosition *)startPosition {
  // ending position must be empty
  if ([self valueAtPosition:pos2]==0 || [pos2 isEqual:startPosition]) {
    int rdiff = [pos2 row]-[pos1 row];
    int cdiff = [pos2 column]-[pos1 column];
    if (cdiff==2 || cdiff==-2) {
      int dr = [self rowIncrementForPlayer:pnum];
      if (rdiff==2*dr || (king && rdiff==-2*dr)) {
        // middle position must be owned by opponent
        id jpos = [DCHypergridPosition positionWithRow:[pos1 row]+rdiff/2
                                                column:[pos1 column]+cdiff/2];
        if ([self ownerOfPosition:jpos]==[self playerNumberMovingAfterPlayer:pnum]) {
          return jpos;
        }
      }
    }
  }
  return nil;
}

// returns nil if move is invalid, empty array if valid but no jumps
-(NSArray *)jumpedPositionsForMoveSequence:(NSArray *)positions {
  int len = [positions count];
  if (len<2) return nil;
  else {
    NSMutableArray *jumpPositions = [NSMutableArray array];
    int i;
    id startpos = [positions objectAtIndex:0];
    int startval = [self valueAtPosition:startpos];
    BOOL king = (startval<0);
    int pnum = [self currentPlayerNumber];
    // must own start position
    if (pnum!=[self ownerOfPosition:startpos]) return NO;
    if (len==2) {
      // handle non-jump move here
      id endpos = [positions objectAtIndex:1];
      int rdiff = [endpos row]-[startpos row];
      int cdiff = [endpos column]-[startpos column];
      int dr = [self rowIncrementForCurrentPlayer];
      if ( (cdiff==1 || cdiff==-1) && (rdiff==dr || (king && rdiff==-dr)) &&
           [self valueAtPosition:endpos]==0) {
        // should make sure there are no possible jumps
        return jumpPositions;
      }
    }
    // if here, then we have a sequence of jumps
    for(i=1; i<len; i++) {
      id pos = [positions objectAtIndex:i];
      id lastpos = [positions objectAtIndex:i-1];
      id jumppos = [self positionJumpedForPlayer:pnum
                                    fromPosition:lastpos
                                      toPosition:pos isKing:king
                                   startPosition:[positions objectAtIndex:0]];
      if (!jumppos) return nil;
      if ([jumpPositions containsObject:jumppos]) return nil;
      // jump is good
      [jumpPositions addObject:jumppos];
    }
    return jumpPositions;
  }  
}

-(BOOL)prepareMoveSequence:(NSArray *)positions {
  NSArray *jumpedPositions = [self jumpedPositionsForMoveSequence:positions];
  [self resetFutureGrid];

  if (jumpedPositions==nil) return NO;
  else {
    int pnum = [self currentPlayerNumber];
    int lastRow = (pnum==1) ? [self numberOfRows]-1 : 0;
    id lastpos = [positions lastObject];
    id firstpos = [positions objectAtIndex:0];
    
    [[self futureGrid] setValue:0 atPositions:jumpedPositions];
    
    if (![firstpos isEqual:lastpos]) {
      [[self futureGrid] setValue:0 atPosition:firstpos];
      // check for promotion
      if ([lastpos row]==lastRow) {
        [[self futureGrid] setValue:-pnum atPosition:lastpos];
      }
      else {
        [[self futureGrid] setValue:[self valueAtPosition:firstpos] atPosition:lastpos];
      }
    }
    return YES;
  }
}

-(BOOL)isGameOver {
  // game over if current player can't move
  int pnum = [self currentPlayerNumber];
  NSEnumerator *pe = [[self grid] positionEnumerator];
  id pos;
  while (pos=[pe nextObject]) {
    if (pnum==[self ownerOfPosition:pos]) {
      BOOL king = [self isKingAtPosition:pos];
      if ([[self validSingleMovesForPlayer:pnum fromPosition:pos isKing:king] count]>0) return NO;
      if ([[self validJumpsForPlayer:pnum fromPosition:pos isKing:king startPosition:pos] count]>0) return NO;
    }
  }
  return YES;
}

-(int)winningPlayer {
  return [self nextPlayerNumber];
}

-(void)_insertValidJumpsForPlayer:(int)pnum
                     fromPosition:(DCHypergridPosition *)pos
                           isKing:(BOOL)king
          ignoringJumpedPositions:(NSArray *)previousJumpedPositions
                startingPositions:(NSArray *)partialMove
                    intoMoveArray:(NSMutableArray *)moves {
  // get available jumps
  NSArray *jumps = [self validJumpsForPlayer:pnum fromPosition:pos isKing:king startPosition:[partialMove objectAtIndex:0]];
  NSArray *jumpedPositions = _averagesOfPositionsWithPosition(jumps, pos);
  int i;
  BOOL foundJump = NO;
  for(i=0; i<[jumps count]; i++) {
    if (![previousJumpedPositions containsObject:[jumpedPositions objectAtIndex:i]]) {
      foundJump = YES;
      // keep going...
      [self _insertValidJumpsForPlayer:pnum
                          fromPosition:[jumps objectAtIndex:i]
                                isKing:king
               ignoringJumpedPositions:[previousJumpedPositions arrayByAddingObject:[jumpedPositions objectAtIndex:i]]
                     startingPositions:[partialMove arrayByAddingObject:[jumps objectAtIndex:i]]
                         intoMoveArray:moves];
    }
  }
  if (!foundJump) {
    if ([partialMove count]>=2) {
      [moves addObject:partialMove];
    }
  }
}

-(NSArray *)allValidMoveSequences {
  NSMutableArray *jumps = [NSMutableArray array];
  NSMutableArray *nonjumps = [NSMutableArray array];
  int pnum = [self currentPlayerNumber];
  NSEnumerator *pe = [[self grid] positionEnumerator];
  id pos;
  while (pos=[pe nextObject]) {
    if (pnum==[self ownerOfPosition:pos]) {
      BOOL king = [self isKingAtPosition:pos];
      // process jumps
      [self _insertValidJumpsForPlayer:pnum
                          fromPosition:pos
                                isKing:king
               ignoringJumpedPositions:[NSArray array]
                     startingPositions:[pos arrayWithSelf_]
                         intoMoveArray:jumps];
      // process nonjumps if no jumps found
      if ([jumps count]==0) {
        NSArray *nonJumpPositions = [self validSingleMovesForPlayer:pnum fromPosition:pos isKing:king];
        NSEnumerator *nje = [nonJumpPositions objectEnumerator];
        id pos2;
        while (pos2=[nje nextObject]) {
          [nonjumps addObject:[NSArray arrayWithObjects:pos, pos2, nil]];
        }
      }      
    }
  }
  return ([jumps count]>0) ? jumps : nonjumps;
}

@end