#ifndef _SYMTAB
#define _SYMTAB
/*
 * SymTab interface file
 *     -- the symbol table module
 *     created by CMB 9/04
 *
 * Note: this is a template class.  Because of this the member
 *    function definitions are "in" this header file.  They are actually in
 *    SymTab.i which is #include'd near the end of this file.  This
 *    means this module will not be compiled separately from the client
 *    program (i.e., no SymTab.o).
 *
 *
 * The SymTab class maps between keys, of type Symbol*, and values,
 * whose type you can specify; SymTab can maintain an arbitrary number
 * of levels of nested scopes.
 *
 *   The Symbol objects used as keys must be created by adding strings
 *   to a StringTable.  A SymTab object is only guaranteed to operate
 *   as defined here if all Symbols used as keys (args to "add",
 *   "lookup", or "lookupCurr") are elements of the *same* stringtable
 *   object.  This is because two instances of the same string entered
 *   into the stringtable return the same Symbol object; SymTab takes
 *   advantage of this by using == on the pointers, rather than
 *   comparing any characters when doing a lookup.  See StringTab.h
 *   for more documentation on the StringTab and Symbol classes.
 *
 *   The type of the value to associate with a key is the template
 *   parameter, called ValueType.  Specifying a particular template
 *   instantiation type means we will be storing *pointers* to that type
 *   of object.  For example:
 *
 *     SymTab<int> *intTab = new SymTab<int>(); // maps Symbol* to int*
 *
 *   maps Symbol* to int*, not int, but we give the param type as
 *   "int".  The client creates the value object being pointed to.
 *   See code below that uses ValueType * all over.
 *
 *   The SymTab class allows for the idea of scoping with the 
 *   most-closely-nested rule.  When you do lookup on an id, it will
 *   look outward in scopes.  An instance of an id in the inner scope
 *   hides an instance of the same id in an outer scope.
 *
 *   We have not provided an exitScope function to revert to an outer
 *   scope once we leave an inner scope.  The SymTab design is
 *   somewhat functional, so if you save the version of the SymTab for
 *   the outer scope, you can use it after you are done with (or at
 *   the same time as) a version with an inner scope.  There's
 *   an example of this shown further on.
 *
 *   It will work best if all symbol tables are created on the heap 
 *   (with new).  Since you create new scopes by passing a pointer to
 *   the symtab for the surrounding scope, you want to make sure
 *   that outer symtab was allocated on the heap (or at least outlives
 *   the inner one).
 *
 *   Here we will show the member functions by example.  For a complete,
 *   runnable example, please look at/compile/run: testSymTab.cc
 *
 *   In the examples below we'll use "int" as ValueType.
 *   Assume also we have the following definition:
 *
 *   Symbol *aSymbolPtr;  // would actually have to point to something
 *                        // to use in the statements below.
 *
 *   SymTab<int> symtab = new SymTab<int>();
 *
 *     Creates a new empty table.  It has one scope level only.
 *
 *
 *   symtab->add(aSymbolPtr, new int(5));
 *
 *       Adds the pair <aSymbolPtr, 5> to the symbol table.  Where the
 *       second one is actually a pointer to an int.  If the same
 *       symbol is added twice to the same scope level, it is
 *       undefined which one will be found on lookup operations.
 *       Normally one would call lookupCurr before adding a symbol to make
 *       sure you aren't adding a duplicate key.
 *       The two pointer parameters to "add" may not be NULL
 *       (see earlier discussion about creating Symbol objects).
 *   
 *
 *   int *value= symtab->lookup(aSymbolPtr); 
 *
 *       Looks up the Symbol accessed via aSymbolPtr in the table.  If
 *       it is present, returns its value.  Otherwise returns NULL.
 *       Starts search in the innermost scope level, and if not found,
 *       searches scopes outwards until it's found, or it runs out of
 *       scopes/symbols.
 *
 *
 *  int *value = symtab->lookupCurr(aSymbolPtr)
 *       
 *       Looks up the Symbol accessed via aSymbolPtr only in the
 *       innermost scope of the table.  This is usually used to check
 *       for multiply defined identifiers at the same scope level
 *       (e.g., in the same formal parameter list).
 *
 *
 *  symtab = new SymTab<int>(symtab);
 *       
 *       Creates an inner scope of symtab.  Any new symbols now added
 *       will be added to this inner scope.  But the entries of the
 *       original symtab are still part of the table, and can be found
 *       with "lookup", except ones whose keys are hidden by entries
 *       in the inner scope.  As described earlier, a client can still
 *       use the old symbol table by saving a pointer to it.  For
 *       example, if we create the new one in a different variable:
 
 *  SymTab<int> *inner = new SymTab<int>(symtab);
 *
 *       we can still do lookups on either inner or symtab, depending
 *       on what scope level we want.
 *
 *       This version of the constructor allows us to create an arbitrary
 *       number of nesting levels, by repeatedly calling it (usually calling
 *       "add" between calls to it to "define" symbols in the inner scope).
 *
 *
 *  symtab->dump(cout); 
 *
 *       Mostly for debugging purposes; prints out to the ostream
 *       given all the entries in the symbol table, from the innermost
 *       scope to the outermost scope, denoting scope boundaries.  It
 *       prints one <key, value> pair per line, separated by a space,
 *       using << on each.  You can only call dump if << is defined
 *       for your ValueType.  << is already defined for built-in types
 *       in C++.  For types you define yourself you may need to add a
 *       << operator.
 *
 *
 *  symtab->dumpKeys(cout); 
 *
 *       Like dump, but only prints keys.  This might be useful if
 *       the value is too complicated to print on one line, if
 *       you cannot create a << operation for it, or if you only care
 *       about the keys.
 *
 */


#include <iostream>

#include <map>
using namespace std;

#include "StringTab.h"

template <class ValueType>
class SymTab {
 public:
  SymTab() : outer(NULL) { }; 

  // pass in a SymTab allocated on the heap.
  // e.g., not a local var
  SymTab(SymTab *enclosing) : outer(enclosing) { }; 

  void add(Symbol *, ValueType *);

  ValueType *lookup(Symbol *) const;

  ValueType *lookupCurr(Symbol *) const;

  void dump(ostream &o) const;  // Dumps keys and values;
                                // using << on each

  void dumpKeys(ostream &o) const;  // Dumps keys only, using <<

 protected:
  
  typedef map<Symbol *,ValueType *> Bindings;

  SymTab *outer;
  
  Bindings bindings;

  void dumpHelper(ostream &o) const;

};


#include "SymTab.i"


#endif