#include "consistent_hash.h"
#include <fstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <assert.h>
#include <stdlib.h>

using namespace std;


typedef struct client {
	int id;
	consistent_hash chash;
	bool faulty;

	set<int> files;

	//metrics
	int mess_in;
	int mess_out;
};

typedef struct file_metric {
	int id;
	bool found;
	int hops;
	int cl_id;
};

//commands
enum {EXIT, JOIN, LEAVE, FAIL, INSERT, FIND};

void get_word(char * str, int & start_pos, char * answ) {
		
	unsigned int i = start_pos;
	while ((str[i] == ' ') && (i <  strlen(str))) {
		i++;
	}
	cout << "i1 = " << i << endl;
	if (i == strlen(str)) {
		answ =  (char *) NULL;
		return;
	}
	
	unsigned int base  = i;
	while ((str[i] != ' ')  && (i < strlen(str))){
		answ[i-base] = str[i];
		i++;
	}
	cout << "i2 = " << i << endl;
	answ[i-base] = '\0';
	start_pos = i;
	
}



int parse(fstream & fh, int & command, int & n, int & id) {
	
	char str[20];
	fh >> str;

 	switch (str[0]) {
		case 'e': { command =  EXIT; n = -1 ; id  = -1; break; }
		case 'j': { command =  JOIN; fh >> str; n = atoi(str); id = -1; break; }
		case 'l': { command =  LEAVE; fh >> str; n = atoi(str); id = -1; break; }
		case 'f': { if (str[1] == 'a') { 
				command =  FAIL;
				fh >> str; n = atoi(str); id = -1;
			    } else {
			   	command =  FIND;
				fh >> str; n = atoi(str); fh >> str; id = atoi(str);
			    }
			    break; 
			  }
		case 'i': { command =  INSERT;fh >> str; n = atoi(str); fh >> str; id = atoi(str);  break; }
		case 's': {break;}
		default:  { cerr << "unknown command" << endl; return -1; }
	}

	return 1;
}

void addToSet(set<int> & dest, set<int> source) {
	for (set<int>::iterator it = source.begin(); it != source.end(); it++) {
		dest.insert(*it);
	}
}

void join(int n, int id,  map<int, client*> & clients, list<client *> & gone_clients, list<file_metric> & file_log) {

	client * cl = new client;
	cl->id = n;
	cl->faulty = false;
	cl->files.clear();
	cl->mess_in = 0;
	cl->mess_out = 0;
	clients[n] = cl;	

	if (clients.size() == 1){
		cl->chash.add_member(member(n));
	} else {
		//choose at random whom to ask
		int r = (int) (clients.size() * ((double)rand() / ((double)(RAND_MAX)+(double)(1))));
		cout << "random nr is  " << r << endl;
		int dest = 0;
		for (map<int,client*>::iterator it = clients.begin(); it != clients.end(); it++) {
			if (r == 0) {
				dest = it->first;
				break;
			} else {
				r--; 
			}
		}
		cout << "dest is " << dest << endl;	
		clients[n]-> chash.set_membership(clients[dest]->chash.get_memb());
		for (map<int, client*>::iterator it = clients.begin() ; it != clients.end(); it++) {
			it->second->chash.add_member(member(n));
			it->second->mess_in++;	
			clients[n]->mess_out++;
		}
	}
			
	cout << n << " joined " << endl;

}

void leave(int n, int id,  map<int, client*> & clients, list<client *> & gone_clients, list<file_metric> & file_log) {
	if (clients.find(n) == clients.end()) {
		cout << n << " left or failed already " << endl;
		return;
	}
	
	cout << "A" << endl;
	int prev = (clients[n]-> chash.lookup_previous(member(n))).id;
	cout << "b" << endl;
	while (clients.find(prev) == clients.end()) {
		prev =  (clients[n]-> chash.lookup_previous(member(prev))).id;
		clients[n]->mess_out++;
	
	}
	if (prev == n) {
		cout << "all gone in the system" << endl;
	} else {
		addToSet(clients[prev]->files, clients[n]->files);
		clients[prev]->mess_in++;
		cout << "C" << endl;
		clients[n]->mess_out++;			
		cout << "d" << endl;
	}

	for (map<int, client*>::iterator it = clients.begin() ; it != clients.end(); it++) {
			it->second->chash.remove_member(member(n));
			it->second->mess_in++;	
			clients[n]->mess_out++;
	}
	gone_clients.push_back(clients[n]);
	clients.erase(n);

	cout << n << " left " << endl;
}

void fail(int n, int id,  map<int, client*> & clients, list<client *> & gone_clients, list<file_metric> & file_log) {
	gone_clients.push_back(clients[n]);
	clients.erase(n);
	cout << n << " failed " << endl;
}

void insert(int n, int id,  map<int, client*> & clients, list<client *> & gone_clients, list<file_metric> & file_log) {
	if (clients.find(n) == clients.end()) {
		cout << id << " insert failed - no insertion node \n" << endl;
		return;
	}
	
	int dest = clients[n]-> chash.lookup(id).id;
			
	while (clients.find(dest) == clients.end()) {
		clients[n]->mess_out++;
		dest = clients[n]-> chash.lookup_previous(dest).id;
							
	}
	clients[dest]->files.insert(id);
	clients[dest]->mess_in++;
	clients[n]->mess_out++;
	cout << id <<" inserted at " << dest << endl;
}

void find(int n, int id,  map<int, client*> & clients, list<client *> & gone_clients, list<file_metric> & file_log) {
	if (clients.find(n) == clients.end()) {
		cout << "error: cannot lookup from failed/gone node" << endl;
		return;
	}
	int dest = clients[n]-> chash.lookup(id).id;
	if (clients.find(dest) == clients.end()) {
		//not found
		file_metric fm;
		fm.id = id;
		fm.found = false;
		file_log.push_back(fm);
		cout << id << " not found " << endl;
		clients[n]->mess_out++;
		return;
		
	} else  {
		if (clients[dest]->files.find(id) == clients[dest]->files.end()) {
			//not found
			file_metric fm;
			fm.id = id;
			fm.found = false;
			file_log.push_back(fm);
			cout << id << "not found" << endl;
		} else {
			file_metric fm;
			fm.id = id;
			fm.found = true;
			fm.hops = 1;
			fm.cl_id = dest;
			cout << id << "found at " << dest << endl;
			file_log.push_back(fm);
		} 
	}
	clients[n]->mess_out++;
	clients[dest]->mess_in++;
	clients[dest]->mess_out++;
}

int exp_hops(int argc, char ** argv) {


   if (argc != 2) {
    	cerr << "USAGE ./chash file " << endl;
	exit(0);
    }

  /*
    * Nodes varying from 0 to 1000 in increments of 50
    * insert 10 pieces for every node
    * lookup 10 random ids
    */

   int NODE_START = 0;
   int NODE_END = 2000;
   int NODE_STEP = 50;
   int PIECES_INSERT_NODE = 10;
   int PIECES_LOOKUP_NODE = 10;

   fstream fo(argv[1],ios::out);


   for (int expr = NODE_START/NODE_STEP; expr <= NODE_END/NODE_STEP; expr++) {
   	  //initialize clients
  	  map<int, client*> clients;
    	  list<client *> gone_clients;
    	  list<file_metric> file_log;
		
	  if (expr == 0) {
	  	fo << 0 << " " << 0 << endl;
		continue;
	  }

	  int nodes = expr * NODE_STEP;
	  //generate random ids from 0 ... 35000
          for (int i = 0; i < nodes; i++) {
	  	int n = (int)((rand() * 1.0/ RAND_MAX) * 35000);
		join(n, -1, clients, gone_clients, file_log);
	  }
	
          //insert pieces
	  for (map<int,client*>::iterator it = clients.begin(); it != clients.end(); it++) {
	  	int n = it->first;
		for (int j = 0; j < PIECES_INSERT_NODE; j++) {
			int id = (int)((rand() * 1.0/ RAND_MAX) * 11131);
			insert(n, id, clients, gone_clients, file_log);
		}
		
	  }

	  //lookup pieces
	  for (map<int,client*>::iterator it = clients.begin(); it != clients.end(); it++) {
	  	int n = it->first;
		for (int j = 0; j < PIECES_LOOKUP_NODE; j++) {
			int id = (int)((rand() * 1.0/ RAND_MAX) * 11131);
			find(n, id, clients, gone_clients, file_log);
		}
		
	  }
		
	  //output average
	 long sum = 0;
	 for (map<int,client*>::iterator it = clients.begin(); it != clients.end(); it++) {
	 	sum += it->second->mess_in + it->second->mess_out; 
         } 
	 fo << nodes << " " << sum/clients.size() << endl;
    }

   fo.close();

   return 0;
}


int exp_failure(int argc, char ** argv) {


   if (argc != 2) {
    	cerr << "USAGE ./chash file " << endl;
	exit(0);
    }

  /*
    * Nodes varying from 0 to 1000 in increments of 50
    * insert 10 pieces for every node
    * lookup 10 random ids
    */

   int NODES = 1000;
   double F_INCREMENT = 0.05;
   int F_SAMPLES = 20; //want 11 
   int PIECES_INSERT_NODE = 10;
   
   fstream fo(argv[1],ios::out);

   //initialize clients
   map<int, client*> clients;
   list<client *> gone_clients;
   list<file_metric> file_log;
   list<int> ids;
	
   int nodes = NODES;
   //generate random ids from 0 ... 35000
   for (int i = 0; i < nodes; i++) {
  	int n = (int)((rand() * 1.0/ RAND_MAX) * 35000);
	join(n, -1, clients, gone_clients, file_log);
   }
	
          //insert pieces
   for (map<int,client*>::iterator it = clients.begin(); it != clients.end(); it++) {
  	int n = it->first;
	for (int j = 0; j < PIECES_INSERT_NODE; j++) {
		int id = (int)((rand() * 1.0/ RAND_MAX) * 11131);
		ids.push_back(id);
		insert(n, id, clients, gone_clients, file_log);
	}
	
   } 
   
  fo << "0.0 1.0" << endl; 	
  //increase failure rate and compute how many are found
  for (int i = 0; i < F_SAMPLES-1; i++) {
  	double f_rate = F_INCREMENT/ (1-F_INCREMENT*i);
  	for (map<int,client*>::iterator it = clients.begin(); it != clients.end(); it++) {
		double f =  rand() * 1.0/ RAND_MAX;
		if (f <= f_rate) {
			fail(it->first, -1, clients, gone_clients, file_log);
		}
	}
	//try to see how many files are found
        file_log.clear();
	int cnt = 0;
	for (list<int>::iterator it= ids.begin(); it != ids.end(); it++) {
		find(clients.begin()->first, *it, clients, gone_clients, file_log);
		if (file_log.back().found) {cnt++;}
	}
	fo << F_INCREMENT*(i+1) << " " << cnt * 1.0 / ids.size() << endl;
  }
		
   
   fo.close();
   return 0;
}

int
main(int argc, char *argv[]) {


  exp_failure(argc, argv);

   

  /*
    fstream fh(argv[1],ios::in);
        
    //initialize clients
    map<int, client*> clients;
    list<client *> gone_clients;
    list<file_metric> file_log;


    srand(100362);

    int command, n, id;

    //begin simulation
    while (parse(fh, command, n, id)) {
    	
	switch (command) {
		case  EXIT: {
			goto statistics;
			break;
		} 

		case  JOIN: {
			join(n, id, clients, gone_clients, file_log);
			break;
		} 


		case  LEAVE: {
			
			leave(n, id, clients, gone_clients, file_log);
			break;
		} 

		case  FAIL: {

			fail(n, id, clients, gone_clients, file_log);			
			break;
		} 

		case  INSERT: {
			insert(n, id, clients, gone_clients, file_log);
			break;
		} 
		case  FIND: {
			find(n, id, clients, gone_clients, file_log);
			break;
		} 
	default: {cerr << "command unknown" << endl;}

	}

     }
    
statistics:
    cout << " statistics clients:  id mess_in mess_out " << endl;
    for (map<int,client *>::iterator it = clients.begin(); it !=clients.end(); it++) {
    	cout << it->first << " " << it->second->mess_in << " " << it->second->mess_out << endl;
    }
    for (list<client *>::iterator it = gone_clients.begin(); it !=gone_clients.end(); it++) {
    	cout << (*it)->id << " " << (*it)->mess_in << " " << (*it)->mess_out << endl;
    }  
	
    cout << "statistics files: id found hops" << endl;	
    for (list<file_metric>::iterator it = file_log.begin(); it != file_log.end(); it++) {
    	cout << it->id << " " << it->found << " " << it->hops << endl;
    } 

    fh.close();

*/

  

    return 0;

}