Geogram  Version 1.9.1
A programming library of geometric algorithms
algorithm.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000-2022 Inria
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright notice,
9  * this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  * * Neither the name of the ALICE Project-Team nor the names of its
14  * contributors may be used to endorse or promote products derived from this
15  * software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27  * POSSIBILITY OF SUCH DAMAGE.
28  *
29  * Contact: Bruno Levy
30  *
31  * https://www.inria.fr/fr/bruno-levy
32  *
33  * Inria,
34  * Domaine de Voluceau,
35  * 78150 Le Chesnay - Rocquencourt
36  * FRANCE
37  *
38  */
39 
40 #ifndef GEOGRAM_BASIC_ALGORITHM
41 #define GEOGRAM_BASIC_ALGORITHM
42 
43 #include <geogram/basic/common.h>
44 
45 #if defined(GEO_OS_LINUX) && defined(GEO_OPENMP)
46 #if (__GNUC__ >= 4) && (__GNUC_MINOR__ >= 4) && !defined(GEO_OS_ANDROID)
47 #include <parallel/algorithm>
48 #define GEO_USE_GCC_PARALLEL_STL
49 #endif
50 #elif defined(GEO_OS_WINDOWS)
51 #if (_MSC_VER >= 1700)
52 #include <ppl.h>
53 #define GEO_USE_MSVC_PARALLEL_STL
54 #endif
55 #endif
56 
57 #include <algorithm>
58 #include <random>
59 
65 namespace GEO {
66 
75  bool GEOGRAM_API uses_parallel_algorithm();
76 
89  template <typename ITERATOR>
90  inline void sort(
91  const ITERATOR& begin, const ITERATOR& end
92  ) {
94 #if defined(GEO_USE_GCC_PARALLEL_STL)
95  __gnu_parallel::sort(begin, end);
96 #elif defined(GEO_USE_MSVC_PARALLEL_STL)
97  concurrency::parallel_sort(begin, end);
98 #else
99  std::sort(begin, end);
100 #endif
101  } else {
102  std::sort(begin, end);
103  }
104  }
105 
125  template <typename ITERATOR, typename CMP>
126  inline void sort(
127  const ITERATOR& begin, const ITERATOR& end, const CMP& cmp
128  ) {
130 #if defined(GEO_USE_GCC_PARALLEL_STL)
131  __gnu_parallel::sort(begin, end, cmp);
132 #elif defined(GEO_USE_MSVC_PARALLEL_STL)
133  concurrency::parallel_sort(begin, end, cmp);
134 #else
135  std::sort(begin, end, cmp);
136 #endif
137  } else {
138  std::sort(begin, end, cmp);
139  }
140  }
141 
142 
147  template <typename VECTOR> inline void sort_unique(VECTOR& v) {
148  std::sort(v.begin(), v.end());
149  // Note that std::unique leaves a 'queue' of duplicated elements
150  // at the end of the vector, and returns an iterator that
151  // indicates where to stop.
152  v.erase(
153  std::unique(v.begin(), v.end()), v.end()
154  );
155  }
156 
163  template <typename ITERATOR> inline void sort_3(ITERATOR items) {
164  if (items[0]> items[1]) {
165  std::swap(items[0], items[1]);
166  }
167  if (items[1]> items[2]) {
168  std::swap(items[1], items[2]);
169  }
170  if (items[0]> items[1]) {
171  std::swap(items[0], items[1]);
172  }
173  }
174 
181  template <typename ITERATOR> inline void sort_4(ITERATOR items) {
182  if (items[1] < items[0]) {
183  std::swap(items[0], items[1]);
184  }
185  if (items[3] < items[2]) {
186  std::swap(items[2], items[3]);
187  }
188  if (items[2] < items[0]) {
189  std::swap(items[0], items[2]);
190  std::swap(items[1], items[3]);
191  }
192  if (items[2] < items[1]) {
193  std::swap(items[1], items[2]);
194  }
195  if (items[3] < items[2]) {
196  std::swap(items[2], items[3]);
197  }
198  }
199 
207  template <typename ITERATOR>
208  inline void random_shuffle(
209  const ITERATOR& begin, const ITERATOR& end
210  ) {
211  std::random_device rng;
212  std::mt19937 urng(rng());
213  std::shuffle(begin, end, urng);
214  }
215 
216 }
217 
218 #endif
Common include file, providing basic definitions. Should be included before anything else by all head...
Global Vorpaline namespace.
Definition: basic.h:55
void sort_unique(VECTOR &v)
Sorts a vector and suppresses all duplicated elements.
Definition: algorithm.h:147
bool uses_parallel_algorithm()
Checks whether parallel algorithms are used.
void sort_4(ITERATOR items)
Specialized sort routine for 4 elements.
Definition: algorithm.h:181
void sort(const ITERATOR &begin, const ITERATOR &end)
Sorts elements in parallel.
Definition: algorithm.h:90
void sort(const ITERATOR &begin, const ITERATOR &end, const CMP &cmp)
Sorts elements in parallel.
Definition: algorithm.h:126
void sort_3(ITERATOR items)
Specialized sort routine for 3 elements.
Definition: algorithm.h:163
void random_shuffle(const ITERATOR &begin, const ITERATOR &end)
Applies a random permutation to a sequence.
Definition: algorithm.h:208