/*
  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.cc,v 1.3 2000/11/29 01:59:10 falk Exp $
*/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "WordListTrie.hh"

WordListTrie::WordListTrie(istream& nin) : in(nin), _done(false) {
    _numReservedNodes = 65536;
    nodes = (TrieNode*) calloc(_numReservedNodes, sizeof(TrieNode));
    if (nodes == NULL) {
	perror("Can't allocate TrieNode memory");
	abort();
    }
    _numNodes = 0;
    nodes[_numNodes++] = TrieNode('*', false, 1, true);

    readNextWord();
    nodes[0]._firstChildOffset = buildNode(0);

    // relativate child indices
    for (int i = 0; i < _numNodes; ++i) {
	if (nodes[i]._firstChildOffset != 0)
	    nodes[i]._firstChildOffset -= i;
    }
}

WordListTrie::~WordListTrie() {
    free(nodes);
}

int WordListTrie::buildNode(unsigned int depth) { // returns index of first child
    assert(!_done);
    if (_currentWord.length() == depth) {
	// End of word reached. If the next word isn't a continuation of
	// the current one, then we've reached the bottom of the recursion
	// tree.
	readNextWord();
	if (_firstDiff < depth)
	    return 0;
    }

    vector<TrieNode> edges;	// FIXME find good name

    // Loop through all the sub-nodes until a word is read which can't be
    // reached via this node.
    do {
	char letter = _currentWord[depth];
	bool isTerminal = _currentWord.length() - 1 == depth;
	edges.push_back(TrieNode(letter, isTerminal, buildNode(depth + 1)));
    } while (_firstDiff == depth && !_done);

    if (!_done)
	assert(_firstDiff < depth);

    edges.back()._isLastSibling = true;

    return addNodes(edges);
}

int WordListTrie::addNodes(const vector<TrieNode>& edges) {
    NodeCache::const_iterator n = nodeCache.find(edges);
    if (n != nodeCache.end())
	return n->second;
	
    while (_numNodes + edges.size() > _numReservedNodes) {
	_numReservedNodes *= 2;
	nodes = (TrieNode*) realloc(nodes, _numReservedNodes * sizeof(TrieNode));
    }

    int firstFreeIndex = _numNodes;
    for (unsigned int i = 0; i < edges.size(); ++i)
	nodes[_numNodes + i] = edges[i];
	
    _numNodes += edges.size();

    nodeCache[edges] = firstFreeIndex;

    return firstFreeIndex;
}

void WordListTrie::readNextWord() {
    string nextWord;
    do {
	getline(in, nextWord);
	if (!in) {
	    _done = true;

	    return;
	}
    } while (nextWord.length() == 0); // skip blank lines
    assert(nextWord.length() > 1);
    assert(nextWord > _currentWord);
    int numCommonLetters = 0;
    int l = min(_currentWord.length(), nextWord.length());
    while (_currentWord[numCommonLetters] == nextWord[numCommonLetters]
	   && numCommonLetters < l)
	++numCommonLetters;
    _firstDiff = numCommonLetters;
    _currentWord = nextWord;
}

void WordListTrie::dump(ostream& out) {
    out.write((char*) &_numNodes, sizeof(int));
    out.write((char*) nodes, _numNodes * sizeof(TrieNode));
}