This is basically a repeat of the previous assignment except that the data is stored in a file. As with the linked list assignment earlier, this forces us to make a few changes to how things are done. We have to remove the normal iterator and have only a const_iterator. Also, [] can't be used to set values. It is a const method that returns a mapped_type by value. To make up for this, we have a set method that will behave the way that [] did on the memory based hash map.
Open addressing (CLRS 11.4), where everything is stored in the "array", does not allow for efficient removal. As such, I have taken out the erase method. I want you to write this using open addressing for the experience of doing so and to keep the assignment shorter. You could do a file based approach using linking where you keep a pool of singly linked list nodes after the table, but I think that would take too long to write.
When you grow your table, you have to make a second file. As with the previous file based solution, you can't move more than two elements in memory at any given time. You can safely assume that if you append a 2 to the end of the file name you are initially passed that it will be safe as a temporary file for growing a bigger table. You will need to copy the result back into the original file though as that is what will be attached to if I open back up a file and expect it to contain proper data.
Your code should be in FileHashMap.h for your submission.
const char UNUSED = 255;
const char USED = 254;
template<typename K,typename V,typename Hash>
class FileHashMap {
Hash hashFunction;
// File name
// File pointer
// Number of records stored
// Capacity of the file
// Placed here to prevent copies.
FileHashMap(const FileHashMap<K,V,Hash> &that);
FileHashMap<K,V,Hash> &operator=(const FileHashMap<K,V,Hash> &that);
// Helper functions recommended
public:
typedef K key_type;
typedef V mapped_type;
typedef std::pair<K,V> value_type;
class const_iterator {
FILE *file;
unsigned cap;
unsigned loc;
void advance() {
// Code to move forward to the next used element after loc.
}
public:
const_iterator(FILE *f,unsigned c):file(f),cap(c),loc(0) {
advance();
}
const_iterator(FILE *f,unsigned c,unsigned i):file(f),cap(c),loc(i) {}
bool operator==(const const_iterator &i) const { return file==i.file && loc==i.loc; }
bool operator!=(const const_iterator &i) const { return !(*this==i); }
const std::pair<K,V> operator*() const {
// seek
std::pair<K,V> p;
// read
return p;
}
const_iterator &operator++() {
++loc;
advance();
return *this;
}
const_iterator operator++(int) {
const_iterator tmp(*this);
++(*this);
return tmp;
}
};
FileHashMap(const std::string &fname,const Hash &hf):hashFunction(hf),fileName(fname),file(fopen(fname.c_str(),"r+b")) {
if(file==nullptr) {
// open with w+b and set up the file
} else {
// read header information
}
}
~FileHashMap() {
// close the file
}
bool empty() const;
unsigned size() const;
const_iterator find(const key_type& k) const;
int count(const key_type& k) const;
std::pair<const_iterator,bool> insert(const value_type& val);
template <class InputIterator>
void insert(InputIterator first, InputIterator last) {
for(auto iter = first; iter!=last; ++iter) {
insert(*iter);
}
}
void clear();
const mapped_type operator[](const K &key) const;
const_iterator set(const value_type &val);
bool operator==(const FileHashMap<K,V,Hash>& rhs) const;
bool operator!=(const FileHashMap<K,V,Hash>& rhs) const;
const_iterator begin() const { return const_iterator(file,capacity); }
const_iterator end() const { return const_iterator(file,capacity,capacity); }
const_iterator cbegin() const { return const_iterator(file,capacity); }
const_iterator cend() const { return const_iterator(file,capacity,capacity); }
private:
void growTableAndRehash();
};