#include <ssi_qsegment.hpp>

Static Public Member Functions

static lrnode * alloc (unsigned size)
static lrnode * make (lrnode *data, unsigned size)

Public Attributes

Detailed Description

Definition at line 13 of file ssi_qsegment.hpp.

Member Function Documentation

lrnode * alloc ( unsigned size ) [static]

Definition at line 15 of file ssi_qsegment.cpp.

    {
      unsigned i, acc;
      i = size, acc =0;
      do { acc += i, i = i / 2 + i % 2; } while ( i > 1 );
      return new lrnode[acc+1];
    };

lrnode * make	(	lrnode *	data,
		unsigned	size
	)		`[static]`

Definition at line 23 of file ssi_qsegment.cpp.

References lrnode::lmax, lrnode::lmin, lrnode::ls, Mmax, Mmin, mmx::shape_ssi::right(), lrnode::rmax, lrnode::rmin, lrnode::rs, lrnode::umax, and lrnode::umin.

  {
#define Mmin(a,b) std::min(a,b)
#define Mmax(a,b) std::max(a,b)
    
    unsigned bsize = size;
    bool     right = true;
    lrnode * built = data;
    lrnode * curr  = data + size;
    unsigned i,j;
    do
      {
        if ( right )
          { 
            for ( i = 0, j = 0; i < bsize-(bsize%2); i += 2, j++ ) 
              {
                curr[j].umin = built[i].umin;
                curr[j].umax = built[i+1].umax;
                curr[j].lmin = Mmin(built[i].lmin,
                                    built[i+1].lmin);
                curr[j].lmax = Mmax(built[i].lmax,
                                    built[i+1].lmax);
                curr[j].rmin = Mmin(built[i].rmin,
                                    built[i+1].rmin);
                curr[j].rmax = Mmax(built[i].rmax,
                                    built[i+1].rmax);
                curr[j].ls   = built + i;
                curr[j].rs   = built + i + 1;
              };
            
            if ( bsize%2 ) { curr[j++] = built[bsize-1];  };
            built = curr;
            curr += j;
          }
        else
          {
            unsigned next_size = bsize/2 + bsize % 2;
            built += bsize-1;
            curr  += next_size-1;
            for ( i = 0, j = 0; i < bsize-(bsize%2); i += 2, j++ ) 
              {
                curr[-j].umin = built[-i-1].umin;
                curr[-j].umax = built[-i].umax;
                curr[-j].lmin = Mmin(built[-i].lmin,
                                     built[-i-1].lmin);
                curr[-j].lmax = Mmax(built[-i].lmax,
                                           built[-i-1].lmax);
                curr[-j].rmin = Mmin(built[-i].rmin,
                                               built[-i-1].rmin);
                curr[-j].rmax = Mmax(built[-i].rmax,
                                     built[-i-1].rmax);
                curr[-j].ls   = built - i - 1;
                curr[-j].rs   = built - i;
              };
            
            if ( bsize%2 ) { curr[-j] = built[-bsize+1];  };
            built = curr - next_size+1;
            curr++;
          };
        right = !right;
        bsize = bsize/2 + bsize%2;
      }
    while( bsize > 1 );
    return --curr;
  };