utestQuicksort.cpp 3.81 KB
Newer Older
1
// ===================================================================================
2 3
// Copyright ScalFmm 2016 INRIA
//
4 5
// This software is a computer program whose purpose is to compute the FMM.
//
6 7 8
// This software is governed by Mozilla Public License Version 2.0 (MPL 2.0) and
// abiding by the rules of distribution of free software.
//
9 10 11
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 13
// Mozilla Public License Version 2.0 (MPL 2.0) for more details.
// https://www.mozilla.org/en-US/MPL/2.0/
14
// ===================================================================================
15
#include "FUTester.hpp"
BRAMAS Berenger's avatar
BRAMAS Berenger committed
16
#include "Utils/FQuickSort.hpp"
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <unistd.h>

/**
* This file is a unit test for the quick sort
*/


/** this class test the list container */
class TestQuickSort : public FUTester<TestQuickSort> {
    static bool IsSorted(long long array[], const long size){
        for(int idx = 1; idx < size ; ++idx){
            if(array[idx-1] > array[idx]){
                return false;
            }
        }
        return true;
    }

    void manyThreads(){
        const long Size = 100000;
        long long* const array = new long long[Size];
BRAMAS Berenger's avatar
BRAMAS Berenger committed
39
        srand48(0);
40 41 42 43 44 45 46 47 48
        const int originalThreadsNumber = omp_get_num_threads();

        for(int idxThread = 1 ; idxThread <= omp_get_max_threads() ; idxThread *= 2){
            omp_set_num_threads(idxThread);

            for(long idx = 0 ; idx < Size ; ++idx){
                array[idx] = rand();
            }

49
            FQuickSort<long long, long>::QsOmp(array, Size);
50

51
            uassert(IsSorted(array,Size));
52 53 54 55 56 57 58
        }

        omp_set_num_threads(originalThreadsNumber);
        delete [] array;
    }

    void bigSize(){
59
        const long Size = 10000000;//100000000;
60 61 62 63 64 65
        long long* const array = new long long[Size];

        for(long idx = 0 ; idx < Size ; ++idx){
            array[idx] = rand();
        }

66
        FQuickSort<long long, long>::QsOmp(array, Size);
67
        uassert(IsSorted(array,Size));
68 69 70 71

        delete [] array;
    }

72 73 74 75 76 77 78 79
    void reversed(){
        const long Size = 10000000;//100000000;
        long long* const array = new long long[Size];

        for(long idx = 0 ; idx < Size ; ++idx){
            array[idx] = Size-idx;
        }

80
        FQuickSort<long long, long>::QsOmp(array, Size);
81 82 83 84 85 86 87 88 89 90 91 92 93
        uassert(IsSorted(array,Size));

        delete [] array;
    }

    void alreadySorted(){
        const long Size = 10000000;//100000000;
        long long* const array = new long long[Size];

        for(long idx = 0 ; idx < Size ; ++idx){
            array[idx] = idx;
        }

94
        FQuickSort<long long, long>::QsOmp(array, Size);
95 96 97 98 99
        uassert(IsSorted(array,Size));

        delete [] array;
    }

BRAMAS Berenger's avatar
BRAMAS Berenger committed
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
    void verySmallParts(){
        {
            long long values[2] = {0, 1};
            FQuickSort<long long, long>::QsSequential(values, 2);
            uassert(values[0] == 0);
            uassert(values[1] == 1);
        }
        {
            long long values[2] = {1, 0};
            FQuickSort<long long, long>::QsSequential(values, 2);
            uassert(values[0] == 0);
            uassert(values[1] == 1);
        }
        {
            long long values[2] = {0, 0};
            FQuickSort<long long, long>::QsSequential(values, 2);
            uassert(values[0] == 0);
            uassert(values[1] == 0);
        }
    }

121 122 123 124
    // set test
    void SetTests(){
        AddTest(&TestQuickSort::manyThreads,"Many threads");
        AddTest(&TestQuickSort::bigSize,"Big sort");
125 126
        AddTest(&TestQuickSort::reversed,"Reversed");
        AddTest(&TestQuickSort::alreadySorted,"Already Sorted");
BRAMAS Berenger's avatar
BRAMAS Berenger committed
127
        AddTest(&TestQuickSort::verySmallParts,"Small Parts");
128 129 130 131 132 133 134 135
    }
};

// You must do this
TestClass(TestQuickSort)