#!/usr/bin/env python

import sys, socket, select, time, json, random, math

# Your ID number
my_id = sys.argv[1]

# The ID numbers of all the other replicas
replica_ids = sys.argv[2:]

last = 0

class KVStore:
    
    def __init__(self, id): 
        self.id = id
        self.db = {}
        self.leader = 'FFFF'
        
        self.term = 0
        self.logIndex = -1
        self.commitedIndex = -1
        
        self.log = []
        
        self.redirectQueue = []
        self.pendingRequests = []
        
        self.last_heartbeat = time.time()
        self.leader_timeout = .3
        
        self.num_replicas = len(replica_ids) + 1
        self.replicaCommits = {}
        for id in replica_ids:
            self.replicaCommits[id] = -1
        
        self.sock = socket.socket(socket.AF_UNIX, socket.SOCK_SEQPACKET)
        self.sock.connect(self.id)
        
    def redirect_to_leader(self, msg):
        to_send = {'src': self.id, 'dst': msg['src'], 'MID': msg['MID'],  'type': 'redirect', 'leader': self.leader}
        if self.leader != 'FFFF':
            self.sock.send(json.dumps(to_send))
            #print self.id + ": redirecting " + msg['MID'] + " to " + self.leader
        else:
            self.send_failed_response(msg)
        
    def send_put_response(self, msg):
        to_send = {'src': self.id, 'dst': msg['src'], 'leader': self.leader, 'type': 'ok', 'MID': msg['MID']}
        self.sock.send(json.dumps(to_send))
        
    def send_get_response(self, msg, value):
        to_send = {'src': self.id, 'dst': msg['src'], 'leader': self.leader, 'type': 'ok', 'MID': msg['MID'], 'value':value}
        self.sock.send(json.dumps(to_send))
        
    def send_failed_response(self, msg):
        to_send = {'src': self.id, 'dst': msg['src'], 'leader': self.leader, 'type': 'fail', 'MID': msg['MID']}
        self.sock.send(json.dumps(msg))
        
    def send_request(self):
        to_send = {'src': self.id, 'dst': self.leader, 'leader': self.leader, 'type': 'request', 'logIndex': self.logIndex, 'commitedIndex': self.commitedIndex}
        self.sock.send(json.dumps(to_send))
        
    def send_RPC(self):
        arr = self.log[self.commitedIndex + 1:]
        msg = {'src': self.id, 'dst': 'FFFF', 'leader': self.leader, 'type': 'rpc', 'term': self.term, 'logIndex': self.logIndex, 'commitedIndex': self.commitedIndex, 'array': arr}
        self.sock.send(json.dumps(msg))
        
    def send_specific_RPC(self, msg):
        arr = self.log[msg['logIndex'] + 1:]
        to_send = {'src': self.id, 'dst': msg['src'], 'leader': self.leader, 'type': 'rpc', 'term': self.term, 'logIndex': self.logIndex, 'commitedIndex': msg['logIndex'], 'array': arr}
        self.sock.send(json.dumps(to_send))
        
        
    def send_vote(self, dest):
        msg = {'src': self.id, 'dst': dest, 'leader': dest, 'type': 'vote'}
        self.sock.send(json.dumps(msg))
        
    def begin_election(self):
        self.leader_timeout = 2
        self.leader = 'FFFF'
        self.send_RPC()
        time_of_last_rpc = time.time()
        votes = [self.id] 
        election_start = time.time()
        election_timeout = (random.random() * .4) + .3
        while len(votes) < math.ceil(self.num_replicas / 2.0):
            if time.time() - time_of_last_rpc > .15:
                self.send_RPC()
                time_of_last_rpc = time.time()
            
                
            ready = select.select([self.sock], [], [], 0.1)[0]
            if self.sock in ready:
                msg_raw = self.sock.recv(32768)
                
                if len(msg_raw) == 0:
                    continue
                    
                msg = json.loads(msg_raw)
                
                if msg['type'] in ['get', 'put']:
                    self.send_failed_response(msg)
                    
                elif msg['type'] == 'rpc':
                    if msg['leader'] == msg['src']:
                        if msg['term'] > self.term:
                            self.leader = msg['src']
                            self.state = 'follower'
                            self.last_heartbeat = time.time()
                            return
                            
                elif msg['type'] == 'vote':
                    if msg['src'] not in votes:
                        votes.append(msg['src'])
                        
            if time.time() - election_start > election_timeout:
                self.last_heartbeat = time.time()
                return
                        
        #after winning the election
        self.leader = self.id
        self.term += 1
        self.state = 'leader'
        self.send_RPC()
        print self.id + " JUST WON THE ELECTION"
        #for v in votes:
        #    print v
        
        for request in self.redirectQueue:
            self.send_failed_response(request)
        
    def vote_in_election(self, candidate_id):
        self.leader_timeout = 2
        self.leader = 'FFFF'
        self.send_vote(candidate_id)
        last_voted = time.time()
        while True:
            if time.time() - last_voted > .25:
                self.send_vote(candidate_id)
        
            ready = select.select([self.sock], [], [], 0.1)[0]
            if self.sock in ready:
                msg_raw = self.sock.recv(32768)
                
                if len(msg_raw) == 0:
                    continue
                    
                msg = json.loads(msg_raw)
                
                if msg['type'] in ['get', 'put']:
                    self.send_failed_response(msg)
                    
                elif msg['type'] == 'rpc':
                
                    if msg['leader'] == msg['src']:
                        self.last_heartbeat = time.time()
                        self.term = msg['term']
                        break
                    elif msg['term'] > self.term:
                        self.vote_in_election(msg['src'])
                        return
                    else:
                        continue
                        
        
        #after the election is over
        self.leader = msg['leader']
        
        
    def time_to_elect_new_leader(self):
        return time.time() - self.last_heartbeat > self.leader_timeout and not self.id == self.leader
    
    def get(self, key):
        if key in self.db:
            return self.db[key]
        else:
            return ""
        
    def put(self, key, value):
        self.db[key] = value
        self.commitedIndex += 1
        
    def addToLog(self, key, value):
        self.log.append((key, value))
        self.logIndex += 1
                
    def is_leader(self):
        return self.id == self.leader
        

kvstore = KVStore(my_id)
time.sleep(.5)
kvstore.last_heartbeat = time.time()
while True:
    if kvstore.time_to_elect_new_leader():
        kvstore.begin_election()
        continue
        
    ready = select.select([kvstore.sock], [], [], 0.1)[0]
    
    if kvstore.sock in ready:
        msg_raw = kvstore.sock.recv(32768)
        
        if len(msg_raw) == 0: 
            continue
            
        msg = json.loads(msg_raw)
        
        if msg['type'] == 'get':
            if kvstore.is_leader():
                value = kvstore.get(msg['key'])
                kvstore.send_get_response(msg, value)
            else:
                kvstore.redirectQueue.append(msg)
        
        elif msg['type'] == 'put':
                
            if kvstore.is_leader():
                kvstore.addToLog(msg['key'], msg['value'])
                kvstore.pendingRequests.append(msg)
                kvstore.send_RPC()
                
            else:
                kvstore.redirectQueue.append(msg)
                
        
        elif msg['type'] == 'request':
            if kvstore.is_leader():
                if msg['logIndex'] < kvstore.commitedIndex:
                    kvstore.send_specific_RPC(msg)
                    
                else:
                    kvstore.replicaCommits[msg['src']] = msg['logIndex']
                    print kvstore.replicaCommits
                
                    commitIndexes = []
                    for key in kvstore.replicaCommits:
                        commitIndexes.append(kvstore.replicaCommits[key])
                    while len(commitIndexes) > math.ceil(kvstore.num_replicas / 2.0) - 1:
                        commitIndexes.remove(min(commitIndexes))
                        
                    num_to_commit = min(commitIndexes) - kvstore.commitedIndex
                    
                    if num_to_commit > 0:
                        log_to_commit = kvstore.log[kvstore.commitedIndex + 1:kvstore.commitedIndex + num_to_commit + 1]
                        puts_to_respond_to = kvstore.pendingRequests[:num_to_commit]
                        
                        for key, value in log_to_commit:
                            kvstore.put(key, value)
                            
                        for request in puts_to_respond_to:
                            kvstore.send_put_response(request)
                        kvstore.pendingRequests = kvstore.pendingRequests[num_to_commit:]
                        
            
        elif msg['type'] == 'rpc':
            if msg['leader'] == msg['src']:
                
                if msg['leader'] != kvstore.leader:
                    if msg['term'] > kvstore.term:
                        kvstore.leader = msg['leader']
                        kvstore.term = msg['term']
                
                elif msg['term'] == kvstore.term:
                    for redirect in kvstore.redirectQueue:
                        kvstore.redirect_to_leader(redirect)
                    kvstore.redirectQueue = []
                    
                    kvstore.last_heartbeat = time.time()
                    commitedIndex = msg['commitedIndex']
                    logIndex = msg['logIndex']
                    arr = msg['array']
                    
                    
                    
                    if logIndex - len(arr) > kvstore.logIndex:
                        kvstore.send_request()
                        
                    else:
                        for key, value in arr[kvstore.logIndex - logIndex:]:
                            kvstore.addToLog(key, value)
                        
                        for key, value in kvstore.log[kvstore.commitedIndex + 1:]:
                            kvstore.put(key, value)
                            
                        kvstore.send_request()
                        
            else:
                if msg['logIndex'] >= kvstore.logIndex and msg['term'] >= kvstore.term:
                    #print kvstore.id + ":" + str(kvstore.index) + ", " + msg['src'] + ":" + str(msg['index'])
                    kvstore.vote_in_election(msg['src'])
                    continue
                
        
    clock = time.time()
    if clock - last > .1 and kvstore.leader == kvstore.id:
        kvstore.send_RPC()
        last = clock
        
