Re: filling area by color atack safety

On 18/03/2024 10:26, Malcolm McLean wrote:

On 18/03/2024 06:58, David Brown wrote:

On 17/03/2024 19:28, Malcolm McLean wrote:

On 17/03/2024 16:45, David Brown wrote:

On 16/03/2024 16:09, Malcolm McLean wrote:

>

The OP's code is simple and obvious, as is its correctness (assuming reasonable definitions of the pixel access and setting functions) and its time and space requirements.  Yours is not.
>

Except it is not. You didn't give the right answer for the space requirements.

>
Unfortunately, I am still fallible - /easier/ does not mean I'll get it right :-(  And I apologise for unhelpfully rushing that and getting it wrong.
>
However, I stand by my claim that the recursive version is much easier to analyse.
>

I this case it s very short code and easy to see that it is right, so a win for recursion.

To be clear - I don't claim that recursive code is /always/ easier to analyse.  I claim it is easier in this case, and in many other cases (thus countering your claim that it is /always/ harder).

Except that it is only right if the stack is bigger than N/2 calls deep, where N is the number fo pixels in the image.

It is completely normal for correctness proofs to make assumptions about things like resources.  An analysis of your code for correctness would also generally assume that the heap would be big enough - if the heap runs out, your code will not correctly flood-fill the image.  Analysis of efficiency in time and space is a separate issue - related, but separate.  Things like maximum recursion depth (and heap size) are very implementation-specific, and thus need to be considered separately from the algorithm itself.
And while this code is in C, the same algorithm could be implemented in other languages.  A language that uses a VM might be fine with a much higher recursion depth - or it might be much lower.  A language for which recursion is a major tool (such as a functional programming language) might automatically convert some recursive code to a queue-based non-recursive solution.  (I'd be impressed to see one do that for this algorithm, however.)

Now a 100x100 woked fine an my machine  - I just checked the main stack, and it's 8MB by default. BUt of cuuurse the bigger than machine, the bigger the image th euser might want to load.
 

You still haven't considered using a spell-checker, even though you use a news client with one built in?  Perhaps you need a better keyboard?

 

It's better to have one function. Subroutines have a way of getting lost.>

>
Seriously?  "Subroutines get lost" ?  So your answer is to put all your ideas in a mixer and scrunch them up until any semblance of logic and structure is lost, and the code works (if it does) by trial and error? And then the whole mess is cut-and-paste duplicated - along with any subtle bugs it might have - for 8-connected version.  And that's better, in your eyes, than re-using code?
>

Exactly. If a routine ia leaf, you can cut and paste it and use it where you will. If you have to take subroutines, you've got to explore the code to understand what you neeed to take, then you have to out them somewhere. So it's better to keep routines leaf is possible and fold a few trivial operations into the code body, even if ideally they would be subroutines. And I understand these trade offs. >

That is a, shall we say, "interesting" attitude.

I have been most interested in being able to be sure the algorithm is correct, rather than considering its absolute (rather than "big O") efficiency in different systems.  It is certainly the case that cache considerations are more relevant now than they used to be on many systems.  And for working on PC's, you would likely dispense with your growing stack entirely and simply allocate a queue big enough for every pixel in the image.
>

That is an idea. But a bit extravanagant. I'd like to try to work out how much quue s actually used in typical as well as worst case.

The worst case is either going to be the stripy path example given by Michael S., or a completely blank image - it depends on how the east-west stripes affect the queue depth.  It should not be hard to try these.  So that would be either approximately half the total pixel count, or the total pixel count.  And I can't think how you could specify a "typical" image and "typical" flood fill request - without specifying this in some way, you need to collect lots of statistics of real-world use, or it's mere guesswork.

 >

I suggested separating the code into functions - that is /definitely/ constructive.  I suggested using sensible names for parameters and variables (well, the suggestion was implied by my criticism).
>
And I am also suggesting now that you allocate a queue that is big enough for every pixel in the image.  Much of what you don't touch of that space, will probably never be physically allocated by the OS, depending on page sizes and free memory.
>
And I would also suggest you drop the requirement for coding in an ancient tongue, and instead switch to reasonably modern C.  Make abstractions for the types and the access functions - it will make the code far easier to follow, easier to show correct, and easier to modify and reuse, without affecting efficiency at run-time.
>
>

And of course the entire binary image library has a consistent style. And we don't want the user mee=ssing about with writing his own getpixel / setpixel functions, thouhg there would be a case for that for a geneeral purpose flood fill.

That would be the "royal we", I presume?  I know /I/ would have no use for a flood-fill routine that did not support colour styles I use.