Index: /inundation/ga/storm_surge/pyvolution/cell.py
===================================================================
--- /inundation/ga/storm_surge/pyvolution/cell.py	(revision 478)
+++ /inundation/ga/storm_surge/pyvolution/cell.py	(revision 478)
@@ -0,0 +1,325 @@
+
+#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)
Index: /inundation/ga/storm_surge/pyvolution/test_cell.py
===================================================================
--- /inundation/ga/storm_surge/pyvolution/test_cell.py	(revision 478)
+++ /inundation/ga/storm_surge/pyvolution/test_cell.py	(revision 478)
@@ -0,0 +1,74 @@
+import unittest
+#from world import World
+#from point import Point
+#from waypoint import Waypoint
+from cell import Cell
+
+from domain import *
+
+import types, sys
+
+#-------------------------------------------------------------
+
+class TestCase(unittest.TestCase):
+
+    def setUp(self):
+        self.cell = Cell(100,140,0,40,'cell')
+        
+        a = [3, 107]
+        b = [5, 107]
+        c = [5, 105]
+        d = [7, 107]
+        e = [15, 115]
+        f = [15, 130]
+        g = [30, 110]
+        h = [30, 130]
+
+        points = [a, b, c, d, e, f, g, h]
+        #bac, bce, ecf, dbe, daf, dae 
+        vertices = [ [1,0,2],[1,3,4], [1,2,3], [5,4,7], [4,6,7]] 
+
+        conserved_quantities = ['level', 'xmomentum', 'ymomentum']
+        other_quantities = ['elevation', 'friction']
+        
+        domain = Domain(points, vertices, None,
+                        conserved_quantities, other_quantities)
+        Cell.initialise(domain)
+        
+    def tearDown(self):
+        pass
+
+    def test_add_points_2_cell(self):
+        self.cell.Insert(0)
+        self.cell.Insert(1)
+        
+        result = self.cell.Retrieve()
+        #result = self.cell.Get_tree()
+        #print  result 
+        assert type(result) in [types.ListType,types.TupleType], 'should be a list'        
+        self.assertEqual(len(result),2)
+        
+    def test_add_points_2_cellII(self):
+        self.cell.Insert([0,1,2,3,4,5,6,7])
+        
+        result = self.cell.Retrieve()
+        #result = self.cell.Get_tree()
+        #print  result 
+        assert type(result) in [types.ListType,types.TupleType], 'should be a list'        
+        self.assertEqual(len(result),8)
+
+
+    def test_search(self):
+        self.cell.Insert([0,1,2,3,4,5,6,7])
+        
+        result =  self.cell.Search(x = 1, y = 101)
+        assert type(result) in [types.ListType,types.TupleType], 'should be a list'        
+        self.assertEqual(result, [0,1,2,3])
+
+#-------------------------------------------------------------
+if __name__ == "__main__":
+
+    mysuite = unittest.makeSuite(TestCase,'test')
+    runner = unittest.TextTestRunner()
+    runner.run(mysuite)
+
Index: /inundation/ga/storm_surge/pyvolution/treenode.py
===================================================================
--- /inundation/ga/storm_surge/pyvolution/treenode.py	(revision 478)
+++ /inundation/ga/storm_surge/pyvolution/treenode.py	(revision 478)
@@ -0,0 +1,138 @@
+
+import string
+import exceptions
+import types
+from errors import VirtualError
+
+
+
+class TreeNode:
+    """class TreeNode
+
+    Base class for nodes in a tree-like structure.
+    Public Methods:
+        GetChildren()
+        GetParent()
+        AddChild(child)
+        GetLeaves()
+        DeleteChild(child)
+        Prune(children)
+        Show()
+    """
+
+
+    def __init__(self,name=None):
+        self.children = None
+        self.parent = None
+
+        # subclasses can implement these attributes as functions, called
+        # when a node (either leaf or internal) is deleted
+        if not hasattr(self,'ClearLeafNode'):
+            self.ClearLeafNode = None
+        if not hasattr(self,'ClearInternalNode'):
+            self.ClearInternalNode = None
+
+        # when not already set by derived class, set unique instance name
+        if not hasattr(self,"name"):
+            if name:
+                self.name = name
+            else:
+                self.name = id(self)
+
+
+    def __iter__(self):
+        self.index = -1   # incremented on first call to next()
+        return self
+
+    def next(self):
+        try:
+            self.index += 1
+            return self.children[self.index]
+        except IndexError:
+            self.index = -1
+            raise StopIteration
+
+
+
+    #---- public methods ------------------------------------
+
+    def GetChildren(self):
+        return self.children
+
+
+    def GetParent(self):
+        return self.parent
+
+
+    def AddChild(self,child):
+        child.parent = self
+        if hasattr(self,'storage'):
+            child.storage = self.storage
+        if self.children is None:
+            self.children = []
+        self.children.append(child)
+
+
+    def DeleteChild(self,child):
+        try:
+            index = self.children.index(child)
+            child.Prune()
+            del self.children[index]
+            if self.children == []:
+                self.children = None
+        except ValueError:
+            raise TreeNodeError
+
+
+    def Prune(self):
+        if self.children is None:                  # Leaf node
+            if callable(self.ClearLeafNode):
+                self.ClearLeafNode()
+        else:
+            if callable(self.ClearInternalNode):   # Internal node
+                self.ClearInternalNode()
+            for child in self.children:
+                child.Prune()
+            self.children = None
+
+
+    #FIXME: I think this one is redundant and should could be removed (OMN)
+    # Really?  Where is the equivalent method? (DEE)
+    # OK - I reliased that we can use it for testing and statistics (OMN)
+    def GetLeaves(self):
+        if self.children is None:
+            myleaves = [self]
+        else:
+            myleaves = []
+            for child in self.children:
+                myleaves += child.GetLeaves()
+
+        return myleaves
+
+
+    def CountLeaves(self):
+        if self.children is None:
+            count = 1
+        else:
+            count = 0
+            for child in self.children:
+                count += child.CountLeaves()
+
+        return count
+
+
+    def Show(self,depth=0):
+        """Traverse tree and print node names.
+        """        
+        print "%s%s" % ('  '*depth, self.name)
+        if self.children:
+            for child in self.children:
+                child.Show(depth+1)
+        else:
+            print ': %d' %self.Count()
+
+         
+#----------------------------------------------------------------
+class TreeNodeError(exceptions.Exception):
+    pass
+ 
