Hashing with Chains done!

Didn't write test cases because the starter code wasn't easy for
testing. Tested using sample input. Fun stuff :)

1 files changed, 71 insertions, 175 deletions

diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 07f8b43..064ca45 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,190 +1,86 @@
 #include <iostream>
-#include <vector>
 #include <string>
+#include <vector>
+#include <algorithm>
 
 using std::string;
 using std::vector;
 using std::cin;
 
 struct Query {
-    string type, name;
-    int number;
+	string type, s;
+	size_t ind;
 };
 
-vector<Query> read_queries() {
-    int n;
-    cin >> n;
-    vector<Query> queries(n);
-    for (int i = 0; i < n; ++i) {
-        cin >> queries[i].type;
-        if (queries[i].type == "add")
-            cin >> queries[i].number >> queries[i].name;
-        else
-            cin >> queries[i].number;
-    }
-    return queries;
-}
+class QueryProcessor {
+	int bucket_count;
+	// store all strings in one vector
+	vector<vector<string>> elems;
+	size_t hash_func(const string& s) const {
+		static const size_t multiplier = 263;
+		static const size_t prime = 1000000007;
+		unsigned long long hash = 0;
+		for (int i = static_cast<int>(s.size()) - 1; i >= 0; --i)
+			hash = (hash * multiplier + s[i]) % prime;
+		return hash % bucket_count;
+	}
 
-void write_responses(const vector<string>& result) {
-    for (size_t i = 0; i < result.size(); ++i)
-        std::cout << result[i] << "\n";
-}
+public:
+	explicit QueryProcessor(int bucket_count) :
+			bucket_count(bucket_count) {
+	}
 
-vector<string> process_queries(const vector<Query>& queries) {
-    vector<string> result;
-    // Keep list of all existing (i.e. not deleted yet) contacts.
-    vector<string> contacts(10000000);
-    for (size_t i = 0; i < contacts.size(); i++) {
-       contacts[i] = "not found";
-    }
-    for (size_t i = 0; i < queries.size(); ++i)
-        if (queries[i].type == "add") {
-        	contacts[queries[i].number] = queries[i].name;
-        } else if (queries[i].type == "del") {
-        	contacts[queries[i].number] = "not found";
-        } else {
-            result.push_back(contacts[queries[i].number]);
-        }
-    return result;
-}
+	Query readQuery() const {
+		Query query;
+		cin >> query.type;
+		if (query.type != "check")
+			cin >> query.s;
+		else
+			cin >> query.ind;
+		return query;
+	}
+
+	void writeSearchResult(bool was_found) const {
+		std::cout << (was_found ? "yes\n" : "no\n");
+	}
+
+	void processQuery(const Query& query) {
+		if (query.type == "check") {
+			// use reverse order, because we append strings to the end
+			for (int i = static_cast<int>(elems[query.ind].size()) - 1; i >= 0;
+					--i)
+				std::cout << elems[query.ind][i] << " ";
+			std::cout << "\n";
+		} else {
+			int hashIndex = hash_func(query.s);
+			vector<string>::iterator it = std::find(elems[hashIndex].begin(), elems[hashIndex].end(),
+					query.s);
+			if (query.type == "find")
+				writeSearchResult(it != elems[hashIndex].end());
+			else if (query.type == "add") {
+				if (it == elems[hashIndex].end())
+					elems[hashIndex].push_back(query.s);
+			} else if (query.type == "del") {
+				if (it != elems[hashIndex].end())
+					elems[hashIndex].erase(it);
+			}
+		}
+	}
+
+	void processQueries() {
+		int n;
+		cin >> n;
+		elems.resize(n);
+		for (int i = 0; i < n; ++i)
+			processQuery(readQuery());
+	}
+};
 
 int main() {
-    write_responses(process_queries(read_queries()));
-    return 0;
+	std::ios_base::sync_with_stdio(false);
+	int bucket_count;
+	cin >> bucket_count;
+	QueryProcessor proc(bucket_count);
+	proc.processQueries();
+	return 0;
 }
-
-//#include <cstdio>
-//#include <cstdlib>
-//#include <vector>
-//#include <algorithm>
-//#include <iostream>
-////#include <gtest/gtest.h>
-//
-//using std::cin;
-//using std::cout;
-//using std::endl;
-//using std::max;
-//using std::vector;
-//
-//struct Table {
-//	int numberOfRows;
-//	int setID;
-//
-//	Table(int numberOfRows, int setID) :
-//			numberOfRows(numberOfRows), setID(setID) {
-//	}
-//};
-//
-//int maximumNumberOfRows = -1;
-//vector<int> parent;
-//vector<int> rank;
-//vector<Table> tables;
-//
-//int find(int i) {
-//	if (i != parent[i])
-//		parent[i] = find(parent[i]);
-//	return parent[i];
-//}
-//
-//void unite(int destination, int source) {
-//	int destination_id = find(destination);
-//	int source_id = find(source);
-//	if (destination_id == source_id)
-//		return;
-//	if (rank[destination_id] > rank[source_id])
-//		parent[source_id] = destination_id;
-//	else {
-//		parent[destination_id] = source_id;
-//		if (rank[destination_id] == rank[source_id])
-//			rank[source_id] = rank[source_id] + 1;
-//	}
-//}
-//
-//void merge(int destination, int source) {
-//	int d = find(destination);
-//	int s = find(source);
-//	Table* realDestination = &tables[d];
-//	Table* realSource = &tables[s];
-//	if (d == s) {
-//		return;
-//	}
-//	maximumNumberOfRows = max(maximumNumberOfRows,
-//			tables[realDestination->setID].numberOfRows + tables[realSource->setID].numberOfRows);
-//	realDestination->numberOfRows = tables[realDestination->setID].numberOfRows
-//			+ tables[realSource->setID].numberOfRows;
-//	realSource->numberOfRows = 0;
-//	realSource->setID = d;
-//	realDestination->setID = d;
-//	unite(destination, source);
-//}
-//
-//int main() {
-//	int n, m;
-//	cin >> n >> m;
-//
-//	parent.resize(n);
-//	rank.resize(n);
-////	tables.resize(n);
-//	for (int i = 0; i < n; i++) {
-//		int numberOfRows;
-//		cin >> numberOfRows;
-//		tables.push_back(Table(numberOfRows, i));
-////		tables[i] = Table(numberOfRows, i);
-//		parent[i] = i;
-//		rank[i] = 0;
-//		maximumNumberOfRows = max(maximumNumberOfRows, numberOfRows);
-//	}
-//
-//	for (int i = 0; i < m; i++) {
-//		int destination, source;
-//		cin >> destination >> source;
-//		--destination;
-//		--source;
-//
-//		merge(destination, source);
-//		cout << maximumNumberOfRows << endl;
-//	}
-//
-//	return 0;
-//}
-//
-////TEST(MergingTables, t) {
-////    maximumNumberOfRows = 1;
-////    rank = {0, 0, 0, 0, 0};
-////    parent = {0, 1, 2, 3, 4};
-////    tables = {Table(1, 0), Table(1, 1), Table(1, 2), Table(1, 3), Table(1, 4)};
-////
-////    merge(2, 4);
-////    ASSERT_EQ(2, maximumNumberOfRows);
-////
-////    merge(1, 3);
-////    ASSERT_EQ(2, maximumNumberOfRows);
-////
-////    merge(0, 3);
-////    ASSERT_EQ(3, maximumNumberOfRows);
-////
-////    merge(4, 3);
-////    ASSERT_EQ(5, maximumNumberOfRows);
-////
-////    merge(4, 2);
-////    ASSERT_EQ(5, maximumNumberOfRows);
-////}
-////
-////TEST(MergingTables, t1) {
-////    maximumNumberOfRows = 10;
-////    rank = {0, 0, 0, 0, 0, 0};
-////    parent = {0, 1, 2, 3, 4, 5};
-////    tables = {Table(10, 0), Table(0, 1), Table(5, 2), Table(0, 3), Table(3, 4), Table(3, 5)};
-////
-////    merge(5, 5);
-////    ASSERT_EQ(10, maximumNumberOfRows);
-////
-////    merge(5, 4);
-////    ASSERT_EQ(10, maximumNumberOfRows);
-////
-////    merge(4, 3);
-////    ASSERT_EQ(10, maximumNumberOfRows);
-////
-////    merge(3, 2);
-////    ASSERT_EQ(11, maximumNumberOfRows);
-////}