#include <iostream>
#include <vector>
#include <string>
#include <ctime>	// to initialize random number generator
//#include <cstdlib>
#include <unordered_map>
#include <algorithm>
using namespace std;

typedef struct {
	string name;
	int weight;
	int key;	// server key. Used in hashing
} server;

vector<float> testConsistentHashingVirtualServer(vector<server> &serverList, int replica) {
	vector<server> replicaList;
	int totalWeight = 0;
	for (int i = 0; i < serverList.size(); i++) {
		totalWeight += serverList[i].weight;
		for (int rep = 0; rep < replica*serverList[i].weight; rep++) {
			server* tmp = new server();
			tmp->key = rand() % RAND_MAX;
			tmp->name = serverList[i].name;
			tmp->weight = 1;
			replicaList.push_back(*tmp);
		}
	}
	sort(replicaList.begin(), replicaList.end(), [](server a, server b){return a.key < b.key; });
	unordered_map<string, float> um;
	for (int i = 0; i < replicaList.size(); i++) {
		if (i == 0) um[replicaList[0].name] = replicaList[0].key+1;
		else {
			um[replicaList[i].name] += replicaList[i].key - replicaList[i - 1].key;
		}
	}
	um[replicaList[0].name] += RAND_MAX - 1 - replicaList.back().key;
	vector<float> ret;
	for (int i = 0; i < serverList.size(); i++) {
		ret.push_back(((float)um[serverList[i].name]) / RAND_MAX * totalWeight);
	}
	return ret;
}

int main() {
	srand(time(0));
	// We simulate 7 servers. Each with different weight (INT value)
	server s[] = { { "a", 1, 0 }, { "b", 3, 0 }, { "c", 2, 0 }, \
	               { "d", 4, 0 }, { "e", 6, 0 }, { "f", 8, 0 }, \
	               { "g", 1, 0 } };
	vector<server> vs;
	for (int i = 0; i < sizeof(s) / sizeof(s[0]); i++) vs.push_back(s[i]);
	// and each server is mapped to 400 replica. In total we simulate 2800 virtual servers.
	auto ret = testConsistentHashingVirtualServer(vs, 400);
	for (int i = 0; i < sizeof(s) / sizeof(s[0]); i++) {
		cout << "Server " << s[i].name << " has weight " << s[i].weight \
			 << " and is now occuping " << ret[i] << " of all hashing space." << endl;
	}

	return EXIT_SUCCESS;
}