/* This file is part of cardwords
   (c) 1998 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_cardselectioncontents.hh

/* This file defines the class CardWords_DicBot_CardSelectionContents.
   The purpose of this class is to scan a CardWords_CardSelection and
   to provide easy access to what is contained in the card selection.

   After initialisation, the following questions should be answered
   or helped to be answered by CardWords_DicBot_CardSelectionContents:

   - How many wild cards are there?
   - How many cards with face value x are there?
   - A letter x can be represented by which cards? (including wildcards);
   - What hash values have the length-n substrings?
   - Can word w be layed using the cards and the musts m?
   - What is the best order to arrange the cards in?

   A bit to the organisation:
   The Cards are stored in an array. Cards with same face value are stored
   consecutively (continuously?), the cards with lowest scores first.
   the Cards can be referenced by their index in that array.
*/

#ifndef CARDWORDS_CARDSELECTIONCONTENTS_HH
#define CARDWORDS_CARDSELECTIONCONTENTS_HH

#include "cardwords_cardselection.hh"
#include "cardwords_string.hh"
#include "cardwords_exceptions.hh"
#include "cardwords_charcombination.hh"
#include "cardwords_fasthashkey.hh"
#include <map>

class CardWords_DicBot_CardSelectionContents {
public:
  CardWords_DicBot_CardSelectionContents(const CardWords_CardSelection &);
  ~CardWords_DicBot_CardSelectionContents();
  
  // Return the number of contained wildcards:
  size_t get_no_of_wildcards(void) const;

  // Return the number of cards with face value x:
  size_t get_no_of(CardWords_Char x) const;

  // Return the total number of contained cards:
  size_t get_no_of_cards(void) const;
  
  // Return the number of cards with face value x and score s:
  size_t get_no_of(CardWords_Char x, int s) const;

  // Return the score of the card with face value x with the highest score:
  int get_high_score_of(CardWords_Char x) const
    ; // Throws CardWords_XOutOfRange

  // Return the score of the card with face value x with the lowest score:
  int get_low_score_of(CardWords_Char x) const
    ; // Throws CardWords_XOutOfRange

  // Return the index of the first card with face value x (The lowscore one):
  size_t get_first_index_of(CardWords_Char x) const
    ; // Throws CardWords_XOutOfRange

  // Return the index of the last card with face value x (The highscore one):
  size_t get_last_index_of(CardWords_Char x) const
    ; // Throws CardWords_XOutOfRange

  // Return the index of the first card with face value x and the number of
  // cards with face value x in a pair:
  pair<size_t /*first_index*/, size_t /*no*/>
  get_index_and_no_of(CardWords_Char x) const; // Throws CardWords_XOutOfRange
  
  // Return the index of the first card whith face value x and score s and the
  // number of such cards:
  // Note: This does *not* throw CardWords_XOutOfRange if there is no card
  // with that index. If the second member of the pair, the number of
  // occurrences, is 0, than the first member(index) has _no_ _meaning_!
  pair<size_t /*first_index*/, size_t /*no*/>
  get_index_and_no_of(CardWords_Char x, int s) const;

  // Return a const reference to the i'th card:
  const CardWords_CardDescription & operator [] (size_t i) const
    ;  // Throws CardWords_XOutOfRange

  // Return the face value of the i'th card:
  CardWords_Char get_face_value_of(size_t i) const
    ;// Throws CardWords_XOutOfRange

  // Return the points of the i'th card:
  int get_points_of(size_t i) const;// Throws CardWords_XOutOfRange
  
  // Return information if hash_keys for possible substrings have been
  // created.
  // This will be false if there are too many wild cards in the selection. The
  // number up to which number of wildcards
  // CardWords_DicBot_CardSelectionContents creates hash_keys must be set
  // using the static member function set_max_hash_wilds(size_t).
  bool have_hash_keys (void) const;

  // That mentioned static member function:
  static void set_max_hash_wilds(size_t);
  
  // return a pointer to the charcombination:
  CardWords_CharCombination<CardWords_FastHashKey> *
  get_charcomb (void);
  const CardWords_CharCombination<CardWords_FastHashKey> *
  get_charcomb (void) const;

  // Tests if there are enough cards for our word. Returns the number of not
  // necessarily needed wildcards, that is, a value >= 0, if there are enough
  // cards. returns -1  or less if there are not enough cards.
  // needed_cards can be the return value from
  // CardWords_DicBot_CardTableRequirements::get_needed_cards().
  int remaining_wildcards (const vector<size_t> & needed_cards) const;

private:
  // The number of existing different CardWords_Chars:
  size_t noOfChars;

  // The arrays in which the info about the cards is stored:
  // face_value and points are redundant, their info is already in card_desc.
  vector<CardWords_CardDescription> card_desc;
  vector<CardWords_Char> face_value;
  vector<int> points;
  

  // A vector with a size_t for every possible CardWords_Char. Index is the
  // internal number of that CardWords_Char. Contents says how many cards with
  // that face value we have.
  vector<size_t> card_count_i;

  // A vector. Index of this vector is, as above, the internal number of a
  // CardWords_Char. The contents of that field gives the card_desc-index of
  // the first occurence of a card with this CardWords_Char as face value. It
  // is of course only valid if the corresponding card_count_i entry is > 0.
  vector<size_t> index_i;

  // A vector of maps: Index of this vector is, as above, the internal number
  // of a CardWords_Char. The contents are maps: The key of the maps is an
  // int:
  // the score of at least one card, the data_type of the maps is
  // pair<size_t,size_t> with the first size_t being the first index where
  // a card with this face value and score occurs, the second size_t being
  // the number of cards with this face value and score.
  vector<map<int /*points*/, pair<size_t/*1stIndex*/,size_t/*no*/> > > maps_i;
  
  // A pointer to the charcombination if we choose to create hash values:
  CardWords_CharCombination<CardWords_FastHashKey> * charcomb;

  // A sorted string of CardWords_Chars:
  CardWords_String sorted_str;
  
  // The number of wildcards up to which we will create those hash values:
  static size_t max_hash_wilds;
};

inline
CardWords_DicBot_CardSelectionContents::
~CardWords_DicBot_CardSelectionContents()
{
  delete charcomb;
}

// Return the number of contained wildcards:
inline size_t
CardWords_DicBot_CardSelectionContents::get_no_of_wildcards(void) const
{
  return card_count_i [ CardWords_Char::blanko.internal_no() ];
}

// Return the number of cards with face value x:
inline size_t
CardWords_DicBot_CardSelectionContents::get_no_of(CardWords_Char x) const
{
  return card_count_i [ x.internal_no() ];
}

// Return the total number of contained cards:
inline size_t
CardWords_DicBot_CardSelectionContents::get_no_of_cards(void) const
{
  return card_desc.size();
}

// Return the number of cards with face value x and score s:
inline size_t
CardWords_DicBot_CardSelectionContents::
get_no_of(CardWords_Char x, int s) const
{
  map<int /*points*/, pair<size_t/*1stIndex*/,size_t/*no*/> >::
    const_iterator i;
  
  i = maps_i [ x.internal_no() ].find( s );
  if (i == maps_i[x.internal_no()].end()) {
    return 0;
    
  }
  return (*i).second.second;
}

// Return the index of the first card whith face value x and score s and the
// number of such cards:
inline
pair<size_t /*first_index*/, size_t /*no*/>
CardWords_DicBot_CardSelectionContents::get_index_and_no_of(CardWords_Char x,
                                                            int s) const
  // Throws CardWords_XOutOfRange
{
  map<int /*points*/, pair<size_t/*1stIndex*/,size_t/*no*/> >::
    const_iterator i;
  
  i = maps_i [ x.internal_no() ].find(s);
  if (i == maps_i[x.internal_no()].end()) {
    throw CardWords_XOutOfRange(gettext("CardWords_DicBot_CardSelection"\
                                        "Contents: "\
                                        "get_index_and_no_of: "\
                                        "No such CardWords_Char/"\
                                        "points pair"));
  }
  return (*i).second;
}
  

         
// Return the score of the card with face value x with the highest score:
inline int
CardWords_DicBot_CardSelectionContents::
get_high_score_of(CardWords_Char x) const
  // Throws CardWords_XOutOfRange
{
  if (card_count_i [ x.internal_no() ] == 0) {
    throw CardWords_XOutOfRange(gettext("CardWords_DicBot_CardSelection"\
                                        "Contents: "\
                                        "get_high_score: "\
                                        "No such CardWords_Char"));
  }

  return points [ index_i [ x.internal_no() ]
                + card_count_i [ x.internal_no() ]
                    - 1 ];
}

// Return the score of the card with face value x with the lowest score:
inline int
CardWords_DicBot_CardSelectionContents::
get_low_score_of(CardWords_Char x) const
  // Throws CardWords_XOutOfRange
{
  if (card_count_i [ x.internal_no() ] == 0) {
    throw CardWords_XOutOfRange(gettext("CardWords_DicBot_CardSelection"\
                                        "Contents: "\
                                        "get_low_score: "\
                                        "No such CardWords_Char"));
  }
  return points [ index_i [ x.internal_no() ] ];
}

// Return the index of the first card with face value x (The lowscore one):
inline size_t
CardWords_DicBot_CardSelectionContents::
get_first_index_of(CardWords_Char x) const
  // Throws CardWords_XOutOfRange
{
  if (card_count_i [ x.internal_no() ] == 0) {
    throw CardWords_XOutOfRange(gettext("CardWords_DicBot_CardSelection"\
                                        "Contents: "\
                                        "get_first_index: "\
                                        "No such CardWords_Char"));
  }
  return index_i [ x.internal_no() ];
}

// Return the index of the last card with face value x (The highscore one):
inline size_t
CardWords_DicBot_CardSelectionContents::
get_last_index_of(CardWords_Char x) const
  // Throws CardWords_XOutOfRange
{
  if (card_count_i [ x.internal_no() ] == 0) {
    throw CardWords_XOutOfRange(gettext("CardWords_DicBot_CardSelection"\
                                        "Contents: "\
                                        "get_last_index: "\
                                        "No such CardWords_Char"));
  }
  return index_i [ x.internal_no() ] + card_count_i [ x.internal_no() ] - 1;
}

// Return the index of the first card with face value x and the number of
// cards with face value x in a pair:
inline pair<size_t /*first_index*/, size_t /*no*/>
CardWords_DicBot_CardSelectionContents::
get_index_and_no_of(CardWords_Char x) const
{
  if (card_count_i [ x.internal_no() ] == 0) {
    return pair<size_t /*first_index*/, size_t /*no*/>(UINT_MAX, 0U);
  }
  return pair<size_t /*first_index*/, size_t /*no*/>
    (index_i [ x.internal_no() ], card_count_i [ x.internal_no() ] );
  
}

// Return information if hash_keys for possible substrings have been created.
// This will be false if there are too many wild cards in the selection. The
// number up to which number of wildcards
// CardWords_DicBot_CardSelectionContents creates hash_keys must be set using
// the static member function set_max_hash_wilds(size_t).
inline bool CardWords_DicBot_CardSelectionContents::
have_hash_keys (void) const
{
  return charcomb != 0;
}

inline CardWords_CharCombination<CardWords_FastHashKey> *
CardWords_DicBot_CardSelectionContents::get_charcomb (void)
{
  return charcomb;
}

inline const CardWords_CharCombination<CardWords_FastHashKey> *
CardWords_DicBot_CardSelectionContents::get_charcomb (void) const
{
  return charcomb;
}

// Return a const reference to the n'th card:
inline const CardWords_CardDescription &
CardWords_DicBot_CardSelectionContents::operator [] (size_t i) const
  // Throws CardWords_XOutOfRange
{
  if (i >= card_desc.size()) {
    throw CardWords_XOutOfRange (gettext("CardWords_DicBot_CardSelection"\
                                         "Contents: "\
                                         "operator []: invalid argument"));
  }
  return card_desc[i];
}

// Return the face value of the i'th card:
inline CardWords_Char
CardWords_DicBot_CardSelectionContents::get_face_value_of(size_t i) const
  // Throws CardWords_XOutOfRange
{
  if (i >= card_desc.size()) {
    throw CardWords_XOutOfRange (gettext("CardWords_DicBot_CardSelection"\
                                         "Contents: "\
                                         "get_face_value_of: "\
                                         "invalid argument"));
  }
  return face_value[i];
}

// Return the points of the i'th card:
inline int CardWords_DicBot_CardSelectionContents::
get_points_of(size_t i) const
  // Throws CardWords_XOutOfRange
{
  if (i >= card_desc.size()) {
    throw CardWords_XOutOfRange (gettext("CardWords_DicBot_CardSelection"\
                                         "Contents: "\
                                         "get_points_of: invalid argument"));
  }
  return points[i];
}

// Tests if there are enough cards for our word. Returns the number of not
// necessarily needed wildcards, that is, a value >= 0, if there are enough
// cards. returns -1  or less if there are not enough cards.
// needed_cards can be the return value from
// CardWords_DicBot_CardTableRequirements::get_needed_cards().
inline int
CardWords_DicBot_CardSelectionContents::
remaining_wildcards (const vector<size_t> & needed_cards) const
{
  assert (needed_cards.size() == noOfChars);
  int    available_wildcards = get_no_of_wildcards();
  size_t index;
  for (index = 0; index < noOfChars; ++index) {
    if (needed_cards[index] > card_count_i[index]) {
      if ( (available_wildcards -= needed_cards[index] - card_count_i[index])
           < 0) {
        return -1;
      }
    }
  }
  return available_wildcards;
}







/* The file originally began here: */
#if 0
/* This file defines the class CardWords_DicBot_CardSelectionContents.
   The purpose of this class is to scan a CardWords_CardSelection and
   to provide some sort of table of contents of what is in this
   selection.
   
   This class is a map(key CardWords_Char face value) of maps(key
   int score) of pairs of {size_t number of occurrences of that
   card} and {const CardWords_CardDesc *) a pointer to an instance
   of such a card.

   It will be used in CardWords_DicBot_BestOrderGenerator and in
   CardWords_DicBot_BestMoveGenerator.
*/

#ifndef CARDWORDS_DICBOT_CARDSELECTIONCONTENTS_HH
#define CARDWORDS_DICBOT_CARDSELECTIONCONTENTS_HH

#include <map>
#include "cardwords_cardselection.hh"
#include "cardwords_wordkey.hh"
#include <assert.h>

class CardWords_DicBot_CardCounts {
private:
  // number of occurences of cards with this face value and score:
  size_t nrOfOccurrences; 

  // How often is this used by CardWords_DicBot_BestOrderGenerator:
  size_t nrOfUsage;
  
public:
  CardWords_DicBot_CardCounts():nrOfOccurrences(1),nrOfUsage(0){}

  void oneMore(void) {++nrOfOccurrences;}
  void oneLess(void) {assert(nrOfOccurrences > nrOfUsage);--nrOfOccurrences;}
  
  void reset_usage(void) {nrOfUsage = 0;}
  bool want_to_use(void) {
    if (nrOfOccurrences > nrOfUsage) {
      ++nrOfUsage;
      return true;
    }
    return false;}
  void finished_usage(void) {
    assert (nrOfUsage > 0);
    --nrOfUsage;
  }
  size_t total_nr(void) {return nrOfOccurrences;}
  size_t avail_nr(void) {return nrOfOccurrences - nrOfUsage;}
};

class CardWords_DicBot_ScoreMap :
  private map <int, // Score of the cards stored here.
               CardWords_DicBot_CardCounts // The counts of their
              >                          // occurrence and usage.
{
private:
  size_t nrOfOccurrences;
  size_t nrOfUsage;

public:
  CardWords_DicBot_ScoreMap() :nrOfOccurrences(0),nrOfUsage(0){}
  CardWords_DicBot_ScoreMap(int score) :nrOfOccurrences(1),nrOfUsage(0)
    {insert(value_type(score,CardWords_DicBot_CardCounts()));}

  void oneMore(int score) {
    iterator i = find(score);
    if (i == end())
      insert(value_type(score,CardWords_DicBot_CardCounts()));
    else
      (*i).second.oneMore();
    ++nrOfOccurrences;
  }
  
  void oneLess(void) {
    iterator i = find(score);
    assert (i != end());
    (*i).second.oneLess();
    --nrOfOccurrences;
  }
  
  void reset_usage(void) {
    for (iterator i = begin(); i != end(); ++i)
      (*i).second.reset_usage();
    nrOfUsage = 0;
  }
  bool want_to_use(int score) {
    iterator i = find(score);
    assert (i != end());
    if ((*i).second.want_to_use() == true) {
      ++nrOfUsage;
      return true;
    }
    return false;
  }
  void finished_usage(int score) {
    iterator i = find(score);
    assert (i != end());
    --nrOfUsage;
  }
  size_t total_nr(void) {return nrOfOccurrences;}
  size_t avail_nr(void) {return nrOfOccurrences - nrOfUsage;}

  size_t total_nr(int score) {
    iterator i = find(score);
    assert (i != end());
    return (*i).second.total_nr();
  }
  size_t avail_nr(int score) {
    iterator i = find(score);
    assert (i != end());
    return (*i).second.avail_nr();
  }
};

class CardWords_DicBot_FaceValueMap :
  private map < CardWords_Char //face value of cards stored here
               ,
               CardWords_DicBot_ScoreMap
             >
{
****************************
  
  
};
class CardWords_DicBot_CardSelectionContents
  : public map < CardWords_Char //face value of cards stored here
                 ,
                 map < int // score of the cards stored here
                       ,
                       CardWords_DicBot_ConcreteCardInfo
                     >
               >
{
public:
  size_t          nrOfWildcards;
  CardWords_WordKey availableChars;

  //  symbolic accessing functions:
  
  data_type *
  sameFaceValueMap (iterator);

  const data_type *
  sameFaceValueMap (const_iterator) const;

  data_type *
  sameFaceValueMap (CardWords_Char face_value);

  const data_type *
  sameFaceValueMap (CardWords_Char face_value) const;

  size_t get_nrOfOccurrences (CardWords_Char face_value) const;
  size_t get_nrOfOccurrences (CardWords_Char face_value, int score) const;

  const CardWords_CardDescription *
  description (CardWords_Char face_value, int score) const;

  void release_card (CardWords_Char face_value, int score);
  void release_card (const CardWords_CardDescription *d)
    {assert(d);release_card(d->get_faceValue(), d->get_points());};

  bool try_occupy (CardWords_Char face_value, int score);
  bool try_occupy (const CardWords_CardDescription *d)
    {assert(d);return try_occupy(d->get_faceValue(), d->get_points());};
  
  CardWords_DicBot_ConcreteCardInfo *info(CardWords_Char face_value,
                                          int score);

  const CardWords_DicBot_ConcreteCardInfo * info
  (CardWords_Char face_value, int score) const;

  CardWords_DicBot_CardSelectionContents (const CardWords_CardSelection &);
#endif
#endif
#endif
