/* This file is part of cardwords
   (c) 1999 Tobias Peters
   see file COPYING for the copyright terms.
   
   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
*/

// cardwords_dicbot_cardtablerequirements.hh

// Please notice the difference between CardWords_DicBot_CardTableRequirement
// and CardWords_DicBot_CardTableRequirements ! (Hint: the latter is plural)

/* This file defines the class CardWords_DicBot_CardTableRequirements. This
   class is a Replacement to CardWords_DicBot_CellValues and
   CardWords_DicBot_LetterFactors. I hope Im doing it more clear in here.

   An instance of CardWords_DicBot_CardTableRequirements should collect
   information about a part of the card-table that is relevant to
   1 - finding words that can be layed in that part
   2 - finding the best arrangement of cards in that part
   .   and provide that information to interested parties.

   The information considered relevant is:
   - the meaning of Cards that are already on the card-table
   - the word factor and letter factor of cells in that part
   - (bool) if there is an adjacent card next to a free cell that would lead
   .   to a side word
   - if the cell is free, a list of characters (meanings/CardWords_Chars) that
   .   are known not to be allowed there because of creating of invalid side
   .   words

   The word factors and letter factors and the fact that a side word would be
   created or not will be combined to a single "aim factor" for every specific
   word length and card-table cell. This "aim factor" is the factor that the
   card points will be multiplied with for a card in this cell when the word
   score is computed.
*/

/* Here's the comment from the earlier file cardwords_dicbot_cellvalues.hh: */
/* When searching for the word with the best score on the card-table,
       the card-table will be searched for twice, once vertically and once
       horizontally.
       
       Assume it is currently searched horizontally. Each cell has
       a letter factor and a word factor.
   
       The letter factor is a factor that will be multiplied with the
       card's score.
   
       The word factor is a factor that will be multiplied with the
       score of all cards that belong to the same word as the card
       lying on the cell with the word factor.

       Possible words will be searched backwards: In a line
       _____________________________________________
       | | | | | |w|o|r|l|d| | | | | | | | | | |i| |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       the search will begin behind the 'i', DicBot will search for
       one-letter-words, if allowed in this game. Next it will search
       for one- and two-letter-words starting with i etc.
       
       When the score of every possible word at one starting place has been
       counted, the search moves on to the previous starting cell.

       This is the time when this cells letter and word factors get saved
       [...] for later reference.
    */


#ifndef CARDWORDS_DICBOT_CARDTABLEREQUIREMENTS_HH
#define CARDWORDS_DICBOT_CARDTABLEREQUIREMENTS_HH

#include "cardwords_dicbot_cardtablerequirement.hh"
#include <slist.h>
#include "cardwords_direction.hh"
#include "cardwords_dicbot_cardtable.hh"
#include <limits.h>
#include "cardwords_string.hh"
#include "cardwords_max.hh"
#include <algo.h>
#include "cardwords_implication.hh"

class CardWords_DicBot_CardTableRequirements :
  public slist<CardWords_DicBot_CardTableRequirement>
{
public:
  // specify the card-table, the direction and the row/column at
  // creation time:
  // The first cell is *not* read at creation time.
  CardWords_DicBot_CardTableRequirements (const
                                          class CardWords_DicBot_CardTable *,

                                          CardWords_Direction,

                                          size_t row_column);
  
  // Add a new cell: push it to the front. new_cell needs no argument, it
  // knows which cell to add. If so wants to check if this was right, check
  // the return value.
  const CardWords_CardTableLocation & new_cell (void);

  // Prepare to be asked things about words with length l:
  void new_length (size_t l);
  size_t get_length (void) const; // Return the length from last call.
  
  // Check if this word is allowed, as far as known by now. The length
  // parameter from the previous method is not relevant for this check,
  // nor is it adjusted.
  // Note: This only checks the musts. It Changes internal data relevant for
  // get_needed_cards.
  bool test_allowed (const CardWords_String &);

  // If a previous check test_allowed returned true, then a call to
  // get_needed_cards could make sense: it returns a const vector<size_t> &.
  // the index of this vector is the internal number of CardWords_Chars (can
  // be accessed by CardWords_Char::internal_no() ) while the contents is the
  // number of cards that must be layed with this meaning. Note that the musts
  // are not counted here.
  const vector<size_t> & get_needed_cards (void) const;

  // Return a reference to a vector of "aim factors". This is needed by the
  // best_order_generator:
  const vector<int>& get_aim_factors(void) const
    // Fields without an aim factor (because there is a card on them) are
    // marked with INT_MAX
    ;
  
  // The same as above, but the given length l and the length from method
  // new_length are checked for equality, and if not, new_length(l) is called.
  // This method does a check more, but its aim is that perhaps unnecessary
  // calls to new_length, which is a very little bit expensive, are avoided:
  const vector<int>& get_aim_factors(size_t l) {
    if (l != get_length()) new_length (l);
    return get_aim_factors();
  }

  // Return the maximum word length that could be layed using n cards,
  // considering count and positions of the musts:
  size_t max_word_length (size_t n) const;

  // Return the minimum word length. This takes into account that a new word
  // on the card-table must touch another card that is already on the
  // card-table. min_word_length of 0 means: no chance to lay any word at all.
  size_t min_word_length () const;
private:
  const class CardWords_DicBot_CardTable * card_table;
  CardWords_Direction direction;
  CardWords_CardTableLocation loc; // The last read card-table cell
  size_t & changing_coordinate; // reference to one of the components of loc
  size_t   aim_word_length;
  vector<int> aim_factors;

  vector<size_t> needed_cards;

  // a vector of aim factors and there indices
  vector<pair<int, size_t> > aim_factors_indices;
  // the counts how many aim factors are >0, <0 and ==0 respectively
  size_t high_aim_factors_count;
  size_t low_aim_factors_count;
  size_t zero_aim_factors_count;

  // the index of the first cell where either a card is contained or a side
  // word is created. A negative value means no such cell so far, or a card in
  // the card-table cell before the first one, which means no_start_possible.
  int first_reached_card_index;
  
public:
  // accessing functions for these last items:
  inline const vector<pair<int, size_t> >& get_aim_factors_indices(void) const
    { return aim_factors_indices; }
  inline size_t get_high_aim_factors_count(void) const
    { return high_aim_factors_count; }
  inline size_t get_low_aim_factors_count(void) const
    { return low_aim_factors_count; }
  inline size_t get_zero_aim_factors_count(void) const
    { return zero_aim_factors_count; }
};
#define CARDTABLE_REQUIREMENTS_DEFINED

// specify the card-table, the direction and the row/column at creation time:
// The first cell is read at creation time.
inline CardWords_DicBot_CardTableRequirements::
CardWords_DicBot_CardTableRequirements (const
                                        class CardWords_DicBot_CardTable *
                                        Card_Table,

                                        CardWords_Direction dir,

                                        size_t row_column)
  : card_table              (Card_Table),
    direction          (dir),
    loc                (Card_Table->get_width() - 1,
                        Card_Table->get_height() - 1),
    changing_coordinate( dir == horizontal ? loc.first : loc.second ),
    aim_word_length    (0),
    aim_factors        (cardwords_max(loc.first, loc.second)),
    needed_cards       (CardWords_Char::noOfChars()),
    aim_factors_indices(cardwords_max(loc.first, loc.second)),
    high_aim_factors_count(0),
    low_aim_factors_count (0),
    zero_aim_factors_count(0),
    first_reached_card_index(INT_MIN)
  
{
  ( (dir == horizontal) ? loc.second : loc.first ) = row_column;  
  needed_cards[0] = 0;
  // prepare for reading first cell:
  ++changing_coordinate;
}
  
// Add a new cell: push it to the front. new_cell needs no argument, it knows
// which cell to add. If so wants to check if this was right, check the return
// value.
inline const CardWords_CardTableLocation &
CardWords_DicBot_CardTableRequirements::new_cell (void)
{
  assert (changing_coordinate != 0);
  --changing_coordinate;
  aim_word_length = 0;
  if (aim_factors.size() != 0) {
    aim_factors.erase(aim_factors.begin(), aim_factors.end());
  }

  if ((*card_table)[loc].is_cell_blocked() == true) {
    // We reached a blocked cell, no word can start here.
    erase(begin(), end());
  }
  bool side_word = card_table->has_neighbour(loc, !direction);
  push_front(CardWords_DicBot_CardTableRequirement((*card_table)[loc],
                                                   side_word,
                                                   direction
                                                   )
             );
  
  // touching another card here?
  if (side_word || front().is_must()) {
    // yes, touching another card.
    first_reached_card_index = 0;
  }
  else {
    // no, not at this cell. Can Words start here?
    if ((*card_table)[loc].is_startPossible(direction)) {
      ++first_reached_card_index;
    } else {
      first_reached_card_index = INT_MIN;
    }
  }
  
  return loc;
}            

// Prepare to be asked things about words with length l:
inline void CardWords_DicBot_CardTableRequirements::new_length (size_t l)
{
  if (aim_word_length != l) {
    aim_word_length = l;
    assert (aim_word_length <= size());
    
    // The combined word factors:
    int word_factor = 1;

    size_t index;
    const_iterator iter;

    aim_factors.erase(aim_factors.begin(), aim_factors.end());
    aim_factors_indices.erase(aim_factors_indices.begin(),
                              aim_factors_indices.end());
    high_aim_factors_count =
      low_aim_factors_count =
      zero_aim_factors_count = 0;
    
    // Copy letterFactors and calculate wordfactor:
    for ((index = 0),(iter = begin());
         index < aim_word_length;
         ++index,++iter) {
      if ((*iter).has_card()) {
        aim_factors.push_back(INT_MAX);
      }
      else {
        aim_factors.push_back((*iter).get_letterFactor());
        word_factor *= (*iter).get_wordFactor();
      }
    }

    // Applicate word factor and check for side words
    for ((index = 0),(iter = begin());
         index < aim_word_length;
         ++index,++iter) {
      if (aim_factors[index] != INT_MAX) {
        aim_factors[index] *= word_factor;
        if ((*iter).has_sideWord()) {
          aim_factors[index] +=
            (*iter).get_letterFactor() * (*iter).get_wordFactor();
        }
        aim_factors_indices.push_back(pair<int,size_t>(aim_factors[index],
                                                       index));
        if (aim_factors[index] > 0) {
          ++high_aim_factors_count;
        } else if (aim_factors[index] < 0) {
          ++low_aim_factors_count;
        } else {
          ++zero_aim_factors_count;
        }
      }
    }
    // transfer complete
    ::sort (aim_factors_indices.begin(), aim_factors_indices.end());
  }
}  

// Return the length from last call to new_length:
inline size_t CardWords_DicBot_CardTableRequirements::get_length (void) const
{
  return aim_word_length;
}

// Check if this word is allowed, as far as known by now. The length parameter
// from the previous method is not relevant for this check, nor is it
// adjusted.
inline bool
CardWords_DicBot_CardTableRequirements::
test_allowed (const CardWords_String &s)
{
  // Specific words should not be tested when *no* words are allowed at all:
  // Allow only words that do not touch other cards when the card-table is
  // empty:
  assert (implication (first_reached_card_index < 0, card_table->is_empty()));
  
  size_t strlen = s.length();
  if (strlen > size() // does not fit on the card-table.

      || first_reached_card_index >= (int)strlen//does not reach other card
      ) {
    return false;
  }
  size_t index;
  const_iterator iter;
  
  vector<size_t>::iterator need_iter = needed_cards.begin();
  vector<size_t>::const_iterator need_end = needed_cards.end();
  while (++need_iter != need_end) { // no need to reset the first member.
    *need_iter = 0U;
  }
  
  for ((index = 0),(iter = begin());
       index < strlen;
       ++index,++iter) {
    if ((*iter).test_allowed(s[index]) == false) {
      return false;
    }
    if (!(*iter).is_must()) {
      ++needed_cards[s[index].internal_no()];
    }
  }
  return true;
}

// Return a reference to a vector of "aim factors". This is needed by the
// best_order_generator:
inline const vector<int>&
CardWords_DicBot_CardTableRequirements::get_aim_factors(void) const
{
  return aim_factors;
}

// Return the maximum word length that could be layed using n cards,
// considering count and positions of the musts:
inline size_t
CardWords_DicBot_CardTableRequirements::max_word_length (size_t n) const
{
  const_iterator iter;
  size_t max_length = n;

  // Should not be called when words can not be layed at all because there is
  // no card they could touch. An exception is when the card-table is empty:
  assert (implication(first_reached_card_index < 0, card_table->is_empty()));

  if (card_table->is_empty()) {
    return cardwords_min(size(), n);
  }
  
  for (iter = begin(); iter != end(); ++iter) {
    if ((*iter).is_must()) {
      // This must will be used.
      ++max_length;
    }
    else {
      // This cell is free, a card must be used:
      if (n-- == 0) { // If we have no more cards than it's over because this
        //^^^            cell is free.
        return max_length;
      }
    }
  }
  // we could not use the remaining n cards, so subtract them:
  return max_length - n;
}

// If a previous check test_allowed returned true, then a call to
// get_needed_cards could make sense: it returns a const vector<size_t> &.
// the index of this vector is the internal number of CardWords_Chars (can be
// accessed by CardWords_Char::internal_no() ) while the contents is the
// number of cards that must be layed with this meaning. Note that the musts
// are not counted here.
inline const vector<size_t> &
CardWords_DicBot_CardTableRequirements::get_needed_cards (void) const
{
  return needed_cards;
}

// Return the minimum word length. This takes into account that a new word
// on the card-table must touch another card that is already on the
// card-table. min_word_length of 0 means: no chance to lay any word at all.
inline size_t
CardWords_DicBot_CardTableRequirements::min_word_length () const
{
  if (size() == 0U) {
    // We are sitting on a blocked cell.
    return 0U;
  }
  return ((first_reached_card_index < 0)
          ? (card_table->is_empty() ? 1U : 0U)
          : (static_cast<size_t>(first_reached_card_index) + 1U)
          );
}

  
#endif
