#include // Throws invalid_argument if numBuckets is non-positive template DefaultHash::DefaultHash(int numBuckets) throw (invalid_argument) { if (numBuckets <= 0) { throw (invalid_argument("numBuckets must be > 0")); } mNumBuckets = numBuckets; } // Uses the division method for hashing. // Treats the key as a sequence of bytes, sums the ASCII // values of the bytes, and mods the total by the number // of buckets. template int DefaultHash::hash(const T& key) const { int bytes = sizeof(key); unsigned long res = 0; for (int i = 0; i < bytes; ++i) { res += *((char*)&key + i); } return (res % mNumBuckets); } // Throws invalid_argument if numBuckets is non-positive DefaultHash::DefaultHash(int numBuckets) throw (invalid_argument) { if (numBuckets <= 0) { throw (invalid_argument("numBuckets must be > 0")); } mNumBuckets = numBuckets; } // Uses the division method for hashing after summing the // ASCII values of all the characters in key. int DefaultHash::hash(const string& key) const { int sum = 0; for (size_t i = 0; i < key.size(); i++) { sum += key[i]; } return (sum % mNumBuckets); } // Dereferencing or incrementing an iterator constructed with the // default ctor is undefined, so it doesn't matter what values we give // here. template HashIterator::HashIterator() { mBucket = -1; mIt = list >::iterator(); mHashmap = NULL; } template HashIterator::HashIterator(int bucket, typename list >::iterator listIt, const hashmap* inHashmap) : mBucket(bucket), mIt(listIt), mHashmap(inHashmap) { } // Return the actual element template pair& HashIterator::operator*() const { return (*mIt); } // Return the iterator, so the compiler can apply -> to it to access // the actual desired field. template pair* HashIterator::operator->() const { return (&(*mIt)); } // Defer the details to the increment() helper template HashIterator& HashIterator::operator++() { increment(); return (*this); } // Defer the details to the increment() helper template const HashIterator HashIterator::operator++(int) { HashIterator oldIt = *this; increment(); return (oldIt); } // Defer the details to the decrement() helper template HashIterator& HashIterator::operator--() { decrement(); return (*this); } // Defer the details to the decrement() helper template const HashIterator HashIterator::operator--(int) { HashIterator newIt = *this; decrement(); return (newIt); } // Behavior is undefined if mIt already refers to the past-the-end // element in the table, or is otherwise invalid. template void HashIterator::increment() { // mIt is an iterator into a single bucket. // Increment it. ++mIt; // If we're at the end of the current bucket, // find the next bucket with elements. if (mIt == (*mHashmap->mElems)[mBucket].end()) { for (size_t i = mBucket + 1; i < (*mHashmap->mElems).size(); i++) { if (!((*mHashmap->mElems)[i].empty())) { // We found a non-empty bucket. // Make mIt refer to the first element in it. mIt = (*mHashmap->mElems)[i].begin(); mBucket = i; return; } } // No more empty buckets. Assign mIt to refer to the end // iterator of the last list. mBucket = (*mHashmap->mElems).size() - 1; mIt = (*mHashmap->mElems)[mBucket].end(); } } // Behavior is undefined if mIt already refers to the first element // in the table, or is otherwise invalid. template void HashIterator::decrement() { // mIt is an iterator into a single bucket. // If it's at the beginning of the current bucket, don't decrement it. // Instead, try to find a non-empty bucket ahead of the current one. if (mIt == (*mHashmap->mElems)[mBucket].begin()) { for (int i = mBucket - 1; i >= 0; --i) { if (!((*mHashmap->mElems)[i].empty())) { mIt = (*mHashmap->mElems)[i].end(); --mIt; mBucket = i; return; } } // No more non-empty buckets. This is an invalid decrement. // Assign mIt to refer to one before the start element of the first // list (an invalid position). mIt = (*mHashmap->mElems)[0].begin(); --mIt; mBucket = 0; } else { // We're not at the beginning of the bucket, so // just move down. --mIt; } } template bool HashIterator::operator==( const HashIterator& rhs) const { // All fields, including the hashmap to which the iterators refer, // must be equal. return (mHashmap == rhs.mHashmap && mBucket == rhs.mBucket && mIt == rhs.mIt); } template bool HashIterator::operator!=( const HashIterator& rhs) const { return (!operator==(rhs)); } // Construct mElems with the number of buckets. template hashmap::hashmap( const Compare& comp, const Hash& hash) throw(invalid_argument) : mSize(0), mComp(comp), mHash(hash) { if (mHash.numBuckets() <= 0) { throw (invalid_argument("Number of buckets must be positive")); } mElems = new vector >(mHash.numBuckets()); } // Make a call to insert() to actually insert the elements. template template hashmap::hashmap( InputIterator first, InputIterator last, const Compare& comp, const Hash& hash) throw(invalid_argument) : mSize(0), mComp(comp), mHash(hash) { if (mHash.numBuckets() <= 0) { throw (invalid_argument("Number of buckets must be positive")); } mElems = new vector >(mHash.numBuckets()); insert(first, last); } template hashmap::~hashmap() { delete mElems; } template hashmap::hashmap(const hashmap< Key, T, Compare, Hash>& src) : mSize(src.mSize), mComp(src.mComp), mHash(src.mHash) { // Don't need to bother checking if numBuckets is positive, because // we know src checked. // Use the vector copy constructor mElems = new vector >(*(src.mElems)); } template hashmap& hashmap::operator=( const hashmap& rhs) { // check for self-assignment if (this != &rhs) { delete mElems; mSize = rhs.mSize; mComp = rhs.mComp; mHash = rhs.mHash; // Don't need to bother checking if numBuckets is positive, because // we know rhs checked // Use the vector copy constructor mElems = new vector >(*(rhs.mElems)); } return (*this); } template typename list >::iterator hashmap::findElement(const key_type& x, int& bucket) const { // hash the key to get the bucket bucket = mHash.hash(x); // Look for the key in the bucket for (typename ListType::iterator it = (*mElems)[bucket].begin(); it != (*mElems)[bucket].end(); ++it) { if (mComp(it->first, x)) { return (it); } } return ((*mElems)[bucket].end()); } template typename hashmap::iterator hashmap::find(const key_type& x) { int bucket; // Use the findElement() helper typename ListType::iterator it = findElement(x, bucket); if (it == (*mElems)[bucket].end()) { // we didn't find the element -- return the end iterator return (end()); } // We found the element -- convert the bucket/iterator to a HashIterator return (HashIterator(bucket, it, this)); } template typename hashmap::const_iterator hashmap::find(const key_type& x) const { int bucket; // Use the findElement() helper typename ListType::iterator it = findElement(x, bucket); if (it == (*mElems)[bucket].end()) { // we didn't find the element -- return the end iterator return (end()); } // We found the element -- convert the bucket/iterator to a HashIterator return (HashIterator(bucket, it, this)); } template typename hashmap::size_type hashmap::count(const key_type& x) const { // There are either 1 or 0 elements matching key x. // If we can find a match, return 1, otherwise return 0. if (find(x) == end()) { return (0); } else { return (1); } } template T& hashmap::operator[] (const key_type& x) { // This definition is the same as that used by map, according to // the standard. // It's a bit cryptic, but it basically attempts to insert // a new key/value pair of x and a new value. Regardless of whether // the insert succeeds or fails, insert() returns a pair of an // iterator/bool. The iterator refers to a key/value pair, the // second element of which is the value we want to return. return (((insert(make_pair(x, T()))).first)->second); } template pair::iterator, bool> hashmap::insert(const value_type& x) { int bucket; // Try to find the element typename ListType::iterator it = findElement(x.first, bucket); if (it != (*mElems)[bucket].end()) { // The element already exists // Convert the list iterator into a HashIterator, which // also requires the bucket and a pointer to the hashmap. HashIterator newIt(bucket, it, this); // Some compilers don't like make_pair here pair, bool> p(newIt, false); return (p); } else { // We didn't find the element, so insert a new one. mSize++; typename ListType::iterator endIt = (*mElems)[bucket].insert((*mElems)[bucket].end(), x); pair, bool> p( HashIterator(bucket, endIt, this), true); return (p); } } template typename hashmap::iterator hashmap::insert(typename hashmap::iterator position, const value_type& x) { // completely ignore position return (insert(x).first); } template template void hashmap::insert(InputIterator first, InputIterator last) { // Copy each element in the range by using an insert_iterator // adapter. Give begin() as a dummy position -- insert ignores it // anyway. std::insert_iterator > it(*this, begin()); copy(first, last, it); } template typename hashmap::size_type hashmap::erase(const key_type& x) { int bucket; // First, try to find the element typename ListType::iterator it = findElement(x, bucket); if (it != (*mElems)[bucket].end()) { // The element already exists -- erase it (*mElems)[bucket].erase(it); mSize--; return (1); } else { return (0); } } template void hashmap::erase( hashmap::iterator position) { // Erase the element from its bucket (*mElems)[position.mBucket].erase(position.mIt); mSize--; } template void hashmap::erase( hashmap::iterator first, hashmap::iterator last) { typename hashmap::iterator cur, next; // erase all the elements in the range for (next = first; next != last; ) { cur = next++; erase(cur); } } template void hashmap::clear() { // Call clear on each list. for_each(mElems->begin(), mElems->end(), mem_fun_ref(&ListType::clear)); mSize = 0; } template bool hashmap::empty() const { return (mSize == 0); } template typename hashmap::size_type hashmap::size() const { return (mSize); } template typename hashmap::size_type hashmap::max_size() const { // In the worst case, all the elements hash to the // same list, so the max_size is the max_size of a single // list. This code assumes that all the lists have the same // max_size. return ((*mElems)[0].max_size()); } // Just swap the four data members // Use the generic swap template template void hashmap::swap(hashmap< Key, T, Compare, Hash>& hashIn) { // explicitly qualify with std:: so the compiler doesn't think // it's a recursive call. std::swap(*this, hashIn); } template typename hashmap::iterator hashmap::begin() { if (mSize == 0) { // Special case: there are no elements, so return the end iterator return (end()); } // We know there is at least one element. Find the first element for (size_t i = 0; i < mElems->size(); ++i) { if (!((*mElems)[i].empty())) { return (HashIterator(i, (*mElems)[i].begin(), this)); } } // should never reach here, but if we do, return the end iterator return (end()); } template typename hashmap::iterator hashmap::end() { // The end iterator is just the end iterator of the list in last bucket return (HashIterator(mElems->size() - 1, (*mElems)[mElems->size() - 1].end(), this)); } template typename hashmap::iterator hashmap::begin() const { if (mSize == 0) { // Special case: there are no elements, so return the end iterator return (end()); } // We know there is at least one element. Find the first element for (size_t i = 0; i < mElems->size(); ++i) { if (!((*mElems)[i].empty())) { return (HashIterator(i, (*mElems)[i].begin(), this)); } } // should never reach here, but if we do, return the end iterator return (end()); } template typename hashmap::iterator hashmap::end() const { // The end iterator is just the end iterator of the list in last bucket return (HashIterator(mElems->size() - 1, (*mElems)[mElems->size() - 1].end(), this)); }