#! /usr/bin/python2.7 
# -*- coding: utf8 -*-

import sys
import os, subprocess, shlex, re, gzip
# Just for DEBUG
#os.chdir('/Users/sofiasilva/GitHub/cool_bgp_stats')
from get_file import get_file
import bgp_rib
import pickle
import radix
import datetime, calendar
import pandas as pd
import hashlib
import ipaddress

# For some reason in my computer os.getenv('PATH') differs from echo $PATH
# /usr/local/bin is not in os.getenv('PATH')
# it also works in matong
bgpdump = '/usr/local/bin/bgpdump'

class BGPDataHandler:
    DEBUG = False
    files_path = ''
    KEEP = False
    RIBfiles = False
    COMPRESSED = False
  
    # STRUCTURES WITH CURRENT ROUTING DATA  
    # Data Frame containing routing info from RIB file or file with 'show ip bgp' output
    bgp_data = pd.DataFrame()
   
   # Radix indexed by routed IPv4 prefix containing the indexes of the rows in
    # the bgp_data Data Frame that contain info of BGP announcements of the IPv4 prefix
    ipv4_prefixes_indexes_radix = radix.Radix()

    # Radix indexed by routed IPv6 prefix containing the indexes of the rows in
    # the bgp_data Data Frame that contain info of BGP announcements of the IPv6 prefix
    ipv6_prefixes_indexes_radix = radix.Radix()
    
    # Dictionary indexed by AS containing all the prefixes originated by each AS
    ASes_originated_prefixes_dic = dict()

    # Dictionary indexed by AS containing all the prefixes propagated by each AS
    ASes_propagated_prefixes_dic = dict()

    # Numeric variable with the longest IPv4 prefix length
    ipv4_longest_pref = -1

    # Numeric variable with the longest IPv6 prefix length
    ipv6_longest_pref = -1   

    # STRUCTURES WITH TEMPORAL DATA
    # Radix indexed by routed IPv4 prefix containing as values dictionaries
    # with the following keys:
    # * periodsSeen - the value for this key is a list of tuples representing
    # periods of time during which the corresponding IPv4 prefix was seen
    # Each tuple has the format (startDate, endDate)
    # * firstSeen - the value for this key is the first date in which the
    # IPv4 prefix was seen
    # * lastSeen - the value for this key is the last date in which the
    # IPv4 prefix was seen
    # * totalDays - the value for this key is the number of days during
    # which the IPv4 prefix was seen
    ipv4_prefixesDates_radix = radix.Radix()

    # Radix indexed by routed IPv6 prefix containing as values dictionaries
    # with the following keys:
    # * periodsSeen - the value for this key is a list of tuples representing
    # periods of time during which the corresponding IPv6 prefix was seen
    # Each tuple has the format (startDate, endDate)
    # * firstSeen - the value for this key is the first date in which the
    # IPv6 prefix was seen
    # * lastSeen - the value for this key is the last date in which the
    # IPv6 prefix was seen
    # * totalDays - the value for this key is the number of days during
    # which the IPv6 prefix was seen
    ipv6_prefixesDates_radix = radix.Radix()

    # Dictionary indexed by origin ASN (ASN that originates at least one prefix)
    # It contains as values dictionaries with the following keys:
    # * periodsSeen - the value for this key is a list of tuples representing
    # periods of time during which the corresponding ASN originated prefixes
    # Each tuple has the format (startDate, endDate)
    # * firstSeen - the value for this key is the first date in which the
    # ASN originated prefixes
    # * lastSeen - the value for this key is the last date in which the
    # ASN originated prefixes
    # * totalDays - the value for this key is the number of days during
    # which the ASN originated prefixes
    originASesDates_dict = dict()
    
    # Dictionary indexed by middle ASN (ASN that propagates at least one prefix)
    # It contains as values dictionaries with the following keys:
    # * periodsSeen - the value for this key is a list of tuples representing
    # periods of time during which the corresponding ASN prpagated prefixes
    # Each tuple has the format (startDate, endDate)
    # * firstSeen - the value for this key is the first date in which the
    # ASN propagated prefixes
    # * lastSeen - the value for this key is the last date in which the
    # ASN propagated prefixes
    # * totalDays - the value for this key is the number of days during
    # which the ASN propagated prefixes
    middleASesDates_dict = dict()
         
    # When we instantiate this class we set the variable with the path to the
    # folder we will use to store files (files_path), we set a boolean variable
    # specifying whether we want to KEEP the intermediate files generated by 
    # different functions, we set another boolean variable specifying whether
    # the routing files we will be working with are RIB files (if False we assume
    # they are outputs of the 'show ip bgp' command) and we set another boolean
    # variable specifying whether the routing files we will be working with are
    # COMPRESSED
    def __init__(self, DEBUG, files_path, KEEP, RIBfiles, COMPRESSED):
        self.DEBUG = DEBUG
        self.files_path = files_path
        self.KEEP = KEEP
        self.RIBfiles = RIBfiles
        self.COMPRESSED = COMPRESSED

        sys.stderr.write("BGPDataHandler instantiated successfully! Remember to load the data structures.\n")
    
    # This function loads the class variables ipv4_prefixesDates and ipv6_prefixesDates
    # from a previously generated pickle file containing Radixes indexed by
    # routed prefix containing as values dictionaries with the following keys:
    # * periodsSeen - the value for this key is a list of tuples representing
    # periods of time during which the corresponding prefix was seen
    # Each tuple has the format (startDate, endDate)
    # * firstSeen - the value for this key is the first date in which the
    # prefix was seen
    # * lastSeen - the value for this key is the last date in which the
    # prefix was seen
    # * totalDays - the value for this key is the number of days during
    # which the prefix was seen
    def loadPrefixDatesFromFiles(self, ipv4_prefixesDates_file, ipv6_prefixesDates_file):
        if ipv4_prefixesDates_file != '':        
            self.ipv4_prefixesDates_radix = pickle.load(open(ipv4_prefixesDates_file, 'rb'))
            sys.stderr.write("Radix with dates in which IPv4 prefixes were seen was loaded successfully!\n")
    
        if ipv6_prefixesDates_file != '':        
            self.ipv6_prefixesDates_radix = pickle.load(open(ipv6_prefixesDates_file, 'rb'))
            sys.stderr.write("Radix with dates in which IPv6 prefixes were seen was loaded successfully!\n")

    # This function loads the class variable originASesDates from a previously
    # generated pickle file containing a originASesDates dictionary 
    def loadOriginASesDatesFromFile(self, originASesDates_file):
        if originASesDates_file != '':        
            self.originASesDates_dict = pickle.load(open(originASesDates_file, 'rb'))
            sys.stderr.write("Dictionary with dates in which ASNs originated prefixes was loaded successfully!\n")
    
    # This function loads the class variable middleASesDates from a previously
    # generated pickle file containing a middleASesDates dictionary 
    def loadMiddleASesDatesFromFile(self, middleASesDates_file):
        if middleASesDates_file != '':        
            self.middleASesDates_dict = pickle.load(open(middleASesDates_file, 'rb'))
            sys.stderr.write("Dictionary with dates in which ASNs propagated prefixes was loaded successfully!\n")
    
    # This function loads the data structures of the class from previously
    # generated pickle files containing the result of already processed routing data
    def loadStructuresFromFiles(self, bgp_data_file, ipv4_prefixes_indexes_file,\
                                ipv6_prefixes_indexes_file, ASes_originated_prefixes_file,\
                                ASes_propagated_prefixes_file):
     
        self.bgp_data = pickle.load(open(bgp_data_file, "rb"))
        self.ipv4_prefixes_indexes_radix = pickle.load(open(ipv4_prefixes_indexes_file, "rb"))
        self.ipv6_prefixes_indexes_radix = pickle.load(open(ipv6_prefixes_indexes_file, "rb"))
        self.ASes_originated_prefixes_dic = pickle.load(open(ASes_originated_prefixes_file, "rb"))
        self.ASes_propagated_prefixes_dic = pickle.load(open(ASes_propagated_prefixes_file, "rb"))
        self.setLongestPrefixLengths()
        sys.stderr.write("Class data structures were loaded successfully!\n")
        return True
        
    # This function processes the routing data contained in the files to which
    # the URLs in the urls_file point, and loads the data structures of the class
    # with the results from this processing
    def loadStructuresFromURLSfile(self, urls_file):
        bgp_data, ipv4_prefixes_indexes_radix, ipv6_prefixes_indexes_radix,\
            ASes_originated_prefixes_dic, ASes_propagated_prefixes_dic,\
            ipv4_longest_pref, ipv6_longest_pref  =\
                        self.processMultipleFiles(files_list=urls_file,\
                                                isList=False, containsURLs=True)
                        
        self.bgp_data = bgp_data
        self.ipv4_prefixes_indexes_radix = ipv4_prefixes_indexes_radix
        self.ipv6_prefixes_indexes_radix = ipv6_prefixes_indexes_radix
        self.ASes_originated_prefixes_dic = ASes_originated_prefixes_dic
        self.ASes_propagated_prefixes_dic = ASes_propagated_prefixes_dic
        
        if ipv4_longest_pref != -1:
            self.ipv4_longest_pref = ipv4_longest_pref
        else:
            self.ipv4_longest_pref = 32
        if ipv6_longest_pref != -1:
            self.ipv6_longest_pref = ipv6_longest_pref
        else:
            self.ipv6_longest_pref = 64

        sys.stderr.write("Class data structures were loaded successfully!\n")
        return True
                                                
    # This function processes the routing data contained in the routing_file
    # and loads the data structures of the class with the results from this processing                                           
    def loadStructuresFromRoutingFile(self, routing_file):
        readable_file_name =  self.getReadableFile(routing_file, False)
        
        if readable_file_name != '':
            bgp_data, ipv4_prefixes_indexes_radix, ipv6_prefixes_indexes_radix,\
                ASes_originated_prefixes_dic, ASes_propagated_prefixes_dic,\
                ipv4_longest_pref, ipv6_longest_pref =\
                                    self.processReadableDF(readable_file_name)
                                
            self.bgp_data = bgp_data
            self.ipv4_prefixes_indexes_radix = ipv4_prefixes_indexes_radix
            self.ipv6_prefixes_indexes_radix = ipv6_prefixes_indexes_radix
            self.ASes_originated_prefixes_dic = ASes_originated_prefixes_dic
            self.ASes_propagated_prefixes_dic = ASes_propagated_prefixes_dic
            
            if ipv4_longest_pref != -1:
                self.ipv4_longest_pref = ipv4_longest_pref
            else:
                self.ipv4_longest_pref = 32
            if ipv6_longest_pref != -1:
                self.ipv6_longest_pref = ipv6_longest_pref
            else:
                self.ipv6_longest_pref = 64
    
            sys.stderr.write("Class data structures were loaded successfully!\n")
            return True
        else:
            sys.stderr.write("Could not process routing file.\n")
            return False

    
    # This function processes the routing data contained in the archive folder
    # provided, and loads the data structures of the class with the results
    # from this processing       
    def loadStructuresFromArchive(self, archive_folder, extension, startDate, endDate):
        historical_files = self.getPathsToHistoricalData(archive_folder, extension)
        
        if historical_files == '':
            sys.stderr.write("Archive is empty!\n")
            return False

        mostRecent_routing_file  =\
                        self.getMostRecentFromHistoricalList(historical_files, endDate)
        
        mostRecent_readable = self.getReadableFile(mostRecent_routing_file,\
                                False)

        # In order for the most recent file not to be processed twice,
        # we load data from this file into the prefixesDates Radixes
        # now that we have the readable file available
        self.loadHistoricalDataFromFile(mostRecent_readable, True)

        # We then load the rest of the data structures
        bgp_data, ipv4_prefixes_indexes_radix, ipv6_prefixes_indexes_radix,\
            ASes_originated_prefixes_dic, ASes_propagated_prefixes_dic,\
            ipv4_longest_pref, ipv6_longest_pref =\
                                self.processReadableDF(mostRecent_readable)
        
        self.bgp_data = bgp_data
        self.ipv4_prefixes_indexes_radix = ipv4_prefixes_indexes_radix
        self.ipv6_prefixes_indexes_radix = ipv6_prefixes_indexes_radix
        self.ASes_originated_prefixes_dic = ASes_originated_prefixes_dic
        self.ASes_propagated_prefixes_dic = ASes_propagated_prefixes_dic
        
        if ipv4_longest_pref != -1:
            self.ipv4_longest_pref = ipv4_longest_pref
        else:
            self.ipv4_longest_pref = 32
        if ipv6_longest_pref != -1:
            self.ipv6_longest_pref = ipv6_longest_pref
        else:
            self.ipv6_longest_pref = 64

        sys.stderr.write("Class data structures were loaded successfully!\n")

        # Finally, we load the prefixesDates Radixes and the originASesDates
        # dictionary with the rest of the routing files from the archive,
        # providing the name of the most recent file in order for it to be skipped.
        self.loadDatesStructures(historical_files, startDate, endDate, mostRecent_routing_file)
        sys.stderr.write("Radixes with dates in which prefixes were seen were loaded successfully!\n")
        
        return True

    # This function returns a path to the most recent file in the provided list 
    # of historical files
    def getMostRecentFromHistoricalList(self, historical_files, endDate):
        files_list_obj = open(historical_files, 'r')

        mostRecentDate = 0
        mostRecentFile = ''
        
        for line in files_list_obj:
            if not line.startswith('#') and line.strip() != '':
                date = self.getDateFromFileName(line.strip())
                
                if date > mostRecentDate:
                    # We add 1 to the endDate because the files in the archive
                    # have routing data for the day before of the date in the
                    # name of the file
                    if endDate == '' or (endDate != '' and date <= int(endDate)+1):
                        mostRecentDate = date
                        mostRecentFile = line.strip()
        
        return mostRecentFile
        
    def getDateFromFileName(self, filename):
        date = ''
        
        dates = re.findall('[1-2][9,0][0,1,8,9][0-9]-[0-1][0-9]-[0-3][0-9]',\
                    filename)
                    
        if len(dates) > 0:
            date = int(dates[0][0:4]+dates[0][5:7]+dates[0][8:10])
        else:
            dates = re.findall('[1-2][9,0][0,1,8,9][0-9][0-1][0-9][0-3][0-9]',\
                        filename)
            if len(dates) > 0:
                date = int(dates[0])
        return date
    
    # This function loads the prefixesDates Radixes (class variables) and
    # the originASesDates dictionary with the routing data from the files
    # listed in the historical_files file and which have a date more recent
    # than startDate in case startDate is provided. If startDate is not
    # provided, all the files listed in the historical_files file will be processed.
    def loadDatesStructures(self, historical_files, startDate, endDate, mostRecent):

        files_list_obj = open(historical_files, 'r')
        
        i = 0
        for line in files_list_obj:
            line = line.strip()
            if line == mostRecent:
                continue

            if startDate != '' or endDate != '':
                file_date = self.getDateFromFileName(line)
                
                if file_date == '' or\
                    (startDate != '' and int(file_date) < int(startDate)) or\
                    (endDate != '' and int(file_date) > int(endDate)+1):
                    # We add 1 to the endDate because the files in the archive
                    # have routing data for the day before of the date in the
                    # name of the file
                    continue
                    
            if not line.startswith('#') and line != '':
                 # If we work with several routing files
                sys.stderr.write("Starting to work with %s\n" % line)

                self.loadHistoricalDataFromFile(line, False)
                        
            i += 1
            if self.DEBUG and i > 1:
                break

    def updateDatesDict(self, dictionary, date):
        if date < dictionary['firstSeen']:
            dictionary['firstSeen'] = date
                
        if date > dictionary['lastSeen']:
            dictionary['lastSeen'] = date
            
        dateReady = False
        for period in dictionary['periodsSeen']:
            if date >= period[0]:
                if date <= period[1]:
                    dateReady = True
                    continue
                elif date == period[1]+1:
                    dictionary['periodsSeen'].remove(period)
                    dictionary['periodsSeen'].append((period[0], date))
                    dictionary['totalDays'] += 1
                    dateReady = True
        if not dateReady:
            dictionary['periodsSeen'].append((date, date))
            dictionary['totalDays'] = 1
                    
    # This function loads the prefixesDates Radixes and the originASesDates
    # dictionary with the routing data from the routing_file provided
    def loadHistoricalDataFromFile(self, routing_file, isReadable):
        prefixes, originASes, middleASes, date =\
                        self.getPrefixesASesAndDate(routing_file, isReadable)

        for pref in prefixes:
            network = ipaddress.ip_network(unicode(pref, 'utf-8'))
            
            if network.version == 4:
                prefixesDates = self.ipv4_prefixesDates_radix
            else:
                prefixesDates = self.ipv6_prefixesDates_radix

            pref_node = prefixesDates.search_exact(pref)
            if pref_node is not None:
                self.updateDatesDict(pref_node.data, date)
            else:
                pref_node = prefixesDates.add(pref)
                pref_node.data['periodsSeen'] = [(date, date)]
                pref_node.data['firstSeen'] = date
                pref_node.data['lastSeen'] = date
                pref_node.data['totalDays'] = 1
        
        for asn in originASes:
            if asn is None or asn == 'nan':
                continue
            elif '{' in asn:
                # If the asn field contains a bracket ({}), there is an as-set
                # in first place in the AS path, therefore, we split it
                # (leaving the brackets out) and consider each AS separately.
                asnList = asn[1:-1] .split(',')
                for asn in asnList:
                    if asn in self.originASesDates_dict:
                        self.updateDatesDict(self.originASesDates_dict[asn], date)
                    else:
                        self.originASesDates_dict[asn] = dict()
                        self.originASesDates_dict[asn]['periodsSeen'] = [(date, date)]
                        self.originASesDates_dict[asn]['firstSeen'] = date
                        self.originASesDates_dict[asn]['lastSeen'] = date
                        self.originASesDates_dict[asn]['totalDays'] = 1
            else:
                asn = int(asn)
                if asn in self.originASesDates_dict:
                    self.updateDatesDict(self.originASesDates_dict[asn], date)
                else:
                    self.originASesDates_dict[asn] = dict()
                    self.originASesDates_dict[asn]['periodsSeen'] = [(date, date)]
                    self.originASesDates_dict[asn]['firstSeen'] = date
                    self.originASesDates_dict[asn]['lastSeen'] = date
                    self.originASesDates_dict[asn]['totalDays'] = 1
                
        for asn in middleASes:
            if asn is None or asn == 'nan':
                continue
            elif '{' in asn:
                asnList = asn[1:-1] .split(',')
                for asn in asnList:
                    if asn in self.middleASesDates_dict:
                        self.updateDatesDict(self.middleASesDates_dict[asn], date)
                    else:
                        self.middleASesDates_dict[asn] = dict()
                        self.middleASesDates_dict[asn]['periodsSeen'] = [(date, date)]
                        self.middleASesDates_dict[asn]['firstSeen'] = date
                        self.middleASesDates_dict[asn]['lastSeen'] = date
                        self.middleASesDates_dict[asn]['totalDays'] = 1
            else:
                asn = int(asn)
                if asn in self.middleASesDates_dict:
                    self.updateDatesDict(self.middleASesDates_dict[asn], date)
                else:
                    self.middleASesDates_dict[asn] = dict()
                    self.middleASesDates_dict[asn]['periodsSeen'] = [(date, date)]
                    self.middleASesDates_dict[asn]['firstSeen'] = date
                    self.middleASesDates_dict[asn]['lastSeen'] = date
                    self.middleASesDates_dict[asn]['totalDays'] = 1
    
    # This function returns a list of prefixes for which the routing_file has
    # announcements, a list of the origin ASes included in the routing_file,
    # a list of the middle ASes included in the routing file
    # and the date of the routing file.
    # The routing file is assumed to include routing data for a single day,
    # therefore the date is taken from the timestamp of the first row in the
    # bgp_df DataFrame.
    def getPrefixesASesAndDate(self, routing_file, isReadable):
        if not isReadable:
            readable_file_name = self.getReadableFile(routing_file, False)
        else:
            readable_file_name = routing_file
        
        if readable_file_name == '':
            return [], [], ''

        bgp_df = pd.read_table(readable_file_name, header=None, sep='|',\
                                index_col=False, usecols=[1,3,5,6,7],\
                                names=['timestamp',\
                                        'peer',\
                                        'prefix',\
                                        'ASpath',\
                                        'origin'])

        if self.DEBUG:
            bgp_df = bgp_df[0:10]
            
        date = datetime.datetime.utcfromtimestamp(bgp_df['timestamp'].tolist()[0]).strftime('%Y%m%d')
        
        # To get the origin ASes and middle ASes we split the ASpath column
        paths_parts = bgp_df.ASpath.str.rsplit(' ', n=1, expand=True)

        return set(bgp_df['prefix'].tolist()),\
                set(paths_parts[1].tolist()),\
                set([item for sublist in paths_parts[0].tolist() for item in\
                        str(sublist).split()]), date
                                        
        
    # This function downloads and processes all the files in the provided list.
    # The boolean variable containsURLs must be True if the files_list is a list
    # of URLs or False if it is a list of paths
    def processMultipleFiles(self, files_list, isList, containsURLs):
        if not isList:
            files_list = open(files_list, 'r')
                    
        bgp_data = pd.DataFrame()
        ipv4_prefixes_indexes_radix = radix.Radix()
        ipv6_prefixes_indexes_radix = radix.Radix()
        ASes_originated_prefixes_dic = dict()
        ASes_propagated_prefixes_dic = dict()
        ipv4_longest_pref = -1
        ipv6_longest_pref = -1
        
        i = 0
        for line in files_list:
            if not line.startswith('#') and line.strip() != '':
                # If we work with several routing files
                sys.stderr.write("Starting to work with %s\n" % line)

                # We obtain partial data structures
                if containsURLs:
                    readable_file_name =  self.getReadableFile(line.strip(), True)          
                    
                    if readable_file_name == '':
                        continue
                    
                    bgp_data_partial, ipv4_prefixes_indexes_radix_partial,\
                        ipv6_prefixes_indexes_radix_partial,\
                        ASes_originated_prefixes_dic_partial,\
                        ASes_propagated_prefixes_dic_partial,\
                        ipv4_longest_pref_partial, ipv6_longest_pref_partial =\
                                self.processReadableDF(readable_file_name)
                else:
                    readable_file_name =  self.getReadableFile(line.strip(), False)
                    
                    if readable_file_name == '':
                        continue
                    
                    bgp_data_partial, ipv4_prefixes_indexes_radix_partial,\
                        ipv6_prefixes_indexes_radix_partial,\
                        ASes_originated_prefixes_dic_partial,\
                        ASes_propagated_prefixes_dic_partial,\
                        ipv4_longest_pref_partial, ipv6_longest_pref_partial =\
                                self.processReadableDF(readable_file_name)
                
                # and then we merge them into the general data structures
                bgp_data = pd.concat([bgp_data, bgp_data_partial])
    
                for prefix in ipv4_prefixes_indexes_radix_partial.prefixes():
                    node_partial = ipv4_prefixes_indexes_radix_partial.search_exact(prefix)
                    node_gral= ipv4_prefixes_indexes_radix.search_exact(prefix)
                    if node_gral is not None:
                        node_gral.data['indexes'].update(list(node_partial.data['indexes']))
                    else:
                        node_gral = ipv4_prefixes_indexes_radix.add(prefix)
                        node_gral.data['indexes'] = node_partial.data['indexes']

                for prefix in ipv6_prefixes_indexes_radix_partial.prefixes():
                    node_partial = ipv6_prefixes_indexes_radix_partial.search_exact(prefix)
                    node_gral= ipv6_prefixes_indexes_radix.search_exact(prefix)
                    if node_gral is not None:
                        node_gral.data['indexes'].update(list(node_partial.data['indexes']))
                    else:
                        node_gral = ipv6_prefixes_indexes_radix.add(prefix)
                        node_gral.data['indexes'] = node_partial.data['indexes']
                        
                for aut_sys, prefixes in ASes_originated_prefixes_dic_partial.iteritems():
                    if aut_sys in ASes_originated_prefixes_dic.keys():
                        ASes_originated_prefixes_dic[aut_sys].update(list(prefixes))
                    else:
                        ASes_originated_prefixes_dic[aut_sys] = prefixes

                for aut_sys, prefixes in ASes_propagated_prefixes_dic_partial.iteritems():
                    if aut_sys in ASes_propagated_prefixes_dic.keys():
                        ASes_propagated_prefixes_dic[aut_sys].update(list(prefixes))
                    else:
                        ASes_propagated_prefixes_dic[aut_sys] = prefixes
                        
                if ipv4_longest_pref_partial > ipv4_longest_pref:
                    ipv4_longest_pref = ipv4_longest_pref_partial
                    
                if ipv6_longest_pref_partial > ipv6_longest_pref:
                    ipv6_longest_pref = ipv6_longest_pref_partial
            
            i += 1
            if self.DEBUG and i > 1:
                break

        if not isList:        
            files_list.close()
        
        return bgp_data, ipv4_prefixes_indexes_radix, ipv6_prefixes_indexes_radix,\
            ASes_originated_prefixes_dic, ASes_propagated_prefixes_dic,\
            ipv4_longest_pref, ipv6_longest_pref
        
    # This function converts a file containing the output of the 'show ip bgp' command
    # to a file in the same format used for BGPDump outputs
    def convertBGPoutput(self, routing_file):
        output_file_name = '%s/%s.readable' % (self.files_path, '.'.join(routing_file.split('/')[-1].split('.')[:-1]))
        output_file = open(output_file_name, 'w')
        
        i = 0
        # load routing table info  (the next loop does it automatically)
        for entry_n, bgp_entry in enumerate(bgp_rib.BGPRIB.parse_cisco_show_ip_bgp_generator(routing_file)):
            date = bgp_entry[8]
#           date_part = str(date)[0:8]
#           time_part = str(date)[8:12]
            timestamp = calendar.timegm(datetime.datetime.strptime(date, "%Y%m%d%H%M").timetuple())
            next_hop = bgp_entry[2]
            prefix = bgp_entry[0]
            as_path = bgp_entry[6]
            
            if as_path:
                nextas = as_path[0]
            else:
            	nextas = ''

            if bgp_entry[7] == 'i':
                origin = "IGP"
            elif bgp_entry[7] == 'e':
                origin = "EGP"
            elif bgp_entry[7] == "?":
                origin = "INCOMPLETE"
            else:
                sys.stderr.write("Found invalid prefix at bgp entry %s, with content %s, on file %s\n" %(entry_n, bgp_entry, routing_file))
            	# ignore this line and continue
                continue

            # save information

            #the order for each line is
            #TABLE_DUMP2|date|B|nexthop|NextAS|prefix|AS_PATH|Origin
            output_file.write('TABLE_DUMP|'+str(timestamp)[:-2]+'|B|'+next_hop+'|'+nextas+'|'+prefix+'|'+" ".join(as_path)+'|'+origin+'\n')
    
            i += 1
            if self.DEBUG and i > 10:
                break
            
        output_file.close()
        
        return output_file_name
 
    # This function processes a readable file with routing info
    # putting all the info into a Data Frame  
    def processReadableDF(self, readable_file_name):
        
        ipv4_prefixes_indexes_radix = radix.Radix()
        ipv6_prefixes_indexes_radix = radix.Radix()
        ASes_originated_prefixes_dic = dict()
        ASes_propagated_prefixes_dic = dict()
        
        ipv4_longest_prefix = -1
        ipv6_longest_prefix = -1
        
        bgp_df = pd.read_table(readable_file_name, header=None, sep='|',\
                                index_col=False, usecols=[1, 3,5,6,7],\
                                names=['timestamp',\
                                        'peer',\
                                        'prefix',\
                                        'ASpath',\
                                        'origin'])
        
        if bgp_df.shape[0] > 0:
        
            if self.DEBUG:
                bgp_df = bgp_df[0:10]
                
            # We create an index that is unique even amongst different routing files
            # so that we can merge partial data structures into a single structure
            file_id = hashlib.md5(readable_file_name).hexdigest()
            bgp_df['source_file'] = '%s_' % file_id
            bgp_df['index'] = bgp_df.index.astype(str)
            bgp_df['index'] = bgp_df['source_file'] + bgp_df['index']
            bgp_df.index = bgp_df['index']
            
             # We add a column to the Data Frame with the corresponding date
            bgp_df['date'] = bgp_df.apply(lambda row: datetime.datetime.utcfromtimestamp(row['timestamp']).strftime('%Y%m%d'), axis=1)
            
            ASpath_parts = bgp_df.ASpath.str.rsplit(' ', n=1, expand=True)
            bgp_df['middleASes'] = ASpath_parts[0]
            bgp_df['originAS'] = ASpath_parts[1]
            
            for prefix, prefix_subset in bgp_df.groupby('prefix'):
                network = ipaddress.ip_network(unicode(prefix, 'utf-8'))
                if network.version == 4:
                    if network.prefixlen > ipv4_longest_prefix:
                        ipv4_longest_prefix = network.prefixlen
                    prefixes_indexes_radix = ipv4_prefixes_indexes_radix
                    
                else:
                    if network.prefixlen > ipv6_longest_prefix:
                        ipv6_longest_prefix = network.prefixlen 
                    prefixes_indexes_radix = ipv6_prefixes_indexes_radix
                    
                node = prefixes_indexes_radix.add(prefix)
                node.data['indexes'] = set(prefix_subset.index)
                            
                for middleASes in prefix_subset['middleASes']:
                    for asn in middleASes.split():
                        asn = int(asn)
                        if asn in ASes_propagated_prefixes_dic.keys():
                            if prefix not in ASes_propagated_prefixes_dic[asn]:
                                ASes_propagated_prefixes_dic[asn].add(prefix)
                        else:
                            ASes_propagated_prefixes_dic[asn] = set([prefix])
                            
            for originAS, originAS_subset in bgp_df.groupby('originAS'):
                originAS = int(originAS)
                ASes_originated_prefixes_dic[originAS] = set(originAS_subset['prefix'])
            
            if not self.KEEP:
                try:
                    os.remove(readable_file_name)
                except OSError:
                    pass
            
        return bgp_df, ipv4_prefixes_indexes_radix, ipv6_prefixes_indexes_radix,\
                ASes_originated_prefixes_dic, ASes_propagated_prefixes_dic,\
                ipv4_longest_prefix, ipv6_longest_prefix

    # This function downloads a routing file if the source provided is a URL
    # If the file is COMPRESSED, it is unzipped
    # and finally it is processed using BGPdump if the file is a RIBfile
    # or using the functions provided by get_rib.py is the file contains the
    # output of the 'show ip bgp' command
    # The path to the resulting readable file is returned
    def getReadableFile(self, source, isURL):
    
        source_filename = source.split('/')[-1]
        
        # If a routing file is not provided, download it from the provided URL        
        if isURL:
            routing_file = '%s/%s' % (self.files_path, source_filename)
            get_file(source, routing_file)
            source = routing_file
        
        # If the routing file is compressed we unzip it
        if self.COMPRESSED:
            output_file = '%s/%s' % (self.files_path,\
                                os.path.splitext(source)[0].split('/')[-1])
            
            with gzip.open(source, 'rb') as gzip_file,\
                open(output_file, 'wb') as output:
                try:
                    output.write(gzip_file.read())
                except IOError:
                    return ''
            gzip_file.close()
            output.close()
            
            source = output_file 
            
        # If the routing file is a RIB file, we process it using BGPdump
        if self.RIBfiles:            
            readable_file_name = '%s/%s.readable' % (self.files_path, os.path.splitext(source_filename)[0])

            cmd = shlex.split('%s -m -O %s %s' % (bgpdump, readable_file_name, source))
            #        cmd = shlex.split('bgpdump -m -O %s %s' % (readable_file_name, routing_file))   
    
            #  BGPDUMP
            #  -m         one-line per entry with unix timestamps
            #  -O <file>  output to <file> instead of STDOUT
    
            subprocess.call(cmd)
        
        # If the file contains the output of the 'show ip bgp' command,
        # we convert it to the same format used by BGPdump for its outputs
        else:
            readable_file_name = self.convertBGPoutput(source)

        return readable_file_name
           
    # This function walks a folder with historical routing info and creates a
    # file with a list of paths to the files with the provided extension
    # in the archive folder
    # It returns the path to the created file
    def getPathsToHistoricalData(self, archive_folder, extension):
        files_list_filename = '%s/RoutingFiles.txt' % self.files_path
        
        files_list_list = []
        
        for root, subdirs, files in os.walk(archive_folder):
            for filename in files:
                if filename.endswith(extension):
                    files_list_list.append(os.path.join(root, filename))
        
        if len(files_list_list) == 0:
            return ''
        else:
            files_list_list_sorted = sorted(files_list_list)
            
            with open(files_list_filename, 'wb') as files_list:
                for filename in files_list_list_sorted:
                    files_list.write("%s\n" % filename)

            return files_list_filename

    # This function saves the data structures of the class to pickle files
    def saveDataToFiles(self):
        today = datetime.date.today().strftime('%Y%m%d')
        
        bgp_file_name = '%s/bgp_data_%s.pkl' % (self.files_path, today)
        with open(bgp_file_name, 'wb') as f:
            pickle.dump(self.bgp_data, f, pickle.HIGHEST_PROTOCOL)
            sys.stderr.write("Saved to disk %s pickle file containing DataFrame with BGP data.\n" % bgp_file_name)

        ipv4_radix_file_name = '%s/ipv4_prefixes_indexes_%s.pkl' % (self.files_path, today)
        with open(ipv4_radix_file_name, 'wb') as f:
            pickle.dump(self.ipv4_prefixes_indexes_radix, f, pickle.HIGHEST_PROTOCOL)
            sys.stderr.write("Saved to disk %s pickle file containing Radix with indexes in the BGP data DataFrame for each IPv4 prefix.\n" % ipv4_radix_file_name)

        ipv6_radix_file_name = '%s/ipv6_prefixes_indexes_%s.pkl' % (self.files_path, today)
        with open(ipv6_radix_file_name, 'wb') as f:
            pickle.dump(self.ipv6_prefixes_indexes_radix, f, pickle.HIGHEST_PROTOCOL)
            sys.stderr.write("Saved to disk %s pickle file containing Radix with indexes in the BGP data DataFrame for each IPv6 prefix.\n" % ipv6_radix_file_name)

        o_ases_dic_file_name = '%s/ASes_originated_prefixes_%s.pkl' % (self.files_path, today)
        with open(o_ases_dic_file_name, 'wb') as f:
            pickle.dump(self.ASes_originated_prefixes_dic, f, pickle.HIGHEST_PROTOCOL)
            sys.stderr.write("Saved to disk %s pickle file containing dictionary with prefixes originated by each AS.\n" % o_ases_dic_file_name)
        
        p_ases_dic_file_name = '%s/ASes_propagated_prefixes_%s.pkl' % (self.files_path, today)
        with open(p_ases_dic_file_name, 'wb') as f:
            pickle.dump(self.ASes_propagated_prefixes_dic, f, pickle.HIGHEST_PROTOCOL)
            sys.stderr.write("Saved to disk %s pickle file containing dictionary with prefixes propagated by each AS.\n" % p_ases_dic_file_name)
        
        ipv4_prefDates_file_name = '%s/ipv4_prefixesDates_%s.pkl' % (self.files_path, today)
        with open(ipv4_prefDates_file_name, 'wb') as f:
            pickle.dump(self.ipv4_prefixesDates_radix, f, pickle.HIGHEST_PROTOCOL)
            sys.stderr.write("Saved to disk %s pickle file containing Radix with the dates in which each IPv4 prefix was seen.\n" % ipv4_prefDates_file_name)
        
        ipv6_prefDates_file_name = '%s/ipv6_prefixesDates_%s.pkl' % (self.files_path, today)
        with open(ipv6_prefDates_file_name, 'wb') as f:
            pickle.dump(self.ipv6_prefixesDates_radix, f, pickle.HIGHEST_PROTOCOL)
            sys.stderr.write("Saved to disk %s pickle file containing Radix with the dates in which each IPv6 prefix was seen.\n" % ipv6_prefDates_file_name)
        
        originASesDates_file_name = '%s/originASesDates_%s.pkl' % (self.files_path, today)
        with open(originASesDates_file_name, 'wb') as f:
            pickle.dump(self.originASesDates_dict, f, pickle.HIGHEST_PROTOCOL)
            sys.stderr.write("Saved to disk %s pickle file containing a dictionary indexed by origin AS with info about the periods of time during which the AS originated prefixes.\n" % originASesDates_file_name)

        middleASesDates_file_name = '%s/middleASesDates_%s.pkl' % (self.files_path, today)
        with open(middleASesDates_file_name, 'wb') as f:
            pickle.dump(self.middleASesDates_dict, f, pickle.HIGHEST_PROTOCOL)
            sys.stderr.write("Saved to disk %s pickle file containing a dictionary indexed by AS with info about the periods of time during which the AS propagated prefixes.\n" % middleASesDates_file_name)

        return bgp_file_name, ipv4_radix_file_name, ipv6_radix_file_name,\
                o_ases_dic_file_name, p_ases_dic_file_name,\
                ipv4_prefDates_file_name, ipv6_prefDates_file_name,\
                originASesDates_file_name, middleASesDates_file_name

    # This function sets the ipv4_longest_pref and ipv6_longest_pref class variables
    # with the corresponding maximum prefix lengths in the ipv4_prefixes_indexes
    # and ipv6_prefixes_indexes Radixes
    def setLongestPrefixLengths(self):
        for prefix in self.ipv4_prefixes_indexes_radix.prefixes():
            network = ipaddress.ip_network(unicode(prefix, 'utf-8'))
            
            if network.prefixlen > self.ipv4_longest_pref:
                self.ipv4_longest_pref = network.prefixlen
                
        for prefix in self.ipv6_prefixes_indexes_radix.prefixes():
            network = ipaddress.ip_network(unicode(prefix, 'utf-8'))

            if network.prefixlen > self.ipv6_longest_pref:
                self.ipv6_longest_pref = network.prefixlen
                
    # This function returns a list of prefixes less specific than the one provided
    # that are included in the keys of the corresponding Radix
    def getRoutedParentAndGrandparents(self, network):        
        if network.version == 4:
            indexes_radix = self.ipv4_prefixes_indexes_radix
        else:
            indexes_radix = self.ipv6_prefixes_indexes_radix
            
        less_specifics = []
       
        for less_spec_node in indexes_radix.search_covering(str(network)):
            less_spec_pref = less_spec_node.prefix
        
            if less_spec_pref != str(network):
                less_specifics.append(less_spec_pref)
            
        return less_specifics
    
    # This function returns a list of prefixes more specific than the one provided
    # that are included in the keys of the corresponding Radix
    def getRoutedChildren(self, network):
        if network.version == 4:
            indexes_radix = self.ipv4_prefixes_indexes_radix
        else:
            indexes_radix = self.ipv6_prefixes_indexes_radix
            
        more_specifics = []
       
        for more_spec_node in indexes_radix.search_covered(str(network)):
            more_specifics.append(more_spec_node.prefix)
                        
        return more_specifics
        
    # This function returns the origin AS for a specific prefix
    # according to the routing data included in the BGP_data class variable
    def getOriginASesForBlock(self, network):        
        if network.version == 4:
            indexes_radix = self.ipv4_prefixes_indexes_radix
        else:
            indexes_radix = self.ipv6_prefixes_indexes_radix
            
        originASes = set()

        pref_node = indexes_radix.search_exact(str(network))
        if pref_node is not None:
            for index in pref_node.data['indexes']:
                originASes.add(self.bgp_data.ix[index, 'originAS'])            
            return originASes
        else:
            return originASes
    
    # This function returns a set with all the AS paths for a specific prefix
    # according to the routing data included in the BGP_data class variable
    def getASpathsForBlock(self, network):
        if network.version == 4:
            indexes_radix = self.ipv4_prefixes_indexes_radix
        else:
            indexes_radix = self.ipv6_prefixes_indexes_radix
            
        ASpaths = set()
        pref_node = indexes_radix.search_exact(str(network))
        if pref_node is not None:
            for index in pref_node.data['indexes']:
                ASpaths.add(self.bgp_data.ix[index, 'ASpath'])
        
        return ASpaths

    # This function returns the date in which a prefix or part of it
    # was first seen
    # If the prefix hasn't been seen yet according to the routing data in the
    # archive, None is returned
    def getDateFirstSeen(self, network):

        if network.version == 4:
            prefixesDates = self.ipv4_prefixesDates_radix
        else:
            prefixesDates = self.ipv6_prefixesDates_radix
                
        sometime_routed_covered_nodes = prefixesDates.search_covered(str(network))
        
        first_seen = float('inf')
        
        for node in sometime_routed_covered_nodes:
            node_first_seen = int(node.data['firstSeen'])
            if node_first_seen < first_seen:
                first_seen = node_first_seen

        if first_seen != float('inf'):
            return datetime.datetime.strptime(str(first_seen), '%Y%m%d').date()
        else:
            return None

    # This function returns the date in which a prefix was first seen
    # If the prefix has never been seen according to the routing data in the
    # archive, None is returned
    def getDateFirstSeenExact(self, network):
        
        if network.version == 4:
            prefixesDates = self.ipv4_prefixesDates_radix
        else:
            prefixesDates = self.ipv6_prefixesDates_radix
                
        network_node = prefixesDates.search_exact(str(network))

        if network_node is not None:
            return datetime.datetime.strptime(str(network_node.data['firstSeen']), '%Y%m%d').date()
        else:
            return None

    # This function returns the list of periods of time during which a prefix
    # was seen. If the prefix has never been seen according to the routing data
    # in the archive, an empty list is returned
    def getPeriodsSeenExact(self, network):        
        if network.version == 4:
            prefixesDates = self.ipv4_prefixesDates_radix
        else:
            prefixesDates = self.ipv6_prefixesDates_radix
                
        network_node = prefixesDates.search_exact(str(network))
        
        if network_node is not None:
            return network_node.data['periodsSeen']
        else:
            return []

    # This function returns a dictionary with the lists of periods of time
    # during which a prefix or parts of it were seen.
    # If any part of the prefix has ever been seen according to the routing data
    # in the archive, an empty dictionary is returned
    def getPeriodsSeenGral(self, network):        
        if network.version == 4:
            prefixesDates = self.ipv4_prefixesDates_radix
        else:
            prefixesDates = self.ipv6_prefixesDates_radix
                
        covered_nodes = prefixesDates.search_covered(str(network))
        
        periods_dict = dict()
        
        for covered_node in covered_nodes:
            covered_prefix = covered_node.prefix
            periods_dict[covered_prefix] = covered_node.data['periodsSeen']
      
        return periods_dict
            

    # This function returns the number of days during which a prefix was seen.
    def getTotalDaysSeenExact(self, network):
        if network.version == 4:
            prefixesDates = self.ipv4_prefixesDates_radix
        else:
            prefixesDates = self.ipv6_prefixesDates_radix
                
        network_node = prefixesDates.search_exact(str(network))
        
        if network_node is not None:
            return int(network_node.data['totalDays'])
        else:
            return 0

    # This function returns the date in which a prefix was last seen.
    # If the prefix has never been seen according to the routing data in the
    # archive, None is returned
    def getDateLastSeenExact(self, network):
        
        if network.version == 4:
            prefixesDates = self.ipv4_prefixesDates_radix
        else:
            prefixesDates = self.ipv6_prefixesDates_radix
                
        network_node = prefixesDates.search_exact(str(network))

        if network_node is not None:
            return datetime.datetime.strptime(str(network_node.data['lastSeen']), '%Y%m%d').date()
        else:
            return None
        
    # This function returns the date in which a prefix or part of it
    # was last seen.
    # If the prefix has never been seen according to the routing data in the
    # archive, None is returned
    def getDateLastSeen(self, network):

        if network.version == 4:
            prefixesDates = self.ipv4_prefixesDates_radix
        else:
            prefixesDates = self.ipv6_prefixesDates_radix
                
        sometime_routed_covered_nodes = prefixesDates.search_covered(str(network))
        
        last_seen = 0
        
        for node in sometime_routed_covered_nodes:
            node_last_seen = int(node.data['lastSeen'])
            if node_last_seen > last_seen:
                last_seen = node_last_seen

        if last_seen != 0:
            return datetime.datetime.strptime(str(last_seen), '%Y%m%d').date()
        else:
            return None