/*
  crossword -- a crossword game
  Copyright (C) 2000 Falk Hueffner

  This program 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 2 of the License, or (at your option)
  any later version.
  
  This program 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
  this program; if not, write to the Free Software Foundation, Inc., 59 Temple
  Place, Suite 330, Boston, MA 02111-1307 USA

  $Id: Bot.cc,v 1.15 2000/11/29 01:29:38 falk Exp $
*/

# include <iostream>
# include <iomanip>

#include "Bot.hh"
#include "Rules.hh"
#include "Tile.hh"
#include "Trie.hh"

void Bot::apply(const Move& move) {
    assert(!isRotated);
    board.apply(move);

    for (Move::const_iterator i = move.begin(); i != move.end(); ++i) {
	// OPTIMIZEME for vertical moves, these loops will all end at the same tile
	Pos p;
	for (p = i->pos() + Rules::up(); p >= 0 && !board.empty(p);
	     p += Rules::up()) { }
	if (p >= 0)
	    updateLetterOk(p);
	for (p = i->pos() + Rules::down(); p < Rules::numFields() && !board.empty(p);
	     p += Rules::down()) { }
	if (p < Rules::numFields())
	    updateLetterOk(p);
    }

    rotateBoard();
    for (Move::const_iterator i = move.begin(); i != move.end(); ++i) {
	// OPTIMIZEME for vertical moves, these loops will all end at the same tile
	Pos p;
	for (p = rotatedPos(i->pos()); p >= 0 && !board.empty(p); p += Rules::up()) { }
	if (p >= 0)
	    updateLetterOk(p);
	for (p = rotatedPos(i->pos()); p < Rules::numFields() && !board.empty(p);
	     p += Rules::down()) { }
	if (p < Rules::numFields())
	    updateLetterOk(p);
    }

    rotateBoard();		// restore usual orientation
}

Move Bot::getMove() {
    // set up everything
    rack.set(letters);
    bestScore = 0;
    bestMove.clear();
    cout << "Rack: " << rack << endl;

    assert(!isRotated);
    scanBoard();		// first find horizontal moves...
    rotateBoard();
    scanBoard();		// ...now vertical.
    rotateBoard();		// restore usual orientation

    return bestMove;
}

void Bot::scanBoard() {
    lastAnchor = anchor = -1;
    for (unsigned int y = 0; y < Rules::ysize(); ++y) {
	rightBorder = (y + 1) * Rules::xsize();
	leftBorder = y * Rules::xsize() - 1;
	for (unsigned int x = 0; x < Rules::xsize(); ++x) {
	    Pos pos = x + y * Rules::xsize();

	    // check if here might be an anchor...
	    if (board.at(pos) != EMPTY)
		continue;

	    dir = RIGHT;
	    score = 0;
	    multiplier = 1;
	    if (pos - 1 != leftBorder && !board.empty(pos - 1)) {
		// there's a tile to the left.
		anchor = pos;
		isContinuation = true;
		tryPutting(pos, dict.root());
	    } else if (board.isStartPos(pos)
		       || (pos + Rules::right() < rightBorder
			   && !board.empty(pos + Rules::right()))
		       || (pos + Rules::up() >= 0
			   && !board.empty(pos + Rules::up()))
		       || (pos + Rules::down() < Rules::numFields()
			   && !board.empty(pos + Rules::down()))) {
		// there's an adjacent tile, or this is the start position.
		anchor = pos;
		isContinuation = false;
		tryPutting(pos, dict.root());
	    }
	    lastAnchor = anchor;
	}
    }
}

void Bot::tryPutting(Pos pos, const TrieNode* node) {
    if (pos >= rightBorder || pos <= leftBorder || pos <= lastAnchor)
	return;

    Tile l = board.at(pos);
    if (l != EMPTY) {
	node = node->child(l);
	if (node != NULL)
	    placeTile(pos, node);
    } else {
	// Here we exploit heavily that both the rack and the children of node
	// are sorted.
	Rack::Handle rackHandle = rack.begin();
	if (rackHandle == rack.end())
	    return;
	const TrieNode* child = node->firstChild();
	if (child == NULL)
	    return;

	if (rack.get(rackHandle) == '*') { // wildcards are sorted first in rack
	    for (; child != NULL; child = child->nextSibling()) {
		Tile childLetter = child->letter();
		if (childLetter == '#' || childLetter < rack.lastBlank())
		    continue;

		if ((*letterOk)[pos][childLetter]) {
		    int oldMultiplier = multiplier, oldScore = score,
			oldLastBlank = rack.lastBlank();

		    rack.setLastBlank(childLetter);
		    score += Rules::score('*') * Rules::letterMultiplier(pos);
		    multiplier *= Rules::wordMultiplier(pos);
		    rack.draw(rackHandle);
		    move.push_back(Put(pos, childLetter));

		    placeTile(pos, child);

		    move.pop_back();
		    rack.putBack(rackHandle);
		    multiplier = oldMultiplier;
		    score = oldScore;
		    rack.setLastBlank(oldLastBlank);
		}
	    }
	    child = node->firstChild();
	}

	while (true) {
	    Tile childLetter = child->letter();

	    while (rack.get(rackHandle) < childLetter) {
		rackHandle = rack.next(rackHandle);
		if (rackHandle == rack.end())
		    return;
	    }

	    Tile rackLetter  = rack.get(rackHandle);

	    while (child->letter() < rackLetter) {
		child = child->nextSibling();
		if (child == NULL)
		    return;
	    }

	    if (child->letter() == rackLetter) {
		if ((*letterOk)[pos][rackLetter]) {
		    int oldMultiplier = multiplier, oldScore = score;

		    score += Rules::score(rackLetter) * Rules::letterMultiplier(pos);
		    multiplier *= Rules::wordMultiplier(pos);
		    rack.draw(rackHandle);
		    move.push_back(Put(pos, rackLetter));

		    placeTile(pos, child);

		    move.pop_back();
		    rack.putBack(rackHandle);
		    multiplier = oldMultiplier;
		    score = oldScore;
		}

		rackHandle = rack.next(rackHandle);
		if (rackHandle == rack.end())
		    return;
		child = child->nextSibling();
		if (child == NULL)
		    return;
	    }
	}
	// FIXME handle blanks
    }
}

// We have chosen to place tile l in position pos. Check for complete words,
// and perhaps extend it to the left.
void Bot::placeTile(Pos pos, const TrieNode* node) {
    Pos nextPos = pos + dir;
    if (nextPos == rightBorder || nextPos == leftBorder ||
	board.at(nextPos) == EMPTY) {
	// OK, here could be a word end.
	if (node->isTerminal() && (!isContinuation || dir == LEFT))
	    scoreWord();

	// also try with a few more letters to the left of the anchor.
	if (dir == RIGHT) {
	    const TrieNode* revNode = node->child('#');
	    if (revNode != NULL) {
		dir = LEFT;
		tryPutting(anchor - 1, revNode);
		dir = RIGHT;
	    }
	}
    }

    tryPutting(pos + dir, node);
}

void Bot::scoreWord() {
    int finalScore = score;
    finalScore *= multiplier;
    if (rack.empty())
	finalScore += 50; // FIXME make customizable

    // count score for already laid tiles
    Put first = *min_element(move.begin(), move.end()),
	last  = *max_element(move.begin(), move.end());

    Pos pStart = first.pos(), pEnd = last.pos(), p2;
    for (p2 = first.pos() + Rules::left();
	 p2 > leftBorder && !board.empty(p2);
	 p2 += Rules::left())
	pStart = p2;
    for (p2 = last.pos() + Rules::right();
	 p2 < rightBorder && !board.empty(p2);
	 p2 += Rules::right())
	pEnd = p2;

    for (Pos p = pStart; p <= pEnd; p += Rules::right())
	if (!board.empty(p))
	    finalScore += Rules::score(board.at(p));

    // count score for vertical words
    for (Move::iterator i = move.begin(); i != move.end(); ++i) {
	Pos p = i->pos(), pStart = p, pEnd = p, p2;
	for (p2 = p + Rules::up();
	     p2 >= 0 && !board.empty(p2);
	     p2 += Rules::up())
	    pStart = p2;
	for (p2 = p + Rules::down();
	     p2 < Rules::numFields() && !board.empty(p2);
	     p2 += Rules::down())
	    pEnd = p2;
	if (pStart != pEnd) {
	    int extraScore = 0;

	    for (p2 = pStart; p2 <= pEnd; p2 += Rules::down()) {
		if (p2 != p)
		    extraScore += Rules::score(board.at(p2));
		else
		    extraScore += Rules::score(i->tile()) * Rules::letterMultiplier(p);
	    }
	    extraScore *= Rules::wordMultiplier(p);
	    finalScore += extraScore;
	}
    }

    if (finalScore > bestScore
	// this clause is to get reproducible choices on same scores.
	/* || (finalScore == bestScore && move > bestMove)*/ ) {
	bestScore = finalScore;
	bestMove = move;
	if (isRotated) {
	    for (Move::iterator i = bestMove.begin(); i != bestMove.end(); ++i)
		*i = Put(rotatedPos(i->pos()), i->tile());
	}
	cout << setw(2) << finalScore << ' ' << bestMove
	     << "(* " << multiplier << ')'
	     << endl;
    }
}

// This assumes a letter has been *added* adjacent to here, not removed.
void Bot::updateLetterOk(Pos pos) {
    assert(board.empty(pos));

    int y = pos / Rules::xsize();
    if ((y == 0 || board.empty(pos + Rules::up()))
	&& (y == Rules::ysize() - 1 || board.empty(pos + Rules::down()))) {
	// No adjacent tiles. Everything stays valid here.
	return;
    }

    for (int i = 0; i < 256; ++i)
	(*letterOk)[pos][i] = false;

    Pos p = pos + Rules::up();
    while (p >= 0 && !board.empty(p))
	p += Rules::up();
    p += Rules::down();

    // p is now the start of the word above, or still (x, y).
    const TrieNode* node = dict.root();
    while (node != NULL && p != pos) {
	node = node->child(board.at(p));
	p += Rules::down();
    }
    if (node == NULL)
	return;

    // node now corresponds to all legal letters for pos.
    for (const TrieNode* child = node->firstChild();
	 child != NULL; child = child->nextSibling()) {
	Pos p = pos + Rules::down();
	const TrieNode* node2 = child;
	while (node2 != NULL && p < Rules::numFields() && !board.empty(p)) {
	    node2 = node2->child(board.at(p));
	    p += Rules::down();
	}
	if (node2 != NULL && node2->isTerminal())
	    (*letterOk)[pos][child->letter()] = true;
    }
}

Pos Bot::rotatedPos(Pos p) {
    int x = p % Rules::xsize();
    int y = p / Rules::xsize();
    return y + x * Rules::xsize();
}

void Bot::rotateBoard() {
    Board rotatedBoard;

    for (unsigned int y = 0; y < Rules::ysize(); ++y) {
	for (unsigned int x = 0; x < Rules::xsize(); ++x) {
	    Pos p1 = x + y * Rules::xsize(),
		p2 = y + x * Rules::xsize();
	    rotatedBoard.set(p2, board.at(p1));
	}
    }

    board = rotatedBoard;
    isRotated = !isRotated;
    if (!isRotated)
	letterOk = &letterOkNormal;
    else
	letterOk = &letterOkRotated;
}