///////////////////////////////////////////////////////////////////////
// HashTable.cpp - HashTable Container                               //
// ver 2.5       - Holds nodes with (key, value) pairs.              //
//               - Supports fast insertion and lookup, using a hash  //
//                 function to compute table addresses.              //
//                                                                   //
// Language:       Visual Studio.Net, using standard C++             //
// Platform:       Dell Dimension 8100, Windows 2000, SP 2           //
// Application:    Demonstration of Programming to Interface for     //
//                 CSE687, Spring 2003                               //
// Author:         Jim Fawcett, CST 2-187, Syracuse University       //
//                 (315) 443-3948, jfawcett@twcny.rr.com             //
///////////////////////////////////////////////////////////////////////

#include <iostream>
#include <string>
#include <cmath>
#include <cstdlib>
#include "HashTable.h"
using namespace std;

//----< hash function computes table address from key >----------

unsigned long HashString::operator ()(const std::string& str) const
{
  if(_size == 0)
    throw std::length_error("no table size specified");
  long int origin = static_cast<int>('A');
  long int sum = 0;
  for(size_t i=0, j=0; i<str.length(); ++i, ++j)
  {
    int temp = abs(static_cast<int>(str[i]) - origin) << j;
    if(temp <= 0) j = 0;
    sum += temp;
  }
  return abs(sum) % _size;
}

//----< title function >-----------------------------------------

template <char ch>
string title(const string &t)
{
  string underline(t.length()+2,ch);
  return (string("\n  ") + t + string("\n ") + underline);
}
//----< show contents of HashTable >-----------------------------

template <typename Cont>
void show(Cont &c, bool showLoc=false)
{
  Cont::iterator it = c.begin();
  while(it != c.end())
  {
    if(showLoc)
    {
      cout << "\n  loc = " << it.CurrentIndex();
      cout << " - " << it->show();
    }
    else
      cout << "\n  " << it->show();
    ++it;
  }
  cout << "\n\n";
}
//
//----< sum values in container >--------------------------------
//
//  Demonstrates use of container traits
//    could just as easily summed keys using key_type declaration
//
template <typename Cont>
typename Cont::value_type sum(Cont &c)
{
  Cont::value_type sum = Cont::value_type();
  Cont::iterator it = c.begin();
  while(it != c.end())
  {
    sum += (it->Value());
    ++it;
  }
  return sum;
}
//
//----< test stub >----------------------------------------------

#ifdef TEST_HASHTABLE

//  Define Hash Functor for doubles
class HashDouble : public HashBase<double>
{
public:
    
  // intentionally suppressing warning about truncation
  // That's what I want to happen, to randomize the address

  #pragma warning(disable : 4244)
  unsigned long operator()(const double &d) const
  {
    const unsigned long PRIME = 1000003;
    unsigned long val = PRIME;
    if(fabs(d) > 1e-7) val += d + 1/d;
    return val % _size;
  }
};

#include <fstream>

int main()
{
  cout << title<'='>("Testing HashTable Classes") << endl;

////////////////////////////////////////////////////////////////////////
//  Test inability to create HashTable for different key type without
//  defining a new derived HashKeyType class
//
//    HashTable<int, int, HashString> try(20);  // good, fails to compile
//    HashTable<int, int, Hash> try(20);        // good, fails to compile
//

  ////////////////////////////////////////////////
  cout << title<'-'>("Test HastTable node class");
  ////////////////////////////////////////////////
 
  node<string,int> n1("first",1,0);
  node<string,int> n2("second",2,&n1);
  node<string,int> n3("third",3,&n2);

  // Note: clients of the HashTable don't have to touch nodes 
  // and their addresses

  node<string,int>* pNode = &n3;
  do
  {
    cout << "\n  " << pNode->show();
    pNode = pNode->next();
  } while(pNode != 0);

  cout << "\n\n";

//
  ///////////////////////////////////////////////////
  cout << title<'-'>("Test HashTable, Hash classes");
  ///////////////////////////////////////////////////

  HashTable< string,int,HashString > ht(100);
  ht.Verbose(true);
  cout << "\n  table size = " << ht.Size() << endl;

  ht.insert("arrdvark",1);
  ht.insert("platypus",2);
  ht.insert("sloth",3);
  ht.insert("kangaroo",4);
  ht.insert("kangaroo",-4);
  ht.insert("pig",5);
  ht.insert("horse",6);
  ht.insert("aa$",1);
  ht.insert("%%%",1);
  cout << endl;

  if(ht.Contains("first"))
    cout << "\n  HashTable contains { \"first\"" << ", " << ht.Value("first") << " }";
  else
    cout << "\n  HashTable does not contain \"first\" key";
  if(ht.Contains("sloth"))
    cout << "\n  HashTable contains { \"sloth\"" << ", " << ht.Value("sloth") << " }";
  if(ht.Contains("kangaroo"))
    cout << "\n  HashTable contains { \"kangaroo\"" << ", " << ht.Value("kangaroo") << " }";
  if(ht.Contains("pig"))
    cout << "\n  HashTable contains { \"pig\"" << ", " << ht.Value("pig") << " }";
  cout << "\n\n";

  ///////////////////////////////////////////////
  cout << title<'-'>("larger test of HashString");
  ///////////////////////////////////////////////

  HashTable<string,int,HashString> fromFile(1000);
  ifstream in("hashtable.h");
  while(in.good())
  {
    HashString hash(1000);
    string word;
    in >> word;
    fromFile.insert(word,hash(word));
  }
  in.close();
  show(fromFile,true);

  //////////////////////////////////////////////
  cout << title<'-'>("Testing Table Iteration");
  //////////////////////////////////////////////

  cout << "\n  first element: " << ht.begin()->show();
  HashTable<string,int,HashString>::iterator It = ht.begin();
  cout << "\n  first element: " << It->show();
  cout << "\n  first element: " << (*It).show();
  cout << "\n\n";

//
  //////////////////////////////////////////////////////
  cout << title<'-'>("forward iteration through table");
  //////////////////////////////////////////////////////

  It = ht.begin();
  while(It != ht.end())
  {
    cout << "\n  " << It->show();
    ++It;
  }
  cout << "\n\n";

  ///////////////////////////////////////////////////////
  cout << title<'-'>("backward iteration through table");
  ///////////////////////////////////////////////////////

  It = ht.end();
  do
  {
    --It;
    cout << "\n  " << It->show();
  } while(It != ht.begin());
  cout << "\n\n";

  ////////////////////////////////////////////////////
  cout << title<'-'>("post-increment from beginning");
  ////////////////////////////////////////////////////

  It = ht.begin();
  cout << "\n  " << (It++)->show();
  cout << "\n  " << It->show();
  cout << "\n\n";

  //////////////////////////////////////////////
  cout << title<'-'>("post-decrement from end");
  //////////////////////////////////////////////

  It = --(ht.end());
  cout << "\n  " << (It--)->show();
  cout << "\n  " << It->show();
  cout << "\n\n";

  //////////////////////////////////////////////
  cout << title<'-'>("Testing node assignment");
  //////////////////////////////////////////////

//
  // save copy using copy construction

  HashTable<string,int,HashString> save(ht);

  cout << "\n assigning new nodes to 2nd, 3rd, and 4th nodes:";
  It = ht.begin();
  ++It;
  *It = node<string,int>("tiger",It.CurrentIndex());
  ++It;
  *It = node<string,int>("fox",It.CurrentIndex());
  ++It;
  *It = node<string,int>("moose",It.CurrentIndex());

  cout << "\n setting all values equal to node's current index:";
  HashTable<string,int,HashString>::iterator iter;
  for(iter=ht.begin(); iter!=ht.end(); ++iter)
  {
    *iter = node<string,int>(iter->Key(),iter.CurrentIndex());
    cout << "\n  " << iter->show();
  }
  cout << "\n\n";

  ///////////////////////////////////////////////////
  cout << title<'-'>("Displaying copy of HashTable");
  ///////////////////////////////////////////////////
  
  // copy made above node assignment
  cout << "\n  Note that there is no guarantee that node chains"
       << "\n  stay in original order, but node set is the same.";
  for(iter=save.begin(); iter!=save.end(); ++iter)
  {
    cout << "\n  " << iter->show();
  }
  cout << "\n\n";

  ///////////////////////////////////////////////////
  cout << title<'-'>("Testing HashTable assignment");
  ///////////////////////////////////////////////////

  ht = save;
  cout << "\n  Note that there is no guarantee that node chains"
       << "\n  stay in original order, but node set is the same.";
  for(iter=ht.begin(); iter!=ht.end(); ++iter)
  {
    cout << "\n  " << iter->show();
  }
  cout << "\n\n";


//
  /////////////////////////////////////////////////
  cout << title<'-'>("Testing HashDouble Functor");
  /////////////////////////////////////////////////

  HashTable<double,string,HashDouble> hd(100);
  hd[4.533]  = "first";
  hd[-2.60] = "second";
  hd[35.63] = "third";
  hd[0.333] = "fourth";
  hd[-75e5] = "fifth";
  hd[4.533]  = "sixth";
  hd[-3456] = "seventh";
  hd[63.42] = "eight";
  hd[0.033] = "ninth";
  hd[75e5] = "tenth";
  show(hd,true);
  
  ////////////////////////////////////////////////////
  cout << title<'-'>("Testing sum function");
  ////////////////////////////////////////////////////

  cout << "\n  " << sum(hd) << "\n\n";
}

#endif