From 717000654d2d58985ba500f730d95327d0a6051f Mon Sep 17 00:00:00 2001
From: Angeld55 <achi_d@abv.bg>
Date: Fri, 20 Sep 2019 17:23:15 +0300
Subject: zdrasti

kak e
---
 DiamondProblemAndPolymorphism/HashTable.hpp | 136 ++++++++++++++++++++++++++++
 1 file changed, 136 insertions(+)
 create mode 100644 DiamondProblemAndPolymorphism/HashTable.hpp

(limited to 'DiamondProblemAndPolymorphism/HashTable.hpp')

diff --git a/DiamondProblemAndPolymorphism/HashTable.hpp b/DiamondProblemAndPolymorphism/HashTable.hpp
new file mode 100644
index 0000000..ee3b9b5
--- /dev/null
+++ b/DiamondProblemAndPolymorphism/HashTable.hpp
@@ -0,0 +1,136 @@
+#ifndef HASHTABLE_H
+#define HASHTABLE_H
+#include<iostream>
+
+const int N = 10;
+
+template<typename K>
+struct List {
+
+	std::string key;
+	K data;
+	List* next;
+
+	List(std::string key, K data) {
+		this->key = key;
+		this->data = data;
+		next = nullptr;
+	}
+};
+
+template<typename K>
+class HashTable {
+
+public:
+	HashTable();
+	HashTable(const HashTable&) = delete;
+	HashTable& operator=(const HashTable&) = delete;
+	~HashTable();
+	void Put(std::string key, K data); //add element
+	K Get(std::string key); //search for element
+	void Remove(std::string key); //remove element
+
+private:
+	List<K>** hashTable;
+	unsigned HashFunction(std::string key);
+	List<K>* CheckKeyUniqueness(std::string key, int index);
+
+};
+
+#endif // !HASHTABLE_H
+
+template<typename K>
+HashTable<K>::HashTable() {
+
+	hashTable = new List<K>*[N];
+	for (int i = 0; i < N; i++) 
+		hashTable[i] = nullptr;
+	
+}
+
+template<typename K>
+HashTable<K>::~HashTable() {
+
+	for (int i = 0; i < N; i++) {
+
+		List<K>* current = hashTable[i];
+		while (current != nullptr) {
+			List<K>* next = current->next;
+			delete current;
+			current = next;
+		}
+	}
+	delete hashTable;
+}
+
+template<typename K>
+void HashTable<K>::Put(std::string key, K data) {
+
+	unsigned result = HashFunction(key);
+	if (CheckKeyUniqueness(key, result) != nullptr)
+		return;
+
+	List<K>* newList = new List<K>(key, data);
+	newList->next = hashTable[result];
+	hashTable[result] = newList;
+}
+
+template<typename K>
+K HashTable<K>::Get(std::string key) {
+
+	unsigned result = HashFunction(key);
+	List<K>* iter = hashTable[result];
+	while (iter->key != key)
+		iter = iter->next;
+
+	if (iter != nullptr)
+		return iter->data;
+	else
+		throw std::logic_error("Can't find this element.\n");
+}
+
+template<typename K>
+void HashTable<K>::Remove(std::string key) {
+
+	unsigned result = HashFunction(key);
+	List<K>* iter = hashTable[result];
+	List<K>* prev = iter;
+
+	if (iter == hashTable[result] && iter->key == key) {
+		hashTable[result] = iter->next;
+		delete iter;
+		return;
+	}
+
+	while (iter->key != key) {
+		prev = iter;
+		iter = iter->next;
+	}
+	
+	prev->next = iter->next;
+	delete iter;
+}
+
+template<typename K>
+unsigned HashTable<K>::HashFunction(std::string key) {
+
+	int keyLength = key.length();
+	int result = keyLength;
+	for (int i = 0; i < keyLength; i++)
+		result = (result << 4) ^ (result >> 8) ^ (key[i]);
+
+	return result % N;
+}
+
+template<typename K>
+List<K>* HashTable<K>::CheckKeyUniqueness(std::string key, int index) {
+
+	List<K>* iter = hashTable[index];
+	while (iter != nullptr) {
+		if (iter->key == key)
+			return iter;
+		iter = iter->next;
+	}
+
+	return nullptr;
+}
-- 
cgit v1.3.1-23-gd82d