Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef DIC_H
- #define DIC_H
- #include <iostream>
- #include <string>
- using namespace std;
- typedef string K; //key type //!!!
- typedef double V; //value type //!!!
- /* Loki Added */
- namespace HA
- {
- int hash(std::string key); // There are plenty of things alerady called hash.
- // This was confusing the compiler so I had
- // to put it in its own namespace to make sure
- // I was using the correct one.
- }
- ** Loki END*/
- class Dic{
- public:
- Dic( ); //an empty Dic
- //The BIG 3: operator=, copyconstructor, destructor
- ~Dic();
- Dic( const Dic & src ); //copy con
- Dic & operator=( const Dic & rhs ); //assignment op
- //return null or a pointer at the value in this Dic
- V * find(K key);
- //returns true if it ADDED (false if modified)
- bool addOrMod(K key, V val);
- int size( );
- private:
- class DicNode{public: K key; V val; DicNode * nxt; };
- int n; int SZ;
- DicNode** table; // DicNode* [ ] an array of linked lists of DicNodes
- int dichash(K); //private hash function
- void deallocate(); //private helper, used by the destructor.
- };
- #endif
- #include "Dic.h"
- #include <string>
- int Dic::dichash(K key){ //DEPENDS ON K. This one assumes K is string
- /*Loki Change */
- return std::abs(HA::hash(key)) % SZ;
- /*Loki END*/
- }
- void Dic::deallocate(){ //separate member called by destruc and op=
- for(int i=0; i<SZ; i++){
- //get rid of chain i
- DicNode * p = table[i];
- while(p!=0){
- DicNode * kill = p;
- p = p->nxt;
- delete kill;
- }
- }
- delete [] table;
- }
- V * Dic::find(K key) {
- /* Loki Wrote */
- int hash = dichash(key);
- DicNode* f = table[hash];
- while(f != nullptr && f->key != key)
- { f = f->nxt;
- }
- return f == nullptr
- ? nullptr
- : &f->val;
- /* Loki END */
- }
- bool Dic::addOrMod(K key, V val){
- /* Loki Wrote */
- V* current = find(key);
- if (current != nullptr)
- {
- *current = val;
- return false; // false indicates value was not added just modified.
- }
- int hash = dichash(key);
- table[hash] = new DicNode{key, val, table[hash]};
- return true; // true indicates new value was added to the table.
- /* Loki END */
- }
- int Dic::size(){
- return n;
- }
- //-----------------------------------------------------------------
- //BIG 3
- Dic::Dic()
- /*Loki Add
- Must initialize all the members.
- Otherwise your object will have random values in it.
- */
- : n(0)
- , SZ(13)
- , table(new DicNode*[SZ]())
- /*Loki END*/
- {}
- Dic::Dic( const Dic & src )
- /*Loki Add
- Must initialize all the members.
- Otherwise your object will have random values in it.
- Having randome valus is not very useful when you call the assignment operator
- which calls the dealloce() method.
- */
- : n(0)
- , SZ(0)
- , table(nullptr)
- /*Loki END*/
- {
- *this = src; //Uses operator= defined for Dic
- }
- Dic & Dic::operator=( const Dic & rhs )
- { //assignment op
- if(this == &rhs){ cout<<"goofy"<<endl; return *this; }
- // clean up any memory allocated by this
- this->deallocate();
- // initialize this n,SZ,table to be like rhs
- this->n=rhs.n; this->SZ = rhs.SZ; this->table=new DicNode*[SZ];
- // duplicate the DicNode chains
- for(int i=0;i<SZ;i++){
- DicNode * q = rhs.table[i];
- if(q==0){
- this->table[i]=0;
- }else{
- this->table[i]=new DicNode; //note: NOT DicNode()
- DicNode * p = this->table[i];
- while(true){ //loop inv: *p is blank node corresp to *q
- p->key = q->key; p->val = q->val;
- if(q->nxt==0)break;
- q=q->nxt; p->nxt=new DicNode; p=p->nxt;
- }
- p->nxt=0;
- }
- }
- return *this;
- }
- namespace HA
- {
- int hash(string s) {
- int ret=0;
- /*Loki Remove
- The SZ member variable is what you want to use.
- This is because you want to take the hash and convert it into an index
- into your table. The string length is the correct value to use as the
- modulus.
- int SZ = s.length();
- * Loki END*/
- for (int i=0; i<s.size(); i++) {
- ret+=s[i]-'A';
- }
- /*Loki Change
- return ret%SZ;
- *Loki End*/
- /* Note returning a hash of the string.
- * It is not modulo anything. So
- * we also need to modify all call points to
- * use modulo if required.
- * I am not going to comment those changes.
- */
- return ret;
- }
- }
- Dic::~Dic(){this->deallocate();}
- int main()
- {
- Dic dict;
- dict.addOrMod("Key", 5);
- std::cout << dict.find("Key") << "n";
- std::cout << *dict.find("Key") << "n";
- }
- using namespace std;
- int hash(std::string key);
- // Prefer to do this:
- int hash(std::string const& key);
- Dic( ); //an empty Dic
- //The BIG 3: operator=, copyconstructor, destructor
- ~Dic();
- Dic( const Dic & src ); //copy con
- Dic & operator=( const Dic & rhs ); //assignment op
- // Too much vertical space (and usless comments) I would have done:
- Dic();
- Dic(const Dic & src);
- Dic(Dic&& src);
- ~Dic();
- Dic& operator=(Dic const& rhs);
- Dic& operator=(Dic&& rhs);
- V * find(K key); // Change to: V* find(K const& key);
- bool addOrMod(K key, V val); // Change to: bool addOrMod(K const& key, V val);
- int size();
- // This should have a const on it:
- int size() const;
- // In addition to the normal find() you specify above.
- // It is also worth have'ing a const version that allows your users to read from the object.
- V const* find(Key const& key) const;
- // Notice that the method is const and the value I return is const.
- // So you can read it but not modify the content.
- class DicNode{public: K key; V val; DicNode * nxt; };
- int n; int SZ;
- DicNode** table; // Note: the * is part of the type.
- // So place it with the type.
- int dichash(K); //private hash function
- int Dic::dichash(K key){ //DEPENDS ON K. This one assumes K is string
- /*Loki Change */
- return std::abs(HA::hash(key)) % SZ;
- /*Loki END*/
- }
- void Dic::deallocate(){ //separate member called by destruc and op=
- for(int i=0; i<SZ; i++){
- //get rid of chain i
- DicNode * p = table[i];
- while(p!=0){
- DicNode * kill = p;
- p = p->nxt;
- delete kill;
- }
- }
- delete [] table;
- }
- V * Dic::find(K key) {
- bool Dic::addOrMod(K key, V val){
- int Dic::size(){
- Dic::Dic()
- Dic::Dic( const Dic & src )
- Dic & Dic::operator=( const Dic & rhs )
- // clean up any memory allocated by this
- this->deallocate();
- this->n=rhs.n; this->SZ = rhs.SZ; this->table=new DicNode*[SZ];
- for(int i=0;i<SZ;i++){
- DicNode * q = rhs.table[i];
- int hash(string s) {
- int ret=0;
- /*Loki Remove
- The SZ member variable is what you want to use.
- This is because you want to take the hash and convert it into an index
- into your table. The string length is the correct value to use as the
- modulus.
- int SZ = s.length();
- * Loki END*/
- for (int i=0; i<s.size(); i++) {
- ret+=s[i]-'A';
- }
- /*Loki Change
- return ret%SZ;
- *Loki End*/
- /* Note returning a hash of the string.
- * It is not modulo anything. So
- * we also need to modify all call points to
- * use modulo if required.
- * I am not going to comment those changes.
- */
- return ret;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement