Re: [bug-gettext] [PATCH] its: Add new preserveSpaceRule "paragraph"

[Bruno Haible]

Hi Daiki,

> +            /* Normalize whitespaces in the paragraph.  */
> +            assert (pend != NULL);
> +            c = *pend;
> +            *pend = '\0';
> +            for (pp = p; *pp != '\0';)
> +              {
> +                size_t len = strspn (pp, " \t\n");
> +                if (len > 0)
> +                  {
> +                    *pp = ' ';
> +                    memmove (pp + 1, pp + len, end - (pp + len));
> +                    end -= len - 1;
> +                    *end = '\0';
> +                    pend -= len - 1;
> +                    *pend = '\0';
> +                    pp++;
> +                  }
> +                pp += strcspn (pp, " \t\n");
> +              }
> +            *pend = c;
> +            p = pp + strspn (pend, "\n");
> +          }
> +        return result;

This loop is O(N*M), where N is the number of whitespace blocks in the
current paragraph and M is the number of characters starting at 'p'
(because the memmove extends from the current paragraph to the end of
the string, and there are as many memmove invocations as there are
whitespace blocks.

Could it be rewritten as an O(N+M) loop, by using two pointers ip
(input pointer) and op (output pointer), instead of pp,
that both run starting at p and satisfy the inequalities
  p <= op <= ip <= pend
?

(I don't like quadratic run time algorithms, when the size of the input
is not known to be guaranteed to be small. The first nontrivial program
I wrote was an implementation of a compression algorithm, with O(N²)
run time...<blunt>.)

Bruno