Advertisement
Guest User

Untitled

a guest
Oct 25th, 2014
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.35 KB | None | 0 0
  1. #ifndef DIC_H
  2. #define DIC_H
  3.  
  4. #include <iostream>
  5. #include <string>
  6. using namespace std;
  7.  
  8. typedef string K; //key type //!!!
  9. typedef double V; //value type //!!!
  10.  
  11. /* Loki Added */
  12. namespace HA
  13. {
  14. int hash(std::string key); // There are plenty of things alerady called hash.
  15. // This was confusing the compiler so I had
  16. // to put it in its own namespace to make sure
  17. // I was using the correct one.
  18. }
  19. ** Loki END*/
  20.  
  21. class Dic{
  22. public:
  23. Dic( ); //an empty Dic
  24.  
  25. //The BIG 3: operator=, copyconstructor, destructor
  26. ~Dic();
  27.  
  28. Dic( const Dic & src ); //copy con
  29.  
  30. Dic & operator=( const Dic & rhs ); //assignment op
  31.  
  32.  
  33. //return null or a pointer at the value in this Dic
  34. V * find(K key);
  35.  
  36. //returns true if it ADDED (false if modified)
  37. bool addOrMod(K key, V val);
  38.  
  39. int size( );
  40.  
  41. private:
  42. class DicNode{public: K key; V val; DicNode * nxt; };
  43. int n; int SZ;
  44. DicNode** table; // DicNode* [ ] an array of linked lists of DicNodes
  45.  
  46. int dichash(K); //private hash function
  47. void deallocate(); //private helper, used by the destructor.
  48. };
  49.  
  50. #endif
  51.  
  52. #include "Dic.h"
  53. #include <string>
  54.  
  55. int Dic::dichash(K key){ //DEPENDS ON K. This one assumes K is string
  56. /*Loki Change */
  57. return std::abs(HA::hash(key)) % SZ;
  58. /*Loki END*/
  59. }
  60.  
  61. void Dic::deallocate(){ //separate member called by destruc and op=
  62. for(int i=0; i<SZ; i++){
  63. //get rid of chain i
  64. DicNode * p = table[i];
  65. while(p!=0){
  66. DicNode * kill = p;
  67. p = p->nxt;
  68. delete kill;
  69. }
  70. }
  71. delete [] table;
  72. }
  73.  
  74. V * Dic::find(K key) {
  75. /* Loki Wrote */
  76. int hash = dichash(key);
  77. DicNode* f = table[hash];
  78. while(f != nullptr && f->key != key)
  79. { f = f->nxt;
  80. }
  81. return f == nullptr
  82. ? nullptr
  83. : &f->val;
  84. /* Loki END */
  85. }
  86.  
  87. bool Dic::addOrMod(K key, V val){
  88.  
  89. /* Loki Wrote */
  90. V* current = find(key);
  91. if (current != nullptr)
  92. {
  93. *current = val;
  94. return false; // false indicates value was not added just modified.
  95. }
  96.  
  97. int hash = dichash(key);
  98. table[hash] = new DicNode{key, val, table[hash]};
  99. return true; // true indicates new value was added to the table.
  100. /* Loki END */
  101. }
  102.  
  103. int Dic::size(){
  104.  
  105. return n;
  106. }
  107. //-----------------------------------------------------------------
  108.  
  109. //BIG 3
  110.  
  111. Dic::Dic()
  112. /*Loki Add
  113. Must initialize all the members.
  114. Otherwise your object will have random values in it.
  115. */
  116. : n(0)
  117. , SZ(13)
  118. , table(new DicNode*[SZ]())
  119. /*Loki END*/
  120. {}
  121.  
  122. Dic::Dic( const Dic & src )
  123. /*Loki Add
  124. Must initialize all the members.
  125. Otherwise your object will have random values in it.
  126. Having randome valus is not very useful when you call the assignment operator
  127. which calls the dealloce() method.
  128. */
  129. : n(0)
  130. , SZ(0)
  131. , table(nullptr)
  132. /*Loki END*/
  133. {
  134. *this = src; //Uses operator= defined for Dic
  135. }
  136.  
  137. Dic & Dic::operator=( const Dic & rhs )
  138. { //assignment op
  139. if(this == &rhs){ cout<<"goofy"<<endl; return *this; }
  140.  
  141. // clean up any memory allocated by this
  142. this->deallocate();
  143. // initialize this n,SZ,table to be like rhs
  144. this->n=rhs.n; this->SZ = rhs.SZ; this->table=new DicNode*[SZ];
  145. // duplicate the DicNode chains
  146. for(int i=0;i<SZ;i++){
  147. DicNode * q = rhs.table[i];
  148. if(q==0){
  149. this->table[i]=0;
  150. }else{
  151. this->table[i]=new DicNode; //note: NOT DicNode()
  152. DicNode * p = this->table[i];
  153. while(true){ //loop inv: *p is blank node corresp to *q
  154. p->key = q->key; p->val = q->val;
  155. if(q->nxt==0)break;
  156. q=q->nxt; p->nxt=new DicNode; p=p->nxt;
  157. }
  158. p->nxt=0;
  159. }
  160. }
  161. return *this;
  162. }
  163. namespace HA
  164. {
  165. int hash(string s) {
  166. int ret=0;
  167. /*Loki Remove
  168. The SZ member variable is what you want to use.
  169. This is because you want to take the hash and convert it into an index
  170. into your table. The string length is the correct value to use as the
  171. modulus.
  172. int SZ = s.length();
  173. * Loki END*/
  174. for (int i=0; i<s.size(); i++) {
  175. ret+=s[i]-'A';
  176. }
  177. /*Loki Change
  178. return ret%SZ;
  179. *Loki End*/
  180.  
  181. /* Note returning a hash of the string.
  182. * It is not modulo anything. So
  183. * we also need to modify all call points to
  184. * use modulo if required.
  185. * I am not going to comment those changes.
  186. */
  187. return ret;
  188. }
  189. }
  190.  
  191. Dic::~Dic(){this->deallocate();}
  192.  
  193. int main()
  194. {
  195. Dic dict;
  196.  
  197. dict.addOrMod("Key", 5);
  198. std::cout << dict.find("Key") << "n";
  199. std::cout << *dict.find("Key") << "n";
  200. }
  201.  
  202. using namespace std;
  203.  
  204. int hash(std::string key);
  205.  
  206. // Prefer to do this:
  207.  
  208. int hash(std::string const& key);
  209.  
  210. Dic( ); //an empty Dic
  211.  
  212. //The BIG 3: operator=, copyconstructor, destructor
  213. ~Dic();
  214.  
  215. Dic( const Dic & src ); //copy con
  216.  
  217. Dic & operator=( const Dic & rhs ); //assignment op
  218.  
  219. // Too much vertical space (and usless comments) I would have done:
  220. Dic();
  221. Dic(const Dic & src);
  222. Dic(Dic&& src);
  223. ~Dic();
  224. Dic& operator=(Dic const& rhs);
  225. Dic& operator=(Dic&& rhs);
  226.  
  227. V * find(K key); // Change to: V* find(K const& key);
  228. bool addOrMod(K key, V val); // Change to: bool addOrMod(K const& key, V val);
  229.  
  230. int size();
  231.  
  232. // This should have a const on it:
  233.  
  234. int size() const;
  235.  
  236. // In addition to the normal find() you specify above.
  237. // It is also worth have'ing a const version that allows your users to read from the object.
  238. V const* find(Key const& key) const;
  239.  
  240. // Notice that the method is const and the value I return is const.
  241. // So you can read it but not modify the content.
  242.  
  243. class DicNode{public: K key; V val; DicNode * nxt; };
  244.  
  245. int n; int SZ;
  246. DicNode** table; // Note: the * is part of the type.
  247. // So place it with the type.
  248.  
  249. int dichash(K); //private hash function
  250.  
  251. int Dic::dichash(K key){ //DEPENDS ON K. This one assumes K is string
  252. /*Loki Change */
  253. return std::abs(HA::hash(key)) % SZ;
  254. /*Loki END*/
  255. }
  256.  
  257. void Dic::deallocate(){ //separate member called by destruc and op=
  258. for(int i=0; i<SZ; i++){
  259. //get rid of chain i
  260. DicNode * p = table[i];
  261. while(p!=0){
  262. DicNode * kill = p;
  263. p = p->nxt;
  264. delete kill;
  265. }
  266. }
  267. delete [] table;
  268. }
  269.  
  270. V * Dic::find(K key) {
  271. bool Dic::addOrMod(K key, V val){
  272. int Dic::size(){
  273.  
  274. Dic::Dic()
  275.  
  276. Dic::Dic( const Dic & src )
  277.  
  278. Dic & Dic::operator=( const Dic & rhs )
  279.  
  280. // clean up any memory allocated by this
  281. this->deallocate();
  282.  
  283. this->n=rhs.n; this->SZ = rhs.SZ; this->table=new DicNode*[SZ];
  284.  
  285. for(int i=0;i<SZ;i++){
  286.  
  287. DicNode * q = rhs.table[i];
  288.  
  289. int hash(string s) {
  290. int ret=0;
  291. /*Loki Remove
  292. The SZ member variable is what you want to use.
  293. This is because you want to take the hash and convert it into an index
  294. into your table. The string length is the correct value to use as the
  295. modulus.
  296. int SZ = s.length();
  297. * Loki END*/
  298. for (int i=0; i<s.size(); i++) {
  299. ret+=s[i]-'A';
  300. }
  301. /*Loki Change
  302. return ret%SZ;
  303. *Loki End*/
  304.  
  305. /* Note returning a hash of the string.
  306. * It is not modulo anything. So
  307. * we also need to modify all call points to
  308. * use modulo if required.
  309. * I am not going to comment those changes.
  310. */
  311. return ret;
  312. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement