lrnode< C, V > Struct Template Reference

#include <ssi_qsegment.hpp>

List of all members.

Static Public Member Functions

static lrnode< C, V > * alloc (unsigned size)
static lrnode< C, V > * make (lrnode< C, V > *data, unsigned size)

Public Attributes

Detailed Description

template<class C, class V>
struct mmx::ssi::lrnode< C, V >

Definition at line 17 of file ssi_qsegment.hpp.

Member Function Documentation

lrnode< C, V > * alloc ( unsigned size ) [inline, static]

Definition at line 33 of file ssi_qsegment.hpp.

00034   {
00035     unsigned i, acc;
00036     i = size, acc =0;
00037     do { acc += i, i = i / 2 + i % 2; } while ( i > 1 );
00038     return new lrnode<C,V>[acc+1];
00039   };

lrnode< C, V > * make	(	lrnode< C, V > *	data,
		unsigned	size
	)			`[inline, static]`

Definition at line 42 of file ssi_qsegment.hpp.

References lrnode< C, V >::lmax, lrnode< C, V >::lmin, lrnode< C, V >::ls, Mmax, Mmin, mmx::ssi::right(), lrnode< C, V >::rmax, lrnode< C, V >::rmin, lrnode< C, V >::rs, lrnode< C, V >::umax, and lrnode< C, V >::umin.

00044 00045 00046 00047 00048 00049 00050 00051 00052 00053 00054     { 00055 00056         { 00057 00058 00059 00060 00061 00062 00063 00064 00065 00066 00067 00068 00069 00070 00071 00072 00073 00074 00075 00076         } 00077 00078         { 00079 00080 00081 00082 00083           { 00084 00085 00086 00087 00088 00089 00090 00091 00092           }; 00093 00094 00095 00096 00097 00098         }; 00099 00100 00101     } 00102 00103 00104 00105 };

class="fragment">00043 { #define Mmin(a,b) std::min(a,b) #define Mmax(a,b) std::max(a,b) //std::cout<<"Enter lrnode make "<<size<< std::endl; unsigned bsize = size; bool right = true; lrnode<C,V> * built = data; lrnode<C,V> * 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[next_size-1-j].umin = built[bsize-1-i-1].umin; curr[next_size-1-j].umax = built[bsize-1-i].umax; curr[next_size-1-j].lmin = Mmin(built[bsize-1-i].lmin, built[bsize-1-i-1].lmin); curr[next_size-1-j].lmax = Mmax(built[bsize-1-i].lmax, built[bsize-1-i-1].lmax); curr[next_size-1-j].rmin = Mmin(built[bsize-1-i].rmin, built[bsize-1-i-1].rmin); curr[next_size-1-j].rmax = Mmax(built[bsize-1-i].rmax, built[bsize-1-i-1].rmax); curr[next_size-1-j].ls = built +(bsize-1- i - 1); curr[next_size-1-j].rs = built +(bsize-1- i); if ( bsize%2 ) { curr[next_size-1-j] = built[bsize-1-bsize+1]; }; built = curr; //- next_size+1; curr += next_size-1; curr++; right = !right; bsize = bsize/2 + bsize%2; while( bsize > 1 ); //std::cout<<"Exit lrnode make"<<std::endl; return --curr;