/ray/src/lib/tl/test-sort.cc

Go to the documentation of this file.

/*
 * lib/tl/test-sort.cc 
 * 
 * Test sort algorithm implementation. Based on test-btree.cc. 
 * 
 * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. (See COPYING.GPL for details.)
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

#include "sort.h"

#include <lib/htime.h>

#include <stdio.h>


char *prg_name="test-sort";


// The operator template classes are not meant to modify themselves; if you 
// want to change some property inside an operator class from within one 
// of the operators, you should attach a pointer or reference to the class 
// and store the data there. 
// This is a good idea as classes like TLBtree store a COPY of the passed 
// operator class instead of a reference/pointer. So, if you want to 
// access the members of the operator class from outside, you need to 
// use a pointer/ref anyways here. 
// BUT in this case for testing, I simply cast away the const with this 
// ugly this-pointer cast. 
template<class T>struct MYOP
{
    int ini_calls;
    int clr_calls;
    int ass_calls;
    int cmp_calls;
    
    MYOP()  {  ini_calls=0; clr_calls=0; ass_calls=0; cmp_calls=0;  }
    ~MYOP() {}
    
    inline bool lt(T const &a,T const &b) const
        {  ++((MYOP*)this)->cmp_calls;  return(a<b);   }
    inline bool le(T const &a,T const &b) const
        {  ++((MYOP*)this)->cmp_calls;  return(a<=b);  }
    inline bool gt(T const &a,T const &b) const
        {  ++((MYOP*)this)->cmp_calls;  return(a>b);   }
    inline bool ge(T const &a,T const &b) const
        {  ++((MYOP*)this)->cmp_calls;  return(a>=b);  }
    inline bool eq(T const &a,T const &b) const
        {  ++((MYOP*)this)->cmp_calls;  return(a==b);  }
    inline bool ne(T const &a,T const &b) const 
        {  ++((MYOP*)this)->cmp_calls;  return(a!=b);  }
    
    inline T &ass(T &l,T const &r) const
        {  ++((MYOP*)this)->ass_calls;  return(l=r);  }
    
    static const bool pdt=1;
    static inline _constfn_ size_t size()  {  return(sizeof(T));  }
    
    inline void ini(T *) const
        { ++((MYOP*)this)->ini_calls; }
    inline void ini(T *p,T const &a) const
        {  *p=a;  ++((MYOP*)this)->ini_calls;  }
    inline void clr(T *) const
        { ++((MYOP*)this)->clr_calls; }
    
    static inline void *alloc(size_t size)  {  return(ALLOC<char>(size));  }
    static inline void *realloc(void *ptr,size_t size)
        {  return(REALLOC((char*)ptr,size));  }
    static inline void *free(void *ptr)  {  return(FREE(ptr));  }
    
    template<typename I>static inline T &idx(T *array,I i)
    {
        //if(i>=32000) fprintf(stderr,"<0x%x>",i);
        //CritAssert(i<32000);
        return(array[i]);
    }
    template<typename I>static inline const T &idx(const T *array,I i)
    {
        //CritAssert(i<32000);
        return(array[i]);
    }
};


int *GenRandomPerm(size_t size,size_t red)
{
    int *array=ALLOC<int>(size);
    for(size_t i=0; i<size; i++)
        array[i]=i/red;
    for(size_t i=0; i<size; i++)
    {
        size_t j=rand()%size;
        int tmp=array[j];
        array[j]=array[i];
        array[i]=tmp;
    }
    return(array);
}


template<typename T,typename _OP>void X_DumbQuickSort(
    T *a,size_t nelem,
    const _OP &op=TLDefaultOperators_PDT<T>())
{  DumbQuickSort(a,nelem,13,op);  }

template<typename T,typename _OP>void X_CleverQuickSort(
    T *a,size_t nelem,
    const _OP &op=TLDefaultOperators_PDT<T>())
{  CleverQuickSort(a,nelem,10,op);  }


int _DoSortAndTest(int *perm,size_t permsize,size_t red,
    void (*sort)(int *,size_t,const MYOP<int> &),
    const char *name)
{
    int nerr=0;
    
    fprintf(stderr,"    %s: ",name);
    
    int *copy=ALLOC<int>(permsize);
    for(size_t i=0; i<permsize; i++)  copy[i]=perm[i];
    
    MYOP<int> op;
    HTime start(HTime::Curr);
    (*sort)(copy,permsize,op);
    long msec=start.MsecElapsed();
    fprintf(stderr,"ini-clr/ass/cmp=%d,%d,%d  (%ld msec)",
        op.ini_calls-op.clr_calls,op.ass_calls,op.cmp_calls,
        msec);
    
    // Check: 
    if(op.ini_calls!=op.clr_calls)  ++nerr;
    for(int i=0; i<(int)permsize; i++)
        if(copy[i]!=(int)(i/red))  ++nerr;
    
    FREE(copy);
    
    if(nerr)
    {  fprintf(stderr," ** %d errors **\n",nerr);  }
    else
    {  fprintf(stderr,"  OK\n");  }
    
    return(nerr ? 1 : 0);
}


int main()
{
    fprintf(stderr,"Testing sort algorithms...\n");
    
    //int *ini_callsA;
    //int *clr_callsA;
    //int *ini_callsB;
    //int *clr_callsB;
    
    int nerrors=0;
    for(size_t red=1; red<=3; red+=2)
    {
        size_t permsize=20000;
        int *perm=GenRandomPerm(permsize,red);
        fprintf(stderr,"  Random permutation (red=%u, size %u):\n",
            red,permsize);
        
        nerrors+=_DoSortAndTest(perm,permsize,red,
            &InsertionSort< int,MYOP<int> >,
            "Insertion sort     ");
        nerrors+=_DoSortAndTest(perm,permsize,red,
            &InsertionSortBS< int,MYOP<int> >,
            "Insertion sort (BS)");
        
        FREE(perm);
        
        //----------
        
        permsize*=20;
        perm=GenRandomPerm(permsize,red);
        fprintf(stderr,"  Random permutation (red=%u, size %u):\n",
            red,permsize);
        
        nerrors+=_DoSortAndTest(perm,permsize,red,
            &X_DumbQuickSort< int,MYOP<int> >,
            "Dumb Quick sort     ");
        nerrors+=_DoSortAndTest(perm,permsize,red,
            &X_CleverQuickSort< int,MYOP<int> >,
            "Clever Quick sort   ");
        nerrors+=_DoSortAndTest(perm,permsize,red,
            &HeapSort< int,MYOP<int> >,
            "Heap sort           ");
        
        FREE(perm);
    }
    if(nerrors)  return(1);
    
    fprintf(stderr,"TODO: Implement test for stability. **********\n");
    
    //fprintf(stderr,"  A: ini_calls=%d, clr_calls=%d, diff=%d\n",
    //  *ini_callsA,*clr_callsA,*ini_callsA-*clr_callsA);
    //fprintf(stderr,"  B: ini_calls=%d, clr_calls=%d, diff=%d\n",
    //  *ini_callsB,*clr_callsB,*ini_callsB-*clr_callsB);
    
    //if(*ini_callsA-*clr_callsA || 
    //   *ini_callsB-*clr_callsB )
    //{  return(1);  }
    
    // Allocation debugging: 
    LMallocUsage lmu;
    LMallocGetUsage(&lmu);
    fprintf(stderr,"%s: %sAlloc: %u bytes in %d chunks; Peak: %u by,%d chks; "
        "(%u/%u/%u)%s\n",
        prg_name,
        lmu.curr_used ? "*** " : "",
        lmu.curr_used,lmu.used_chunks,lmu.max_used,lmu.max_used_chunks,
        lmu.malloc_calls,lmu.realloc_calls,lmu.free_calls,
        lmu.curr_used ? " ***" : "");
    if(lmu.curr_used)  return(1);
    
    fprintf(stderr,"Sort test SUCCESSFUL.\n");
    return(0);
}

---