'''
Created on Apr 26, 2011
Modified on Apr 25, 2011
@author: Dilum Bandara
@version: 0.1
@copyright: Copyright(c) 2011, Dilum Bandara
@license: GPL
'''

from BaseClasses.BaseOverlay import BaseOverlay
from BaseClasses.BaseHash import BaseHash
import BaseClasses.BaseConfig as BaseConfig
import Config
import random
import copy

class Overlay(BaseOverlay):
    '''
    Overlay class. 
    '''
    def __init__(self):
        '''
        Constructor
        Read both node distance & key files
        '''
        fdDis = open(BaseConfig.DISTANCE_FILE, 'r') #Extract from distance file
        self._distances = []
        for line in fdDis:
            list = line.split()
            tmp_list = []   
            for i in range(0, len(list)): tmp_list.append(int(list[i]))
            self._distances.append(tmp_list)
        fdDis.close()
        self._key_list = []
        fdKey = open(BaseConfig.KEY_FILE, 'r') #extract from key file
        for line in fdKey: self._key_list.append(long(line, 16))
        fdKey.close()
        #generate node key list
        tmp_key_list = copy.deepcopy(self._key_list)
        shuffled_key_list = [copy.deepcopy(tmp_key_list)] #Shuffled key list for each ring
        for i in range(1, Config.NUM_RINGS):
            random.shuffle(tmp_key_list)
            shuffled_key_list.append(copy.deepcopy(tmp_key_list))
        self.node_key_list = []
        for j in range(0, Config.NUM_SUPERPEERS): #Assign keys to nodes
            keys = []
            for k in range(0, Config.NUM_RINGS):
                keys.append(shuffled_key_list[k][j])
            self.node_key_list.append(keys)
        self._my_hash = BaseHash()
        self._nbr_list = self.find_all_neighbors()


    def route_new_ads(self, source, atts):
        '''
        Route resource ads to given destination & return no of overlay hops. 
        Use random walk
        @param source: Source node ID
        @param atts: Attributes
        @return: Success/Failure
        '''
        if source == BaseConfig.PEERS[source]._sid: #I'm a superpeer
            result = BaseConfig.PEERS[source].add_to_index(source, atts) #Add to index
            if result == False:
                print 'add_ to_index failed. Trying to add to myself Atts: ' \
                + str(atts) + ' node: ' + str(source)
                return []
            return [0];
        else: #Send to superpeer
            result = BaseConfig.PEERS[BaseConfig.PEERS[source]._sid].add_to_index(\
                                            source, atts)
            if result == False:
                print 'add_ to_index failed. Atts: ' + str(atts) + ' node: ' + str(source)
                return []
            return [1];


    def route_DHT_new_ads(self, source, nid, atts):
        '''
        Route resource ads to given destination in DHT & return no of overlay hops.
        Send all attribs in list 
        Use random walk
        @param source: Node ID of superpeer that send the messages
        @param nid: Node ID of the original resource 
        @param atts: Attributes
        @return: Success/Failure
        '''
        hops = []
        for i in range(len(atts)): #For each attribute
            key = self._my_hash.ULP_hash(atts[i])  #Get hash
            ring = 0 #Which ring?
            next = self.find_successor(key, ring) #Successor of given key
            result = BaseConfig.PEERS[next].add_to_DHT_index(nid, atts) #Add to index
            if result == False: 
                print 'add_ to_index failed. atts: ' + str(atts) + ' node: ' + str(nid)
                return []
            hops.append(self.get_distance(source, next)) #Collect hops from superpeer
        return  hops


    def route_old_ads(self, source, atts):
        '''
        Route resource remove msgs to given destination & return no of overlay hops
        @param source: Source node ID
        @param atts: Attributes
        @return: Success/Failure
        '''
        return [0] #No remove message routing


    def route_DHT_old_ads(self, source, nid, atts):
        '''
        Route resource remove msgs to given DHT node & return no of overlay hops
        @param source: Node ID of superpeer that send the messages
        @param nid: Node ID of the original resource
        @param atts: Attributes
        @return: Success/Failure
        '''
        hops = []
        for i in range(len(atts)): #For each attribute
            key = self._my_hash.ULP_hash(atts[i])  #Get hash
            ring = 0 #Which ring?
            next = self.find_successor(key, ring) #Successor of given key
            result = BaseConfig.PEERS[next].remove_from_DHT_index(nid, atts[i]) #remove
            if result == False: 
                print 'remove_from_index failed. Check unless multiple atts map to same' \
                ' node. atts: ' + str(atts[i]) + ' node: ' + str(nid)
            hops.append(self.get_distance(source, next)) #Collect hops from superpeer
        return  hops        
    
    
    def route_query(self, que_msg):
        '''
        Route query to given destination & return no of overlay hops   
        @param que_msg: Query message
        @return: Modified query message
        '''
        #If not a superpeer, first send to superpeer
        if que_msg.source != BaseConfig.PEERS[que_msg.source]._sid : 
            sp = BaseConfig.PEERS[que_msg.source]._sid #Superpeer
            que_msg.hops += 1 #1 hop to send to superpeer
            que_msg.visited_peers.append(que_msg.source)
        else: sp = que_msg.source

        result = BaseConfig.PEERS[sp].query_index(que_msg)
        result.hops = [result.hops]
        return result
                             

    def route_DHT_query(self, que_msg):
        '''
        Route query to given DHT node & return no of overlay hops   
        @param que_msg: Query message
        @return: Modified query message
        '''
        tmp_atts = que_msg.query
        #Pick more selective attribute
        min_range = self._my_hash.max_key
        min_i = -1
        for i in range(len(tmp_atts)): #For each attribute
            min_key = self._my_hash.ULP_hash([tmp_atts[i][0], tmp_atts[i][1]]) #MIN hash
            max_key = self._my_hash.ULP_hash([tmp_atts[i][0], tmp_atts[i][2]]) #MAX hash
            #No need to worry about address range wrapping            
            tmp_range = max_key - min_key
            if tmp_range <= min_range:
                min_range = tmp_range
                min_i = i
        atts = tmp_atts[min_i] #attribute to query
   
        min_key = self._my_hash.ULP_hash([atts[0], atts[1]]) #MIN hash value
        ring = 0 #Which ring?
        next = self.find_successor(min_key, ring) #Destination node
        result = BaseConfig.PEERS[next].query_DHT_index(que_msg) #Query index
        que_msg = result
        que_msg.hops += self.get_distance(que_msg.source, next) #Collect hops
        if que_msg.success == True: return que_msg #Query answered  
        #If query is still not answered check neighbors. Also skip for categorical data           
        max_key = self._my_hash.ULP_hash([atts[0], atts[2]]) #MAX hash value
        max_node = self.find_successor(max_key, ring) #Destination node
        max_node_key = BaseConfig.PEERS[max_node].keys[ring]
        last = next
        if last != max_node:  #More to explore
            while True:
                next = self.get_neighbor(last, ring) #Destination node
                #Query neighbor
                result = BaseConfig.PEERS[next].query_DHT_index(que_msg) 
                que_msg = result
                que_msg.hops += 1
                if que_msg.success == True: return que_msg #Query answered
                #Return actual cost so far
                if BaseConfig.PEERS[next].keys[ring] == max_node_key: #MAX-key reached 
                    break
                last = next
        return que_msg


    def get_unvisited_neighbor(self, nid, que_msg):
        '''
        Find a random unvisited neighbor of given node. If unable to find, 
        pick node before me        
        @param nid: Current node ID
        @param que_msg: Query message
        '''
        if len(self._distances[nid]) == 0: return -1 #No neighbor
        idx = random.randint(0, len(self._distances[nid]) - 1)
        next = self._distances[nid][idx]
        while next in que_msg.visited_peers: #Don't go to same node
            already_in = True
            for i in range (0, len(self._distances[nid])):
                if self._distances[nid][i] not in que_msg.visited_peers: #If neighbor is not visited
                    already_in = False
                    break
            if already_in == False: #There are new ones to explore
                idx = random.randint(0, len(self._distances[nid]) - 1)
                next = self._distances[nid][idx]
            else: #No new ones. Return my predecessor
                next = que_msg.visited_peers[que_msg.visited_peers.index(nid) - 1]
                break
        return next


    def find_successor(self, key, ring_no):
        '''
        Find successor for a given key in given ring
        @param key: key to find success for
        @param ring_no: Which ring to use
        '''
        min_dis = self._my_hash.max_key
        successor = -1
        for i in range(Config.NUM_SUPERPEERS):
            dis = 0
            if (self.node_key_list[i][ring_no] < key): dis = self._my_hash.max_key +\
                1 + self.node_key_list[i][ring_no] - key
            else: dis = self.node_key_list[i][ring_no] - key
            if dis < min_dis:
                min_dis = dis
                successor = i
        if successor == -1:
            print 'Unable to find successor'
            return -1
        else: return successor


    def get_distance(self, source, destination):
        '''
        Get overlay distance between 2 nodes
        @param source: Source node ID
        @param destination: Destination node ID
        '''
        return self._distances[source][destination]


    def get_neighbor(self, nid, ring):
        '''
        Find neighbor of given node
        @param nid: Node ID
        @param ring: Which ring to use
        @return: Neighbor ID
        '''
        return self._nbr_list[nid][ring]
    
    def find_all_neighbors(self):
        '''
        Find all neighbors for each node in each ring
        '''
        nbr_list = []
        for i in range(0, Config.NUM_SUPERPEERS):
            tmp_list = []
            for j in range(0, Config.NUM_RINGS):
                key = self.node_key_list[i][j]
                key = (key + 1) % (self._my_hash.max_key + 1) #increment key
                tmp_list.append(self.find_successor(key, j))
            nbr_list.append(tmp_list)
        return nbr_list