Path: csiph.com!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: C++ named requirements as concepts
Date: Sat, 12 Oct 2024 08:18:34 -0700
Organization: A noiseless patient Spider
Lines: 92
Message-ID: <86ldytxsc5.fsf@linuxsc.com>
References: <vcn7kn$1n3bh$2@dont-email.me> <20240929144913.000051e4@yahoo.com> <vde8ki$28003$1@dont-email.me> <vdehu2$29uog$1@dont-email.me> <vdeoej$2b22u$1@dont-email.me> <vdg8qn$2l73s$1@dont-email.me> <vdga7d$2lbv9$1@raubtier-asyl.eternal-september.org> <vdgcku$2lih8$1@dont-email.me> <20241001125332.000058ba@yahoo.com> <vdghc8$2me2g$1@dont-email.me> <20241001131141.000016b1@yahoo.com> <vdh739$2q4kk$1@dont-email.me> <20241001215050.000027aa@yahoo.com> <86bk0319w3.fsf@linuxsc.com> <20241002130236.000005e0@yahoo.com> <8634lc0y43.fsf@linuxsc.com> <20241006141907.00005a57@yahoo.com> <86iku3zydq.fsf@linuxsc.com> <20241007225315.00006d81@yahoo.com> <ve3i3c$27d8p$1@dont-email.me> <20241008224816.00004f1d@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sat, 12 Oct 2024 17:18:34 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="8ff887bf9043e35f2c7bcab96c66add3"; logging-data="226463"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/rHF5RayFOkvYl3pT+aR4RSHjE+hslU7Q="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:hNXI5QAuNDbhQKZUzZEdqekCOTg= sha1:QKdG5w1/snQWGSLjCwmjSaDN7pw=
Xref: csiph.com comp.lang.c++:120711

Michael S <already5chosen@yahoo.com> writes:

[...]

> Here is an example of more interesting sort that demonstrates what
> I was talking about and where I would like to use bwt_cmp_t::less
> directly instead of via operator():
>
> #include <cstdint>
> #include <cstring>
> #include <algorithm>
>
> // BWT sort - sort in lexicographic order with circular shift
> void bwt_sort(int* dst, const uint8_t* src, int srclen)
> {
>   for (int i = 0; i < srclen; ++i)
>     dst[i] = i;
>
>   struct bwt_cmp_t {
>     const uint8_t* src;
>     int srclen;
>     bool less(int a, int b) const {
>       if (a >= b) {
>         if (a > b)
>           return !less(b, a);
>         return false; // a == b
>       }
>       // a < b;
>       int diff = memcmp(&src[a], &src[b], srclen-b);
>       if (diff == 0) {
>         diff = memcmp(&src[a+srclen-b], &src[0], b-a);
>         if (diff == 0) {
>           diff = memcmp(&src[0], &src[b-a], a);
>           if (diff == 0)
>             return true; // stable sort
>         }
>       }
>       return diff < 0;
>     }
>     bool operator() (int a, int b) const {
>       return less(a, b);
>     }
>   } cmp;
>   cmp.src = src;
>   cmp.srclen = srclen;
>   std::sort(dst, dst+srclen, cmp);
> }

I appreciate that this code illustrates your coding preferences.

For comparison here is an alternate approach to writing the
central routine (and also some incidental differences in other
parts of the code but those are not so important).


#include <cstring>
#include <algorithm>

// code for sorting rotations of a string in lexicographic order

typedef unsigned char U8;

class bwt_cmp_t {
   const U8* s;
   unsigned n;

 public:
   bwt_cmp_t( const U8 *s0, unsigned n0 ) : s(s0), n( n0 ) {}

   bool
   operator()( unsigned a, unsigned b ) const {
      unsigned  j, k,  a1, b1, a2, b2;
      int  mc0, mc1, mc2;

      if( a<b )  j = n-b,  k = b-a,  a1 = a+j, b1 = 0,    a2 = 0,  b2 = k;
      else       j = n-a,  k = a-b,  a1 = 0,   b1 = b+j,  a2 = k,  b2 = 0;

      if(  mc0 = memcmp( s+a,  s+b,  j ),  mc0  )  return  mc0 < 0;
      if(  mc1 = memcmp( s+a1, s+b1, k ),  mc1  )  return  mc1 < 0;

      mc2 = memcmp( s+a2, s+b2, n-j-k );
      return  mc2 < 0  ||  mc2 == 0 && a <= b;
   }
};


void
bwt_sort( unsigned* dst, U8* s, unsigned n ){
    for(  unsigned i = 0;  i < n;  ++i  )  dst[i] = i;

    std::sort( dst, dst + n, bwt_cmp_t( s, n ) );
}