#!/usr/bin/env python3
""" Skeleton Implementation of Project 2 for NEU CS3700 """

import argparse
import json
import select
import socket
import os

##########################################################################################

# Message Fields
TYPE = "type"
SRCE = "src"
DEST = "dst"
MESG = "msg"
TABL = "table"

# Message Types
DATA = "data"
DUMP = "dump"
UPDT = "update"
RVKE = "revoke"
NRTE = "no route"

# Update Message Fields
NTWK = "network"
NMSK = "netmask"
ORIG = "origin"
LPRF = "localpref"
APTH = "ASPath"
SORG = "selfOrigin"     

# internal route info
CUST = "cust"
PEER = "peer"
PROV = "prov"


##########################################################################################

class Router:
  """ Your Router """
  def __init__(self, asn, networks):
    self.asn = asn
    self.routes = [] 
    self.updates = []
    self.revocation = []
    self.relations = {}
    self.sockets = {}
    for relationship in networks:
      network, relation = relationship.split("-")
      self.sockets[network] = socket.socket(socket.AF_UNIX, socket.SOCK_SEQPACKET)
      self.sockets[network].setblocking(0)
      self.sockets[network].connect(network)
      self.relations[network] = relation

  def decimalToBinaryString(self, ip):
    """ converts a given ip string to a binary string """
    binary = ".".join([bin(int(x)+256)[3:] for x in ip.split('.')])
    return str(binary)

  def longestCommonPrefix(self, stringArray):
      """ returns the longest common prefix between the strings in the string array """
      if len(stringArray) == 0: return ""
      longestPrefix = stringArray[0]
      for i in range(1,len(stringArray)):
         temp = ""
         if len(longestPrefix) == 0: break
         for j in range(len(stringArray[i])):
            if j<len(longestPrefix) and longestPrefix[j] == stringArray[i][j]:
               temp+=longestPrefix[j]
            else: break
         longestPrefix = temp
      return longestPrefix

  def findLongestPrefix(self, daddr):
    """ returns network(s) with the longest prefix between the daddr and all values in our routing table """
    potentialRoutes = []
    longestPrefix = 0
    for route in self.routes:
      prefix = self.longestCommonPrefix([self.decimalToBinaryString(daddr), self.decimalToBinaryString(route["network"])])
      if len(prefix) > longestPrefix:
        longestPrefix = len(prefix)
        potentialRoutes = [route]
      elif len(prefix) == longestPrefix:
        potentialRoutes.append(route)
    return potentialRoutes

  def lookup_routes(self, daddr):
    """ Lookup all valid routes (longest prefix) for an address """
    outroutes = self.findLongestPrefix(daddr)
    return outroutes

  def get_shortest_as_path(self, routes):
    """ select the route with the shortest AS Path """
    if len(routes) == 0:
      return []
    outroutes = []
    # assuming there will always be one route in the list given
    shortestRoute = len(routes[0]["ASPath"])
    # find the shortest route
    for i in range(len(routes)):
      currentRoute = len(routes[i]["ASPath"])
      if currentRoute < shortestRoute:
        shortestRoute = currentRoute
    # add shortest routes to output
    for i in range(len(routes)):
      currentRoute = len(routes[i]["ASPath"])
      if currentRoute == shortestRoute:
        outroutes.append(routes[i])
    return outroutes

  def get_highest_preference(self, routes):
    """ select the route with the shortest AS Path """
    if len(routes) == 0:
      return []
    outroutes = []
    # assuming there will always be one route in the list given
    highestPreference = routes[0]["localpref"]
    # find the highest preference
    for i in range(len(routes)):
      currentPreference = routes[i]["localpref"]
      if currentPreference > highestPreference:
        highestPreference = currentPreference
    # add routes with highest preference to output
    for i in range(len(routes)):
      currentPreference = routes[i]["localpref"]
      if currentPreference == highestPreference:
        outroutes.append(routes[i])
    return outroutes

  def get_self_origin(self, routes):
    """ select self originating routes """
    selfOrigin = []
    notSelfOrigin = []
    for i in range(len(routes)):
      if routes[i]["selfOrigin"]:
        selfOrigin.append(routes[i])
      else:
        notSelfOrigin.append(routes[i])
    if len(selfOrigin) > 0:
      return selfOrigin
    else:
      return notSelfOrigin

  def get_origin_routes(self, routes):
    """ select origin routes: IGP > EGP > UNK """
    egp = []
    igp = []
    unk = []
    # Populate fields above with respective routes
    for i in range(len(routes)):
      if routes[i]["origin"] == "EGP":
        egp.append(routes[i])
      elif routes[i]["origin"] == "IGP":
        igp.append(routes[i])
      else:
        unk.append(routes[i])
    if igp != []:
      return igp
    elif egp != []:
      return egp
    else:
      return unk

  def get_lowest_ip(self, routes):
    """ returns the lowest IP addrest in the given routes """
    outroutes = []
    currentLowest = -1
    for route in routes:
      currentIP = int("".join(route["peer"].split(".")))
      if currentLowest == -1 or currentIP > currentLowest:
        outroutes = [route]
      elif currentIP == currentLowest:
        outroutes.append(route)
    return outroutes

  def filter_relationships(self, srcif, routes):
    """ Don't allow Peer->Peer, Peer->Prov, or Prov->Peer forwards """
    outroutes = []
    sourceRelation = self.relations[srcif]
    for route in routes:
      destinationRelation = self.relations[route["peer"]]
      if sourceRelation == "cust" or destinationRelation == "cust": 
        outroutes.append(route)
    return outroutes

  def get_route(self, srcif, daddr):
    """ Select the best route for a given address """
    routes = self.lookup_routes(daddr)
    # Rules go here
    if routes:
      # 1. Highest Preference
      routes = self.get_highest_preference(routes)
      # 2. Self Origin
      routes = self.get_self_origin(routes)
      # 3. Shortest ASPath
      routes = self.get_shortest_as_path(routes)
      # 4. EGP > IGP > UNK
      routes = self.get_origin_routes(routes)
      # 5. Lowest IP Address
      routes = self.get_lowest_ip(routes)
      # 6. Filter Relationships
      routes = self.filter_relationships(srcif, routes)
    peer = None
    if routes:
      peer = routes[0]["peer"]
    return peer

  def forward(self, srcif, packet):
    """ Forward a data packet """
    socket = self.sockets[srcif]
    data = json.dumps(packet)
    socket.sendall(data.encode())
    return False

  def decrementNetmask(self, netmask, diff):
    """ shift the netmask by one """
    binaryString = "".join(self.decimalToBinaryString(netmask).split("."))
    newNetmask = binaryString[2:] 
    if diff < 0:
      newNetmask = newNetmask.replace("10", "11")
    elif diff > 0:
      newNetmask = newNetmask.replace("10", "00")
    output = ""
    output = output + str(int(newNetmask[:8],2)) + "."
    output = output + str(int(newNetmask[8:16],2)) + "."
    output = output + str(int(newNetmask[16:24],2)) + "."
    output = output + str(int(newNetmask[24:32],2))
    return output

  def coalesce(self, packet):
    """ coalesce any routes that are right next to each other, recursively """
    #Compare supplied packet to entries in forwarding table
    for route in self.routes:
    #Check if supplied packet and route have the same attributes
      if(packet["ASPath"] == route["ASPath"] and packet["localpref"] == route["localpref"]):
        if(packet["origin"] == route["origin"] and packet["selfOrigin"] == route["selfOrigin"]):
          #Check if packet and route are numerically adjecent
          routeNet = "".join(self.decimalToBinaryString(route["network"]).split(".")) # decimal string
          packetNet = "".join(self.decimalToBinaryString(packet["network"]).split("."))
          diff = int(routeNet, 2) - int(packetNet, 2) # 1 2 -1 -2
          if diff == 1 or diff == -256 or ((route["aggregationCount"] == 1 and packet["aggregationCount"] == 1)) :
            #Do the actual coalescing
            newRoute = {"network": route["network"], 
                "netmask": self.decrementNetmask(route["netmask"], diff), 
                "localpref": route["localpref"], 
                "ASPath": route["ASPath"], 
                "origin": route["origin"], 
                "selfOrigin": route["selfOrigin"],
                "peer": route["peer"],
                "aggregationCount": route["aggregationCount"] + 1}
            self.routes.remove(route)
            self.coalesce(newRoute)
            return True
    self.routes.append(packet)
    return True

  def send_new_packet(self, route, packet):
    """ send a newly created packet """
    packetCopySrc = ('.').join(route.split('.', 3)[:3]) + '.1' #Add a .1 to the end 
    packet["src"] = packetCopySrc
    packet["dst"] = route
    self.sockets[route].sendall(json.dumps(packet).encode())

  def update(self, srcif, packet):
    """ handle update packets """
    message = packet["msg"]
    currentUpdate = {"network": message["network"], 
        "netmask": message["netmask"], 
        "localpref": message["localpref"], 
        "ASPath": message["ASPath"], 
        "origin": message["origin"], 
        "selfOrigin": message["selfOrigin"],
        "peer": packet["src"],
        "aggregationCount": 0
        }
    # 1) save a copy of the announcement in case we need it later
    self.updates.append(currentUpdate)
    # 2) add an entry to our forwarding table through coalesce
    newASPath = message["ASPath"]
    newASPath.append(self.asn)
    self.coalesce(currentUpdate)
    # 3) potentially send copies of the announcement to neighboring routers 
    sourceRelation = self.relations[srcif]
    if sourceRelation == "cust":
      # a) update received from a customer: send update to all other neighbors
      for key in self.sockets:
        if key != srcif:
          self.send_new_packet(key, packet)
    elif sourceRelation == "prov" or sourceRelation == "peer":
      # b) update received from a peer or provider: only send update to our customers
      for key in self.sockets:
        socketRelation = self.relations[key]
        if socketRelation == "cust" and key != srcif:
          self.send_new_packet(key, packet)
    return False

  def revoke(self, packet):
    """ handle revoke packets """
    # 1) save a copy of the revocation, in case we need it later
    self.revocation.append(packet)
    # 2) remove the dead entry from list of stored updates
    neighborToRevokeFrom = packet["src"]
    networksToRevoke = packet["msg"] 
    for network in networksToRevoke:
        for x in range(len(self.updates) - 1):
          update = self.updates[x]
          sameNeighbor = update["peer"] == neighborToRevokeFrom 
          sameIP = update["network"] == network["network"]
          sameMask = update["netmask"] == network["netmask"]
          if sameNeighbor and sameIP and sameMask:
            self.updates.pop(x)
    # rebuild forwarding table from modified stored updates
    self.routes = []
    for update in self.updates:
      self.coalesce(update)
    # 3) potentially send copies of the announcement to neighboring routers
    revokeRelation = self.relations[neighborToRevokeFrom]
    if revokeRelation == "cust":
      # a) update received from a customer: send revoke to all other neighbors
      for key in self.sockets:
        if key != neighborToRevokeFrom:
          self.send_new_packet(key, packet)
    elif revokeRelation == "prov" or revokeRelation == "peer":
      # b) update received from a peer or provider: only send revoke to our customers
      for key in self.sockets:
        socketRelation = self.relations[key]
        if socketRelation == "cust" and key != neighborToRevokeFrom:
          self.send_new_packet(key, packet)
    return True

  def dump(self, packet):
    """ handles dump table requests """
    dumpMessage = []
    for route in self.routes:
      dumpMessage.append({
        "network": route["network"],
        "netmask": route["netmask"],
        "peer": route["peer"]
      })
    dumpPacket = {
      "src":  packet["dst"],          
      "dst":  packet["src"],         
      "type": "table",                   
      "msg": dumpMessage
    }
    self.forward(packet["src"], dumpPacket)
    return True

  def handle_packet(self, srcif, packet):
    """ dispatches a packet """
    messageType = packet["type"]
    if messageType == "update":
      return self.update(srcif, packet)
    elif messageType == "revoke":
      return self.revoke(packet)
    elif messageType == "data":
      route = self.get_route(srcif, packet["dst"])
      if route:
        socket = self.sockets[route]
        data = json.dumps(packet)
        socket.sendall(data.encode())
      else:
        data = {
          "src":  srcif[:-1] + "1",         
          "dst":  packet["src"],          
          "type": "no route",                   
          "msg":  {}
        }
        self.forward(srcif, data)
      return 
    elif messageType == "no route":
      return 
    elif messageType == "dump":
      self.dump(packet)
      return
    elif messageType == "table":
      return
    else:
      return
    return False

  def send_error(self, conn, msg):
    """ Send a no_route error message """
    return

  def run(self):
    """ main loop for the router """
    while True:
      socks = select.select(self.sockets.values(), [], [], 0.1)[0]
      for conn in socks:
        try:
          k = conn.recv(65535)
        except:
          # either died on a connection reset, or was SIGTERM's by parent
          return
        if k:
          for sock in self.sockets:
            if self.sockets[sock] == conn:
              srcif = sock
          msg = json.loads(k)
          if not self.handle_packet(srcif, msg):
            self.send_error(conn, msg)
        else:
          return

if __name__ == "__main__":
  PARSER = argparse.ArgumentParser(description='route packets')
  PARSER.add_argument('asn', metavar='asn', type=int, help="asn")
  PARSER.add_argument('networks', metavar='networks', type=str, nargs='+', help="networks")
  ARGS = PARSER.parse_args()
  Router(ARGS.asn, ARGS.networks).run()