Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef HASHMAPA_H
- #define HASHMAPA_H
- #include "Mapa.h"
- template <typename TipKljuca, typename TipVrijednosti>
- class HashMapa : public Mapa<TipKljuca, TipVrijednosti> {
- struct Kljuc {
- TipKljuca k;
- bool obrisan;
- };
- Kljuc **kljucevi;
- TipVrijednosti **vrijednosti;
- int kapacitet;
- int brojEl;
- unsigned int (*hash)(TipKljuca kljuc, unsigned int max);
- void realociraj() {
- int stari_kapacitet=kapacitet;
- kapacitet+=1000;
- Kljuc **noviK = new Kljuc*[kapacitet];
- TipVrijednosti **noveV = new TipVrijednosti*[kapacitet];
- for(int i=0; i<kapacitet; i++) { noviK[i]=0; noveV[i]=0; }
- for(int i=0; i<stari_kapacitet; i++) {
- if(kljucevi[i]!=0) {
- int hes=hash(kljucevi[i]->k,kapacitet);
- if(noviK[hes]==0) {
- noviK[hes]=new Kljuc;
- *noviK[hes]=*kljucevi[i];
- if(vrijednosti[i]!=0) { noveV[hes]=new TipVrijednosti; *noveV[hes]=*vrijednosti[i]; }
- }
- else {
- int j(hes);
- while(noviK[j]!=0) {
- j++;
- if(j==kapacitet) j=0;
- }
- noviK[j]=new Kljuc;
- *noviK[j]=*kljucevi[i];
- if(vrijednosti[i]!=0) { noveV[j]=new TipVrijednosti; *noveV[hes]=*vrijednosti[i]; }
- }
- delete kljucevi[i];
- if(vrijednosti[i]!=0) delete vrijednosti[i];
- }
- }
- delete[] kljucevi;
- delete[] vrijednosti;
- kljucevi=noviK;
- vrijednosti=noveV;
- }
- public:
- HashMapa() : kljucevi(new Kljuc*[1000]), vrijednosti(new TipVrijednosti*[1000]), kapacitet(1000), brojEl(0), hash(0) {
- for(int i=0; i<1000; i++) {
- kljucevi[i]=0;
- vrijednosti[i]=0;
- }
- }
- ~HashMapa() {
- obrisi();
- delete[] kljucevi;
- delete[] vrijednosti;
- }
- HashMapa(const HashMapa &n) {
- kapacitet=n.kapacitet; brojEl=n.brojEl;
- kljucevi=new Kljuc*[kapacitet]; vrijednosti=new TipVrijednosti*[kapacitet];
- for(int i=0; i<kapacitet; i++) {
- if(n.kljucevi[i]!=0) {
- kljucevi[i]=new Kljuc;
- *kljucevi[i]=*n.kljucevi[i];
- if(kljucevi[i]->obrisan==false) { vrijednosti[i]=new TipVrijednosti; *vrijednosti[i]=*n.vrijednosti[i]; }
- }
- else { vrijednosti[i]=0; kljucevi[i]=0; }
- }
- }
- HashMapa &operator =(const HashMapa &n) {
- obrisi();
- delete[] kljucevi; delete[] vrijednosti;
- kapacitet=n.kapacitet; brojEl=n.brojEl;
- kljucevi=new Kljuc*[kapacitet]; vrijednosti=new TipVrijednosti*[kapacitet];
- for(int i=0; i<kapacitet; i++) {
- if(n.kljucevi[i]!=0) {
- kljucevi[i]=new Kljuc;
- *kljucevi[i]=*n.kljucevi[i];
- if(kljucevi[i]->obrisan==false) { vrijednosti[i]=new TipVrijednosti; *vrijednosti[i]=*n.vrijednosti[i]; }
- *vrijednosti[i]=*n.vrijednosti[i];
- }
- else { vrijednosti[i]=0; kljucevi[i]=0; }
- }
- }
- TipVrijednosti operator [](TipKljuca kljuc) const {
- if(hash==0) throw "Niste definirali hash funkciju!";
- unsigned int hes=hash(kljuc, kapacitet);
- if(kljucevi[hes]!=0) return *vrijednosti[hes];
- }
- TipVrijednosti &operator [](TipKljuca kljuc) {
- if(hash==0) throw "Niste definirali hash funkciju!";
- if(brojEl+1==kapacitet) realociraj();
- unsigned int hes=hash(kljuc, kapacitet);
- if(kljucevi[hes]!=0) {
- int i(hes);
- while(kljucevi[i]!=0) {
- if(kljucevi[i]->k==kljuc && kljucevi[i]->obrisan==true) vrijednosti[i]=new TipVrijednosti; return *vrijednosti[i];
- if(kljucevi[i]->k==kljuc && kljucevi[i]->obrisan==false) return *vrijednosti[i];
- i++;
- if(i==kapacitet) i=0;
- }
- }
- if(kljucevi[hes]!=0 && kljucevi[hes]->k!=kljuc) {
- int i(hes);
- while(kljucevi[i]!=0 && i!=kapacitet) i++;
- if(i==kapacitet) {
- i=0;
- while(kljucevi[i]!=0 && i!=hes) i++;
- }
- kljucevi[i]=new Kljuc;
- vrijednosti[i]=new TipVrijednosti;
- kljucevi[i]->k=kljuc;
- kljucevi[i]->obrisan=false;
- brojEl++;
- return *vrijednosti[i];
- }
- else if(kljucevi[hes]==0) {
- kljucevi[hes]=new Kljuc;
- vrijednosti[hes]=new TipVrijednosti;
- kljucevi[hes]->k=kljuc;
- kljucevi[hes]->obrisan=false;
- brojEl++;
- return *vrijednosti[hes];
- }
- }
- int brojElemenata() const { return brojEl; }
- void obrisi() {
- if(brojEl!=0) {
- for(int i=0; i<kapacitet; i++) {
- if(kljucevi[i]!=0) { delete kljucevi[i]; kljucevi[i]=0; }
- if(vrijednosti[i]!=0) { delete vrijednosti[i]; vrijednosti[i]=0; }
- }
- brojEl=0;
- }
- }
- void obrisi(TipKljuca kljuc) {
- unsigned int hes=hash(kljuc, kapacitet);
- if(kljucevi[hes]!=0) {
- int i(hes);
- while(kljucevi[i]!=0) {
- if(kljucevi[i]->k==kljuc) {
- delete vrijednosti[i];
- kljucevi[i]->obrisan=true;
- vrijednosti[i]=0;
- brojEl--;
- break;
- }
- i++;
- if(i==kapacitet) i=0;
- }
- }
- }
- void definisiHashFunkciju(unsigned int(*funkcija)(TipKljuca kljuc, unsigned int max)) { hash=funkcija; }
- };
- #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement