/*
  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: WordListTrie.hh,v 1.1 2000/11/29 01:27:37 falk Exp $
*/

#ifndef WORD_LIST_TRIE_HH
#define WORD_LIST_TRIE_HH

#include <iostream>
#if HAVE_EXT_HASH_MAP
# include <ext/hash_map>
# define HAVE_HASH_MAP 1
#elif HAVE_HASH_MAP
# include <hash_map>
#else
# include <map>
#endif
#include <vector>

#include "TrieNode.hh"

class WordListTrie {
public:
    WordListTrie(istream& nin);
    ~WordListTrie();

    int numNodes() const { return _numNodes; }
    void dump(ostream& out);

private:
#ifdef HAVE_HASH_MAP
    struct NodeVectorHash {
	size_t operator()(const vector<TrieNode>& nodes) const {
	    size_t result = 0;
	    // FIXME is this a good hash on 32-bit architectures?
	    for (int i = 0; i < nodes.size(); ++i)
		result += nodes[i].asInt();
	    return result;
	}
    };

    typedef hash_map<vector<TrieNode>, int, NodeVectorHash> NodeCache;
#else
    typedef map<vector<TrieNode>, int> NodeCache;
#endif

    int buildNode(unsigned int depth);
    int addNodes(const vector<TrieNode>& edges);
    void readNextWord();

    istream& in;
    string _currentWord;
    unsigned int _firstDiff;	// index of first letter where _currentWord
				// differs from the last word
    int _numNodes;
    int _numReservedNodes;
    bool _done;
    NodeCache nodeCache;
    TrieNode* nodes;

};

#endif