Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety - worst memory size
Date: Wed, 5 Jun 2024 17:59:07 +0300
Organization: A noiseless patient Spider
Lines: 229
Message-ID: <20240605175907.000002f0@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
	<20240319131842.00002138@yahoo.com>
	<86o7b9ms7d.fsf@linuxsc.com>
	<20240320115416.00001ab5@yahoo.com>
	<86zfusltwp.fsf@linuxsc.com>
	<20240324193352.000062e9@yahoo.com>
	<86jzlrk0f6.fsf@linuxsc.com>
	<20240405173033.00006145@yahoo.com>
	<868r1k1uq8.fsf@linuxsc.com>
	<20240411152033.00007173@yahoo.com>
	<86bk6ez9te.fsf@linuxsc.com>
	<20240417004609.000010aa@yahoo.com>
	<86plunyj82.fsf@linuxsc.com>
	<20240417224126.0000727a@yahoo.com>
	<86a5lpxbd3.fsf@linuxsc.com>
	<20240420211023.000067cc@yahoo.com>
	<20240425175606.000059d5@yahoo.com>
	<20240503183305.000079e0@yahoo.com>
	<20240605174545.00002c4e@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 05 Jun 2024 16:58:55 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="af421c1bf631e23d6a62a4e576399d10";
	logging-data="966879"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+zyAbfoGLsMsLVOJLvd2wq13nhdPmAja4="
Cancel-Lock: sha1:MkYve3UaNP+BUsrf7Kn8tbC3fXw=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 8265

On Wed, 5 Jun 2024 17:45:45 +0300
Michael S <already5chosen@yahoo.com> wrote:

> On Fri, 3 May 2024 18:33:05 +0300
> Michael S <already5chosen@yahoo.com> wrote:
> 
> > On Thu, 25 Apr 2024 17:56:06 +0300
> > Michael S <already5chosen@yahoo.com> wrote:
> > 
> > 
> > A solution (sort of) is in line with the famous quite of David
> > Wheeler
> > - to turn todo lists from bit maps into arrays of
> > abscesses-or-ordinates of contact points.
> > 
> > The cost is a memory footprint - 4x bigger than the previous
> > version, 32 times bigger than above-mentioned "packed" variant of
> > the previous version. But in BigO sense it's the same.
> > 
> > In my tests it reduced the worst case time from O(max(A,B)**3) to
> > O(A*B*log(max(A,B)). Which is non-ideal, but probably acceptable,
> > because the bad cases should be very rare in practice.
> > 
> > The real trouble is different - I don't know if my "worst case" is
> > really the worst.
> > 
> > The code below is for presentation of algorithm in both clear and
> > compact manner, with emphasis on symmetry between x and y
> > directions. It is not optimal in any sense and can be made
> > no-trivially faster both by algorithm enhancements an by
> > specialization of critical loops.
> > 
> >  
> 
> Following code improves on ideas from the previous post.
> Unlike the previous one, it is purely iterative, with no recursion.
> The algorithm is simpler and access storage in more compact manner,
> i.e. all accessed memory area starts from beginning and grows
> according to need. Previous attempt did not have this property.
> It's still longer and less simple than I would like.
> 

And here is something that I found by chance when developing the code
presented in the previous post. 
Unlike for the previous one, I can not prove that memory requirements
of this algorithm are O(N). However, for all my tests cases it's not
just O(N), but consumes significantly less memory than the one above.
And it is simpler and shorter.

// HIS - todo stack of Horizontal Intervals
// with periodic Squeeze of empty intervals
#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>

typedef unsigned char Color;

int floodfill4(
  Color* image,
  int width, int height,
  int x,     int y,
  Color old_color, Color new_color)
{
  if (width <= 0 || height <= 0)
    return 0;

  if (x < 0 || x >= width || y < 0 || y >= height)
    return 0;

  size_t w = width;
  Color* row = &image[w*y];
  if (row[x] != old_color)
    return 0;

  typedef struct {
    int x0, x1, y;
    int8_t from; // -1 => from y-1, +1 => from y+1
  } interval_t;

  enum {
    INITIAL_STACK_SIZE = 128,
    SQUEEZE_THR        = 32,
  };
  interval_t* stack_base =
  malloc(INITIAL_STACK_SIZE*sizeof(*stack_base));
  if (!stack_base)
    return -1;
  interval_t* stack_end = &stack_base[INITIAL_STACK_SIZE];
  interval_t* todo = stack_base;

  // recolor initial horizontal interval
  row[x] = new_color;
  // look backward
  int x00;
  for (x00 = x-1; x00 >= 0 && row[x00]==old_color; --x00)
    row[x00] = new_color;
  x00 += 1;
  // look forward
  int x01;
  for (x01 = x+1; x01 < width && row[x01]==old_color; ++x01)
    row[x01] = new_color;
  x01 -= 1;

  // push neighbors of initial interval on todo stack
  for (int from = -1; from <= 1; from += 2) {
    unsigned next_y = y-from;
    if (next_y < (unsigned)height) {
      todo->x0 = x00;
      todo->x1 = x01;
      todo->y  = next_y;
      todo->from = from;
      ++todo;
    }
  }

  interval_t* squeezed = stack_base;
  unsigned periodic_i = 0;
  while (todo != stack_base) {
    --todo; // pop interval from todo stack
    int xBeg = todo->x0;
    int xEnd = todo->x1;
    int y    = todo->y;

    if (todo < squeezed)
      squeezed = todo;

    // look for target points
    Color* row = &image[y*w];
    int x = xBeg;
    do {
      if (row[x] == old_color) { // target found
        row[x] = new_color;
        int x0 = x;
        if (x == xBeg) {
          // look backward
          for (x0 = x-1; x0 >= 0 && row[x0]==old_color; --x0)
            row[x0] = new_color;
          x0 += 1;
        }
        // look forward
        int x1;
        for (x1 = x+1; x1 < width && row[x1]==old_color; ++x1)
          row[x1] = new_color;
        x1 -= 1;

        int from = todo->from;
        // remaining part of current interval
        if (x1+2 <= xEnd) {
          todo->x0 = x+2;
          todo->x1 = xEnd;
          todo->y = y;
          todo->from = from;
          ++todo;
        }
        // forward continuation
        unsigned next_y = y-from;
        if (next_y < (unsigned)height) {
          todo->x0 = x0;
          todo->x1 = x1;
          todo->y = next_y;
          todo->from = from;
========== REMAINDER OF ARTICLE TRUNCATED ==========