View | Details | Return to bug 58800
Collapse All | Expand All

(-)include/bits/stl_algo.h (-1 / +1 lines)
Lines 1917-1923 Link Here
1917
				_RandomAccessIterator __last, _Compare __comp)
1917
				_RandomAccessIterator __last, _Compare __comp)
1918
    {
1918
    {
1919
      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1919
      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1920
      std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2),
1920
      std::__move_median_to_first(__first, __first + 1, __mid, (__last - 1),
1921
				  __comp);
1921
				  __comp);
1922
      return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1922
      return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1923
    }
1923
    }
(-)testsuite/25_algorithms/nth_element/58800.cc (+47 lines)
Line 0 Link Here
1
// Copyright (C) 2005-2013 Free Software Foundation, Inc.
2
//
3
// This file is part of the GNU ISO C++ Library.  This library is free
4
// software; you can redistribute it and/or modify it under the
5
// terms of the GNU General Public License as published by the
6
// Free Software Foundation; either version 3, or (at your option)
7
// any later version.
8
9
// This library is distributed in the hope that it will be useful,
10
// but WITHOUT ANY WARRANTY; without even the implied warranty of
11
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
// GNU General Public License for more details.
13
14
// You should have received a copy of the GNU General Public License along
15
// with this library; see the file COPYING3.  If not see
16
// <http://www.gnu.org/licenses/>.
17
18
// 25.3.2 [lib.alg.nth.element]
19
20
// { dg-options "-std=gnu++0x" }
21
22
#include <algorithm>
23
#include <testsuite_hooks.h>
24
#include <testsuite_iterators.h>
25
26
using __gnu_test::test_container;
27
using __gnu_test::random_access_iterator_wrapper;
28
29
typedef test_container<int, random_access_iterator_wrapper> Container;
30
31
int main()
32
{
33
        std::vector<int> v = {
34
                207089,
35
                202585,
36
                180067,
37
                157549,
38
                211592,
39
                216096,
40
                207089
41
        };
42
43
        Container con(v.data(), v.data() + 7);
44
45
        std::nth_element(con.begin(), con.begin() + 3, con.end());
46
        return 0;
47
}
(-)testsuite/25_algorithms/nth_element/random_test.cc (+65 lines)
Line 0 Link Here
1
// Copyright (C) 2005-2013 Free Software Foundation, Inc.
2
//
3
// This file is part of the GNU ISO C++ Library.  This library is free
4
// software; you can redistribute it and/or modify it under the
5
// terms of the GNU General Public License as published by the
6
// Free Software Foundation; either version 3, or (at your option)
7
// any later version.
8
9
// This library is distributed in the hope that it will be useful,
10
// but WITHOUT ANY WARRANTY; without even the implied warranty of
11
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
// GNU General Public License for more details.
13
14
// You should have received a copy of the GNU General Public License along
15
// with this library; see the file COPYING3.  If not see
16
// <http://www.gnu.org/licenses/>.
17
18
// { dg-options "-std=gnu++0x" }
19
// { dg-options "-std=gnu++0x -DSIMULATOR_TEST" { target simulator } }
20
21
// 25.4.2 [lib.alg.nth.element]
22
23
#include <algorithm>
24
#include <testsuite_hooks.h>
25
#include <testsuite_iterators.h>
26
#include <random>
27
#include <testsuite_containergen.h>
28
29
30
using __gnu_test::test_container;
31
using __gnu_test::random_access_iterator_wrapper;
32
33
typedef test_container<int, random_access_iterator_wrapper> Container;
34
35
bool test __attribute__((unused)) = true;
36
37
struct testNthElement
38
{
39
  template<typename Container, typename RandomGen>
40
  void operator()(Container con, RandomGen& rg)
41
  {
42
    int size = con.end() - con.begin();
43
    int element = rg() % (size + 1);
44
45
    std::nth_element(con.begin(), con.begin() + element, con.end());
46
47
    if(element < size)
48
      {
49
        for(int i = 0; i < element; ++i)
50
          {
51
            VERIFY(con.val(i) <= con.val(element));
52
          }
53
        for(int i = element + 1; i < size; ++i)
54
          {
55
            VERIFY(con.val(i) >= con.val(element));
56
          }
57
      }
58
  }
59
};
60
61
int 
62
main()
63
{
64
  __gnu_test::test_containers<Container>(testNthElement());
65
}
(-)testsuite/25_algorithms/partial_sort/random_test.cc (+63 lines)
Line 0 Link Here
1
// Copyright (C) 2005-2013 Free Software Foundation, Inc.
2
//
3
// This file is part of the GNU ISO C++ Library.  This library is free
4
// software; you can redistribute it and/or modify it under the
5
// terms of the GNU General Public License as published by the
6
// Free Software Foundation; either version 3, or (at your option)
7
// any later version.
8
9
// This library is distributed in the hope that it will be useful,
10
// but WITHOUT ANY WARRANTY; without even the implied warranty of
11
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
// GNU General Public License for more details.
13
14
// You should have received a copy of the GNU General Public License along
15
// with this library; see the file COPYING3.  If not see
16
// <http://www.gnu.org/licenses/>.
17
18
// { dg-options "-std=gnu++0x" }
19
// { dg-options "-std=gnu++0x -DSIMULATOR_TEST" { target simulator } }
20
21
// 25.4.1.3 [lib.alg.partial.sort]
22
23
#include <algorithm>
24
#include <testsuite_hooks.h>
25
#include <testsuite_iterators.h>
26
#include <random>
27
#include <testsuite_containergen.h>
28
29
30
using __gnu_test::test_container;
31
using __gnu_test::random_access_iterator_wrapper;
32
33
typedef test_container<int, random_access_iterator_wrapper> Container;
34
35
bool test __attribute__((unused)) = true;
36
37
struct testPartialSort
38
{
39
  template<typename Container, typename RandomGen>
40
  void operator()(Container con, RandomGen& rg)
41
  {
42
    int size = con.end() - con.begin();
43
    int element = rg() % (size + 1);
44
45
    std::partial_sort(con.begin(), con.begin() + element, con.end());
46
47
    VERIFY(std::is_sorted(con.begin(), con.begin() + element));
48
    
49
    if(element > 0)
50
      {
51
        for(int i = element; i < size; ++i)
52
          {
53
            VERIFY(con.val(element - 1) <= con.val(i));
54
          }
55
      }
56
  }
57
};
58
59
int 
60
main()
61
{
62
  __gnu_test::test_containers<Container>(testPartialSort());
63
}
(-)testsuite/25_algorithms/partial_sort_copy/random_test.cc (+66 lines)
Line 0 Link Here
1
// Copyright (C) 2005-2013 Free Software Foundation, Inc.
2
//
3
// This file is part of the GNU ISO C++ Library.  This library is free
4
// software; you can redistribute it and/or modify it under the
5
// terms of the GNU General Public License as published by the
6
// Free Software Foundation; either version 3, or (at your option)
7
// any later version.
8
9
// This library is distributed in the hope that it will be useful,
10
// but WITHOUT ANY WARRANTY; without even the implied warranty of
11
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
// GNU General Public License for more details.
13
14
// You should have received a copy of the GNU General Public License along
15
// with this library; see the file COPYING3.  If not see
16
// <http://www.gnu.org/licenses/>.
17
18
// { dg-options "-std=gnu++0x" }
19
// { dg-options "-std=gnu++0x -DSIMULATOR_TEST" { target simulator } }
20
21
// 25.4.1.4 [lib.alg.partial.sort.copy]
22
23
#include <algorithm>
24
#include <testsuite_hooks.h>
25
#include <testsuite_iterators.h>
26
#include <random>
27
#include <testsuite_containergen.h>
28
#include <vector>
29
30
using __gnu_test::test_container;
31
using __gnu_test::random_access_iterator_wrapper;
32
33
typedef test_container<int, random_access_iterator_wrapper> Container;
34
35
bool test __attribute__((unused)) = true;
36
37
struct testPartialSortCopy
38
{
39
  template<typename Container, typename RandomGen>
40
  void operator()(Container con, RandomGen& rg)
41
  {
42
    int size = con.end() - con.begin();
43
    int element = rg() % (size + 1);
44
45
    std::vector<int> outvec(element + 1); // add +1 to stop empty issues
46
47
    Container out(outvec.data(), outvec.data() + element);
48
49
    std::partial_sort_copy(con.begin(), con.end(), out.begin(), out.begin() + element);
50
51
    VERIFY(std::is_sorted(out.begin(), out.begin() + element));
52
53
    std::sort(con.begin(), con.end());
54
    
55
    for(int i = 0; i < element; ++i)
56
      {
57
	VERIFY(con.val(i) == out.val(i));
58
      }
59
  }
60
};
61
62
int 
63
main()
64
{
65
  __gnu_test::test_containers<Container>(testPartialSortCopy());
66
}
(-)testsuite/25_algorithms/sort/random_test.cc (+51 lines)
Line 0 Link Here
1
// Copyright (C) 2005-2013 Free Software Foundation, Inc.
2
//
3
// This file is part of the GNU ISO C++ Library.  This library is free
4
// software; you can redistribute it and/or modify it under the
5
// terms of the GNU General Public License as published by the
6
// Free Software Foundation; either version 3, or (at your option)
7
// any later version.
8
9
// This library is distributed in the hope that it will be useful,
10
// but WITHOUT ANY WARRANTY; without even the implied warranty of
11
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
// GNU General Public License for more details.
13
14
// You should have received a copy of the GNU General Public License along
15
// with this library; see the file COPYING3.  If not see
16
// <http://www.gnu.org/licenses/>.
17
18
// { dg-options "-std=gnu++0x" }
19
// { dg-options "-std=gnu++0x -DSIMULATOR_TEST" { target simulator } }
20
21
// 25.4.1 [lib.alg.sort]
22
23
#include <algorithm>
24
#include <testsuite_hooks.h>
25
#include <testsuite_iterators.h>
26
#include <random>
27
#include <testsuite_containergen.h>
28
29
30
using __gnu_test::test_container;
31
using __gnu_test::random_access_iterator_wrapper;
32
33
typedef test_container<int, random_access_iterator_wrapper> Container;
34
35
bool test __attribute__((unused)) = true;
36
37
struct testSort
38
{
39
  template<typename Container, typename RandomGen>
40
  void operator()(Container con, RandomGen& rg)
41
  {
42
    std::sort(con.begin(), con.end());
43
    VERIFY(is_sorted(con.begin(), con.end()));
44
  }
45
};
46
47
int 
48
main()
49
{
50
  __gnu_test::test_containers<Container>(testSort());
51
}
(-)testsuite/util/testsuite_containergen.h (+110 lines)
Line 0 Link Here
1
// -*- C++ -*-
2
3
// Copyright (C) 2013 Free Software Foundation, Inc.
4
//
5
// This file is part of the GNU ISO C++ Library.  This library is free
6
// software; you can redistribute it and/or modify it under the terms
7
// of the GNU General Public License as published by the Free Software
8
// Foundation; either version 3, or (at your option) any later
9
// version.
10
11
// This library is distributed in the hope that it will be useful, but
12
// WITHOUT ANY WARRANTY; without even the implied warranty of
13
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14
// General Public License for more details.
15
16
// You should have received a copy of the GNU General Public License along
17
// with this library; see the file COPYING3.  If not see
18
// <http://www.gnu.org/licenses/>.
19
20
#ifndef _GLIBCXX_TESTSUITE_CONTAINER_GEN_H
21
#define _GLIBCXX_TESTSUITE_CONTAINER_GEN_H
22
23
#include <cassert>
24
#include <testsuite_container_traits.h>
25
26
// Container requirement testing.
27
namespace __gnu_test
28
{
29
30
31
  template<typename ContainerType, typename Tester, typename RandomGen>
32
    void test_single_container(Tester test, RandomGen& rg, int length, int domain)
33
    {
34
      std::vector<int> values;
35
      for(int i = 0; i < length; ++i)
36
	{
37
	  values.push_back(rg() % domain);
38
	}
39
40
      ContainerType con(values.data(), values.data() + length);
41
      test(con, rg);
42
    }
43
44
  template<typename ContainerType, typename Tester, typename RandomGen>
45
    void test_special_containers(Tester test, RandomGen& rg, int length)
46
    {
47
      std::vector<int> values(length);
48
      ContainerType con(values.data(), values.data() + length);
49
      for(int i = 0; i < length; ++i)
50
	{
51
	  values[i] = 0;
52
	}
53
      test(con, rg);
54
55
      for(int i = 0; i < length; ++i)
56
	{
57
	  values[i] = i;
58
	}
59
      test(con, rg);
60
61
      for(int i = 0; i < length; ++i)
62
	{
63
	  values[i] = -i;
64
	}
65
      test(con, rg);
66
67
    }
68
69
  template<typename ContainerType, typename Tester>
70
    void test_containers(Tester test)
71
    {
72
      std::mt19937_64 random_gen;
73
      
74
#ifdef SIMULATOR_TEST
75
      int loops = 10;
76
#else
77
      int loops = 1000;
78
#endif
79
80
      for(int i = 0; i < loops; ++i)
81
	{
82
	  test_special_containers<ContainerType>(test, random_gen, i);
83
	}
84
85
      for(int i = 1; i < 100; ++i)
86
	for(int j = 0; j < loops; ++j)
87
	{
88
	  test_single_container<ContainerType>(test, random_gen, i, i);
89
	}
90
91
      
92
      for(int i = 0; i < loops; ++i)
93
	{
94
	  test_single_container<ContainerType>(test, random_gen, 10, 10);
95
	  test_single_container<ContainerType>(test, random_gen, 100, 10);
96
	  test_single_container<ContainerType>(test, random_gen, 1000, 10);
97
	  test_single_container<ContainerType>(test, random_gen, 10, 1000);
98
	}
99
100
#ifndef SIMULATOR_TEST
101
      for(int i = 0; i < 1000; ++i)
102
	{
103
	  test_single_container<ContainerType>(test, random_gen, 10000, 10);	 
104
	  test_single_container<ContainerType>(test, random_gen, 10000, 100000);
105
	}
106
#endif
107
    }
108
} // namespace __gnu_test
109
110
#endif
(-)testsuite/util/testsuite_iterators.h (+4 lines)
Lines 539-544 Link Here
539
      return ItType<T>(pos, &bounds);
539
      return ItType<T>(pos, &bounds);
540
    }
540
    }
541
541
542
    const T&
543
    val(int pos)
544
    { return (bounds.first)[pos]; }
545
542
    ItType<T>
546
    ItType<T>
543
    begin()
547
    begin()
544
    { return it(bounds.first); }
548
    { return it(bounds.first); }

Return to bug 58800