from test.test_decorators import memoize
from world.staticObject import StaticObject
from world.face import Face
import numpy
import array
        
        
class Mesh(object):
    '''
    Represents a mesh. Defined by a non-empty sequence of boundaries
    in two or three dimensions.
    
    We disallow disconnected meshes.
    
    Note that a mesh does not include a translation or rotation inside of it.
    Transformations are the responsibility of the WorldObject, not the mesh itself.
    So, meshes should be defined here 
    '''
    def __init__(self, dim, boundaries):
        '''
        @param boundaries: the boundaries that are on this mesh.
        '''
        if len(boundaries) == 0:
            raise ValueError("A mesh must contain one or more boundaries!")
        
        # boundaries are paired with their respective faces
        self.dim = dim
        self.boundaries = boundaries
        
        if not self._checkDimensions():
            raise ValueError("Not all boundaries specified have dimension " + dim + "!")
        
        self.neighborMap = self._buildNeighborMap() # map of boundary -> neighboring boundaries
        
        
        if self._isConnected():
            raise ValueError("Specified mesh is disconnected!")
        
        self.normals = self._calculateNormals()
        
        self.faceMap, self.faces = self._buildFaces() # calculated faces
    
    def _checkDimensions(self):
        '''
        quick check to see if all of the dimensions work out as
        expected.
        '''
        for boundary in self.boundaries:
            if boundary.dim != self.dim:
                return False
        return True
    
    def _buildNeighborMap(self):
        '''
        Here we build the map of neighbors for each face.
        currently unimplemented, so we have two options
        
        1. Use a naive O(n^2) algorithm where we check each 
        boundary against each other (maybe a bad idea)
        2. Use a set to determine vertices that are relatively
        close, then we just grab all of the objects inside of the
        same bucket and check neighbors there (probably better, can eliminate
        many checks). Can cut cost from n choose 2 to n in the 2d case.
        '''
        
        neighborMap={}
        for i, boundary in enumerate(self.boundaries):
            # create set for each boundary.
            neighbors = array.array()
            
            for j, neighbor in enumerate(self.boundaries):
                if i == j: 
                    continue
                edge = boundary.getConnection(neighbor)
                if edge:
                    neighbors.append((neighbor, edge))
                    
            neighborMap[boundary] = neighbors
            
        return neighborMap
    
    def _isConnected(self):
        '''
        Tests the connectivity of this mesh. We might have a mesh
        where all of the edges have neighbors, but is disconnected.
        
        We disallow this case
        '''
        
        visited = set()
        frontier = [self.boundaries[0]]
        
        while True:
            next = frontier.pop()
            if next in visited:
                continue
            visited.add(next)
            for neighbor, edge in self.neighborMap[next]:
                frontier.append(neighbor)
            
            if len(frontier) == 0:
                break
        
        # we should have visited each boundary. Otherwise we 
        # have a connection problem, housten!
        return len(visited) == len(self.boundaries)
    
    @memoize
    def isClosed(self):
        '''
        @return: True iff this mesh is a closed surface.
        '''
        for boundary, neighbors in self.neighborMap:
            #need dim neighbors
            
            if len(neighbors) != self.dim:
                return False
            
            for i, (neighbori, edgei) in enumerate(neighbors):
                for (neighborj, edgej) in neighbors[i+1:]:
                    # for each neighbor i, check that the other neighbors
                    # are not defining the same boundary.
                    
                    if edgei.connectionEqual(edgej) :
                        # we know that edgei and edgej are not the same,
                        # yet generate the same connection. So, we 
                        # know that we have too many edges on this boundary. 
                        return False
                    
        return True
    
    def _calculateNormals(self):
        '''
        @return: a list of length len(boundaries) where each element corresponds to 
        -1 or 1. -1 if we want to flip the normal, 1 otherwise.
        @requires: self.neighborMap is defined and built correctly
        '''
        
        '''
        Here we treat the mesh as a graph G = (V, E) such that 
        \forall v \in V. deg(v) = self.dim
        
        and \forall (v1, v2) \in E. weight(v1, v2) = v1.consistent(v2)
        
        Our goal is to change all weight(e) such that all edges are consistent.
        Note that we can only change an edge's consistency by flipping all of the
        neighbors of a single vertex.
        
        We perform a DFS, maintaining a set of visited nodes X.
        
        On vertex v, we flip if necessary, put v into X, then continue.
        
        We flip iff both conditions are satisfied.
        a. \exists neighbor \in N(v). \not v.consistent(neighbor)
        b. \exists neighbor \in (N(v) \cap X). v.consistent(neighbor) 
        
        a. essentially means that we will not flip when all edges are already consistent (performance reasons, not actually required)
        b. means that we will not flip when this would make a visited edge inconsistent with this one. (required)
        '''
        visited = set()
        frontier = [self.boundaries[0]]
        
        # initially set all normals to 1
        normals = {i:1 for i in self.boundaries}
        
        # returns the consistency of the two meshes modified by the normals.
        def isConsistent(connection):
            return connection.isConsistent(normals)
        
        def flipBoundary(boundary):
            normals[boundary] *= -1 # flip using sign
            return
        
        while True:
            next = frontier.pop()
            if next in visited:
                continue
            
            flip = False
            for (neighbor, edge) in self.neighborMap[next]:
                if not isConsistent(edge): 
                    flip = True
                if (neighbor in visited) and isConsistent(edge):
                    flip = False
                    break
            if flip:
                flipBoundary(next)
                
            visited.add(next)
            if len(frontier) == 0:
                break
            
        return normals
    
    @memoize
    def volume(self):
        if not self.isClosed():
            raise RuntimeError("Cannot find the volume on a non-closed mesh")
        volume = 0.0
        for norm, b in zip(self.normals, self.boundaries):
            #carved volume with respect to the origin
            volume = volume + norm * b.carvedVolume()
            
        return volume
        
    def getFaces(self):
        return self.faces
    
    def getFaceMap(self):
        return self.faceMap
    
    def _buildFaces(self):
        '''
        Construct faces. Here, we run a DFS from each boundary, and stop traversing the 
        DFS when we meet another boundary that is not parallel to this one.
        
        @return: faceMap, faces. faceMap is a map that goes from boundary -> face, such
        that faceMap[boundary] is the face that the specified boundary belongs to. faces
        represents all faces that are present inside of this mesh.
        '''
        # construct the faces for the boundary.
        # at least four (tetrahedron), at most len(boundaries) (none are parallel and adjacent)
        faces = []
        faceMap = {}
        visited = set()
        for boundary in self.boundaries:
            if boundary in visited:
                continue
            frontier = [boundary]
            faceBoundaries = []
            while True:
                next = frontier.pop()
                if next in visited:
                    continue
                visited.add(next)
                faceBoundaries.append(next)
                for neighbor, edge in self.neighborMap[boundary]:
                    if next.isParallel(neighbor):
                        frontier.append(neighbor)
                if len(frontier) == 0:
                    break
            face = Face(self.dim, faceBoundaries, self.boundaryMap)
            faces.append(face)
            for b in faceBoundaries:
                faceMap[b] = face
        return faceMap, faces
    
# we provide these methods in case the user wants to 
# have a consitency of material. 
# A typical use case involves having an object that the user 
# wants a certain mass, then for material consistency has every
# object of the same mass 

def calculateMass(density, mesh):
    '''
    Calculate the mass of a mesh given its density
    '''
    return mesh.volume() * density
    
def calculateDensity(mass, mesh):
    '''
    Calculate the density of a mesh given its mass
    '''
    return mass / mesh.volume()