'''
Created on Jan 25, 2012
Modified on July 14, 2012
@author: Dilum Bandara
@version: 0.1
@license: Apache License v2.0

   Copyright 2012 H. M. N. Dilum Bandara and Anura P. Jayasumana, Colorado State
   University

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
'''

'''
Overlay key related operations
'''

import Config


def distance(source, dest):
    '''
    Get overlay distance between 2 nodes on a circular address space
    @param source: Source key
    @param destination: Destination key
    @return: Overlay distance
    '''
    dist = dest - source
    if dist < 0: return (dist + Config.MAX_KEY + 1)
    return dist


def inRangeR(key, startKey, endKey):
    '''
    If given key between the given 2 keys (start key, end key]
    @param key: Key
    @param startKey: start of range
    @param endKey: end of range
    @result: True or False   
    '''
    keyToEnd = distance(key, endKey)
    startToEnd = distance(startKey, endKey)
    if startToEnd == 0: startToEnd = Config.MAX_KEY + 1
    if keyToEnd < startToEnd: return True
    return False


def inRangeLR(key, startKey, endKey, handleStartEqualEnd = False):
    '''
    If given key between the given 2 keys [start key, end key]
    @param key: Key
    @param startKey: start of range
    @param endKey: end of range
    @param handleStartEqualEnd: When set to True, address range is not 
    considered to wrap around if startKey == endKey 
    @result: True or False   
    '''
    if startKey == endKey and handleStartEqualEnd == True:
        if key == endKey: return True
        else: return False
    keyToEnd = distance(key, endKey)
    startToEnd = distance(startKey, endKey)
    if startToEnd == 0: startToEnd = Config.MAX_KEY + 1
    if keyToEnd <= startToEnd: return True
    return False


def inRange(key, startKey, endKey):
    '''
    If given key between the given 2 keys (start key, end key)
    @param key: Key
    @param startKey: start of range
    @param endKey: end of range
    @result: True or False   
    '''
    if key == startKey or key == endKey: return False #Can't have exact match
    keyToEnd = distance(key, endKey)
    if keyToEnd == 0: keyToEnd = Config.MAX_KEY + 1
    startToEnd = distance(startKey, endKey)
    if startToEnd == 0: startToEnd = Config.MAX_KEY + 1
    if keyToEnd < startToEnd: return True
    return False


def coverage(startRange, endRange, startNodeKey, endNodeKey):
    '''
    How much of the given range is covered by given node & is it fully covered
    @param startRange: Start key of range
    @param endRange: End key of range
    @param startNodeKey: Node's start key
    @param endNodeKey: Node's end key
    @return: [size of coverage, full or partial coverage]
    '''
    assert(startRange != endRange), 'Start & end is same'
    disR = distance(startRange, endRange)
    disS = distance(startRange, startNodeKey)
    disE = distance(startRange, endNodeKey)
    disK = distance(startNodeKey, endNodeKey)
    disKS = distance(startNodeKey, startRange)
    disKE = distance(startNodeKey, endRange)
    
    if (disR < disS) and (disR < disE) and (disK <= disKE) and (disK < disKS):
        return [0, False] #Completely out side
    cover = 0
    full = False
    if (disR <= disE) and (disR < disS): 
        cover = disR + 1
        full = True
    elif (disR >= disE) and (disR < disS): cover = disE + 1
    elif (disR >= disE) and (disR > disS):
        cover = disK + 1
        if disR == disK: full = True
    elif (disR > disS) and (disR <= disE): 
        cover = disKE + 1
        if disR == disKE: full = True
    return [cover, full]


def mini(keys, nodeKey):
    '''
    Given a list of keys find key that is closest (minimum distance) from the 
    given node (while being aware that address space wraps around). If key is
    same as node key it's considered as furtherest
    @param keys: List of keys
    @param nodeKey: Key of the node asking for minimum. Will be calculated with
    respect to this key
    @return: Minimum key
    '''
    assert(len(keys) > 0), 'Empty key list'    
    minKey = -1
    minDis = Config.MAX_KEY + 2
    for i in keys:
        #If same key, it's the furtherest
        dis = distance(nodeKey, i) if (i != nodeKey) else (Config.MAX_KEY + 1) 
        if dis < minDis:
            minDis = dis
            minKey = i
    return minKey


def maxi(keys, nodeKey):
    '''
    Given a list of keys find the key that is furtherest away (largest distance)
    from the given node (while being aware that address space wraps around)
    @param keys: List of keys
    @param nodeKey: Key of the node asking for maximum. Will be calculated with
    respect to this key  
    @return: Minimum key
    '''
    assert(len(keys) > 0), 'Empty key list'
    maxKey = -1
    maxDis = -1
    for i in keys:
        #If same key it's the furtherest
        dis = distance(nodeKey, i) if (i != nodeKey) else (Config.MAX_KEY + 1)
        if dis > maxDis:
            maxDis = dis
            maxKey = i
    return maxKey


def sortKeys(keys, nodeKey):
    '''
    Sort given list of keys while taking into account that address space 
    wraps around
    @param keys: List of keys
    @param nodeKey: Key of the node calling this function 
    @return: Sorted key list with respect to global key of this node  
    '''
    idx = -1
    sortedKeys = sorted(keys) #Sort as usual
    for i in range(len(sortedKeys)):
        if sortedKeys[i] == nodeKey: #can't exceed node's key 
            idx = i
            break
        if sortedKeys[i] > nodeKey:
            if i == 0: 
                idx = len(sortedKeys) - 1
                break
            else: 
                idx = i - 1
                break
    if idx == -1: idx = len(sortedKeys) - 1 #Address range didn't wrap up
    
    if idx == (len(sortedKeys) - 1): return sortedKeys#Already in order
    #Put keys in proper order move prefix to end of suffix after idx
    return sortedKeys[(idx + 1):] + sortedKeys[:(idx + 1)]
