Xmap

 avatar
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