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?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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: fsxNet Usenet Gateway (21:1/5)