#C++ #HashTable #QuadraticHashing

Your task in this assignment is to implement a class that derives from Bigram_base (given below) and implements open addressing hashing using quadratic hashing to resolve collisions. The underlying hash table should use either a vector or an array (your choice), and it should increase its size and re-hash the entire table when the load factor becomes more than 0.5.

Implement the Bigram class in the file Bigram.h (given below).

In addition to the methods from Bigram_base, your Bigram should also have a default constructor that creates a new empty Bigram object like this:

Bigram b; // creates a new empty Bigram object // ... 

To test your Bigram class, create a file called a5.cpp that includes Bigram.h and thoroughly tests all the methods from Bigram_base. It should work reasonably efficiently on files with hundreds of thousands of strings.

What to Submit

Submit just the file Bigram.h, and nothing else. The marker will test your Bigram class with their own main function.

See Canvas for the exact due date and marking scheme.

Dont put a main function in Bigram.h that will cause it to fail when it is marked! The marker will supply their own .cpp file with a mainfunction that #includes your Bigram.h file.

You may want to build your program using the -B option with make to force it to re-compile your program every time, e.g.:

$ make -B a5 

If a5.cpp #includes a5.h, then calling just make a5.cpp will not re-compile a5.cpp if youve only made changes to a5.h.

Use valgrind to help ensure your program has no memory leaks or other memory errors, e.g.:

$ make -B a5 $ valgrind ./a5 // ... lots of output ... 

A program is considered to have no memory leaks or problems if:

In the LEAK SUMMARY, definitely lost, indirectly lost, and possibly lost must all be 0.

The ERROR SUMMARY must report 0 errors.

It is usually okay if still reachable reports a non-zero number of bytes.

Use only new and delete to allocate and de-allocate memory. Do not use malloc and free.

Do not use C++ smart pointers, such as unique_ptr or shared_ptr. Stick to raw pointers, and use new and delete (or delete[]) and constructors/destructors (plus valgrind) to manage memory.

You can implement you hash table using either a vector or an array. Do not use any other pre-defined data structures or algorithms to implement your solution do it using only basic C++ functions and features.

You must include this statement of originality comment at the start of a5.cpp (see below). If your a5.cpp does not have this, then we will assume your work is not original and it will not be marked.

If your program meets all these basic requirements, then it will graded using the marking scheme on Canvas.

Bigram_base.h

// Bigram_base.h //////////////////////////////////////////////////////////////// // // IMPORTANT: Don't make any changes to this file! // //////////////////////////////////////////////////////////////// #include  using namespace std; struct Bigram_key { string first; string second; }; // // Defines a comparison operator for Bigram_key objects, letting you write code // like this: // // // s and t are previously defined Bigram_key objects // if (s <= t) { // // ... s is equal to t, or comes before it // } else { // // ... s comes after t ... // } // bool operator<=(const Bigram_key& a, const Bigram_key& b) { if (a.first == b.first) { return a.second <= b.second;; } else { return a.first <= b.first; } } // // Bigram_base is an abstract base class for a map that stores (key, value) // pairs, where the key is a Bigram and its associated value is an int. // class Bigram_base { public: // Abstract base classes should always include a virtual destructor so // that inheriting classes can, if they need to, implement their own // destructor. virtual ~Bigram_base() { } // Pre-condition: // none // Post-condition: // Returns the number of pairs in this map. // Performance: // O(1) worst-case. virtual int size() const = 0; // Pre-condition: // none // Post-condition: // Returns the size of the underlying vector for this map. // Performance: // O(1) worst-case. virtual int capacity() const = 0; // Pre-condition: // none // Post-condition: // Returns the load factor for this map. // If the capacity is 0, then 0 is returned. // Performance: // O(1) worst-case. double load_factor() const { if (capacity() == 0) { return 0; } else { return double(size()) / capacity(); } } // Pre-condition: // none // Post-condition: // Returns true if there is a pair in this map with the given // key, and false otherwise. // Performance: // O(1) average-case number of comparisons. virtual bool contains(const Bigram_key& key) const = 0; // Pre-condition: // contains(key) // Post-condition: // Returns the value associated with key. // Performance: // O(1) average-case number of comparisons. virtual int value_of(const Bigram_key& key) const = 0; // Pre-condition: // none // Post-condition: // contains(key) and value_of(key) == val // Performance: // O(1) average-case number of comparisons. virtual void put(const Bigram_key& key, int val) = 0; // Pre-condition: // none // Post-condition: // !contains(key) // Performance: // O(1) average-case number of comparisons. virtual void remove(const Bigram_key& key) = 0; // Pre-condition: // !is_empty() // Post-condition: // Returns the key in this map with the largest associated // value. If there is more than one (key, value) pair tied // for the largest value, then return the one with the smaller // key (use operator<= defined above to compare them). // Performance: // O(1) worst-case (not average-case!) number of comparisons. virtual Bigram_key max() const = 0; // Pre-condition: // !is_empty() // Post-condition: // Returns the key in this map with the smallest associated // value. If there is more than one (key, value) pair tied // for the smallest value, then return the one with the smaller // key (use operator<= defined above to compare them). // Performance: // O(1) worst-case (not average-case!) number of comparisons. virtual Bigram_key min() const = 0; }; // class Bigram_base 

Bigram.h

// Bigram.h //////////////////////////////////////////////////////////////////////// #include "Bigram_base.h" // // Put any other standard includes or helper functions/classes you need ... // class Bigram : public Bigram_base { // Implement all the non-implemented methods from Bigram_base here. Be // sure to include a default constructor that creates a new empty Bigram. }; // class Bigram