Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #14558

Re: How a spreadsheet works

Show all headers | View raw

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.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

How a spreadsheet works Paul N <gw7rib@aol.com> - 2022-02-11 08:09 -0800
  Re: How a spreadsheet works Richard Heathfield <rjh@cpax.org.uk> - 2022-02-11 17:31 +0000
    Re: How a spreadsheet works Paul N <gw7rib@aol.com> - 2022-02-12 04:43 -0800

csiph-web