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

#ifndef CARDWORDS_CHARCOMBINATION_HH
#define CARDWORDS_CHARCOMBINATION_HH

/* The purpose of class CardWords_CharCombination:
   When it comes to search for possible words to lay with a
   fixed length of characters, we have a certain pool of N characters
   from which to choose and we know how many of them we need (Z).

   We then want to iterate over all possible combinations of Z
   characters chosen from those N characters.

   The class defined in this file will iterate through all possible
   combinations for us. When created (constructor), we have to tell it
   about the pool of possible characters (this is done in the form of
   a const CardWords_String &). It is not necessary to tell how long the
   combinations should be, the CardWords_CharCombinations object will
   calculate all combinations from length 1 to pool.length().  This is
   different from the previous implementation and saves recalculation
   for every single table position.

   After the creation there are CardWords_CharCombination[i].size()
   combinations with length (i+1). They are not CardWords_Strings, but
   only hash_keys of type hashing_type, because thats all we need. they
   are accessible through CardWords_CharCombinations[i][j] whith
   0 <= j <= CardWords_CharCombination[i].size().
   
   If there are many wildcards (many may also be 2 or even 1), it may be that
   calculating possible combinations is an unnecessary overhead.

   Consider there are 5,000 - 10,000 words with length 5,6,7, contained in a
   hash table in as many buckets or less. Consider there are 2 Wildcards,
   each of the wildcard can take N meanings. They can form
   \sum_{n=1}^N{n} or N(N+1)/2 different combinations. For a german charset
   (N=30) that's 465 combinations only for the wildcards. Then, for a
   5-letter-word, we also need 3 from the remaining 5 non-wildcard cards.
   That's another 10 combinations. Together we have about 4,000 combinations
   to check. That's not far from the total number of words we have in the
   dictionary at all.
   It might be better, not to calculate combinations (and store them!), but to
   search every word in the dictionary and test if it fits.

   At the moment, I am uncertain where to place the border, at 2 or 3
   wildcards, or even 1? A generic aproach seems to be the best to me now.
   Nothing of this is implemented yet.
*/
#include "cardwords_string.hh"
#include "cardwords_exceptions.hh"
#include <vector>
#include <assert.h>
#include <set>
namespace CardWords {

template <class hashing_type>
class CharCombination : public vector< vector< hashing_type > >
{
public:
  // This constructor is for Cards without wildcards:
  CharCombination ( const String & possibleChars);

  // This constructor is for Cards with wildcards:
  CharCombination ( const String & possibleChars,
                              //                           w/o wildcards
                              
                              size_t no_of_wildcards);
private:
  // combinate is for initialisation and directly called from the constructor.
  // It is a recursive (and cascading) function and needs to know about how
  // deep the recursion has gone already. This is done in this way:
  // 
  // combinate gets a param size_t length_so_far. That's the length of the
  // combination that the calling function generated. It is at the same time
  // the index of the parent class vector where this instance has to store its
  // calculated combinations of length length_so_far+1. Another param is
  // size_t next_usable_index. This is the index of the first Char
  // in sorted_pool that this instance of combinate is allowed to use.
  void
  combinate (const hashing_type   & combination_so_far,
             size_t                 length_so_far,
             size_t                 next_usable_index,
             const String & sorted_pool);

  // the number of available chars:
  const size_t noAvail;
};
}
#include "cardwords_charcombination.icc"
#endif