source: inundation/ga/storm_surge/pyvolution/cell.py @ 479

#from point import Point
#from waypoint import Waypoint
from treenode import TreeNode
import string, types, sys

#FIXME remove point, waypoint

#FIXME verts are added one at a time. 
#FIXME add max min x y in general_mesh

#FIXME hacky.  maybe have as an attribute (or class att') for cell?
MAX_WAY_POINTS = 4

class Cell(TreeNode):
    """class Cell

    One cell on the planet surface delimited by southern, northern,
    western, eastern boundaries.

    Public Methods:
        Prune()
        Insert(Waypoint w)
        Search(Point p, [keywords c])
        Collapse()
        Split()
        Store()
        Retrieve()
        Count()
    """
  
    def __init__(self, southern, northern, western, eastern, name):
  
        # Initialise base classes
        TreeNode.__init__(self, string.lower(name))
        # Initialise cell
        self.southern = round(southern,5)    
        self.northern = round(northern,5)
        self.western = round(western,5)    
        self.eastern = round(eastern,5)

        # Corners
        #self.SW = Point(self.southern,self.western) 
        #self.NW = Point(self.northern,self.western) 
        #self.NE = Point(self.northern,self.eastern)
        #self.SE = Point(self.southern,self.eastern)

        # The points in this cell     
        self.points = []
        
    def __repr__(self):
        return self.name  


    def Spawn(self):
        """Create four child cells unless they already exist
        """

        if self.children:
            return
        else:
            self.children = []

        # convenience variables
        cs = self.southern    
        cn = self.northern
        cw = self.western    
        ce = self.eastern

        # create 4 child cells
        self.AddChild(Cell((cn+cs)/2,cn,cw,(cw+ce)/2,self.name+'_nw'))
        self.AddChild(Cell((cn+cs)/2,cn,(cw+ce)/2,ce,self.name+'_ne'))
        self.AddChild(Cell(cs,(cn+cs)/2,(cw+ce)/2,ce,self.name+'_se'))
        self.AddChild(Cell(cs,(cn+cs)/2,cw,(cw+ce)/2,self.name+'_sw'))
     
 

    def Search(self, x,y):
        """Find all waypoints within given radius from point P meeting 
        specified keywords (an optional comma-separated string).
        """
      
        waypoints = []
        if self.children:
            for child in self:
                if child.Contains(None,x=x,y=y):
                     waypoints += child.Search(x,y)
        else:
            # Leaf node: Get actual waypoints
            waypoints = self.Retrieve()
            
        return waypoints



    def Contains(self, point_id, x= 0, y= 0):
        """True only if P's coordinates lie within cell boundaries
        """

        if point_id <> None:
            x = self.__class__.domain.coordinates[point_id][0]
            y = self.__class__.domain.coordinates[point_id][1]
        #print "x",x
        #print "y",y
        #print "self.southern",self.southern
        #print "self.northern",self.northern
        #print "self.western",self.western
        #print "self.eastern",self.eastern
        if y <  self.southern: return 0
        if y >= self.northern: return 0
        if x <  self.western:  return 0
        if x >= self.eastern:  return 0
        return 1
    
    def Contains_old(self, P):
        """True only if P's coordinates lie within cell boundaries
        """
    
        if P.latitude  <  self.southern: return 0
        if P.latitude  >= self.northern: return 0
        if P.longitude <  self.western:  return 0
        if P.longitude >= self.eastern:  return 0
        return 1
    
    
    def Insert(self, W):
        """Insert waypoint in existing tree structure below self
           and split if necessary
        """
  
        # Call insert for each element of a list of waypoints
        if type(W) == types.ListType:
            for w in W:
                self.Insert(w)
            return
   
        # Find appropriate cell
        if self.children:
            for child in self:
                if child.Contains(W):
                    child.Insert(W)
                    break
        else:
            # Cell is a leaf cell. Insert waypoint in database table
            if self.Contains(W):
                self.Store(W)
                
                #FIXME? - where was this called before?  
                self.Split()
            else:
                #FIXME rasie exception
               raise "point not in region"


    def Store(self,objects):
        #import storage
        #storage = storage.Factory()
        
        if type(objects) not in [types.ListType,types.TupleType]:
            self.points.append(objects)
        else:
            self.points.extend(objects)
            
        #for object in objects:
        #    storage.Store(self.name,object)



    def Retrieve(self):
         objects = []
         if self.children is None:
             objects = self.points
         else:  
             for child in self:
                 objects += child.Retrieve()
         return objects  


    def Count(self, keywords=None):
        """Retrieve number of stored objects beneath this node inclusive
        """
        
        num_waypoint = 0
        if self.children:
            for child in self:
                num_waypoint = num_waypoint + child.Count()
        else:
            num_waypoint = len(self.points)
        return num_waypoint
  

    def Clear(self):
        self.Prune()   # TreeNode method


    def ClearLeafNode(self):
        self.points = []



    def Split(self, threshold=None):
        """
        Partition cell when number of contained waypoints exceeds 
        threshold.  All waypoints are then moved into correct 
        child cell.
        """
        if  threshold == None:
            threshold = MAX_WAY_POINTS
        #FIXME, mincellsize removed.  base it on side lenght, if needed
        
        if not self.children:               # Leaf cell
            if self.Count() > threshold : #and self.radius > mincellsize: 
                
                waypoints = self.Retrieve() # Get waypoints from leaf cell
                self.Clear()                # and remove them from storage
                
                self.Spawn()                # Spawn child cells and move
                for wp in waypoints:        # waypoints to appropriate child
                    for child in self:
                        if child.Contains(wp):
                            child.Insert(wp) 
                            break
    
        if self.children:                   # Parent cell
            for child in self:              # Split (possibly newly created) 
                child.Split(threshold)      # child cells recursively
                


    def Collapse(self,threshold=None):
        """
        Collapse child cells into immediate parent if total number of contained waypoints
        in subtree below is less than or equal to threshold.
        All waypoints are then moved into parent cell and
        children are removed. If self is a leaf node initially, do nothing.
        """
        
        if threshold is None:
            threshold = config['maxwaypoints']

        if self.children:                   # Parent cell    
            if self.Count() <= threshold:   # Collapse
                waypoints = self.Retrieve() # Get all waypoints from child cells
                self.Clear()                # Remove children, self is now a leaf node
                self.Insert(waypoints)      # Insert all waypoints in local storage
            else:                          
                for child in self:          # Check if any sub tree can be collapsed
                    child.Collapse(threshold)


    def Get_tree(self,depth=0):
        """Traverse tree below self
           Print for each node the name and
           if it is a leaf the number of objects
        """
        s = ''
        if depth == 0:
            s = '\n'
            
        s += "%s%s:" % ('  '*depth, self.name)
        if self.children:
            s += '\n'
            for child in self.children:
                s += child.Get_tree(depth+1)
        else:
            s += '(#wp=%d)\n' %(self.Count())

        return s

    def Show(self,depth=0):
        """Traverse tree below self
           Print for each node the name and
           if it is a leaf the number of objects
        """
        if depth == 0:
            print 
        print "%s%s:" % ('  '*depth, self.name),
        if self.children:
            print
            for child in self.children:
                child.Show(depth+1)
        else:
            print '#wp=%d, c=(%.2f,%.2f)'\
                  %(self.Count(), self.latitude, self.longitude)

            

    def ShowAll(self,depth=0):
        """Traverse tree below self
           Print for each node the name and if it is a leaf all its objects
        """
        if depth == 0:
            print 
        print "%s%s:" % ('  '*depth, self.name),
        if self.children:
            print
            for child in self.children:
                child.ShowAll(depth+1)
        else:
            print '%s' %self.Retrieve()


    def Stats(self,depth=0,min_rad=sys.maxint,max_depth=0,max_points=0):
        """Traverse tree below self and find minimal cell radius,
           maximumtree depth and maximum number of waypoints per leaf.
        """

        if self.children:
            for child in self.children:
                min_rad, max_depth, max_points =\
                         child.Stats(depth+1,min_rad,max_depth,max_points)
        else:
            #FIXME remvoe radius stuff
            min_rad = sys.maxint
            #if self.radius < min_rad:   min_rad = self.radius
            if depth > max_depth:       max_depth = depth
            num_points = self.Count()
            if num_points > max_points: max_points = num_points

        return min_rad, max_depth, max_points    

    def initialise(cls,domain):
        cls.domain = domain

    initialise = classmethod(initialise)