/**
 * Hash Table with open addressing, linear probing.
 * http://e...content-available-to-author-only...a.org/wiki/Hash_table#Open_addressing
 *
 * INPUT: rows of the format:
 *   <command> <args>
 * available commands:
 *   insert <string> <int>
 *   remove <string>
 *   get <string>
 *   print
 *   reset <int>
 *
 * Author: Erel Segal  http://t...content-available-to-author-only...s.fm/rentabrain
 * Date: 2010-10-13 
 */

#include <string>
#include <iostream>
using namespace std;

template <typename T,typename K> struct HashTableNode {
  K key;
  T value;
  bool isEmpty, isRemoved;

  HashTableNode<T,K>() { isEmpty=true; isRemoved=false; }
  HashTableNode<T,K>(K newKey, T newValue) { set(newKey,newValue); }

  void set(K newKey, T newValue) {
    key=newKey;
    value=newValue;
    isEmpty=isRemoved=false;
  }

  void remove() {
    isRemoved=true;
  }
};



/**
 * A hash table with open addressing, linear probing.
 * PARAMETERS:
 *   T - type of values stored in hash.
 *   K - type of keys by which the values are stored.
 *   hash - a hash function that gets a key and the table size m, and returns 
 *          an integer in 0...m-1
 */
template <typename T, typename K, int HASH(K, int)> class HashTable {
  HashTableNode<T,K>* myTable;
  int mySize;

  int hashFunction(K key, int baseHashValue, int trialNumber) {
    return (baseHashValue + trialNumber) % mySize;
  }
public:

  void reset(int newSize) { 
    if (myTable) delete[] myTable;
    myTable = new HashTableNode<T,K>[newSize]; 
    mySize = newSize;
  }
  HashTable<T,K,HASH> (int newSize=10): myTable(NULL) { reset(newSize); }
  ~HashTable<T,K,HASH> () { 
     // if (myTable) delete[] myTable; // runtime error!
   }


  /**
   * Look for the given key in the hash.
   * If it exists - return a pointer to the matching value.
   * Otherwise - return NULL.
   */
  T* get (K key) {
    int baseHashValue = HASH(key,mySize);
    for (int trialNumber=0; trialNumber<mySize; ++trialNumber) {
      int hashValue = hashFunction(key, baseHashValue, trialNumber);
      if (myTable[hashValue].isEmpty) {
        return NULL;      // not found
      }
      if (myTable[hashValue].key==key) {
        if (myTable[hashValue].isRemoved) {
          return NULL;    // found but deleted
        } else {
          return &myTable[hashValue].value;
        }
      }
    }
    return NULL; // not found
  }



  /**
   * Insert the given value to the table, under the given key.
   */
  void insert (K key, T value) {
    int baseHashValue = HASH(key,mySize);
    for (int trialNumber=0; trialNumber<mySize; ++trialNumber) {
      int hashValue = hashFunction(key, baseHashValue, trialNumber);
      if (myTable[hashValue].isEmpty || myTable[hashValue].isRemoved || myTable[hashValue].key==key) {
        // found a place to insert:
        myTable[hashValue].set(key,value);
        return;
      }
    }

    // could not find a place to insert:
    throw string("Hash Table overflow");
  }


  /**
   * Look for the given key in the hash.
   * If it exists - remove it.
   * Otherwise - return NULL.
   */
  void remove (K key) {
    int baseHashValue = HASH(key,mySize);
    for (int trialNumber=0; trialNumber<mySize; ++trialNumber) {
      int hashValue = hashFunction(key, baseHashValue, trialNumber);
      if (myTable[hashValue].isEmpty) {
        return;      // not found
      }
      if (myTable[hashValue].key==key) {
        myTable[hashValue].remove();
        return;
      }
    }
  }



  friend ostream& operator<< (ostream& out, const HashTable<T,K,HASH> theHash) {
    out << "{ ";
    for (int i=0; i<theHash.mySize; ++i) {
      if (!theHash.myTable[i].isEmpty && !theHash.myTable[i].isRemoved) {
         out << "  (" << i << ") "
             << theHash.myTable[i].key << " -> "
             << theHash.myTable[i].value << ", ";
      }
    }
    out << " }";
    return out;
  }


};  // template class HashTable<T,K,HASH>



/**
 * calculate a hash value for a string - convert the string to a number modulu the given base
 */
int string2number(string str, int modulu) {
  int num=0;
  for (size_t i=0; i<str.length(); ++i) {
    num = (num*256 + str[i])%modulu;
  }
  return num;
}


int main() {
  HashTable<int, string, &string2number> mapWordToNumber;
  cout << mapWordToNumber << endl;
  string command, word;
  int number;
  for (;;) {
    cin >> command;
    if (cin.eof()) return 0;
    try {
      if (command=="reset") {
        cin >> number;
        cout << command << " " << number << ":" << endl;
        mapWordToNumber.reset(number);
      } else if (command=="insert") {
        cin >> word >> number;
        cout << command << " " << word << " " << number << ":" << endl;
        mapWordToNumber.insert(word,number);
      } else if (command=="remove") {
        cin >> word;
        cout << command << " " << word << ":" << endl;
        mapWordToNumber.remove(word);
      } else if (command=="get") {
        cin >> word;
        cout << command << " " << word << ":";
        int* value = mapWordToNumber.get(word);
        if (value==NULL)
          cout << "doesn't exist!";
        else
          cout << *value;
        cout << endl;
      } else if (command=="print") {
        cout << mapWordToNumber << endl;
      }
    } catch (string error) {
      cout << "ERROR: " << error << endl;
    }
  }
}