/*
  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: TrieNode.hh,v 1.3 2000/11/29 02:08:52 falk Exp $
*/

#ifndef TRIE_NODE_HH
#define TRIE_NODE_HH

#include <iostream>
#include <string>

using namespace std;

class TrieNode {
    friend class WordListTrie;
public:
    TrieNode() { }		// to make STL happy
    TrieNode(char letter, bool isTerminal, int firstChildOffset,
	     bool isLastSibling = false)
	: _letter(letter), _firstChildOffset(firstChildOffset),
	  _isTerminal(isTerminal), _isLastSibling(isLastSibling) { }

    char letter() const { return _letter; }
    bool isTerminal() const { return _isTerminal; }
    const TrieNode* firstChild() const {
	if (_firstChildOffset == 0)
	    return NULL;
	else
	    return this + _firstChildOffset;
    }
    // note this depends on all siblings being directly adjacent in memory
    const TrieNode* nextSibling() const {
	if (isLastSibling())
	    return  NULL;
	else
	    return this + 1;
    }
    const TrieNode* child(unsigned char c) const {
	for (const TrieNode* child = firstChild(); child != NULL;
	     child = child->nextSibling()) {
	    if (child->letter() == c)
		return child;
	    else if (child->letter() > c)
		return NULL;
	}
	return NULL;
    }

    bool operator==(TrieNode other) const { return asInt() == other.asInt(); }
    bool operator!=(TrieNode other) const { return asInt() != other.asInt(); }
    bool operator< (TrieNode other) const { return asInt() <  other.asInt(); }
    int asInt() const { return *((int*) this); }

private:
    bool isLastSibling() const { return _isLastSibling; }

    unsigned char _letter	: 8;
    int  _firstChildOffset	: 22;
    bool _isTerminal		: 1;
    bool _isLastSibling		: 1;
}
#if HAVE_ATTRIBUTE_PACKED
    __attribute__ ((packed))
#endif
    ;

#endif