Advertisement
Guest User

Untitled

a guest
Sep 21st, 2014
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.80 KB | None | 0 0
  1. #ifndef HASHMAPA_H
  2. #define HASHMAPA_H
  3. #include "Mapa.h"
  4. template <typename TipKljuca, typename TipVrijednosti>
  5. class HashMapa : public Mapa<TipKljuca, TipVrijednosti> {
  6. struct Kljuc {
  7. TipKljuca k;
  8. bool obrisan;
  9. };
  10. Kljuc **kljucevi;
  11. TipVrijednosti **vrijednosti;
  12. int kapacitet;
  13. int brojEl;
  14. unsigned int (*hash)(TipKljuca kljuc, unsigned int max);
  15. void realociraj() {
  16. int stari_kapacitet=kapacitet;
  17. kapacitet+=1000;
  18. Kljuc **noviK = new Kljuc*[kapacitet];
  19. TipVrijednosti **noveV = new TipVrijednosti*[kapacitet];
  20. for(int i=0; i<kapacitet; i++) { noviK[i]=0; noveV[i]=0; }
  21. for(int i=0; i<stari_kapacitet; i++) {
  22. if(kljucevi[i]!=0) {
  23. int hes=hash(kljucevi[i]->k,kapacitet);
  24. if(noviK[hes]==0) {
  25. noviK[hes]=new Kljuc;
  26. *noviK[hes]=*kljucevi[i];
  27. if(vrijednosti[i]!=0) { noveV[hes]=new TipVrijednosti; *noveV[hes]=*vrijednosti[i]; }
  28. }
  29. else {
  30. int j(hes);
  31. while(noviK[j]!=0) {
  32. j++;
  33. if(j==kapacitet) j=0;
  34. }
  35. noviK[j]=new Kljuc;
  36. *noviK[j]=*kljucevi[i];
  37. if(vrijednosti[i]!=0) { noveV[j]=new TipVrijednosti; *noveV[hes]=*vrijednosti[i]; }
  38. }
  39. delete kljucevi[i];
  40. if(vrijednosti[i]!=0) delete vrijednosti[i];
  41. }
  42. }
  43. delete[] kljucevi;
  44. delete[] vrijednosti;
  45. kljucevi=noviK;
  46. vrijednosti=noveV;
  47. }
  48. public:
  49. HashMapa() : kljucevi(new Kljuc*[1000]), vrijednosti(new TipVrijednosti*[1000]), kapacitet(1000), brojEl(0), hash(0) {
  50. for(int i=0; i<1000; i++) {
  51. kljucevi[i]=0;
  52. vrijednosti[i]=0;
  53. }
  54. }
  55. ~HashMapa() {
  56. obrisi();
  57. delete[] kljucevi;
  58. delete[] vrijednosti;
  59. }
  60. HashMapa(const HashMapa &n) {
  61. kapacitet=n.kapacitet; brojEl=n.brojEl;
  62. kljucevi=new Kljuc*[kapacitet]; vrijednosti=new TipVrijednosti*[kapacitet];
  63. for(int i=0; i<kapacitet; i++) {
  64. if(n.kljucevi[i]!=0) {
  65. kljucevi[i]=new Kljuc;
  66. *kljucevi[i]=*n.kljucevi[i];
  67. if(kljucevi[i]->obrisan==false) { vrijednosti[i]=new TipVrijednosti; *vrijednosti[i]=*n.vrijednosti[i]; }
  68. }
  69. else { vrijednosti[i]=0; kljucevi[i]=0; }
  70. }
  71. }
  72. HashMapa &operator =(const HashMapa &n) {
  73. obrisi();
  74. delete[] kljucevi; delete[] vrijednosti;
  75. kapacitet=n.kapacitet; brojEl=n.brojEl;
  76. kljucevi=new Kljuc*[kapacitet]; vrijednosti=new TipVrijednosti*[kapacitet];
  77. for(int i=0; i<kapacitet; i++) {
  78. if(n.kljucevi[i]!=0) {
  79. kljucevi[i]=new Kljuc;
  80. *kljucevi[i]=*n.kljucevi[i];
  81. if(kljucevi[i]->obrisan==false) { vrijednosti[i]=new TipVrijednosti; *vrijednosti[i]=*n.vrijednosti[i]; }
  82. *vrijednosti[i]=*n.vrijednosti[i];
  83. }
  84. else { vrijednosti[i]=0; kljucevi[i]=0; }
  85. }
  86. }
  87. TipVrijednosti operator [](TipKljuca kljuc) const {
  88. if(hash==0) throw "Niste definirali hash funkciju!";
  89. unsigned int hes=hash(kljuc, kapacitet);
  90. if(kljucevi[hes]!=0) return *vrijednosti[hes];
  91. }
  92. TipVrijednosti &operator [](TipKljuca kljuc) {
  93. if(hash==0) throw "Niste definirali hash funkciju!";
  94. if(brojEl+1==kapacitet) realociraj();
  95. unsigned int hes=hash(kljuc, kapacitet);
  96. if(kljucevi[hes]!=0) {
  97. int i(hes);
  98. while(kljucevi[i]!=0) {
  99. if(kljucevi[i]->k==kljuc && kljucevi[i]->obrisan==true) vrijednosti[i]=new TipVrijednosti; return *vrijednosti[i];
  100. if(kljucevi[i]->k==kljuc && kljucevi[i]->obrisan==false) return *vrijednosti[i];
  101. i++;
  102. if(i==kapacitet) i=0;
  103. }
  104. }
  105. if(kljucevi[hes]!=0 && kljucevi[hes]->k!=kljuc) {
  106. int i(hes);
  107. while(kljucevi[i]!=0 && i!=kapacitet) i++;
  108. if(i==kapacitet) {
  109. i=0;
  110. while(kljucevi[i]!=0 && i!=hes) i++;
  111. }
  112. kljucevi[i]=new Kljuc;
  113. vrijednosti[i]=new TipVrijednosti;
  114. kljucevi[i]->k=kljuc;
  115. kljucevi[i]->obrisan=false;
  116. brojEl++;
  117. return *vrijednosti[i];
  118. }
  119. else if(kljucevi[hes]==0) {
  120. kljucevi[hes]=new Kljuc;
  121. vrijednosti[hes]=new TipVrijednosti;
  122. kljucevi[hes]->k=kljuc;
  123. kljucevi[hes]->obrisan=false;
  124. brojEl++;
  125. return *vrijednosti[hes];
  126. }
  127. }
  128. int brojElemenata() const { return brojEl; }
  129. void obrisi() {
  130. if(brojEl!=0) {
  131. for(int i=0; i<kapacitet; i++) {
  132. if(kljucevi[i]!=0) { delete kljucevi[i]; kljucevi[i]=0; }
  133. if(vrijednosti[i]!=0) { delete vrijednosti[i]; vrijednosti[i]=0; }
  134. }
  135. brojEl=0;
  136. }
  137. }
  138. void obrisi(TipKljuca kljuc) {
  139. unsigned int hes=hash(kljuc, kapacitet);
  140. if(kljucevi[hes]!=0) {
  141. int i(hes);
  142. while(kljucevi[i]!=0) {
  143. if(kljucevi[i]->k==kljuc) {
  144. delete vrijednosti[i];
  145. kljucevi[i]->obrisan=true;
  146. vrijednosti[i]=0;
  147. brojEl--;
  148. break;
  149. }
  150. i++;
  151. if(i==kapacitet) i=0;
  152. }
  153. }
  154. }
  155. void definisiHashFunkciju(unsigned int(*funkcija)(TipKljuca kljuc, unsigned int max)) { hash=funkcija; }
  156. };
  157. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement