Xmap
Sunny
c_cpp
6 months ago
19 kB
7
Indexable
/* * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license * Click nbfs://nbhost/SystemFileSystem/Templates/cppFiles/file.h to edit this template */ /* * File: xMap.h * Author: ltsach * * Created on October 11, 2024, 7:08 PM */ #ifndef XMAP_H #define XMAP_H #include <iostream> #include <iomanip> #include <string> #include <sstream> #include <memory.h> using namespace std; #include "list/DLinkedList.h" #include "hash/IMap.h" /* * xMap<K, V>: * + K: key type * + V: value type * For example: * xMap<string, int>: map from string to int */ template<class K, class V> class xMap: public IMap<K,V>{ public: class Entry; //forward declaration protected: DLinkedList<Entry* >* table; //array of DLinkedList objects int capacity; //size of table int count; //number of entries stored hash-map float loadFactor; //define max number of entries can be stored (< (loadFactor * capacity)) int (*hashCode)(K&,int); //hasCode(K key, int tableSize): tableSize means capacity bool (*keyEqual)(K&,K&); //keyEqual(K& lhs, K& rhs): test if lhs == rhs bool (*valueEqual)(V&,V&); //valueEqual(V& lhs, V& rhs): test if lhs == rhs void (*deleteKeys)(xMap<K,V>*); //deleteKeys(xMap<K,V>* pMap): delete all keys stored in pMap void (*deleteValues)(xMap<K,V>*); //deleteValues(xMap<K,V>* pMap): delete all values stored in pMap public: xMap( int (*hashCode)(K&,int), //require float loadFactor=0.75f, bool (*valueEqual)(V&, V&)=0, void (*deleteValues)(xMap<K,V>*)=0, bool (*keyEqual)(K&, K&)=0, void (*deleteKeys)(xMap<K,V>*)=0); xMap(const xMap<K,V>& map); //copy constructor xMap<K,V>& operator=(const xMap<K,V>& map); //assignment operator ~xMap(); //Inherit from IMap:BEGIN V put(K key, V value); V& get(K key); V remove(K key, void (*deleteKeyInMap)(K)=0); bool remove(K key, V value, void (*deleteKeyInMap)(K)=0, void (*deleteValueInMap)(V)=0); bool containsKey(K key); bool containsValue(V value); bool empty(); int size(); void clear(); string toString(string (*key2str)(K&)=0, string (*value2str)(V&)=0 ); DLinkedList<K> keys(); DLinkedList<V> values(); DLinkedList<int> clashes(); //Inherit from IMap:END //Show map on screen: need to convert key to string (key2str) and value2str void println(string (*key2str)(K&)=0, string (*value2str)(V&)=0 ){ cout << this->toString(key2str, value2str) << endl; } int getCapacity(){ return capacity; } /////////////////////////////////////////////////// // STATIC METHODS: BEGIN // * Used to create xMap objects /////////////////////////////////////////////////// /* * sample hash function for keys of types integer and string: */ static int intKeyHash(int& key, int capacity){ return key%capacity; } static int stringKeyHash(string& key, int capacity){ long long int sum = 0; for (int idx = 0; idx < key.length(); idx++) sum += key[idx]; return sum % capacity; } /* * freeKey(xMap<K,V> *pMap): * Purpose: a typical function for deleting keys stored in map * WHEN to use: * 1. K is a pointer type; AND * 2. Users need xMap to free keys */ static void freeKey(xMap<K,V> *pMap){ for(int idx=0; idx < pMap->capacity; idx++){ DLinkedList<Entry*> list = pMap->table[idx]; for(auto pEntry: list){ delete pEntry->key; } } } /* * freeValue(xMap<K,V> *pMap): * Purpose: a typical function for deleting values stored in map * WHEN to use: * 1. V is a pointer type; AND * 2. Users need xMap to free values */ static void freeValue(xMap<K,V> *pMap){ for(int idx=0; idx < pMap->capacity; idx++){ DLinkedList<Entry*> list = pMap->table[idx]; for(auto pEntry: list){ delete pEntry->value; } } } /* * deleteEntry(Entry* ptr): a function pointer to delete pointer to Entry */ static void deleteEntry(Entry* ptr){ delete ptr; } /////////////////////////////////////////////////// // STATIC METHODS: END // * Used to create xMap objects /////////////////////////////////////////////////// protected: //////////////////////////////////////////////////////// //////////////////////// UTILITIES //////////////////// //////////////////////////////////////////////////////// void ensureLoadFactor(int minCapacity); //future version: // should add a method to trim table shorter when removing key (and value) void rehash(int newCapacity); void removeInternalData(); void copyMapFrom(const xMap<K,V>& map); void moveEntries( DLinkedList<Entry*>* oldTable, int oldCapacity, DLinkedList<Entry*>* newTable, int newCapacity); /* * keyEQ(K& lhs, K& rhs): verify the equality of two keys */ bool keyEQ(K& lhs, K& rhs){ if(keyEqual != 0) return keyEqual(lhs, rhs); else return lhs==rhs; } /* * valueEQ(V& lhs, V& rhs): verify the equality of two values */ bool valueEQ(V& lhs, V& rhs){ if(valueEqual != 0) return valueEqual(lhs, rhs); else return lhs==rhs; } ////////////////////////////////////////////////////////////////////// //////////////////////// INNER CLASSES DEFNITION //////////////////// ////////////////////////////////////////////////////////////////////// public: //Entry: BEGIN class Entry{ private: K key; V value; friend class xMap<K,V>; public: Entry(K key, V value){ this->key = key; this->value = value; } }; //Entry: END }; ////////////////////////////////////////////////////////////////////// //////////////////////// METHOD DEFNITION /////////////////// ////////////////////////////////////////////////////////////////////// template<class K, class V> xMap<K,V>::xMap( int (*hashCode)(K&,int), float loadFactor, bool (*valueEqual)(V& lhs, V& rhs), void (*deleteValues)(xMap<K,V>*), bool (*keyEqual)(K& lhs, K& rhs), void (*deleteKeys)(xMap<K,V>* pMap) ){ this->hashCode = hashCode; this->loadFactor = loadFactor; this->valueEqual = valueEqual; this->deleteValues = deleteValues; this->keyEqual = keyEqual; this->deleteKeys = deleteKeys; this->count = 0; this->capacity = 10; this->table = new DLinkedList<Entry*>[capacity]; } template<class K, class V> xMap<K,V>::xMap(const xMap<K,V>& map){ this->hashCode = map.hashCode; this->loadFactor = map.loadFactor; this->valueEqual = map.valueEqual; this->deleteValues = map.deleteValues; this->keyEqual = map.keyEqual; this->deleteKeys = map.deleteKeys; this->count = 0; this->capacity = map.capacity; this->table = new DLinkedList<Entry*>[capacity]; copyMapFrom(map); } template<class K, class V> xMap<K,V>& xMap<K,V>::operator=(const xMap<K,V>& map){ if(this != &map){ removeInternalData(); copyMapFrom(map); } return *this; } template<class K, class V> xMap<K,V>::~xMap(){ removeInternalData(); } ////////////////////////////////////////////////////////////////////// //////////////////////// IMPLEMENTATION of IMap /////////////////// ////////////////////////////////////////////////////////////////////// template<class K, class V> V xMap<K,V>::put(K key, V value) { // Check load factor before insertion ensureLoadFactor(count + 1); int index = this->hashCode(key, capacity); V retValue = V(); // Get the bucket at index DLinkedList<Entry*>& bucket = table[index]; // Create a temporary entry for comparison Entry* tempEntry = new Entry(key, value); // Use indexOf to find if key exists int entryIndex = -1; for(typename DLinkedList<Entry*>::Iterator it = bucket.begin(); it != bucket.end(); it++) { if(keyEQ((*it)->key, key)) { entryIndex = bucket.indexOf(*it); break; } } if(entryIndex != -1) { // Key found - update value Entry* existingEntry = bucket.get(entryIndex); retValue = existingEntry->value; // If values are pointers and we have a deletion callback if(deleteValues != 0) { V* pValue = &(existingEntry->value); deleteValues(pValue); } existingEntry->value = value; delete tempEntry; // Clean up temporary entry } else { // Key not found - add new entry bucket.add(tempEntry); count++; } return retValue; } template<class K, class V> V& xMap<K,V>::get(K key){ int index = hashCode(key, capacity); DLinkedList<Entry*>& bucket = table[index]; // Search for key in the bucket for(typename DLinkedList<Entry*>::Iterator it = bucket.begin(); it != bucket.end(); it++) { if(keyEQ((*it)->key, key)) { return (*it)->value; } } // Key not found - throw exception stringstream os; os << "key (" << key << ") is not found"; throw KeyNotFound(os.str()); } template<class K, class V> V xMap<K,V>::remove(K key, void (*deleteKeyInMap)(K)) { int index = hashCode(key, capacity); DLinkedList<Entry*>& bucket = table[index]; V retValue; // Search for key in bucket Entry* foundEntry = nullptr; for(typename DLinkedList<Entry*>::Iterator it = bucket.begin(); it != bucket.end(); it++) { if(keyEQ((*it)->key, key)) { foundEntry = *it; retValue = foundEntry->value; break; } } if(foundEntry != nullptr) { // Key found - remove entry if(deleteKeyInMap) { deleteKeyInMap(foundEntry->key); } // Use the static member function directly bucket.removeItem(foundEntry, xMap<K,V>::deleteEntry); count--; return retValue; } // Key not found stringstream os; os << "key (" << key << ") is not found"; throw KeyNotFound(os.str()); } template<class K, class V> bool xMap<K,V>::remove(K key, V value, void (*deleteKeyInMap)(K), void (*deleteValueInMap)(V)) { int index = hashCode(key, capacity); DLinkedList<Entry*>& bucket = table[index]; // Search for key-value pair in bucket Entry* foundEntry = nullptr; for(typename DLinkedList<Entry*>::Iterator it = bucket.begin(); it != bucket.end(); it++) { if(keyEQ((*it)->key, key) && (*it)->value == value) { foundEntry = *it; break; } } if(foundEntry != nullptr) { if(deleteKeyInMap) { deleteKeyInMap(foundEntry->key); } if(deleteValueInMap) { deleteValueInMap(foundEntry->value); } // Use the static member function bucket.removeItem(foundEntry, xMap<K,V>::deleteEntry); count--; return true; } return false; } template<class K, class V> bool xMap<K,V>::containsKey(K key){ int index = hashCode(key, capacity); DLinkedList<Entry*>& bucket = table[index]; // Search for key in bucket for(typename DLinkedList<Entry*>::Iterator it = bucket.begin(); it != bucket.end(); it++) { if(keyEQ((*it)->key, key)) { return true; } } return false; } template <class K, class V> bool xMap<K, V>::containsValue(V value) { for(int idx = 0; idx < capacity; idx++) { DLinkedList<Entry*>& bucket = table[idx]; for(auto pEntry: bucket) { if(valueEQ(pEntry->value, value)) return true; } } return false; } template<class K, class V> bool xMap<K,V>::empty(){ return count == 0; } template<class K, class V> int xMap<K,V>::size(){ return count; } template<class K, class V> void xMap<K,V>::clear(){ removeInternalData(); capacity = 10; count = 0; table = new DLinkedList<Entry*>[capacity]; } template<class K, class V> DLinkedList<K> xMap<K,V>::keys(){ DLinkedList<K> result; for(int idx = 0; idx < capacity; idx++) { DLinkedList<Entry*>& bucket = table[idx]; for(auto pEntry: bucket) { result.add(pEntry->key); } } return result; } template<class K, class V> DLinkedList<V> xMap<K,V>::values(){ DLinkedList<V> result; for(int idx = 0; idx < capacity; idx++) { DLinkedList<Entry*>& bucket = table[idx]; for(auto pEntry: bucket) { result.add(pEntry->value); } } return result; } template<class K, class V> DLinkedList<int> xMap<K,V>::clashes(){ DLinkedList<int> result; // Initialize empty list to store counts // Loop through each bucket in hash table for(int i = 0; i < capacity; i++){ // Get count of elements at current index and add to result if(&table[i] == nullptr){ result.add(0); } else { int elementsInBucket = table[i].count(); result.add(elementsInBucket); } } return result; } template<class K, class V> string xMap<K,V>::toString(string (*key2str)(K&), string (*value2str)(V&)){ stringstream os; string mark(50, '='); os << mark << endl; os << setw(12) << left << "capacity: " << capacity << endl; os << setw(12) << left << "size: " << count << endl; for(int idx=0; idx < capacity; idx++){ DLinkedList<Entry*> list = table[idx]; os << setw(4) << left << idx << ": "; stringstream itemos; for(auto pEntry: list){ itemos << " ("; if(key2str != 0) itemos << key2str(pEntry->key); else itemos << pEntry->key; itemos << ","; if(value2str != 0) itemos << value2str(pEntry->value); else itemos << pEntry->value; itemos << ");"; } string valuestr = itemos.str(); if(valuestr.length() > 0) valuestr = valuestr.substr(0, valuestr.length()-1); os << valuestr << endl; } os << mark << endl; return os.str(); } //////////////////////////////////////////////////////// // UTILITIES // Code are provided //////////////////////////////////////////////////////// /* * moveEntries: * Purpose: move all entries in the old hash table (oldTable) to the new table (newTable) */ template<class K, class V> void xMap<K,V>::moveEntries( DLinkedList<Entry*>* oldTable, int oldCapacity, DLinkedList<Entry*>* newTable, int newCapacity){ for(int old_index=0; old_index < oldCapacity; old_index++){ DLinkedList<Entry*>& oldList= oldTable[old_index]; for(auto oldEntry: oldList){ int new_index = this->hashCode(oldEntry->key, newCapacity); DLinkedList<Entry*>& newList = newTable[new_index]; newList.add(oldEntry); } } } /* * ensureLoadFactor: * Purpose: ensure the load-factor, * i.e., the maximum number of entries does not exceed "loadFactor*capacity" */ template<class K, class V> void xMap<K,V>::ensureLoadFactor(int current_size){ int maxSize = (int)(loadFactor*capacity); //cout << "ensureLoadFactor: count = " << count << "; maxSize = " << maxSize << endl; if(current_size > maxSize){ int oldCapacity = capacity; //int newCapacity = oldCapacity + (oldCapacity >> 1); int newCapacity = 1.5*oldCapacity; rehash(newCapacity); } } /* * rehash(int newCapacity) * Purpose: * 1. create a new hash-table with newCapacity, and * 2. move all the old table to to new one * 3. free the old table. */ template<class K, class V> void xMap<K,V>::rehash(int newCapacity){ DLinkedList<Entry*>* pOldMap = this->table; int oldCapacity = capacity; //Create new table: this->table = new DLinkedList<Entry*>[newCapacity]; this->capacity = newCapacity; //keep "count" not changed moveEntries(pOldMap, oldCapacity, this->table, newCapacity); //remove old data: only remove nodes in list, no entry for(int idx=0; idx < oldCapacity; idx++){ DLinkedList<Entry*>& list = pOldMap[idx]; list.clear(); } //Remove oldTable delete []pOldMap; } /* * removeInternalData: * Purpose: * 1. Remove all keys and values if users require, * i.e., deleteKeys and deleteValues are not nullptr * 2. Remove all entry * 3. Remove table */ template<class K, class V> void xMap<K,V>::removeInternalData(){ // First handle user data deletion if callbacks are provided if(deleteKeys != 0) deleteKeys(this); if(deleteValues != 0) deleteValues(this); // Then clear each bucket's entries for(int idx=0; idx < this->capacity; idx++){ DLinkedList<Entry*>& list = this->table[idx]; typename DLinkedList<Entry*>::Iterator it = list.begin(); while(it != list.end()) { Entry* entry = *it; // Clean up the entry object delete entry; it++; } // list.clear(); co the thu nghiem dung list.removeInternalData(); } // Finally, delete the table array delete[] table; } /* * copyMapFrom(const xMap<K,V>& map): * Purpose: * 1. Remove all the entries of the current hash-table * 2. Copy (Shallow-copy only) all the entries in the input map * to the current table */ template<class K, class V> void xMap<K,V>::copyMapFrom(const xMap<K,V>& map){ removeInternalData(); this->capacity = map.capacity; this->count = 0; this->table = new DLinkedList<Entry*>[capacity]; this->hashCode = hashCode; this->loadFactor = loadFactor; this->valueEqual = valueEqual; this->keyEqual = keyEqual; //SHOULD NOT COPY: deleteKeys, deleteValues => delete ONLY TIME in map if needed //copy entries for(int idx=0; idx < map.capacity; idx++){ DLinkedList<Entry*>& list = map.table[idx]; for(auto pEntry: list){ this->put(pEntry->key, pEntry->value); } } } #endif /* XMAP_H */
Editor is loading...
Leave a Comment