Untitled

#pragma once
#include <sstream>
#include <exception>
#include <vector>
#include <memory>
namespace cs251 {

// Custom exception classes
class duplicate_key : public std::runtime_error {
	public: duplicate_key() : std::runtime_error("Duplicate key!") {} };
class nonexistent_key : public std::runtime_error {
	public: nonexistent_key() : std::runtime_error("Key does not exist!") {} };

template <typename K, typename V>
class hash_map {
public:
	class hash_map_node {
	public:
		// The key of current node.
		K m_key = {};
		// The value of current node.
		std::unique_ptr<V> m_value{};
	};

	// Return a constant reference to the hash table vector
	const std::vector<std::shared_ptr<hash_map_node>>& get_data() const;

	// Default constructor - create a hash map with an initial capacity of 1
	hash_map();
	// Constructor - create a hash map with an intial capacity of bucketCount
	hash_map(size_t bucketCount);

	// Get the hash code for a given key
	size_t hash_code(K key) const;

	// Change the size of the table to bucketCount, re-hashing all existing elements
	// bucketCount will never be 0 or less than the current number of elements
	void resize(size_t bucketCount);

	// Insert the key/value pair into the table, if the key doesn't already exist
	// Throw duplicate_key if the key already exists
	void insert(const K& key, std::unique_ptr<V> value);
	// Return a const reference to the value associated with the given key
	// Throw nonexistent_key if the key is not in the hash table
	const std::unique_ptr<V>& peek(const K& key);
	// Remove and return the key-value pair associated with the given key
	// Throw nonexistent_key if the key is not in the hash table
	std::unique_ptr<V> extract(const K& key);

	// Return the current number of elements in the hash table
	size_t size() const;
	// Return the current capacity of the hash table
	size_t bucket_count() const;
	// Return whether the hash table is currently empty
	bool empty() const;

private:
	// The array that holds key-value pairs
	std::vector<std::shared_ptr<hash_map_node>> m_data = {};

	size_t m_size = 0;

	// TODO: Add any additional methods or variables here
};

template <typename K, typename V>
const std::vector<std::shared_ptr<typename hash_map<K,V>::hash_map_node>>& hash_map<K,V>::get_data() const {
	return m_data;
}

template <typename K, typename V>
hash_map<K,V>::hash_map() {
	// TODO: Remove the following line and add your implementation here.
	m_data.resize(1);
}

template <typename K, typename V>
hash_map<K,V>::hash_map(const size_t bucketCount) {
	// TODO: Remove the following line and add your implementation here.
	m_data.resize(bucketCount);
}

template <typename K, typename V>
size_t hash_map<K,V>::hash_code(K key) const {
	// TODO: Remove the following line and add your implementation here.
	return key % m_data.size();
}

template <typename K, typename V>
void hash_map<K,V>::resize(const size_t bucketCount) {
	// TODO: Remove the following line and add your implementation here.
	 if (bucketCount < m_data.size())
        return;

    std::vector<std::shared_ptr<hash_map_node>> newData(bucketCount);
    for (const auto& node : m_data) {
        if (node) {
            size_t index = (node->m_key) % bucketCount;
            while (newData[index] != nullptr) {
                index = (index + 1) % bucketCount; // Linear probing
            }
            newData[index] = node;
        }
    }
    m_data = std::move(newData); 
}

template <typename K, typename V>
 void hash_map<K,V>::insert(const K& key, std::unique_ptr<V> value) {
	// TODO: Remove the following line and add your implementation here.
	 size_t index = hash_code(key);
    /*while (m_data[index] != nullptr && m_data[index]->m_key != key) {
        index = (index + 1) % m_data.size(); // Linear probing
    } */
	bool found = false;;
	for(int i=0; i<m_data.size(); i++) {
		if(m_data[index] != nullptr) {
			if(m_data[index]->m_key == key){
				found = true;
				break;
			}
		}
		index = (index + 1) % m_data.size();
		
	}
    if (found) {
        throw duplicate_key();
    }

	index = hash_code(key);
    while (m_data[index] != nullptr ) {
        index = (index + 1) % m_data.size(); // Linear probing
    } 
    m_data[index] = std::make_shared<hash_map_node>(hash_map_node{key, std::move(value)});

	m_size++; 
}

template <typename K, typename V>
const std::unique_ptr<V>& hash_map<K,V>::peek(const K& key) {
	// TODO: Remove the following line and add your implementation here.
	 size_t index = hash_code(key);
    /* while (m_data[index] != nullptr && m_data[index]->m_key != key) {
        index = (index + 1) % m_data.size(); // Linear probing
    }

    if (m_data[index] == nullptr) {
        throw nonexistent_key();
    }

    return m_data[index]->m_value; */
	bool found = false;;
	for(int i=0; i<m_data.size(); i++) {
		if(m_data[index] != nullptr) {
			if(m_data[index]->m_key == key){
				found = true;
				break;
			}
		}
		index = (index + 1) % m_data.size();
		
	}
    if (found == false) {
        throw nonexistent_key();
    }
	return m_data[index]->m_value;
}

template <typename K, typename V>
std::unique_ptr<V> hash_map<K,V>::extract(const K& key) {
	// TODO: Remove the following line and add your implementation here.
	size_t index = hash_code(key);
	 /* while (m_data[index] != nullptr && m_data[index]->m_key != key) {
        index = (index + 1) % m_data.size(); // Linear probing
    }

	if (m_data[index] == nullptr) {
        throw nonexistent_key();
    }

	auto element = std::move(m_data[index] -> m_value);
	m_data[index] = nullptr;
	m_size--;
	return element;
	//decrement m_size at the end */
	bool found = false;;
	for(int i=0; i<m_data.size(); i++) {
		if(m_data[index] != nullptr) {
			if(m_data[index]->m_key == key){
				found = true;
				break;
			}
		}
		index = (index + 1) % m_data.size();
		
	}
    if (found == false) {
        throw nonexistent_key();
    }
	
	auto element = std::move(m_data[index] -> m_value);
	m_data[index] = nullptr;
	m_size--;
	return element;
}



template <typename K, typename V>
size_t hash_map<K,V>::size() const {
	// TODO: Remove the following line and add your implementation here.
	return m_size;
}

template <typename K, typename V>
size_t hash_map<K,V>::bucket_count() const {
	// TODO: Remove the following line and add your implementation here.
	return m_data.size();
}

template <typename K, typename V>
bool hash_map<K,V>::empty() const {
	// TODO: Remove the following line and add your implementation here.
	return m_size == 0;
}


}