#!/usr/bin/env python
#
"""General 2D triangular classes for triangular mesh generation.

   Note: A .index attribute is added to objects such as vertices and
   segments, often when reading and writing to files.  This information
   should not be used as percistant information.  It is not the 'index' of
   an element in a list.

   
   Copyright 2003/2004
   Ole Nielsen, Stephen Roberts, Duncan Gray, Christopher Zoppou
   Geoscience Australia
"""

import load_mesh.loadASCII

import sys
import math
import triang
import re
import os
import pickle

import types
import exceptions

# 1st and third values must be the same
#initialconversions = ['internal', 'external','internal']
# FIXME: maybe make this a switch that the user can change?
initialconversions = ['', 'external','']

#from os import sep
#sys.path.append('..'+sep+'pmesh')
#print "sys.path",sys.path

class MeshObject:
    """
    An abstract superclass for the basic mesh objects, eg vertex, segment,
    triangle.
    """
    def __init__(self):
        pass
    
class Point(MeshObject): 
    """
    Define a point in a 2D space.
    """
    def __init__(self,X,Y):
        __slots__ = ['x','y']
        self.x=X
        self.y=Y
        
    def DistanceToPoint(self, OtherPoint):
        """
        Returns the distance from this point to another
        """
        SumOfSquares = ((self.x - OtherPoint.x)**2) + ((self.y - OtherPoint.y)**2)
        return math.sqrt(SumOfSquares)
        
    def IsInsideCircle(self, Center, Radius):
        """
        Return 1 if this point is inside the circle, 
        0 otherwise
        """
        
        if (self.DistanceToPoint(Center)<Radius):
            return 1
        else:
            return 0
        
    def __repr__(self):
        return "(%f,%f)" % (self.x,self.y) 

    def cmp_xy(self, point):
        if self.x < point.x:
            return -1
        elif self.x > point.x:
            return 1
        else:           
            if self.y < point.y:
                return -1
            elif self.y > point.y:
                return 1
            else:
                return 0
        
    def same_x_y(self, point):
        if self.x == point.x and self.y == point.y:
            return True
        else:
            return False
        
            

class Vertex(Point):
    """
    A point on the mesh.
    Object attributes based on the Triangle program
    """
    def __init__(self,X,Y, attributes = None):
        __slots__ = ['x','y','attributes']
        self.x=X
        self.y=Y        
        self.attributes=[] 
        
        if attributes is None:
            self.attributes=[]
        else:
            self.attributes=attributes
    

    def setAttributes(self,attributes):
        """
        attributes is a list.
        """
        self.attributes = attributes
        
    VERTEXSQUARESIDELENGTH = 6
    def draw(self, canvas, tags, colour = 'black',scale = 1, xoffset = 0, yoffset =0, ):
        x =  scale*(self.x + xoffset)
        y = -1*scale*(self.y + yoffset)  # - since for a canvas - is up
        #print "draw x:", x
        #print "draw y:", y
        cornerOffset= self.VERTEXSQUARESIDELENGTH/2

        # A hack to see the vert tags  
        #canvas.create_text(x+ 2*cornerOffset,
        #                   y+ 2*cornerOffset,
        #                        text=tags)
        
        return canvas.create_rectangle(x-cornerOffset,
                                       y-cornerOffset,
                                       x+cornerOffset,
                                       y+cornerOffset,
                                       tags = tags,
                                       outline=colour,
                                       fill = 'white')
     
    def __repr__(self):
        return "[(%f,%f),%r]" % (self.x,self.y,self.attributes)
    
class Hole(Point):
    """
    A region of the mesh were no triangles are generated.
    Defined by a point in the hole enclosed by segments.
    """
    HOLECORNERLENGTH = 6
    def draw(self, canvas, tags, colour = 'purple',scale = 1, xoffset = 0, yoffset =0, ):
        x =  scale*(self.x + xoffset)
        y = -1*scale*(self.y + yoffset)  # - since for a canvas - is up
        #print "draw x:", x
        #print "draw y:", y
        cornerOffset= self.HOLECORNERLENGTH/2
        return canvas.create_oval(x-cornerOffset,
                                       y-cornerOffset,
                                       x+cornerOffset,
                                       y+cornerOffset,
                                       tags = tags,
                                       outline=colour,
                                       fill = 'white')
    
class Region(Point):
    """ 
    A region of the mesh, defined by a point in the region
    enclosed by segments. Used to tag areas.
    """
    CROSSLENGTH = 6
    TAG = 0
    MAXAREA = 1
    
    def __init__(self,X,Y, tag = None, maxArea = None):
        """Precondition: tag is a string and maxArea is a real
        """
        # This didn't work.  
        #super(Region,self)._init_(self,X,Y)
        self.x=X
        self.y=Y    
        self.attributes =[] # index 0 is the tag string
                            #optoinal index 1 is the max triangle area
                            #NOTE the size of this attribute is assumed
                            # to be 1 or 2 in regionstrings2int
        if tag is None:
            self.attributes.append("")
        else:
            self.attributes.append(tag) #this is a string
            
        if maxArea is not None:
            self.setMaxArea(maxArea) # maxArea is a number
            
    def getTag(self,):
        return self.attributes[self.TAG]
    
    def setTag(self,tag):
        self.attributes[self.TAG] = tag
        
    def getMaxArea(self):
        """ Returns the Max Area of a Triangle or
        None, if the Max Area has not been set.
        """
        if self.isMaxArea():
            return self.attributes[1]
        else:
            return None
    
    def setMaxArea(self,MaxArea):
        if self.isMaxArea(): 
            self.attributes[self.MAXAREA] = float(MaxArea)
        else:
            self.attributes.append( float(MaxArea) )
    
    def deleteMaxArea(self):
        if self.isMaxArea():
            self.attributes.pop(self.MAXAREA)
            
    def isMaxArea(self):
        return len(self.attributes)> 1
    
    def draw(self, canvas, tags, scale=1, xoffset = 0, yoffset =0, colour = "black"):
        """
        Draw a black cross, returning the objectID
        """
        x =  scale*(self.x + xoffset)
        y = -1*scale*(self.y + yoffset) 
        cornerOffset= self.CROSSLENGTH/2
        return canvas.create_polygon(x,
                                     y-cornerOffset,
                                     x,
                                     y,
                                     x+cornerOffset,
                                     y,
                                     x,
                                     y,
                                     x,
                                     y+cornerOffset,
                                     x,
                                     y,
                                     x-cornerOffset,
                                     y,
                                     x,
                                     y,
                                     tags = tags,
                                     outline = colour,fill = '')
    
    def __repr__(self):
        if self.isMaxArea():
            area = self.getMaxArea() 
            return "(%f,%f,%s,%f)" % (self.x,self.y,
                                      self.getTag(), self.getMaxArea())
        else:
            return "(%f,%f,%s)" % (self.x,self.y,
                                   self.getTag())
        
class Triangle(MeshObject):
    """
    A triangle element, defined by 3 vertices.
    Attributes based on the Triangle program.
    """

    def __init__(self, vertex1, vertex2, vertex3, attribute = None, neighbors = None ):
        """
        Vertices, the initial arguments, are listed in counterclockwise order.
        """
        self.vertices= [vertex1,vertex2, vertex3 ]
        
        if attribute is None:
            self.attribute =""
        else:
            self.attribute = attribute #this is a string
            
        if neighbors is None:
            self.neighbors=[]
        else:
            self.neighbors=neighbors

    def getVertices(self):
        return self.vertices
    
    def calcArea(self):
        ax = self.vertices[0].x
        ay = self.vertices[0].y
        
        bx = self.vertices[1].x
        by = self.vertices[1].y
        
        cx = self.vertices[2].x
        cy = self.vertices[2].y
        
        return abs((bx*ay-ax*by)+(cx*by-bx*cy)+(ax*cy-cx*ay))/2
    
    def setNeighbors(self,neighbor1 = None, neighbor2 = None, neighbor3 = None):
        """
        neighbor1 is the triangle opposite vertex1 and so on.
        Null represents no neighbor
        """
        self.neighbors = [neighbor1, neighbor2, neighbor3]

    def setAttribute(self,attribute):
        """
        neighbor1 is the triangle opposite vertex1 and so on.
        Null represents no neighbor
        """
        self.attribute = attribute
        
    def __repr__(self):
        return "[%s,%s]" % (self.vertices,self.attribute)
        

    def draw(self, canvas, tags, scale=1, xoffset = 0, yoffset =0, colour = "green"):
        """
        Draw a red triagle, returning the objectID
        """
        return canvas.create_polygon(scale*(self.vertices[1].x + xoffset),
                                     scale*-1*(self.vertices[1].y + yoffset),
                                     scale*(self.vertices[0].x + xoffset),
                                     scale*-1*(self.vertices[0].y + yoffset),
                                     scale*(self.vertices[2].x + xoffset),
                                     scale*-1*(self.vertices[2].y + yoffset),
                                     tags = tags,
                                     outline = colour,fill = '')

class Segment(MeshObject):
    """
    Segments are edges whose presence in the triangulation is enforced.
    
    """
    def __init__(self, vertex1, vertex2, marker = None ):
        """
        Each segment is specified by listing the vertices of its endpoints
        """

        assert(vertex1 != vertex2)
        self.vertices = [vertex1,vertex2 ]
        
        if marker is None:
            self.marker = self.__class__.default
        else:
            self.marker = marker #this is a string 
        
    def __repr__(self):
        return "[%s,%s]" % (self.vertices,self.marker)
            
        
    def draw(self, canvas, tags,scale=1 , xoffset=0 , yoffset=0,colour='blue' ):
        x=[]
        y=[]
        for end in self.vertices:
            #end.draw(canvas,scale, xoffset, yoffset ) # draw the vertices
            x.append(scale*(end.x + xoffset))
            y.append(-1*scale*(end.y + yoffset))  # - since for a canvas - is up 
        return canvas.create_line(x[0], y[0], x[1], y[1], tags = tags,fill=colour)
    # Class methods
    def set_default_tag(cls, default):
        cls.default = default 
    
    def get_default_tag(cls):
        return cls.default
    
    set_default_tag = classmethod(set_default_tag)  
    get_default_tag = classmethod(get_default_tag)

Segment.set_default_tag("")       

class Mesh:
    """
    Representation of a 2D triangular mesh.
    User attributes describe the mesh region/segments/vertices/attributes

    mesh attributes describe the mesh that is produced eg triangles and vertices.
    
    The Mesh holds user information to define the 
    """

    def __repr__(self):
        return """
        mesh Triangles: %s 
        mesh Segments: %s  
        mesh Vertices: %s 
        user Segments: %s  
        user Vertices: %s  
        holes: %s 
        regions: %s""" % (self.meshTriangles,
                                self.meshSegments,
                                self.meshVertices,
                                self.userSegments,
                                self.userVertices,
                                self.holes,
                                self.regions) 
    
    def __init__(self, userSegments=None, userVertices=None, holes=None, regions=None):
        self.meshTriangles=[] 
        self.meshSegments=[]
        self.meshVertices=[]
        
        if userSegments is None:
            self.userSegments=[]
        else:
            self.userSegments=userSegments
            
        if userVertices is None:
            self.userVertices=[]
        else:
            self.userVertices=userVertices
            
        if holes is None:
            self.holes=[]
        else:
            self.holes=holes
            
        if regions is None:
            self.regions=[]
        else:
            self.regions=regions
    def __cmp__(self,other):
        
        # A dic for the initial m
        dic = self.Mesh2triangList()
        dic_mesh = self.Mesh2MeshList()
        for element in dic_mesh.keys():
            dic[element] = dic_mesh[element]
        
        # A dic for the exported/imported m
        dic_other = other.Mesh2triangList()
        dic_mesh = other.Mesh2MeshList()
        for element in dic_mesh.keys():
            dic_other[element] = dic_mesh[element]

        #print "dsg************************8"
        #print "dic ",dic
        #print "*******8"
        #print "mesh",dic_other
        #print "dic.__cmp__(dic_o)",dic.__cmp__(dic_other)
        #print "dsg************************8"
        
        return (dic.__cmp__(dic_other))
        
    def generateMesh(self, mode = None, maxArea = None, isRegionalMaxAreas = True):
        """
        Based on the current user vaules, holes and regions
        generate a new mesh
        mode is a string that sets conditions on the mesh generations
        see triangle_instructions.txt for a definition of the commands
        PreCondition: maxArea is a double
        """
        if mode == None:
            self.mode = ""
        else:
            self.mode = mode
        
        if not re.match('p',self.mode):
            self.mode += 'p' #p - read a planar straight line graph.
            #there must be segments to use this switch
            # TODO throw an aception if there aren't seg's
            # it's more comlex than this.  eg holes
        if not re.match('z',self.mode):
            self.mode += 'z' # z - Number all items starting from zero (rather than one)
        if not re.match('n',self.mode):
            self.mode += 'n' # n - output a list of neighboring triangles 
        if not re.match('A',self.mode):
            self.mode += 'A' # A - output region attribute list for triangles
        if not re.match('V',self.mode):
            self.mode += 'V' # V - output info about what Triangle is doing
        
        if maxArea != None:
            self.mode += 'a' + str(maxArea)

        if isRegionalMaxAreas:
            self.mode += 'a'
            
        meshDict = self.Mesh2triangList()
        #print "!@!@ This is going to triangle   !@!@"
        #print meshDict
        #print "!@!@ This is going to triangle   !@!@"

        #print "meshDict['segmentmarkerlist']", meshDict['segmentmarkerlist']
        #initialconversions = ['internal boundary', 'external boundary','internal boundary']
        [meshDict['segmentmarkerlist'],
         segconverter] =  segment_strings2ints(meshDict['segmentmarkerlist'],
                                             initialconversions)
        #print "regionlist",meshDict['regionlist']
        [meshDict['regionlist'],
         regionconverter] =  region_strings2ints(meshDict['regionlist'])
        #print "regionlist",meshDict['regionlist']
        
        #print "meshDict['segmentmarkerlist']", meshDict['segmentmarkerlist'
        generatedMesh = triang.genMesh(
                              meshDict['pointlist'],
                              meshDict['segmentlist'],
                              meshDict['holelist'],
                              meshDict['regionlist'],
                              meshDict['pointattributelist'],
                              meshDict['segmentmarkerlist'],
                              [],  # since the trianglelist isn't used
                              self.mode)
        #print "generated",generatedMesh['generatedsegmentmarkerlist']
        generatedMesh['generatedsegmentmarkerlist'] = \
                     segment_ints2strings(generatedMesh['generatedsegmentmarkerlist'],
                                  segconverter)
        #print "processed gen",generatedMesh['generatedsegmentmarkerlist']
        generatedMesh['generatedtriangleattributelist'] = \
         region_ints2strings(generatedMesh['generatedtriangleattributelist'],
                                  regionconverter)
        
        self.setTriangulation(generatedMesh)
    
    def addUserPoint(self, pointType, x,y):
        if pointType == Vertex:
            point = self.addUserVertex(x,y)
        if pointType == Hole:
            point = self.addHole(x,y)
        if pointType == Region:
            point = self.addRegion(x,y)
        return point
    
    def addUserVertex(self, x,y):
        v=Vertex(x, y)
        self.userVertices.append(v)
        return v

    def addHole(self, x,y):
        h=Hole(x, y)
        self.holes.append(h)
        return h
   
    def addRegion(self, x,y):
        h=Region(x, y)
        self.regions.append(h)
        return h
    
    def getUserVertices(self):
        return self.userVertices
    
    def getUserSegments(self):
        return self.userSegments
    
    def getTriangulation(self):
        return self.meshTriangles
    
    def getMeshVertices(self):
        return self.meshVertices
 
    def getMeshSegments(self):
        return self.meshSegments
    
    def getHoles(self):
        return self.holes
    
    def getRegions(self):
        return self.regions
    
    def isTriangulation(self):
        if self.meshVertices == []:
            return False 
        else:
            return True
    
    def addUserSegment(self, v1,v2):
        """
        PRECON: A segment between the two vertices is not already present.
        Check by calling isUserSegmentNew before calling this function.
        
        """
        s=Segment( v1,v2)
        self.userSegments.append(s)
        return s
    
    def clearTriangulation(self):

        #Clear the current generated mesh values
        self.meshTriangles=[] 
        self.meshSegments=[]
        self.meshVertices=[]

    def removeDuplicatedUserVertices(self):
        """Pre-condition: There are no user segments
        This function will keep the first duplicate
        """
        assert self.userSegments == []
        self.userVertices, counter =  self.removeDuplicatedVertices(self.userVertices)
        return counter
    
    def removeDuplicatedVertices(self, Vertices):
        """
        This function will keep the first duplicate, remove all others
        Precondition: Each vertex has a dupindex, which is the list
        index.
        """
        remove = []
        index = 0
        for v in Vertices:
            v.dupindex = index
            index += 1
        t = list(Vertices)
        t.sort(Point.cmp_xy)
    
        length = len(t)
        behind = 0
        ahead  = 1
        counter = 0
        while ahead < length:
            b = t[behind]
            ah = t[ahead]
            if (b.y == ah.y and b.x == ah.x):
                remove.append(ah.dupindex) 
            behind += 1
            ahead += 1

        # remove the duplicate vertices
        remove.sort()
        remove.reverse()
        for i in remove:
            Vertices.pop(i)
            pass

        #Remove the attribute that this function added
        for v in Vertices:
            del v.dupindex
        return Vertices,counter
    
    def thinoutVertices(self, delta):
        """Pre-condition: There are no user segments
        This function will keep the first duplicate
        """
        assert self.userSegments == []
        #t = self.userVertices
        #self.userVertices =[]
        boxedVertices = {}
        thinnedUserVertices =[]
        delta = round(delta,1)
        
        for v in self.userVertices :
            # marker is the center of the boxes
            marker = (round(v.x/delta,0)*delta,round(v.y/delta,0)*delta)
            #this creates a dict of lists of faces, indexed by marker
            boxedVertices.setdefault(marker,[]).append(v)

        for [marker,verts] in boxedVertices.items():
            min = delta
            bestVert = None
            markerVert = Vertex(marker[0],marker[1])
            for v in verts:
                dist = v.DistanceToPoint(markerVert)
                if (dist<min):
                    min = dist
                    bestVert = v
            thinnedUserVertices.append(bestVert)
        self.userVertices =thinnedUserVertices
        
            
    def isUserSegmentNew(self, v1,v2):
        identicalSegs= [x for x in self.userSegments if (x.vertices[0] == v1 and x.vertices[1] == v2) or (x.vertices[0] == v2 and x.vertices[1] == v1) ]
        
        return len(identicalSegs) == 0

    def deleteSegsOfVertex(self, delVertex):
        """
        Delete this vertex and any segments that connect to it.
        """
        #Find segments that connect to delVertex
        deletedSegments = []
        for seg in self.userSegments:
            if (delVertex in seg.vertices):
                deletedSegments.append(seg)
        # Delete segments that connect to delVertex
        for seg in deletedSegments:
            self.userSegments.remove(seg)
        # Delete delVertex
        # self.userVertices.remove(delVertex)
        return deletedSegments

    
    def deleteMeshObject(self, MeshObject):
        """
        Returns a list of all objects that were removed
        """
        deletedObs = []
        if isinstance(MeshObject, Vertex ):
            deletedObs = self.deleteSegsOfVertex(MeshObject)
            deletedObs.append(MeshObject)
            self.userVertices.remove(MeshObject)
        elif isinstance(MeshObject, Segment):
            deletedObs.append(MeshObject)
            self.userSegments.remove(MeshObject)
        elif isinstance(MeshObject, Hole):
            deletedObs.append(MeshObject)
            self.holes.remove(MeshObject)
        elif isinstance(MeshObject, Region):
            deletedObs.append(MeshObject)
            self.regions.remove(MeshObject)          
        return deletedObs
                                                 
    def Mesh2triangList(self):
        """
        Convert the Mesh to a dictionary of the lists needed for the triang modul;
        points list: [(x1,y1),(x2,y2),...] (Tuples of doubles)
        pointattributelist: [(a11,a12,...),(a21,a22),...] (Tuples of doubles)
        segment list: [(point1,point2),(p3,p4),...] (Tuples of integers) 
        hole list: [(x1,y1),...](Tuples of doubles, one inside each hole region)
        regionlist: [ (x1,y1,index),...] (Tuple of 3 doubles) 
        Note, this adds an index attribute to the user Vertex objects.
        """
        
        meshDict = {}
        
        pointlist=[]
        pointattributelist=[]
        
        index = 0
        for vertex in self.userVertices:
            vertex.index = index 
            pointlist.append((vertex.x,vertex.y))
            pointattributelist.append((vertex.attributes))
            
            index += 1
        meshDict['pointlist'] = pointlist
        meshDict['pointattributelist'] = pointattributelist

        segmentlist=[]
        segmentmarkerlist=[]
        for seg in self.userSegments:
            segmentlist.append((seg.vertices[0].index,seg.vertices[1].index))
            segmentmarkerlist.append(seg.marker)
        meshDict['segmentlist'] =segmentlist 
        meshDict['segmentmarkerlist'] =segmentmarkerlist 

        holelist=[]
        for hole in self.holes:
            holelist.append((hole.x,hole.y)) 
        meshDict['holelist'] = holelist
        
        regionlist=[]
        for region in self.regions:
            if (region.getMaxArea() != None): 
                regionlist.append((region.x,region.y,region.getTag(),
                               region.getMaxArea()))
            else:
                regionlist.append((region.x,region.y,region.getTag()))
        meshDict['regionlist'] = regionlist
        #print "*(*("
        #print meshDict
        #print meshDict['regionlist']
        #print "*(*("
        return meshDict
                                                
    def Mesh2MeshList(self):
        """
        Convert the Mesh to a dictionary of lists describing the triangulation variables;
        generated point list: [(x1,y1),(x2,y2),...] (Tuples of doubles)
        generated point attribute list: [(a11,a12,...),(a21,a22),...] (Tuples of doubles)
        generated segment list: [(point1,point2),(p3,p4),...] (Tuples of integers) 
        hole list: [(x1,y1),...](Tuples of doubles, one inside each hole region)
        regionlist: [ (x1,y1,index),...] (Tuple of 3 doubles) 
        Note, this adds an index attribute to the user Vertex objects.
        """
        
        meshDict = {}        
        pointlist=[]
        pointattributelist=[]
        
        index = 0
        for vertex in self.meshVertices:
            vertex.index = index 
            pointlist.append((vertex.x,vertex.y))
            pointattributelist.append((vertex.attributes))           
            index += 1
            
        meshDict['generatedpointlist'] = pointlist
        meshDict['generatedpointattributelist'] = pointattributelist

        #segments
        segmentlist=[]
        segmentmarkerlist=[]
        for seg in self.meshSegments:
            segmentlist.append((seg.vertices[0].index,seg.vertices[1].index))
            segmentmarkerlist.append(seg.marker)
        meshDict['generatedsegmentlist'] =segmentlist 
        meshDict['generatedsegmentmarkerlist'] =segmentmarkerlist 

        # Make sure that the indexation is correct
        index = 0
        for tri in self.meshTriangles:
            tri.index = index           
            index += 1

        trianglelist = []
        triangleattributelist = []
        triangleneighborlist = []
        for tri in self.meshTriangles:  
            trianglelist.append((tri.vertices[0].index,tri.vertices[1].index,tri.vertices[2].index))  
            triangleattributelist.append(tri.attribute)
            neighborlist = [-1,-1,-1]
            for neighbor,index in map(None,tri.neighbors,
                                      range(len(tri.neighbors))):
                if neighbor:    
                    neighborlist[index] = neighbor.index
            triangleneighborlist.append(neighborlist)
        
        meshDict['generatedtrianglelist'] = trianglelist 
        meshDict['generatedtriangleattributelist'] = triangleattributelist
        meshDict['generatedtriangleneighborlist'] = triangleneighborlist
        
        #print "*(*("
        #print meshDict
        #print "*(*("

        return meshDict

                               
    def Mesh2MeshDic(self):
        """
        Convert the user and generated info of a mesh to a dictionary
        structure
        """
        dic = self.Mesh2triangList()
        dic_mesh = self.Mesh2MeshList()
        for element in dic_mesh.keys():
            dic[element] = dic_mesh[element]
        return dic
    
    def setTriangulation(self, genDict):
        """
        Set the mesh attributes given a dictionary of the lists
        returned from the triang module       
        generated point list: [(x1,y1),(x2,y2),...] (Tuples of doubles)  
        generated point attribute list:[(P1att1,P1attt2, ...),(P2att1,P2attt2,...),...]
        generated segment list: [(point1,point2),(p3,p4),...] (Tuples of integers)
        generated segment marker list: [S1Marker, S2Marker, ...] (list of ints)
        triangle list:  [(point1,point2, point3),(p5,p4, p1),...] (Tuples of integers)
        triangle neighbor list: [(triangle1,triangle2, triangle3),(t5,t4, t1),...] (Tuples of integers) -1 means there's no triangle neighbor
        triangle attribute list: [(T1att), (T2att), ...] (list of a list of strings)
        """

        #Clear the current generated mesh values
        self.meshTriangles=[] 
        self.meshSegments=[]
        self.meshVertices=[]

        #print "@#@#@#"
        #print genDict
        #print "@#@#@#"
        
        index = 0
        for point in genDict['generatedpointlist']:
            v=Vertex(point[0], point[1])
            v.index = index
            index +=1
            self.meshVertices.append(v)

        index = 0
        for seg,marker in map(None,genDict['generatedsegmentlist'],genDict['generatedsegmentmarkerlist']):
            segObject = Segment( self.meshVertices[seg[0]],
                           self.meshVertices[seg[1]], marker = marker )
            segObject.index = index
            index +=1
            self.meshSegments.append(segObject)

        index = 0
        for triangle in genDict['generatedtrianglelist']:
            tObject =Triangle( self.meshVertices[triangle[0]],
                        self.meshVertices[triangle[1]],
                        self.meshVertices[triangle[2]] )
            tObject.index = index
            index +=1
            self.meshTriangles.append(tObject)

        index = 0
        for att in genDict['generatedtriangleattributelist']:
            if att == []:
                self.meshTriangles[index].setAttribute("")
            else:
                # Note, is the first attribute always the region att?
                # haven't confirmed this
                self.meshTriangles[index].setAttribute(att[0])
            index += 1
            
        index = 0
        for att in genDict['generatedpointattributelist']:
            if att == None:
                self.meshVertices[index].setAttributes([])
            else:
                self.meshVertices[index].setAttributes(att)
            index += 1
    
        index = 0
        for triangle in genDict['generatedtriangleneighborlist']:
            # Build a list of triangle object neighbors
            ObjectNeighbor = []
            for neighbor in triangle:
                if ( neighbor != -1):
                    ObjectNeighbor.append(self.meshTriangles[neighbor])
                else:
                    ObjectNeighbor.append(None)
            self.meshTriangles[index].setNeighbors(ObjectNeighbor[0],ObjectNeighbor[1],ObjectNeighbor[2])
            index += 1


    def setMesh(self, genDict):
        """
        Set the user Mesh attributes given a dictionary of the lists
        point list: [(x1,y1),(x2,y2),...] (Tuples of doubles)  
        point attribute list:[(P1att1,P1attt2, ...),(P2att1,P2attt2,...),...]
        segment list: [(point1,point2),(p3,p4),...] (Tuples of integers)
        segment marker list: [S1Marker, S2Marker, ...] (list of ints)
        region list: [(x1,y1),(x2,y2),...] (Tuples of doubles)
        region attribute list: ["","reservoir",""] list of strings
        region max area list:[real, None, Real,...] list of None and reals
        
        mesh is an instance of a mesh object
        """

        #Clear the current user mesh values
        self.userSegments=[]
        self.userVertices=[]
        self.Holes=[]
        self.Regions=[]

        #print "@#@#@#"
        #print genDict
        #print "@#@#@#"
        
        #index = 0
        for point in genDict['pointlist']:
            v=Vertex(point[0], point[1])
            #v.index = index
            #index +=1
            self.userVertices.append(v)

        #index = 0
        for seg,marker in map(None,genDict['segmentlist'],genDict['segmentmarkerlist']):
            segObject = Segment( self.userVertices[seg[0]],
                           self.userVertices[seg[1]], marker = marker )
            #segObject.index = index
            #index +=1
            self.userSegments.append(segObject)

# Remove the loading of attribute info.
# Have attribute info added using least_squares in pyvolution
#         index = 0
#         for att in genDict['pointattributelist']:
#             if att == None:
#                 self.userVertices[index].setAttributes([])
#             else:
#                 self.userVertices[index].setAttributes(att)
#            index += 1
        
        #index = 0
        for point in genDict['holelist']:
            h=Hole(point[0], point[1])
            #h.index = index
            #index +=1
            self.holes.append(h)

        #index = 0
        for reg,att,maxArea in map(None,
                                   genDict['regionlist'],
                                   genDict['regionattributelist'],
                                   genDict['regionmaxarealist']):
            Object = Region( reg[0],
                             reg[1],
                             tag = att,
                             maxArea = maxArea)
            #Object.index = index
            #index +=1
            self.regions.append(Object)
        
    def addVertsSegs(self, outlineDict):
        """
        Add out-line (user Mesh) attributes given a dictionary of the lists
        point list: [(x1,y1),(x2,y2),...] (Tuples of doubles)  
        segment list: [(point1,point2),(p3,p4),...] (Tuples of integers)
        #segment marker list: [S1Marker, S2Marker, ...] (list of ints)
        """

        localUserVertices = []
        #index = 0
        for point in outlineDict['pointlist']:
            v=Vertex(point[0], point[1])
            #v.index = index
            #index +=1
            self.userVertices.append(v)
            localUserVertices.append(v)
            
        #index = 0
        for seg in map(None,outlineDict['segmentlist']):
            segObject = Segment( localUserVertices[seg[0]],
                           localUserVertices[seg[1]] )
            #segObject.index = index
            #index +=1
            self.userSegments.append(segObject)
        
    def TestautoSegment(self):
        newsegs = []
        s1 = Segment(self.userVertices[0],
                               self.userVertices[1])
        s2 = Segment(self.userVertices[0],
                               self.userVertices[2])
        s3 = Segment(self.userVertices[2],
                               self.userVertices[1])
        if self.isUserSegmentNew(s1.vertices[0],s1.vertices[1]):
            newsegs.append(s1)
        if self.isUserSegmentNew(s2.vertices[0],s2.vertices[1]):
            newsegs.append(s2)
        if self.isUserSegmentNew(s3.vertices[0],s3.vertices[1]):
            newsegs.append(s3)
        self.userSegments.extend(newsegs)
        return newsegs

    
    def savePickle(self, currentName):
        fd = open(currentName, 'w')
        pickle.dump(self,fd)
        fd.close()

    def autoSegment(self):
        """
        initially work by running an executable
        Later compile the c code with a python wrapper.

        Precon: There must be 3 or more vertices in the userVertices structure
        """
        newsegs = []
        inputfile = 'hull_in.txt'
        outputfile = inputfile + '-alf'
        #write vertices to file
        fd = open(inputfile,'w')
        for v in self.userVertices:
            fd.write(str(v.x))
            fd.write(' ')
            fd.write(str(v.y))
            fd.write('\n')
        fd.close()

        # os.system('SET PATH=..\pmesh;%PATH%') # this doesn't work
        #print "os.getcwd()",os.getcwd()    # this could be usefull
        #command = "k:\\EQRMsens\\" + s
        #os.chdir(command)
        #command = 'env'
        #os.system(command)
        
        #run hull executable
        #warning need to compile hull for the current operating system
        command = 'hull.exe -A -i ' + inputfile
        os.system(command)
        
        #read results into this object
        fd = open(outputfile)
        lines = fd.readlines()
        fd.close()
        #print "(*(*(*("
        #print lines
        #print "(*(*(*("
        lines.pop(0) #remove the first (title) line
        for line in lines:
            vertindexs = line.split()
            #print 'int(vertindexs[0])', int(vertindexs[0])
            #print 'int(vertindexs[1])', int(vertindexs[1])
            #print 'self.userVertices[int(vertindexs[0])]' ,self.userVertices[int(vertindexs[0])]
            #print 'self.userVertices[int(vertindexs[1])]' ,self.userVertices[int(vertindexs[1])]
            v1 = self.userVertices[int(vertindexs[0])]
            v2 = self.userVertices[int(vertindexs[1])]
            
            if self.isUserSegmentNew(v1,v2):
                newseg = Segment(v1, v2)
                newsegs.append(newseg)
        self.userSegments.extend(newsegs)
        return newsegs
     
    def joinVertices(self):
        """
        Return list of segments connecting all userVertices
        in the order they were given
        
        Precon: There must be 3 or more vertices in the userVertices structure
        """

        newsegs = []
        
        v1 = self.userVertices[0]
        for v2 in self.userVertices[1:]:
            if self.isUserSegmentNew(v1,v2):            
                newseg = Segment(v1, v2)
                newsegs.append(newseg)
            v1 = v2

        #Connect last point to the first
        v2 = self.userVertices[0]        
        if self.isUserSegmentNew(v1,v2):            
                newseg = Segment(v1, v2)
                newsegs.append(newseg)
            

        #Update list of user segments        
        self.userSegments.extend(newsegs)                
        return newsegs
    
    def normaliseMesh(self,scale, offset, height_scale):
        [xmin, ymin, xmax, ymax] = self.boxsize()
        [attmin0, attmax0] = self.maxMinVertAtt(0)
        #print "[attmin0, attmax0]" ,[attmin0, attmax0] 
        [attmin1, attmax1] = self.maxMinVertAtt(1)
        #print [xmin, ymin, xmax, ymax]
        xrange = xmax - xmin
        yrange = ymax - ymin
        if xrange > yrange:
            min,max = xmin, xmax
        else:
            min,max = ymin, ymax
            
        for obj in self.getUserVertices():
            obj.x = (obj.x - xmin)/(max- min)*scale + offset
            obj.y = (obj.y - ymin)/(max- min)*scale + offset
            if len(obj.attributes)  > 0 and attmin0 != attmax0:
                obj.attributes[0] = (obj.attributes[0]-attmin0)/ \
                                    (attmax0-attmin0)*height_scale
            if len(obj.attributes) > 1 and attmin1 != attmax1:
                obj.attributes[1] = (obj.attributes[1]-attmin1)/ \
                                    (attmax1-attmin1)*height_scale
            
        for obj in self.getMeshVertices():
            obj.x = (obj.x - xmin)/(max- min)*scale + offset
            obj.y = (obj.y - ymin)/(max- min)*scale + offset
            if len(obj.attributes)  > 0 and attmin0 != attmax0:
                obj.attributes[0] = (obj.attributes[0]-attmin0)/ \
                                    (attmax0-attmin0)*height_scale
            if len(obj.attributes) > 1 and attmin1 != attmax1:
                obj.attributes[1] = (obj.attributes[1]-attmin1)/ \
                                    (attmax1-attmin1)*height_scale
                
        for obj in self.getHoles():
            obj.x = (obj.x - xmin)/(max- min)*scale + offset
            obj.y = (obj.y - ymin)/(max- min)*scale + offset
        for obj in self.getRegions():
            obj.x = (obj.x - xmin)/(max- min)*scale + offset
            obj.y = (obj.y - ymin)/(max- min)*scale + offset
        [xmin, ymin, xmax, ymax] = self.boxsize()
        #print [xmin, ymin, xmax, ymax]
     
    def boxsize(self):
        """
        Returns a list denoting a box that contains the entire structure of vertices
        Structure: [xmin, ymin, xmax, ymax] 
        """
        # FIXME dsg!!! large is a hack
        #You want the kinds package, part of Numeric:
        #In [2]: import kinds
        
        #In [3]: kinds.default_float_kind.M
        #kinds.default_float_kind.MAX         kinds.default_float_kind.MIN
    #kinds.default_float_kind.MAX_10_EXP  kinds.default_float_kind.MIN_10_EXP
        #kinds.default_float_kind.MAX_EXP     kinds.default_float_kind.MIN_EXP

        #In [3]: kinds.default_float_kind.MIN
        #Out[3]: 2.2250738585072014e-308

        large = 1e100
        xmin= large
        xmax=-large
        ymin= large
        ymax=-large
        for vertex in self.userVertices:
            if vertex.x < xmin:
                xmin = vertex.x 
            if vertex.x > xmax:
                xmax = vertex.x
                
            if vertex.y < ymin:
                ymin = vertex.y 
            if vertex.y > ymax:
                ymax = vertex.y
        return [xmin, ymin, xmax, ymax]
 
    def maxMinVertAtt(self, iatt):
        """
        Returns a list denoting a box that contains the entire structure of vertices
        Structure: [xmin, ymin, xmax, ymax] 
        """
        # FIXME dsg!!! large is a hack
        #You want the kinds package, part of Numeric:
        #In [2]: import kinds
        
        #In [3]: kinds.default_float_kind.M
        #kinds.default_float_kind.MAX         kinds.default_float_kind.MIN
    #kinds.default_float_kind.MAX_10_EXP  kinds.default_float_kind.MIN_10_EXP
        #kinds.default_float_kind.MAX_EXP     kinds.default_float_kind.MIN_EXP

        #In [3]: kinds.default_float_kind.MIN
        #Out[3]: 2.2250738585072014e-308

        large = 1e100
        min= large
        max=-large
        for vertex in self.userVertices:
            if len(vertex.attributes) > iatt:
                if vertex.attributes[iatt] < min:
                    min = vertex.attributes[iatt]
                if vertex.attributes[iatt] > max:
                    max = vertex.attributes[iatt] 
        for vertex in self.meshVertices:
            if len(vertex.attributes) > iatt:
                if vertex.attributes[iatt] < min:
                    min = vertex.attributes[iatt]
                if vertex.attributes[iatt] > max:
                    max = vertex.attributes[iatt] 
        return [min, max]
    
    def scaleoffset(self, WIDTH, HEIGHT):
        """
        Returns a list denoting the scale and offset terms that need to be
        applied when converting  mesh co-ordinates onto grid co-ordinates 
        Structure: [scale, xoffset, yoffset] 
        """   
        OFFSET = 0.05*min([WIDTH, HEIGHT])
        [xmin, ymin, xmax, ymax] = self.boxsize()
        SCALE = min([0.9*WIDTH, 0.9*HEIGHT])/max([xmax-xmin, ymax-ymin])
        
        if SCALE*xmin < OFFSET:
            xoffset = abs(SCALE*xmin) + OFFSET
        if SCALE*xmax > WIDTH - OFFSET:
            xoffset= -(SCALE*xmax - WIDTH + OFFSET)
        if SCALE*ymin < OFFSET:
            b = abs(SCALE*ymin)+OFFSET
        if SCALE*ymax > HEIGHT-OFFSET:
            b = -(SCALE*ymax - HEIGHT + OFFSET)
        yoffset = HEIGHT - b
        return [SCALE, xoffset, yoffset]
            
    def plotMeshTriangle(self,tag = 0,WIDTH = 400,HEIGHT = 400):
        """
        Plots all node connections.
        tag = 0 (no node numbers), tag = 1 (node numbers)
        """

        try:
            from Tkinter import Tk, Frame, Button, Canvas, BOTTOM, Label

            [SCALE, xoffset, yoffset] = self.scaleoffset( WIDTH, HEIGHT)
            
            root = Tk()
            frame = Frame(root)
            frame.pack()
            button = Button(frame, text="OK", fg="red", command=frame.quit)
            button.pack(side=BOTTOM)
            canvas = Canvas(frame,bg="white", width=WIDTH, height=HEIGHT)
            canvas.pack()
            text = Label(frame, width=20, height=10, text='triangle mesh')
            text.pack()

            #print self.meshTriangles
            for triangle in self.meshTriangles:
                triangle.draw(canvas,1,
                              scale = SCALE,
                              xoffset = xoffset,
                              yoffset = yoffset )
                
            root.mainloop()

        except:
            print "Unexpected error:", sys.exc_info()[0]
            raise

            #print """
            #node::plot Failed.
            #Most probably, the Tkinter module is not available.
            #"""

    def plotUserSegments(self,tag = 0,WIDTH = 400,HEIGHT = 400):
        """
        Plots all node connections.
        tag = 0 (no node numbers), tag = 1 (node numbers)
        """

        try:
            from Tkinter import Tk, Frame, Button, Canvas, BOTTOM, Label
            
            [SCALE, xoffset, yoffset] = self.scaleoffset( WIDTH, HEIGHT)

            root = Tk()
            frame = Frame(root)
            frame.pack()
            button = Button(frame, text="OK", fg="red", command=frame.quit)
            button.pack(side=BOTTOM)
            canvas = Canvas(frame, bg="white", width=WIDTH, height=HEIGHT)
            canvas.pack()
            text = Label(frame, width=20, height=10, text='user segments')
            text.pack()
           
            for segment in self.userSegments:
                segment.draw(canvas,SCALE, xoffset, yoffset )
                
            root.mainloop()

        except:
            print "Unexpected error:", sys.exc_info()[0]
            raise

            #print """
            #node::plot Failed.
            #Most probably, the Tkinter module is not available.
            #"""
      
    def exportASCIItrianglulationfile(self,ofile):
        """
        export a file, ofile, with the format
        
        First line:  <# of vertices> <# of attributes>
        Following lines:  <vertex #> <x> <y> [attributes]
        One line:  <# of triangles> 
        Following lines:  <triangle #> <vertex #>  <vertex #> <vertex #> <neigbouring triangle #> <neigbouring triangle #> <neigbouring triangle #> [attribute of region]
        One line:  <# of segments> 
        Following lines:  <segment #> <vertex #>  <vertex #> [boundary marker]
        """
        fd = open(ofile,'w')
        gen_dict = self.Mesh2MeshList()
        load_mesh.loadASCII.write_ASCII_trianglulation(fd,gen_dict)
        self.writeASCIImesh(fd,
                            self.userVertices,
                            self.userSegments,
                            self.holes,
                            self.regions)    
        fd.close()

    def exportASCIIsegmentoutlinefile(self,ofile):
        """
        export a file, ofile, with no triangulation and only vertices connected to segments.
        """
        fd = open(ofile,'w')
        meshDict = {}
        
        meshDict['generatedpointlist'] = []
        meshDict['generatedpointattributelist'] = []
        meshDict['generatedsegmentlist'] = []
        meshDict['generatedsegmentmarkerlist'] = []

        meshDict['generatedtrianglelist'] = [] 
        meshDict['generatedtriangleattributelist'] = []
        meshDict['generatedtriangleneighborlist'] = []
        
        load_mesh.loadASCII.write_ASCII_trianglulation(fd,meshDict)
        self.writeASCIIsegmentoutline(fd,
                            self.userVertices,
                            self.userSegments,
                            self.holes,
                            self.regions)    
        fd.close()

    def exportASCIIobj(self,ofile):
        """
        export a file, ofile, with the format
         lines:  v <x> <y> <first attribute>
        f <vertex #>  <vertex #> <vertex #> (of the triangles)
        """
        fd = open(ofile,'w')
        self.writeASCIIobj(fd)   
        fd.close()


    def writeASCIIobj(self,fd):
        fd.write(" # Triangulation as an obj file\n")
        numVert = str(len(self.meshVertices))
        
        index1 = 1 
        for vert in self.meshVertices:
            vert.index1 = index1
            index1 += 1
            
            fd.write("v "
                     + str(vert.x) + " "
                     + str(vert.y) + " "
                     + str(vert.attributes[0]) + "\n")
            
        for tri in self.meshTriangles:
            fd.write("f "
                     + str(tri.vertices[0].index1) + " " 
                     + str(tri.vertices[1].index1) + " " 
                     + str(tri.vertices[2].index1) + "\n")
                
    def writeASCIIsegmentoutline(self,
                       fd,
                       userVertices,
                       userSegments,
                       holes,
                       regions):
        """Write the user mesh info, only with vertices that are connected to segs
        """
        verts = []
        #dupindex = 0
        for seg in self.userSegments:
            verts.append(seg.vertices[0])
            verts.append(seg.vertices[1])
        #print 'verts>',verts

        verts, count = self.removeDuplicatedVertices(verts)
        #print 'verts no dups>',verts
        self.writeASCIImesh(fd,
                            verts,
                            self.userSegments,
                            self.holes,
                            self.regions)    
           
    def exportASCIImeshfile(self,ofile):
        """
        export a file, ofile, with the format
        
        First line:  <# of user vertices> <# of attributes>
        Following lines:  <x> <y> [attributes]
        One line:  <# of segments> 
        Following lines:  <segment #> <vertex #>  <vertex #> [boundary marker]
        """
        
        fd = open(ofile,'w')
        self.writeASCIImesh(fd,
                            self.userVertices,
                            self.userSegments,
                            self.holes,
                            self.regions)        
        fd.close()

    def writeASCIImesh(self,
                       fd,
                       userVertices,
                       userSegments,
                       holes,
                       regions):
        numVert = str(len(userVertices))
        if (numVert == "0"):
            numVertAttrib = "0"
        else:
            numVertAttrib = str(len(userVertices[0].attributes))
        fd.write(numVert + " " + numVertAttrib + " # <vertex #> <x> <y> [attributes] ...Mesh Vertices..." + "\n")
        
        # <x> <y> [attributes]
        index = 0 
        for vert in userVertices:
            vert.index = index
            index += 1
            attlist = ""
            for att in vert.attributes:
                attlist = attlist + str(att)+" "
            attlist.strip()
            fd.write(str(vert.index) + " "
                     +str(vert.x) + " "
                     + str(vert.y) + " "
                     + attlist + "\n")
            
        #One line:  <# of segments> 
        fd.write(str(len(userSegments)) + 
                 " # <segment #> <vertex #>  <vertex #> [boundary marker] ...Mesh Segments..." + "\n")
        
        #Following lines:  <vertex #>  <vertex #> [boundary marker]
        index = 0
        for seg in userSegments:
            fd.write(str(index) + " "
                     + str(seg.vertices[0].index) + " " 
                     + str(seg.vertices[1].index) + " " 
                     + str(seg.marker) + "\n")
            index += 1

        #One line:  <# of holes> 
        fd.write(str(len(holes)) + 
                 " # <Hole #> <x> <y> ...Mesh Holes..." + "\n")    
        # <x> <y>
        index = 0
        for h in holes:
            fd.write(str(index) + " "
                     + str(h.x) + " "
                     + str(h.y) + "\n")
            index += 1
        
        #One line:  <# of regions> 
        fd.write(str(len(regions)) + 
                 " # <Region #> <x> <y> <tag>...Mesh Regions..." + "\n")    
        # <index> <x> <y> <tag>
        index = 0
        for r in regions:
            fd.write(str(index) + " " 
                     + str(r.x) + " "
                     + str(r.y)+ " "
                     + str(r.getTag()) + "\n")
            index += 1
        index = 0
        # <index> [<MaxArea>|""]
        for r in regions:
            area = r.getMaxArea()
            if area == None:
                area = ""
            else:
                area = str(area)
            
            fd.write(str(index) + " " + area + "\n")
            index += 1
                
    def exportxyafile(self,ofile):
        """
        export a file, ofile, with the format
        
        First line:  <# of vertices> <# of attributes>
        Following lines:  <vertex #> <x> <y> [attributes]
        """
        #load_mesh.loadASCII

        if self.meshVertices == []:
            Vertices = self.userVertices
        else:
            Vertices = self.meshVertices
            
        numVert = str(len(Vertices))
        
        if Vertices == []:
            raise RuntimeError
        numVertAttrib = str(len(Vertices[0].attributes))
        title = numVert + " " + numVertAttrib + " # <vertex #> <x> <y> [attributes]"

        #Convert the Vertices to pointlist and pointattributelist
        xya_dict = {}
        pointattributes = []
        points = []
        
        for vert in Vertices:
            points.append([vert.x,vert.y])
            pointattributes.append(vert.attributes)
            
        xya_dict['pointlist'] = points
        xya_dict['pointattributelist'] = pointattributes

        load_mesh.loadASCII.export_xya_file(ofile, xya_dict, title, delimiter = " ")
        
def importUngenerateFile(ofile):
    """
    import a file, ofile, with the format
    [poly]
    poly format:
    First line:  <# of vertices> <x centroid> <y centroid>
    Following lines: <x> <y> 
    last line:  "END"

    Note: These are clockwise.
    """
    fd = open(ofile,'r')
    Dict = readUngenerateFile(fd)
    fd.close()
    return Dict

def readUngenerateFile(fd):
    """
    import a file, ofile, with the format
    [poly]
    poly format:
    First line:  <# of polynomial> <x centroid> <y centroid>
    Following lines: <x> <y> 
    last line:  "END"
    """
    END_DELIMITER = 'END\n'
    
    points = []
    segments = []
    
    isEnd = False
    line = fd.readline() #not used <# of polynomial> <x> <y>
    while not isEnd:
        line = fd.readline()
        fragments = line.split()
        vert = [float(fragments.pop(0)),float(fragments.pop(0))]
        points.append(vert)
        PreviousVertIndex = len(points)-1
        firstVertIndex = PreviousVertIndex
        
        line = fd.readline() #Read the next line
        while line <> END_DELIMITER: 
            #print "line >" + line + "<"
            fragments = line.split()
            vert = [float(fragments.pop(0)),float(fragments.pop(0))]
            points.append(vert)
            thisVertIndex = len(points)-1
            segment = [PreviousVertIndex,thisVertIndex]
            segments.append(segment)
            PreviousVertIndex = thisVertIndex
            line = fd.readline() #Read the next line
            i =+ 1
        # If the last and first segments are the same,
        # Remove the last segment and the last vertex
        # then add a segment from the second last vert to the 1st vert
        thisVertIndex = len(points)-1
        firstVert = points[firstVertIndex]
        thisVert = points[thisVertIndex]
        #print "firstVert",firstVert
        #print "thisVert",thisVert
        if (firstVert[0] == thisVert[0] and firstVert[1] == thisVert[1]):
            points.pop()
            segments.pop()
            thisVertIndex = len(points)-1
            segments.append([thisVertIndex, firstVertIndex])
        
        line = fd.readline() # read <# of polynomial> <x> <y> OR END
        #print "line >>" + line + "<<"
        if line == END_DELIMITER:
            isEnd = True
    
    #print "points", points       
    #print "segments", segments
    ungenerated_dict = {}
    ungenerated_dict['pointlist'] = points
    ungenerated_dict['segmentlist'] = segments
    return ungenerated_dict

def importMeshFromFile(ofile):
    """returns a mesh object, made from a .xya or .txh file
    Often raises SyntaxError, IOError
    """
    newmesh = None
    if ofile[-4:]== ".xya":
        print "loading " + ofile
        try:
            dict = load_mesh.loadASCII.load_xya_file(ofile, delimiter = ',')
        except SyntaxError:
            dict = load_mesh.loadASCII.load_xya_file(ofile, delimiter = ' ')
        newmesh= Mesh()
        newmesh.setMesh(dict)
        counter = newmesh.removeDuplicatedUserVertices()
        if (counter >0):
            print "%i duplicate vertices removed from dataset" % (counter) 
    elif ofile[-4:]== ".tsh":
        dict = load_mesh.loadASCII.import_trianglulation(ofile)
        newmesh= Mesh()
        newmesh.setMesh(dict)
        newmesh.setTriangulation(dict)
    else:
        raise RuntimeError
    return newmesh

def loadPickle(currentName):
    fd = open(currentName)
    mesh = pickle.load(fd)
    fd.close()
    return mesh
    
def square_outline(side_length = 1,up = "top", left = "left", right = "right",
                   down = "bottom"):
    
        a = Vertex (0,0)
        b = Vertex (0,side_length)
        c = Vertex (side_length,0)
        d = Vertex (side_length,side_length)
      
        s2 = Segment(b,d, marker = up)
        s3 = Segment(b,a, marker = left)
        s4 = Segment(d,c, marker = right)
        s5 = Segment(a,c, marker = down)
     
        return Mesh(userVertices=[a,b,c,d],
                 userSegments=[s2,s3,s4,s5]) 

def region_strings2ints(region_list):
    """Given a list of (x_int,y_int,marker_string) lists it returns a list of
    (x_int,y_int,marker_int) and a list to convert the marker_int's back to
    the marker_strings  
    """
    # Make sure "" has an index of 0 
    region_list.reverse()
    region_list.append((1.0,2.0,""))
    region_list.reverse()
    convertint2string = []
    for i in xrange(len(region_list)):
        convertint2string.append(region_list[i][2])
        if len(region_list[i]) == 4: # there's an area value
            region_list[i] = (region_list[i][0],
                              region_list[i][1],i,region_list[i][3])
        elif len(region_list[i]) == 3: # no area value
            region_list[i] = (region_list[i][0],region_list[i][1],i)
        else:
            print "The region list has a bad size"
            # raise an error ..
            raise Error

    #remove "" from the region_list
    region_list.pop(0)
    
    return [region_list, convertint2string]

def region_ints2strings(region_list,convertint2string):
    """Reverses the transformation of region_strings2ints
    """
    if region_list[0] != []:
        for i in xrange(len(region_list)):
            region_list[i] = [convertint2string[int(region_list[i][0])]]
    return region_list

def segment_ints2strings(intlist, convertint2string):
    """Reverses the transformation of segment_strings2ints """
    stringlist = []
    for x in intlist:
        stringlist.append(convertint2string[x])
    return stringlist

def segment_strings2ints(stringlist, preset):
    """Given a list of strings return a list of 0 to n ints which represent
    the strings and a converting list of the strings, indexed by 0 to n ints.
    Also, input an initial converting list of the strings
    Note, the converting list starts off with
    ["internal boundary", "external boundary", "internal boundary"]
    example input and output 
    input ["a","b","a","c"],["c"]
    output [[2, 1, 2, 0], ['c', 'b', 'a']]

    the first element in the converting list will be
    overwritten with "".
    ?This will become the third item in the converting list?
    
    # note, order the initial converting list is important,
     since the index = the int marker
    """
    nodups = unique(stringlist)
    # note, order is important, the index = the int marker
    #preset = ["internal boundary", "external boundary"]
    #Remove the preset tags from the list with no duplicates
    nodups = [x for x in nodups if x not in preset]

    try:
        nodups.remove("") # this has to go to zero
    except ValueError:
        pass
    
    # Add the preset list at the beginning of no duplicates
    preset.reverse()
    nodups.extend(preset)
    nodups.reverse()

        
    convertstring2int = {}
    convertint2string = []
    index = 0
    for x in nodups:
        convertstring2int[x] = index
        convertint2string.append(x)
        index += 1
    convertstring2int[""] = 0

    intlist = []
    for x in stringlist:
        intlist.append(convertstring2int[x])
    return [intlist, convertint2string]


def unique(s):
    """Return a list of the elements in s, but without duplicates.

    For example, unique([1,2,3,1,2,3]) is some permutation of [1,2,3],
    unique("abcabc") some permutation of ["a", "b", "c"], and
    unique(([1, 2], [2, 3], [1, 2])) some permutation of
    [[2, 3], [1, 2]].

    For best speed, all sequence elements should be hashable.  Then
    unique() will usually work in linear time.

    If not possible, the sequence elements should enjoy a total
    ordering, and if list(s).sort() doesn't raise TypeError it's
    assumed that they do enjoy a total ordering.  Then unique() will
    usually work in O(N*log2(N)) time.

    If that's not possible either, the sequence elements must support
    equality-testing.  Then unique() will usually work in quadratic
    time.
    """

    n = len(s)
    if n == 0:
        return []

    # Try using a dict first, as that's the fastest and will usually
    # work.  If it doesn't work, it will usually fail quickly, so it
    # usually doesn't cost much to *try* it.  It requires that all the
    # sequence elements be hashable, and support equality comparison.
    u = {}
    try:
        for x in s:
            u[x] = 1
    except TypeError:
        del u  # move on to the next method
    else:
        return u.keys()

    # We can't hash all the elements.  Second fastest is to sort,
    # which brings the equal elements together; then duplicates are
    # easy to weed out in a single pass.
    # NOTE:  Python's list.sort() was designed to be efficient in the
    # presence of many duplicate elements.  This isn't true of all
    # sort functions in all languages or libraries, so this approach
    # is more effective in Python than it may be elsewhere.
    try:
        t = list(s)
        t.sort()
    except TypeError:
        del t  # move on to the next method
    else:
        assert n > 0
        last = t[0]
        lasti = i = 1
        while i < n:
            if t[i] != last:
                t[lasti] = last = t[i]
                lasti += 1
            i += 1
        return t[:lasti]

    # Brute force is all that's left.
    u = []
    for x in s:
        if x not in u:
            u.append(x)
    return u

         

if __name__ == "__main__":
    #from mesh import *
    # THIS CAN BE DELETED
    m = Mesh()
    dict = importUngenerateFile("ungen_test.txt")
    m.addVertsSegs(dict)
    print m