'''
Created on Jan 23, 2011
Modified on June 07, 2011
@author: Dilum Bandara
@version: 0.22
@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):
        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_PEERS): #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.
        Send all attribs in list 
        Use random walk
        @param source: Source node ID
        @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_index(source, atts) #Add to index
            if result == False: 
                print 'add_ to_index failed. atts: ' + str(atts) + ' node: ' + str(source)
                return []
            hops.append(self.get_distance(source, next)) #Collect hops
        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
        '''
        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_index(source, atts[i]) #remove from index
            if result == False: 
                print 'remove_from_index failed. Check unless multiple atts map to same' \
                ' node. atts: ' + str(atts[i]) + ' node: ' + str(source)
            hops.append(self.get_distance(source, next)) #Collect hops
        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
        @todo: Make sure not to consider same resource multiple times while going through
        tree. This happens in SADQ where same resource appear in multiple nodes along
        path due to other attributes that are keep track by nodes ------------------
        '''
        tmp_atts = que_msg.query
        hops = []
        #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

        for i in range(len(atts)): #For each attribute
            min_key = self._my_hash.ULP_hash([atts[i][0], atts[i][1]]) #MIN hash value
            ring = 0 #Which ring?
            next = self.find_successor(min_key, ring) #Destination node
            result = BaseConfig.PEERS[next].query_index(que_msg) #Query index
            que_msg = result
            hops.append(self.get_distance(que_msg.source, next)) #Collect hops
            if que_msg.num_res_found >= que_msg.n:
                que_msg.success = True
                que_msg.hops = hops
                return que_msg  
            #If not enough resources check neighbors. Also skip for categorical data           
            max_key = self._my_hash.ULP_hash([atts[i][0], atts[i][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_index(que_msg) 
                    hops[i] += 1 #Increment hops                   
                    que_msg = result
                    if que_msg.num_res_found >= que_msg.n:
                        que_msg.success = True
                        que_msg.hops = hops
                        return que_msg
                    #Return actual cost so far
                    if BaseConfig.PEERS[next].keys[ring] == max_node_key: #MAX-key reached 
                        break
                    last = next
        que_msg.hops = hops
        return que_msg


    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_PEERS):
            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_PEERS):
            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
