From: gw7rib@aol.com   
      
   On Friday, February 11, 2022 at 5:31:06 PM UTC, Richard Heathfield wrote:   
   > On 11/02/2022 4:09 pm, Paul N wrote:    
   > > I was thinking about how a spreadsheet knows which cells to update and   
   what order to do them in when the value in a cell changes. I've though of a   
   possible method - would this work and is it how things are normally done? I've   
   assumed that there are    
   no circular references, for completeness I would need to check for this.    
   > >    
   > > I'll say that if a cell B depends on the value of a cell A, then B is a   
   "child" of A and A a "parent" of B. Each cell keeps track of its parents, its   
   children and also has a flag to say whether it needs to be updated.    
   > >    
   > > When a cell is altered, you first look at what its parents now are, make a   
   note of this and also inform the old and new parents so they can update their   
   list of children. Then do the following, starting with the updated cell:    
   > >    
   > > If the cell is already marked as needing updating, do nothing;    
   > > otherwise, mark the cell as needing updating and apply the same procedure   
   to its children.    
   > >    
   > > Then do the following, again starting with the updated cell:    
   > >    
   > > If one of more of the parents requires updating, do nothing;    
   > > otherwise, update the value, clear the flag, and apply the same procedure   
   to its children.    
   > >    
   > > The idea is that no cell is updated too early, but each cell which is   
   "passed over" will eventually be done, after its last parent gets done.    
   > >    
   > > So will this work, and is it normal?   
   > If I've read it right, it should work fine. To check for circular    
   > reference, seek the root of the tree you've built. You should find it    
   > before you find yourself, so to speak.    
   >    
   > t = here;    
   >    
   > do    
   > {    
   > t = t->parent;    
   > } while(t!= NULL && t != here);    
   >    
   > if(t == here)    
   > {    
   > circular reference    
   > }    
   >    
   > If you do that for ALL active (occupied) cells, you will detect any    
   > circular refs.    
      
   Thanks Richard.   
      
   I think your method of checking for circular references won't work quite as   
   you say because a cell can have multiple parents (at least in the sense I'm   
   using the term). But I think my method will detect the circular reference if I   
   simply add a check in    
   the "marking" stage to see whether we are back at the original cell. I was   
   more concerned about what to do if you did discover a circular reference. I   
   think the best solution is to put the newly-updated cell into a special error   
   state, and to split it    
   from its parents. (Ie, the user may say that that the cell ought to depend on   
   other cells, but Computer Says No.) The "update" can then go ahead as planned,   
   presumably turning all the child cells into some sort of error themselves.   
   This way there will be    
   no loops left which might cause other cell updates to run forever. When the   
   user edits the cell you can remove the error state and see whether the new   
   contents are acceptable.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)