tabelahash.h

"tiny" language interpreter written in java

#ifndef _TABELAHASH_H_
#define _TABELAHASH_H_
#include "Lista.h" // @{\it vide Programa~\ref{c_3.3}}@
#include <string>
#include <iostream>
using std::ostream;
using std::cout;
using std::endl;
using std::string;
using cap3_autoreferencia::Lista; // @{\it vide Programa~\ref{c_3.3}}@
namespace cap5_listaenc {
  // @{\it Para utilizar a classe TabelaHash<T> o tipo de dado fornecido no}@ 
  // @{\it lugar do par\^ametro de tipo T deve possuir um construtor de}@ 
  // @{\it c\'opia e os operadores <<, = sobrecarregados.}@  
  template <class T> class TabelaHash {
  private: 
    class Celula {
    friend class TabelaHash<T>;
    friend ostream& operator<< (ostream& out, const Celula& celula) {
      if (celula.item != NULL) out << *(celula.item);
      else out << "NULL";
      return out;
    }    
    private:
      string chave; T *item;
    public: 
      Celula (string chave, const T& item) {
        this->chave = chave; this->item = new T (item);
      }
      Celula (string chave) { 
        this->chave = chave; this->item = NULL; 
      }      
      Celula (const Celula& cel) { *this = cel; }      
      bool operator== (const Celula& celula) const {
        return this->chave == celula.chave;
      }
      bool operator!= (const Celula& celula) const {
        return this->chave != celula.chave;
      }
      const Celula& operator= (const Celula& cel) {     
        if (this != &cel) { // @{\it evita auto-atribui\c{c}\~ao}@
            this->chave = cel.chave;
            this->item = cel.item != NULL ? new T (*(cel.item)) : NULL;
        }
        return *this; // @{\it permite atribui\c{c}\~oes encadeadas}@
      }      
      ~Celula () { if (item != 0) delete item; }
    };    
    int M; // @{\it tamanho da tabela}@
    Lista<Celula> *tabela;
    int *pesos;
  
    int *geraPesos (int n) const;
    int h (string chave, int* pesos) const;
  public:
    TabelaHash (int m, int maxTamChave);    
    T *pesquisa (string chave) const;
    bool insere (string chave, const T& item);
    void retira (string chave);
    void imprime () const;
    ~TabelaHash ();    
  };
  template <class T>    
  int *TabelaHash<T>::geraPesos (int n) const {
    int *p = new int[n];
    for (int i = 0; i < n; i++) p[i] = (rand () % M) + 1;
    return p;
  }
  template <class T>    
  int TabelaHash<T>::h (string chave, int* pesos) const {
    int soma = 0;
    for (unsigned int i = 0; i < chave.length(); i++) 
      soma = soma + ((unsigned char)chave[i]) * pesos[i]; 
    return soma % this->M;
  }  
  template <class T>    
  TabelaHash<T>::TabelaHash (int m, int maxTamChave) {
    this->M = m; this->tabela = new Lista<Celula>[this->M];
    this->pesos = this->geraPesos (maxTamChave);    
  }    
  template <class T>      
  T *TabelaHash<T>::pesquisa (string chave) const {
    int i = this->h (chave, this->pesos);
    if (this->tabela[i].vazia()) return NULL; // @{\it pesquisa sem sucesso}@
    else {
      Celula c (chave);
      Celula *cel = this->tabela[i].pesquisa (c);
      if (cel == NULL) return NULL; // @{\it pesquisa sem sucesso}@
      else return cel->item;
    }
  }  
  template <class T>      
  bool TabelaHash<T>::insere (string chave, const T& item) {    
//    Modificado para poder inserir na mesma posicao sem restricoes
    if (this->pesquisa (chave) == NULL) {
      int i = this->h (chave, this->pesos);
      Celula cel (chave, item);
      this->tabela[i].insere (cel);
      return true;
    }
    else
      return false;
  } 
  template <class T>      
  void TabelaHash<T>::retira (string chave) {
    int i = this->h (chave, this->pesos);
    Celula c (chave);
    Celula *cel = this->tabela[i].retira (c);
    if (cel == NULL) cout << "Registro nao esta presente" << endl;
    else delete cel;    
  }     
  template <class T>      
  void TabelaHash<T>::imprime () const {
    for (int i = 0; i < this->M; i++) {
      if (!this->tabela[i].vazia ()) {
        cout << "Entrada: " << i << endl; 
        this->tabela[i].imprime ();
      }
    }
  }  
  template <class T>      
  TabelaHash<T>::~TabelaHash () {
    delete [] this->tabela;    
    delete [] this->pesos;    
  }
}
#endif