'''
Accessible Access Control 1.0
2012-2104 Michigan Technological University
Supported in part by NSF grants: DUE-1140512, DUE-1245310 and IIS-1319363
Developer: Yifei Li
Advisors:Dr. Steve Carr, Dr. Jean Mayo, Dr. Ching-Kuang Shene and Dr. Chaoli Wang
'''
'''
Created on Jan 5, 2012

@author: yifli
'''
from PyQt4.QtCore import QObject, QPointF, QLineF, QThread, pyqtSignal
from RadialTreeLayout import RadialTreeLayout
from DomainNode import DomainNode
from TypeNode import TypeNode
from EdgeItem import EdgeItem
import math
import random

class GeneralGraphLayoutStrategy(QThread):
    showCurrentResult = pyqtSignal()

    def __init__(self, scene):
        QThread.__init__(self)
        self.scene = scene
        self.sceneWidth = scene.width()
        self.sceneHeight = scene.height()
        self.radialTreeLayout = RadialTreeLayout(scene)

        self.SAiterations = 15
        
        # used in fine-tuing state
        self.lambda1 = 1
        self.lambda2 = 1
        self.lambda3 = 1
        
        
        self.lambda4 = 1
        self.lambda5 = 1
        self.lambda6 = 1

        self.nodeSpacing = 80
        
        self.quit = False
        self.F = 1.5
        self.CR = 0.5
            
    def mapToScene(self):
        for item in self.V:
            item.setPos(item.relativeX+self.sceneWidth/2.0, -item.relativeY+self.sceneHeight/2.0)
        
        for edge in self.E:
            edge.updatePosition()
                
               
    def run(self):
        # first layout all the domain nodes using a radial tree
        root = None 
        self.typeNodes = []
        self.V = []
        self.E = []
        for item in self.scene.items():
            if isinstance(item, DomainNode):
                self.V.append(item)
                if item.initialDomain:
                    root = item
            elif isinstance(item, TypeNode):
                self.typeNodes.append(item)
                self.V.append(item)
            elif isinstance(item, EdgeItem):
                if item.type != EdgeItem.FILE_CONN:
                    self.E.append(item)
        self.radialTreeLayout.buildTreeTable(root)   
        self.radialTreeLayout.d = self.radialTreeLayout.radius / self.radialTreeLayout.numLevels + 100       
        self.radialTreeLayout.layout()
        for v in self.V:
            if isinstance(v, DomainNode):
                if v.relativeY < 0:
                    if v.relativeY - 50 <= -self.radialTreeLayout.viewportHeight/2.0:
                        v.relativeY = -self.radialTreeLayout.viewportHeight/2.0 + 50
                else:
                    if v.relativeY + 50 >= self.radialTreeLayout.viewportHeight/2.0:
                        v.relativeY = self.radialTreeLayout.viewportHeight/2.0 - 50
        
        # compute the centroid of the domain nodes
        self.centerX = 0
        counter = 0
        for v in self.V:
            if isinstance(v, DomainNode):
                self.centerX += v.relativeX
                counter += 1
        self.centerX /= counter
        for v in self.V:
            if isinstance(v, DomainNode):
                v.relativeX -= self.centerX
        
        # set initial positons of type nodes on a ellipse
        self.a2 = (self.radialTreeLayout.viewportWidth/2.0) ** 2
        self.b2 = (self.radialTreeLayout.viewportHeight/2.0) ** 2
        delta = 2*math.pi / len(self.typeNodes) 
        angle = 0.0
        for t in self.typeNodes:
            k2 = math.tan(angle) ** 2
            if angle >= math.pi/2.0 and angle <= 3.0 * math.pi/2.0:
                t.relativeX = -math.sqrt(self.a2*self.b2 / (self.a2*k2+self.b2))
            else:
                t.relativeX = math.sqrt(self.a2*self.b2 / (self.a2*k2+self.b2))
                
            t.relativeY = math.tan(angle) * t.relativeX
            angle += delta
        
        #self.simulatedAnnealing()
        #self.DifferentialEvolution()
            
        for item in self.scene.items():
            if isinstance(item, DomainNode) or isinstance(item, TypeNode):
                item.setPos(item.relativeX+self.sceneWidth/2.0, -item.relativeY+self.sceneHeight/2.0)
        
        for edge in self.E:
            edge.updatePosition()
    
    def costChange(self, v, x, y):
        deltaCost = 0.0
        # node distribution
        for i in self.V:
            if i is not v:
                deltaCost += self.lambda1 * (1.0 / ((i.relativeX-x-self.nodeSpacing)**2 + (i.relativeY-y-self.nodeSpacing)**2) -
                                             1.0 / ((i.relativeX-v.relativeX-self.nodeSpacing)**2 + (i.relativeY-v.relativeY-self.nodeSpacing)**2)
                                            )
        # borderlines
        rr = x + self.radialTreeLayout.viewportWidth/2.0-self.nodeSpacing
        ll = self.radialTreeLayout.viewportWidth/2.0-x-self.nodeSpacing
        tt = y + self.radialTreeLayout.viewportHeight/2.0-self.nodeSpacing
        bb = self.radialTreeLayout.viewportHeight/2.0-y-self.nodeSpacing
        if rr == 0:
            rr = 0.0001
        if ll == 0:
            ll = 0.0001
        if tt == 0:
            tt = 0.0001
        if bb == 0:
            bb = 0.0001
    
        r = v.relativeX + self.radialTreeLayout.viewportWidth/2.0-self.nodeSpacing
        l = self.radialTreeLayout.viewportWidth/2.0-v.relativeX-self.nodeSpacing
        t = v.relativeY + self.radialTreeLayout.viewportHeight/2.0-self.nodeSpacing
        b = self.radialTreeLayout.viewportHeight/2.0-v.relativeY-self.nodeSpacing
        if r == 0:
            r = 0.0001
        if l == 0:
            l = 0.0001
        if t == 0:
            t = 0.0001
        if b == 0:
            b = 0.0001
    
        deltaCost += self.lambda2 * (1.0/(rr**2) + 1.0/(ll**2) + 1.0/(tt**2) + 1.0/(bb**2) -
                                     1.0/(r**2) - 1.0/(l**2) - 1.0/(t**2) - 1.0/(b**2))
    
        # edge lengths
        for e in self.E:
            if e.startItem is v or e.endItem is v:
                if e.startItem is v:
                    xx = x - e.endItem.relativeX
                    yy = y - e.endItem.relativeY
                else:
                    xx = x - e.startItem.relativeX
                    yy = y - e.startItem.relativeY
                
                x = e.startItem.relativeX - e.endItem.relativeX
                y = e.startItem.relativeY - e.endItem.relativeY
    
                deltaCost += self.lambda3 * (xx**2 + yy*2 - x**2 - y**2)
            
        
        # edge crossings
        for e1 in self.E:
            if e1.startItem is not v and e1.endItem is not v:
                continue
            oldCrossings = 0
            newCrossings = 0
            for e2 in self.E:
                if e1 is not e2 and e1.endItem is not e2.endItem:
                    line1 = QLineF(QPointF(e1.startItem.relativeX, e1.startItem.relativeY),
                                   QPointF(e1.endItem.relativeX, e1.endItem.relativeY))
                    line2 = QLineF(QPointF(e2.startItem.relativeX, e2.startItem.relativeY),
                                   QPointF(e2.endItem.relativeX, e2.endItem.relativeY))
            
                    p = QPointF()
                    intersectionType = line1.intersect(line2, p)
                    if intersectionType == QLineF.BoundedIntersection:
                        oldCrossings += 1 
                        
                    
                    
                    if v is e1.startItem:
                        line1 = QLineF(QPointF(x,y), 
                                       QPointF(e1.endItem.relativeX, e1.endItem.relativeY))
                    else:
                        line1 = QLineF(QPointF(x,y),
                                       QPointF(e1.startItem.relativeX, e1.startItem.relativeY))
                    intersectionType = line1.intersect(line2, p)

                    if line1.intersect(line2, p) == QLineF.BoundedIntersection:
                        newCrossings += 1

            deltaCost +=self.lambda4 * (newCrossings - oldCrossings)**2

                
        
        # node-edge distance
        for e in self.E:
            if v is not e.startItem and v is not e.endItem:
                p1 = QPointF(e.startItem.relativeX, e.startItem.relativeY)
                p2 = QPointF(e.endItem.relativeX, e.endItem.relativeY)
                k = (p2.y() - p1.y()) / (p2.x() - p1.x())
                d = p1.y() - k*p1.x()
                old_dist = math.fabs(k*v.relativeX-v.relativeY+d) / math.sqrt(k**2+1)-self.nodeSpacing
                new_dist = math.fabs(k*x-y+d) / math.sqrt(k**2+1)-self.nodeSpacing
                
                deltaCost += self.lambda5 * (1.0 / max(50, new_dist)**2 - 1.0 / max(50, old_dist)**2)

        # node-node intersection
        rectHalfWidth = self.typeNodes[0].rect().width()/2.0+self.nodeSpacing
        rectHalfHeight = self.typeNodes[1].rect().height()/2.0+self.nodeSpacing
        for v1 in self.typeNodes:
            oldCrossings = 0
            newCrossings = 0
            for v2 in self.typeNodes:
                if v1 is not v2:
                    l1 = v1.relativeX - rectHalfWidth
                    r1 = v1.relativeY + rectHalfWidth
                    t1 = v1.relativeY + rectHalfHeight
                    b1 = v1.relativeY - rectHalfHeight 
                    
                    l2 = v2.relativeX - rectHalfWidth
                    r2 = v2.relativeY + rectHalfWidth
                    t2 = v2.relativeY + rectHalfHeight
                    b2 = v2.relativeY - rectHalfHeight 
                    
                    if r1 <= r2 and r1 >= l2 or r2 >= l1 and r2 <= r1:
                        if t1 >= b2 and t1 <= t2 or t2 >= b1 and t2 <= t1:
                            oldCrossings += 1
                            
                    l1 = x - rectHalfWidth
                    r1 = x + rectHalfWidth
                    t1 = y + rectHalfHeight
                    b1 = y - rectHalfHeight 
                    
                    if r1 <= r2 and r1 >= l2 or r2 >= l1 and r2 <= r1:
                        if t1 >= b2 and t1 <= t2 or t2 >= b1 and t2 <= t1:
                            newCrossings += 1
                            
            deltaCost += self.lambda6*(newCrossings - oldCrossings) ** 2


                       
        return deltaCost
                
                
    def simulatedAnnealing(self):        
        T = 2000
        for i in xrange(self.SAiterations):
            self.showCurrentResult.emit()
            self.msleep(1000)
            if self.quit:
                return
            for j in xrange(30):
                for v in self.typeNodes:
                    direction = QPointF(random.random(), random.random())
                    t = direction.y() / direction.x()
                    angle = math.atan(t)
                    k2 = t ** 2
                    if angle >= math.pi/2.0 and angle <= 3.0 * math.pi/2.0:
                        x = -math.sqrt(self.a2*self.b2 / (self.a2*k2+self.b2))
                    else:
                        x = math.sqrt(self.a2*self.b2 / (self.a2*k2+self.b2))
                
                    y = math.tan(angle) * x

 
                    costChange = self.costChange(v, x, y)
                    if costChange < 0 or random.random() < math.exp(-costChange/T):
                        v.relativeX = x
                        v.relativeY = y
            
            T = 0.75 * T
            
          
        for v in self.typeNodes:
            v.radius = 500 
            v.originalX = v.relativeX
            v.originalY = v.relativeY
    
        for i in xrange(10):
            self.showCurrentResult.emit()
            if self.quit:
                return
 
            for j in xrange(30):
                for v in self.typeNodes:
                    if v.relativeX >= 0 and v.relativeY >= 0:
                        direction = QPointF(-random.random(), -random.random())
                    elif v.relativeX >= 0 and v.relativeY < 0:
                        direction = QPointF(-random.random(), random.random())
                    elif v.relativeX < 0 and v.relativeY >= 0:
                        direction = QPointF(random.random(), -random.random())
                    elif v.relativeX < 0 and v.relativeY <= 0:
                        direction = QPointF(random.random(), random.random())

                    len = math.sqrt(direction.x()**2 + direction.y()**2) 
                    x = v.radius * (direction.x() / len) + v.originalX
                    y = v.radius * (direction.y() / len) + v.originalY
                    costChange = self.costChange(v, x, y)
                    if costChange < 0:
                        v.relativeX = x
                        v.relativeY = y
                        v.radius *= 0.95
        
    
    def evaluateCost(self):
        cost = 0.0
        # node distribution
        for i in self.V:
            for j in self.typeNodes:
                if j is not i:
                    cost += self.lambda1 * (1.0 / ((i.relativeX-j.relativeX-self.nodeSpacing)**2 + (i.relativeY-j.relativeY-self.nodeSpacing)**2)) 
                                                    
        # borderlines
        for i in self.typeNodes:        
            r = i.relativeX + self.radialTreeLayout.viewportWidth/2.0-self.nodeSpacing
            l = self.radialTreeLayout.viewportWidth/2.0-i.relativeX-self.nodeSpacing
            t = i.relativeY + self.radialTreeLayout.viewportHeight/2.0-self.nodeSpacing
            b = self.radialTreeLayout.viewportHeight/2.0-i.relativeY-self.nodeSpacing
            if r == 0:
                r = 0.0001
            if l == 0:
                l = 0.0001
            if t == 0:
                t = 0.0001
            if b == 0:
                b = 0.0001
            cost += self.lambda2 * (1.0/(r**2) + 1.0/(l**2) + 1.0/(t**2) + 1.0/(b**2))
                                            
        # edge lengths
        for e in self.E:
            if isinstance(e.endItem, TypeNode):
                x = e.startItem.relativeX - e.endItem.relativeX
                y = e.startItem.relativeY - e.endItem.relativeY
    
                cost += self.lambda3 * (x**2 + y**2)
            
        
        # edge crossings
        crossings = 0

        for e1 in self.E:
            if not isinstance(e1.endItem, TypeNode):
                continue
            for e2 in self.E:
                if e1 is not e2 and e1.endItem is not e2.endItem:
                    line1 = QLineF(QPointF(e1.startItem.relativeX, e1.startItem.relativeY),
                                   QPointF(e1.endItem.relativeX, e1.endItem.relativeY))
                    line2 = QLineF(QPointF(e2.startItem.relativeX, e2.startItem.relativeY),
                                   QPointF(e2.endItem.relativeX, e2.endItem.relativeY))
            
                    p = QPointF()
                    intersectionType = line1.intersect(line2, p)
                    if intersectionType == QLineF.BoundedIntersection:
                        crossings += 1 
                        
                    
    
        cost +=self.lambda4 * (crossings **2)

                
        
        # node-edge distance
        for v in self.V:
            for e in self.E:
                if v is not e.startItem and v is not e.endItem:
                    p1 = QPointF(e.startItem.relativeX, e.startItem.relativeY)
                    p2 = QPointF(e.endItem.relativeX, e.endItem.relativeY)
                    k = (p2.y() - p1.y()) / (p2.x() - p1.x())
                    d = p1.y() - k*p1.x()
                    dist = math.fabs(k*v.relativeX-v.relativeY+d) / math.sqrt(k**2+1)-self.nodeSpacing
                    
                    cost += self.lambda5 * (1.0 / max(100, dist))**2 

        '''
        # node-node intersection
        rectHalfWidth = self.typeNodes[0].rect().width()/2.0+self.nodeSpacing
        rectHalfHeight = self.typeNodes[1].rect().height()/2.0+self.nodeSpacing
        for v1 in self.typeNodes:
            oldCrossings = 0
            newCrossings = 0
            for v2 in self.typeNodes:
                if v1 is not v2:
                    l1 = v1.relativeX - rectHalfWidth
                    r1 = v1.relativeY + rectHalfWidth
                    t1 = v1.relativeY + rectHalfHeight
                    b1 = v1.relativeY - rectHalfHeight 
                    
                    l2 = v2.relativeX - rectHalfWidth
                    r2 = v2.relativeY + rectHalfWidth
                    t2 = v2.relativeY + rectHalfHeight
                    b2 = v2.relativeY - rectHalfHeight 
                    
                    if r1 <= r2 and r1 >= l2 or r2 >= l1 and r2 <= r1:
                        if t1 >= b2 and t1 <= t2 or t2 >= b1 and t2 <= t1:
                            oldCrossings += 1
                            
                    l1 = x - rectHalfWidth
                    r1 = x + rectHalfWidth
                    t1 = y + rectHalfHeight
                    b1 = y - rectHalfHeight 
                    
                    if r1 <= r2 and r1 >= l2 or r2 >= l1 and r2 <= r1:
                        if t1 >= b2 and t1 <= t2 or t2 >= b1 and t2 <= t1:
                            newCrossings += 1
                            
            deltaCost += self.lambda6*(newCrossings - oldCrossings) ** 2
        '''

                       
        return cost

        
    def DifferentialEvolution(self):
        # population
        x = []
        width = self.radialTreeLayout.viewportWidth-100
        height = self.radialTreeLayout.viewportHeight-100
        
        # initialization
        for item in self.scene.items():
            if isinstance(item, TypeNode):
                item.relativeX = random.uniform(-width/2.0, width/2.0)
                item.relativeY = random.uniform(-height/2.0, height/2.0)
                x.append([item.relativeX, item.relativeY])
        
        for i in xrange(10):
            # mutation
            v = []
            for j in xrange(len(x)):
                indices = range(len(x))
                indices.remove(j)
                r1, r2, r3 = random.sample(indices ,3)
                
                xx = x[r1][0] + self.F * (x[r2][0] - x[r3][0])
                yy = x[r1][1] + self.F * (x[r2][1] - x[r3][1])
                v.append([xx, yy])
                
            # cross-over
            u = []
            for j in xrange(len(x)):
                uu = []
                for k in xrange(2):
                    if random.uniform(0.0,1.0) <= self.CR or k == random.choice([0,1]):
                        uu.append(v[j][k])
                    elif random.uniform(0.0,1.0) > self.CR and k != random.choice([0,1]):
                        uu.append(x[j][k])
                u.append(uu)
                
            # selection
            cost1 = self.evaluateCost()
            for j, t in enumerate(self.typeNodes):
                t.relativeX = u[j][0]
                t.relativeY = u[j][1]
            cost2 = self.evaluateCost()
            if cost1 < cost2:
                for j, t in enumerate(self.typeNodes):
                    t.relativeX = x[j][0]
                    t.relativeY = x[j][1]
                

            
                          
                        
                        
                        
                    
                        
                        
                        
                        
                        
                        

   

            
        
        
        
