#!/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:]

# number of replicas that constitutes a quorom
quorum_size = int(math.ceil((len(replica_ids) + 1) / 2.0))

# A State is one of:
FOLLOWER = "FOLLOWER"
LEADER = "LEADER"
CANDIDATE = "CANDIDATE"

# Current state of the replica
my_state = FOLLOWER

# ID number of the leader
leader_id = '0000'

# ID of replica voted as leader in this term - only for outstanding elections,
# will be None otherwise
voted_for = None

# current term number
term = 1

# count of votes received
vote_count = 0

# Random timeout before electing self as leader, in seconds
leader_timeout = None

def pick_random_timeout():
    global leader_timeout
    leader_timeout = random.randint(150, 300) / 1000.0

pick_random_timeout()


# key-value store for the leader
store = {}
# log entries; contains (command for machine, term, client id)
# also, first index is apparently supposed to be 1
# command for machine: ['GET', 123]
log = [{
    "command": {
        "type": 1,
        "key": 1,
        "val": 1,
    },
    "term": 1,
    "client_id": 1
}]
# index in the log of the most recent commit
commit_index = 0
# index of highest log entry applied to machine
last_applied = 0
# for each server, index of the next log entry that you need to send
next_index = {}
# for each server, index of highest log entry known to be replicated
match_index = {}

# Message Types:
GET = 'get'
PUT = 'put'
REQUEST_VOTE = 'request_vote'
SEND_VOTE = 'send_vote'
APPEND_ENTRIES = 'append_entries'
AE_REPLY = 'ae_reply'
FAIL = 'fail'
OK = 'ok'
REDIRECT = 'redirect'

# Connect to the network. All messages to/from other replicas and clients will
# occur over this socket
sock = socket.socket(socket.AF_UNIX, socket.SOCK_SEQPACKET)
sock.connect(my_id)

# last time a message from the leader was received
last_leader_msg = time.time()

# list of messages received while the leader is unknown
redirect_queue = []


def send(msg):
    sock.send(json.dumps(msg))

def get(msg):
    get_source = msg['src']
    get_mid = msg.get('MID', None)
    if my_state == LEADER:
        key = msg['key']

        command = {
            "type": GET,
            "key": key,
        }
        entry = {
            "command": command,
            "term": term,
            "client_id": get_source,
        }
        if get_mid:
            entry["MID"] = get_mid

        log.append(entry)
        send_append_entries()
    else:
        reply = {'src': my_id, 'dst': get_source, 'leader': leader_id}
        if get_mid:
            reply['MID'] = get_mid
        reply['type'] = REDIRECT
        send(reply)

def put(msg):
    global log

    put_source = msg['src']
    put_mid = msg.get('MID', None)
    if my_state == LEADER:
        key = msg['key']
        val = msg['value']

        command = {
            "type": PUT,
            "key": key,
            "val": val,
        }
        entry = {
            "command": command,
            "term": term,
            "client_id": put_source,
        }

        if put_mid:
            entry["MID"] = put_mid

        log.append(entry)
        send_append_entries()
    else:
        reply = {'src': my_id, 'dst': put_source, 'leader': leader_id}
        if put_mid:
            reply['MID'] = put_mid
        reply['type'] = REDIRECT
        send(reply)

def send_vote(msg):
    global voted_for, term, my_state, last_leader_msg

    # if recv term < my term, false
    # if i voted for someone already, false
    # if their log has everything in my log, vote for them
    # else update my term and vote for them

    received_term = msg['term']
    candidate_id = msg['src']
    last_log = msg['last_log']
    last_log_term = msg['last_log_term']

    reply = {'src': my_id, 'dst': candidate_id, 'type':SEND_VOTE }
    up_to_date = last_log_term > log[len(log) - 1]['term'] or (last_log_term == log[len(log) - 1]['term'] and last_log >= len(log) - 1)

    if received_term > term:
        # must downgrade LEADER -> FOLLOWER if we find out about an election
        my_state = FOLLOWER
	term = received_term
	voted_for = None

    if not up_to_date or received_term < term or (received_term == term and voted_for is not None):
        reply['leader'] = leader_id
        reply['granted'] = False
        reply['term'] = term
        send(reply)
    else:
        voted_for = candidate_id

        # must not timeout before election has time to finish
        last_leader_msg = time.time()
        #print my_id, 'has voted for', candidate_id, ' in term ', term, time.time()
        reply['leader'] = leader_id
        reply['granted'] = True
        reply['term'] = term
        send(reply)

def accept_vote(msg):
    global vote_count
    granted = msg['granted']

    if granted:
        vote_count += 1
        #print my_id, 'received vote from', msg['src'], vote_count, ' in term ', term
    if vote_count >= quorum_size:
        #print my_id, 'has won the vote - term: ', term
        become_leader()
        send_append_entries()


def become_leader():
    global my_state, leader_id, next_index, match_index
    my_state = LEADER
    leader_id = my_id

    next_index = {}
    match_index = {}
    for server_id in replica_ids:
        next_index[server_id] = len(log)
        match_index[server_id] = 0

should_print = False

def send_append_entries():
    global next_index, should_print, last_leader_msg
    # per every follower, send append-entries method with ones that they don't have
    for server_id in next_index.keys():
        next_log_entry = next_index[server_id]
        logs_to_send = log[next_log_entry:next_log_entry + 10]
	if next_log_entry - 1 >= len(log):
            #print my_id, "log size:", len(log), "next log entry:", next_log_entry
	    return

        prev_entry = log[next_log_entry - 1]
        msg = {'src': my_id, 'dst': server_id, 'leader': leader_id, 'term': term, 'type': APPEND_ENTRIES,
               'logs': logs_to_send, 'prev_log_idx': next_log_entry - 1, 'prev_log_term': prev_entry['term'],
               'leader_commit': commit_index}
        if len(logs_to_send) > 10:
            should_print = True
	    #print 'sending next log entry', next_log_entry, 'num logs', len(logs_to_send), 'total logs', len(log), 'to', server_id
            #print next_index
        send(msg)
    last_leader_msg = time.time()


def recv_append_entries_reply(msg):
    global match_index, next_index
    follower_id = msg['src']
    succeeded = msg['response']

    if succeeded:
        follower_index = msg['current_index']
        next_index[follower_id] = follower_index + 1
        match_index[follower_id] = follower_index
    else:
        #print follower_id, 'failed to receive'
        next_index[follower_id] -= 1

    sorted_matching_indices = sorted(match_index.values())
    quorum_commit = sorted_matching_indices[2]
    if quorum_commit >= len(log):
	#print my_id, "quorum commit:", quorum_commit, "log len:", len(log)
	return
    commit_entry = log[quorum_commit]
    if commit_entry['term'] == term and quorum_commit > commit_index:
        update_commit_idx(quorum_commit)


def append_new_entries(new_entries, prev_log_idx):
    global log
   #if len(new_entries) > 5:
        #print my_id, 'received', len(new_entries), 'currently has', len(log), 'prev', prev_log_idx
    for i in range(0, len(new_entries)):
        new_entry = new_entries[i]
        log_idx = prev_log_idx + i + 1
        if log_idx >= len(log):
            log += new_entries[i:]
#	    if len(new_entries) > 5:
                #print my_id, 'appended', len(new_entries[i:]), 'onto log', len(log), 'from', i, 'in new entries, sent starting with', prev_log_idx + 1
            break
        log_entry = log[log_idx]

        if new_entry['term'] != log_entry['term']:
            del log[log_idx:]
            log += new_entries[i:]
            #print my_id, 'deleted all from', log_idx, 'on, appended', len(new_entries), 'onto log', len(log)
            break

def update_commit_idx(leader_commit):
    global commit_index, last_applied
    if leader_commit > commit_index:
        commit_index = min(leader_commit, len(log) - 1)
    while last_applied < commit_index:
        last_applied += 1
        apply_command(last_applied)


def apply_command(log_index):
    entry = log[log_index]
    command = entry['command']
    command_type = command['type']
    key = command['key']

    if command_type == GET and my_state == LEADER:
        val = store.get(key, None)
        reply = { 'src': my_id, 'dst': entry['client_id'], 'leader': leader_id }
        mid = entry.get('MID', None)
        if mid:
            reply['MID'] = mid
        if val:
            reply['type'] = OK
            reply['value'] = val
        else:
            reply['type'] = FAIL
        send(reply)
    elif command_type == PUT:
        val = command['val']
        store[key] = val
        if my_state == LEADER:
            reply = {'src': my_id, 'dst': entry['client_id'], 'leader': leader_id}
            mid = entry.get('MID', None)
            if mid:
                reply['MID'] = mid
            reply['type'] = OK
            send(reply)


def recv_append_entries(msg):
    global leader_id, last_leader_msg, leader_timeout, voted_for, term, my_state, commit_index
    msg_leader = msg['leader']
    recv_term = msg['term']

    reply = {'src': my_id, 'dst': msg['src'], 'type': AE_REPLY, 'leader': leader_id }

    if recv_term >= term:
        term = recv_term
        reply['term'] = term
        my_state = FOLLOWER
        last_leader_msg = time.time()

        prev_log_idx = msg['prev_log_idx']
        prev_log_term = msg['prev_log_term']

        if prev_log_idx >= len(log):
            #print my_id, 'failed because prev entry out of bounds'
	    reply['response'] = False
	    send(reply)
            return

        my_prev_log_term = log[prev_log_idx]['term']

        if my_prev_log_term != prev_log_term:
            #print my_id, 'failed because wrong previous entry'
            #print my_prev_log_term, prev_log_term
            reply['response'] = False
            send(reply)
	    return

        new_entries = msg['logs']
        append_new_entries(new_entries, prev_log_idx)
        update_commit_idx(msg['leader_commit'])

        reply['response'] = True
        reply['current_index'] = len(log) - 1
#        if len(new_entries) > 5:
	    #print my_id, 'replying to AE', reply
        send(reply)

        if msg_leader != leader_id:
            #print my_id, 'has accepted leader:', msg_leader, 'term: ', term, time.time()
            leader_id = msg_leader
            pick_random_timeout()
            voted_for = None
    else:
        reply['term'] = term
        reply['response'] = False
        #print my_id, 'failed because wrong term'
        return


def conduct_election():
    global leader_id, my_state, vote_count, term, voted_for, last_leader_msg

    my_state = CANDIDATE
    term += 1
    vote_count = 1
    voted_for = my_id
    pick_random_timeout()
    last_leader_msg = time.time()
    request_vote_msg = { 'src': my_id, 'dst': 'FFFF', 'leader': leader_id, 'term': term, 'last_log': len(log) - 1, 
                         'last_log_term': log[len(log)-1]['term'], 'type': REQUEST_VOTE }
    send(request_vote_msg)



if my_id == '0000':
    become_leader()


while True:
    ready = select.select([sock], [], [], 0.01)[0]

    if sock in ready:
        msg_raw = sock.recv(32768)

        if len(msg_raw) == 0: continue
        msg = json.loads(msg_raw)	

        if msg['type'] == GET:
            get(msg)
        if msg['type'] == PUT:
            put(msg)
        if msg['type'] == REQUEST_VOTE:
            send_vote(msg)
        if msg['type'] == SEND_VOTE and my_state == CANDIDATE:
            accept_vote(msg)
        if msg['type'] == APPEND_ENTRIES:
            recv_append_entries(msg)
        if msg['type'] == AE_REPLY:
            recv_append_entries_reply(msg)

    clock = time.time()
    if clock - last_leader_msg > leader_timeout:
        # trigger leader elections if a follower
        if my_state != LEADER:
            conduct_election()
    if my_state == LEADER and clock - last_leader_msg > 0.1:
        # send mass heartbeat
        send_append_entries()
        last_leader_msg = clock
