Archived

This topic is now archived and is closed to further replies.

Template Metaprogrammed Quicksort

This topic is 5670 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Null and Void provided his template metaprogrammed quicksort:
    
  #include <iostream>
using namespace std;

template <class Type, int LHold, int RHold, int Left, int Right, bool LlessR> 
struct InnerQSort_0;

template <class Type, int LHold, int RHold, int Left, int Right, bool LnotR>
struct InnerQSort_4 
{
    static inline void Go(Type Data[], Type &Pivot) 
    {		
        Data[Right] = Data[Left];		
        InnerQSort_0<Type,LHold,RHold,Left,Right-1, (Left<(Right-1)) >::Go(Data,Pivot);	
    }
};

template <class Type, int LHold, int RHold, int Left, int Right>
struct InnerQSort_4 <Type, LHold, RHold, Left, Right, false> 
{	
    static inline void Go(Type Data[], Type &Pivot)
    {		
        InnerQSort_0<Type,LHold,RHold,Left,Right, (Left<Right) >::Go(Data,Pivot);	
    }
};

template <class Type, int LHold, int RHold, int Left, int Right, bool LlessR>
struct InnerQSort_3 
{	
    static inline void Go(Type Data[], Type &Pivot) 
    {		
        if(Data[Left] <= Pivot)			
            InnerQSort_3<Type,LHold,RHold,Left+1,Right, ((Left+1)<Right) >::Go(Data,Pivot);		
        else			
            InnerQSort_4<Type,LHold,RHold,Left,Right, (Left!=Right) >::Go(Data,Pivot);	
    }
};

template <class Type, int LHold, int RHold, int Left, int Right>
struct InnerQSort_3 <Type, LHold, RHold, Left, Right, false> 
{	
    static inline void Go(Type Data[], Type &Pivot) 
    {		
        InnerQSort_4<Type,LHold,RHold,Left,Right, (Left!=Right) >::Go(Data, Pivot);	
    }
};

template <class Type, int LHold, int RHold, int Left, int Right, bool LnotR>
struct InnerQSort_2 
{	
    static inline void Go(Type Data[], Type &Pivot) 
    {		
        Data[Left] = Data[Right];		
        InnerQSort_3<Type,LHold,RHold,Left+1,Right, ((Left+1)<Right) >::Go(Data,Pivot);	
    }
};

template <class Type, int LHold, int RHold, int Left, int Right>
struct InnerQSort_2 <Type, LHold, RHold, Left, Right, false> 
{	
    static inline void Go(Type Data[], Type &Pivot) 
    {		
        InnerQSort_3<Type,LHold,RHold,Left,Right, (Left<Right) >::Go(Data,Pivot);	
    }
};

template <class Type, int LHold, int RHold, int Left, int Right, bool LlessR>
struct InnerQSort_1 
{	
    static inline void Go(Type Data[], Type &Pivot) 
    {		
        if(Data[Right] >= Pivot)			
            InnerQSort_1<Type,LHold,RHold,Left,Right-1, (Left<(Right-1)) >::Go(Data,Pivot);	
        else			
            InnerQSort_2<Type,LHold,RHold,Left,Right, (Left!=Right) >::Go(Data, Pivot);	
    }
};

template <class Type, int LHold, int RHold, int Left, int Right>
struct InnerQSort_1 <Type, LHold, RHold, Left, Right, false> 
{
    static inline void Go(Type Data[], Type &Pivot)
    {		
        InnerQSort_2<Type,LHold,RHold,Left,Right, (Left!=Right) >::Go(Data, Pivot);	
    }
};

template <class Type, int LHold, int RHold, int Left, int Right, bool LlessR>
struct InnerQSort_0 
{	
    static inline void Go(Type Data[], Type &Pivot) 
    {		
        InnerQSort_1<Type,LHold,RHold,Left,Right, (Left<Right) >::Go(Data,Pivot);	
    }
};

template <class Type, int Left, int Right, bool LlessR> struct InnerQSort;

template <class Type, int LHold, int RHold, int Left, int Right>
struct InnerQSort_0 <Type, LHold, RHold, Left, Right, false> 
{
    static inline void Go(Type Data[], Type &Pivot) 
    {
        Data[Left] = Pivot;		
        if(LHold < Left)		
            InnerQSort<Type, LHold, Left-1, (LHold<(Left-1)) >::Sort(Data);	
        if(RHold > Left)			
            InnerQSort<Type, Left+1, RHold, ((Left+1)<RHold) >::Sort(Data);	
    }
};

template <class Type, int Left, int Right, bool LlessR>
struct InnerQSort 
{	
    static inline void Sort(Type Data[]) 
    {		
        Type Pivot = Data[Left];		
        InnerQSort_0<Type,Left,Right,Left,Right, (Left<Right) >::Go(Data,Pivot);	
    }
};

template <class Type, int Left, int Right>
struct InnerQSort <Type, Left, Right, false> 
{	
    static inline void Sort(Type Data[]) 
    {	
    }
};

template <int Size, class Type>
struct QuickSort 
{	
    static inline void Sort(Type Data[]) 
    {		
        InnerQSort<Type,0,Size-1,(0 < (Size-1))>::Sort(Data);	
    }
};    

int main()
{
    int data[]={1,3,5,7,9,2,4,6,8,0};
    QuickSort<10,int>::Sort(data);
    for(int i=0;i<10;i++)
    {
        cerr<<data[i]<<endl;
    }
    return 0;
}     
So I tried it on gcc 2.96, but I have been unable to get the compiler to inline the code. Am I making faulty assumptions, or should it be possible to get the compiler to completely inline it, and replace it all with some MOVs? edit:formatting [edited by - sjelkjd on June 4, 2002 4:26:22 AM]

Share this post


Link to post
Share on other sites