/* trie.hh -- make a struct / class to replace perl hashes -- store
   and look up pointers based on strings, sacrifice a little space in
   the pursuit of speed.

   This assumes your strings are composed only of small chars and
   underscores.

   $Log: braintrie.hh,v $
   Revision 1.1  1999/12/27 23:48:46  joanna
   Initial revision

   Revision 1.3  1997/09/10 01:36:43  joanna
   works with robs stuff -- fixed loads more chaining problems,
   new rob libraries.  Interactive rob ringrose, not piped yet.

   Revision 1.1  1997/08/10 18:34:11  joanna
   Initial revision

*/

const int TRIESIZE = (int) 'z' - (int) '_';
const int TRIEOFFSET = (int) '_';

class braintrie {
private:
  Brain * value;      // these are sort of a union, but are also
  braintrie * trie;   // flags for the current state of a branch.
          // value == 0 && trie == 0   -- new init, store here
          // value != 0                -- leaf  (trie should == 0)
          // trie != 0                 -- trie, go deeper (value should == 0)
          // there MAY be a trie and a value if a word is a subset of another.
  // state for finding each element, see below
  int narr;             // which trie element were you in, or -1 for value next
public:
  inline ~braintrie();           //seek and destroy, recursive
  braintrie() :value(0), trie(0) {};
  inline bool add(char * keyst, Brain * elem);
  inline Brain * find  (char * keyst);     // find a key, assume its there
  inline Brain * safefind  (char * keyst); // find and check a key
  // functions for finding each element
  inline void reset ();    // reset the "next" counter, narr
  inline Brain * next ();  // return the "next" element, or 0
  Brain * first() {  reset();  return (next());}  // pix standard...
}; // Class braintrie

inline braintrie::~braintrie() {
  if (trie) {
    for (int ixi = 0; ixi < TRIESIZE; ixi++) {
      trie[ixi].~braintrie();
    }
  delete trie;
  } // if trie
  if (value) {
    delete value;
  }
} // braintrie::~braintrie
  
// this assumes names/keystrings are null terminated
inline bool braintrie::add(char * keyst, Brain * elem) {
  braintrie * mytrie = this;
  for (int inxi = 0; ; inxi++) { // for each character of the keystring
    if (!mytrie->value) {
      if (!mytrie->trie || !keyst[inxi]) {
	mytrie->value = elem;
	return (true);
      } // if room and no trie (or end of keyst), stick it here
      mytrie = &(mytrie->trie[(int)(keyst[inxi]) - TRIEOFFSET]); //iterate
    } // if no value
    else { // a value exists
      if (!strcmp(&(keyst[inxi]), &(mytrie->value->name[inxi]))) {
	cerr << "Two entries for key " << keyst << "!\n";
	return (false); // collision!
      } // if two values need to be here
      else if (mytrie->trie)  {
	// if both trie and value, value must terminate here and is irrelevant
	mytrie = &(mytrie->trie[(int)(keyst[inxi]) - TRIEOFFSET]); //iterate
      } 
      else { // no trie, but a prior value with a different key
	mytrie->trie = new braintrie [TRIESIZE];
	if (!mytrie->trie) { // check if "new" worked
	  cerr << "Out of space in braintrie::add! (key " << keyst << ")\n";
	  ::exit(-1);} // no space! THROWME  ;-)
	if (mytrie->value->name[inxi]) { 
	  mytrie->trie[(int) (mytrie->value->name[inxi]) - TRIEOFFSET].value
	    = mytrie->value;
	  if (! keyst[inxi]) {
	    mytrie->value = elem;
	    return (true);
	  } else { // keyst doesn't term here either
	    if (mytrie->value->name[inxi] == keyst[inxi]) { 
	      mytrie->value = 0;
	      mytrie = &(mytrie->trie[(int)(keyst[inxi] - TRIEOFFSET)]); 
	      //iterate
	    } else { // value and elem not the same at this key index
	      mytrie->value = 0;
	      mytrie->trie[(int) (keyst[inxi]) - TRIEOFFSET].value
		= elem;
	      return (true);
	    }}} // if value doesn't have to be here
	else { // value does have to be here
	  // keyst can't have to, we've already checked for dupes
	  mytrie->trie[(int) (keyst[inxi]) - TRIEOFFSET].value
	    = elem;  // so just insert it
	  return (true);
	} // else value key terminates here
      } // else no trie
    } // else there is a value
  } // for inxi
  cerr << "Impossible situation!  braintree::add\n";
  ::exit (-1); // should never get here; loop exits when end of string reached
} //braintrie::add  


// this checks whether or not you get the right element
inline Brain * braintrie::safefind  (char * keyst) {
  braintrie * mytrie = this;
  for (int ouxi = 0; ; ouxi++) { // for each character of the keystring
    if (!mytrie->trie) {
      if (!mytrie->value ||
	  strcmp(&(mytrie->value->name[ouxi]), &(keyst[ouxi]))) {
	return (0);
      } else {
	return (mytrie->value);
      }
    } // if no trie
    else if (!keyst[ouxi])
      return (mytrie->value);// if value doesn't exist, then it signals failure
    else 
      mytrie = &(mytrie->trie[(int)(keyst[ouxi]) - TRIEOFFSET]);  // iterate
  } // for ouxi
}  // braintrie::safefind


// this one saves a function call, but assumes you know you have a key
inline Brain * braintrie::find  (char * keyst) {
  braintrie * mytrie = this;
  for (int ouxi = 0; ; ouxi++) { // for each character of the keystring
    if (!mytrie->trie) {
      return (mytrie->value);
    } // if no trie
    else if (!keyst[ouxi])
      return (mytrie->value);// if value doesn't exist, then it signals failure
    else 
      mytrie = &(mytrie->trie[(int)(keyst[ouxi]) - TRIEOFFSET]);  // iterate
  } // for ouxi
}  // braintrie::find

inline void braintrie::reset () {
  if (trie) 
    for (int ick = 0; ick < TRIESIZE; ick++) 
      trie[ick].reset();
  narr = -1;
}  // braintrie::reset
  
inline Brain * braintrie::next() {
  if (narr == -1) {
    narr++;
    if (value != (Brain *) 0)
      return (value);
  }
  if (trie == 0)
    return (0);
  Brain *res;
  for (;narr < TRIESIZE; narr++)
    if ((res = trie[narr].next()) != (Brain *) 0)
      return (res);
  return((Brain *) 0);
} // braintrie::next
