Index_Hash_Table.h

#ifndef QNANO_NEW_INDEX_HASH_TABLE_DEFINED_H
#define QNANO_NEW_INDEX_HASH_TABLE_DEFINED_H

#include <vector>
#include <iostream>
#include <cstdlib>

template <class Key_Type> class Index_Hash_Table_Node {
public:
  Key_Type key;
  int next;
 
  Index_Hash_Table_Node(const Key_Type &key_, int next_=-1) :key(key_), next(next_){
  }

};

template <class Key_Type> class Index_Hash_Table {
public:
  std::vector<Index_Hash_Table_Node<Key_Type> > nodes;
  std::vector<int> start_table;

  size_t (*hash_fct)(const Key_Type &key);
  
  void clear(){
    nodes.clear();
    for(size_t i=0; i<start_table.size(); i++)start_table[i]=-1;
  }
  size_t size()const{return nodes.size();}

  inline size_t get_start_index(const Key_Type &key, size_t stsize)const{
    size_t hash=hash_fct(key);
    return hash%stsize;
  }
  inline size_t get_start_index(const Key_Type &key)const{
    return get_start_index(key,start_table.size());
  }

  int get_index(const Key_Type &key)const{
    int index=start_table[get_start_index(key)];
    while(index>=0){
      if(nodes[index].key==key)return index;
      index=nodes[index].next;
    }
    return -1;
  }
  int get_index_check(const Key_Type &key)const{
    int i=get_index(key);
    if(i<0){
      std::cerr<<"Index_Hash_Table::get_index_check: key "<<key<<"not found!"<<std::endl;
      exit(1);
    }
  }

  const Key_Type & get_key(int index)const{
    if(index<0 || index >=(int)nodes.size()){
      std::cerr<<"Index_Hash_Table::get_key: index out of bound: "<<index<<" vs. [0,"<<nodes.size()<<"["<<std::endl;
      exit(1);
    }
    return nodes[index].key;
  }


  void resize_start_table(size_t size){
    start_table.resize(size);
    for(size_t i=0; i<size; i++){
      start_table[i]=-1;
    }

    for(size_t i=0; i<nodes.size(); i++){
      nodes[i].next=-1;
    }


    for(size_t n=0; n<nodes.size(); n++){
      size_t start_index=get_start_index(nodes[n].key);
      int index=start_table[start_index];

      //need to make an entry in the start_table?
      if(index<0){
        start_table[start_index]=n;
        continue;
      }
 
      while(true){
        if(nodes[index].key==nodes[n].key)break; //already exists. Don't do anything
        int next_index=nodes[index].next;
        if(next_index<0){//reached the end of the linked list: append
          nodes[index].next=n;
          break;
        }
        index=next_index;
      }
    }

//    std::cout<<"Index_Hash_Table::resize(): -> "<<size<<std::endl;
  }



  void add(const Key_Type &key){
    if(nodes.size()>=1.5*start_table.size())resize_start_table(start_table.size()*2);

    size_t start_index=get_start_index(key);
    int index=start_table[start_index];

    //need to make an entry in the start_table?
    if(index<0){
      size_t old_nodes_size=nodes.size();
      nodes.push_back(Index_Hash_Table_Node<Key_Type>(key));
      start_table[start_index]=old_nodes_size;
      return;
    }


    while(true){
      if(nodes[index].key==key)return; //already exists. Don't do anything
      int next_index=nodes[index].next;
      if(next_index<0){//reached the end of the linked list: append
        size_t old_nodes_size=nodes.size();
        nodes.push_back(Index_Hash_Table_Node<Key_Type>(key));
        nodes[index].next=old_nodes_size;
        return;
      }
      index=next_index;
    }

  }

  void print_start_table(std::ostream &os=std::cout)const{
    os<<"Start Table:"<<std::endl;
    for(size_t i=0; i<start_table.size(); i++){
      os<<i<<": "<<start_table[i]<<std::endl;
    }
  }
  void print_nodes(std::ostream &os=std::cout)const{
    os<<"Nodes:"<<std::endl;
    for(size_t i=0; i<nodes.size(); i++){
      os<<i<<": "<<nodes[i].key<<": "<<nodes[i].next<<std::endl;
    }
  }
  void print(std::ostream &os=std::cout)const{
    std::cout<<"start_table.size(): "<<start_table.size()<<std::endl;
    std::cout<<"nodes.size(): "<<nodes.size()<<std::endl;
    print_start_table(os);
    print_nodes(os);
  }


  Index_Hash_Table(const Index_Hash_Table &other) 
    :  nodes(other.nodes), start_table(other.start_table), 
       hash_fct(other.hash_fct){
  }

  Index_Hash_Table(size_t (*hash_fct_)(const Key_Type &), size_t start_table_size=128) 
    :  hash_fct(hash_fct_) {

    start_table.resize(start_table_size);
    for(size_t i=0; i<start_table_size; i++){
      start_table[i]=-1;
    }
  }


};

#endif