Geogram Version 1.8.5
A programming library of geometric algorithms
Loading...
Searching...
No Matches
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
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
64namespace GEO {
65
74 bool GEOGRAM_API uses_parallel_algorithm();
75
88 template <typename ITERATOR>
89 inline void sort(
90 const ITERATOR& begin, const ITERATOR& end
91 ) {
93#if defined(GEO_USE_GCC_PARALLEL_STL)
94 __gnu_parallel::sort(begin, end);
95#elif defined(GEO_USE_MSVC_PARALLEL_STL)
96 concurrency::parallel_sort(begin, end);
97#else
98 std::sort(begin, end);
99#endif
100 } else {
101 std::sort(begin, end);
102 }
103 }
104
124 template <typename ITERATOR, typename CMP>
125 inline void sort(
126 const ITERATOR& begin, const ITERATOR& end, const CMP& cmp
127 ) {
129#if defined(GEO_USE_GCC_PARALLEL_STL)
130 __gnu_parallel::sort(begin, end, cmp);
131#elif defined(GEO_USE_MSVC_PARALLEL_STL)
132 concurrency::parallel_sort(begin, end, cmp);
133#else
134 std::sort(begin, end, cmp);
135#endif
136 } else {
137 std::sort(begin, end, cmp);
138 }
139 }
140
141
146 template <typename VECTOR> inline void sort_unique(VECTOR& v) {
147 std::sort(v.begin(), v.end());
148 // Note that std::unique leaves a 'queue' of duplicated elements
149 // at the end of the vector, and returns an iterator that
150 // indicates where to stop.
151 v.erase(
152 std::unique(v.begin(), v.end()), v.end()
153 );
154 }
155
162 template <typename ITERATOR> inline void sort_3(ITERATOR items) {
163 if (items[0]> items[1]) {
164 std::swap(items[0], items[1]);
165 }
166 if (items[1]> items[2]) {
167 std::swap(items[1], items[2]);
168 }
169 if (items[0]> items[1]) {
170 std::swap(items[0], items[1]);
171 }
172 }
173
180 template <typename ITERATOR> inline void sort_4(ITERATOR items) {
181 if (items[1] < items[0]) {
182 std::swap(items[0], items[1]);
183 }
184 if (items[3] < items[2]) {
185 std::swap(items[2], items[3]);
186 }
187 if (items[2] < items[0]) {
188 std::swap(items[0], items[2]);
189 std::swap(items[1], items[3]);
190 }
191 if (items[2] < items[1]) {
192 std::swap(items[1], items[2]);
193 }
194 if (items[3] < items[2]) {
195 std::swap(items[2], items[3]);
196 }
197 }
198
199}
200
201#endif
202
Common include file, providing basic definitions. Should be included before anything else by all head...
Global Vorpaline namespace.
Definition algorithm.h:64
void sort_unique(VECTOR &v)
Sorts a vector and suppresses all duplicated elements.
Definition algorithm.h:146
bool uses_parallel_algorithm()
Checks whether parallel algorithms are used.
void sort_4(ITERATOR items)
Specialized sort routine for 4 elements.
Definition algorithm.h:180
void sort(const ITERATOR &begin, const ITERATOR &end)
Sorts elements in parallel.
Definition algorithm.h:89
void sort_3(ITERATOR items)
Specialized sort routine for 3 elements.
Definition algorithm.h:162