Core Library 1.7.0.0 Library containing core utilities and tools for threading, networking, logging, INI and CSV file management etc.

GenericSorting.h
Go to the documentation of this file.
1 // This file is part of CoreLibrary containing useful reusable utility
2 // classes.
3 //
4 // Copyright (C) 2014 to present, Duncan Crutchley
5 // Contact <dac1976github@outlook.com>
6 //
7 // This program is free software: you can redistribute it and/or modify
8 // it under the terms of the GNU Lesser General Public License as published
9 // by the Free Software Foundation, either version 3 of the License, or
10 // (at your option) any later version.
11 //
12 // This program is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License and GNU Lesser General Public License
16 // for more details.
17 //
18 // You should have received a copy of the GNU General Public License
19 // and GNU Lesser General Public License along with this program. If
20 // not, see <http://www.gnu.org/licenses/>.
21
27 #ifndef GENERICSORTING
28 #define GENERICSORTING
29
30 #include <functional>
31 #include <algorithm>
32 #include <utility>
33 #include <vector>
34 #include <list>
35 #include <iterator>
36 #include <stdexcept>
37 #include <boost/throw_exception.hpp>
38
40 namespace core_lib
41 {
43 namespace sorting
44 {
45
53 template <typename T, typename Pred = std::less<T>> class Bubble
54 {
55 public:
57 using item_compare = Pred;
58
68 template <typename TIterator> static void Sort(TIterator begin, TIterator end)
69 {
70 item_compare compare;
71 bool changesMade;
72
73 do
74 {
75 changesMade = false;
76
77 for (auto item = begin; item != end - 1; ++item)
78 {
79 if (compare(*(item + 1), *item))
80 {
81 std::swap(*item, *(item + 1));
82 changesMade = true;
83 }
84 }
85 } while (changesMade);
86 }
87 };
88
96 template <typename T, typename Pred = std::less<T>> class Selection
97 {
98 public:
100 using item_compare = Pred;
101
111 template <typename TIterator> static void Sort(TIterator begin, TIterator end)
112 {
113 item_compare compare;
114 auto item = begin;
115
116 while (item != end)
117 {
118 auto minValue = std::min_element(item, end, compare);
119
120 if (minValue != item)
121 {
122 std::swap(*item, *minValue);
123 }
124
125 ++item;
126 }
127 }
128 };
129
137 template <typename T, typename Pred = std::less<T>> class Insertion
138 {
139 public:
141 using item_compare = Pred;
142
152 template <typename TIterator> static void Sort(TIterator begin, TIterator end)
153 {
154 item_compare compare;
155
156 // we'll iterate over our items and for each item we'll move it to
157 // the correct position in the collection inserting it and shuffling
158 // the other items in the correct direction.
159 for (auto item = begin; item != end; ++item)
160 {
161 std::rotate(std::upper_bound(begin, item, *item, compare), item, std::next(item));
162 }
163 }
164 };
165
174 template <typename T, typename Pred = std::less<T>> class Quick
175 {
176 public:
178 using item_compare = Pred;
179
189 template <typename TIterator> static void Sort(TIterator begin, TIterator end)
190 {
191 auto length = std::distance(begin, end);
192
193 if (length <= 1)
194 {
195 return;
196 }
197
198 auto const pivot = std::next(begin, length / 2);
199 item_compare compare;
200 std::nth_element(begin, pivot, end, compare);
201
202 Sort(begin, pivot);
203 Sort(std::next(pivot), end);
204 }
205 };
206
214 template <typename T, typename Pred = std::less<T>> class Bucket
215 {
216 public:
218 using item_compare = Pred;
220 using bucket_definitions = std::vector<std::pair<T, T>>;
222 using bucket_values = std::vector<std::list<T>>;
223
240 template <typename TIterator>
241 static void Sort(TIterator begin, TIterator end, const bucket_definitions& bucketDefinitions,
242 bucket_values& bucketValues)
243 {
244 if (begin >= end)
245 {
246 return;
247 }
248
249 PutIntoBuckets(begin, end, bucketDefinitions, bucketValues);
250 WriteBackBuckets(begin, bucketValues);
251 SortResult(begin, end);
252 }
253
267 template <typename TIterator>
268 static void Sort(TIterator begin, TIterator end, const bucket_definitions& bucketDefinitions)
269 {
270 bucket_values bucketValues;
271 Sort(begin, end, bucketDefinitions, bucketValues);
272 }
273
274 private:
285 static void CheckBucketsSize(const bucket_definitions& bucketDefinitions,
286 bucket_values& bucketValues)
287 {
288 if (bucketValues.size() != bucketDefinitions.size())
289 {
290 bucketValues.resize(bucketDefinitions.size());
291 }
292 }
293
303 static size_t GetBucketIndex(const T& value, const bucket_definitions& bucketDefinitions)
304 {
305 size_t index{};
306
307 for (const auto& bucket : bucketDefinitions)
308 {
309 if ((value >= bucket.first) && (value <= bucket.second))
310 {
311 break;
312 }
313
314 ++index;
315 }
316
317 if (index == bucketDefinitions.size())
318 {
319 BOOST_THROW_EXCEPTION(std::runtime_error("bucket not found"));
320 }
321
322 return index;
323 }
324
337 template <typename TIterator>
338 static void PutIntoBuckets(TIterator begin, TIterator end,
339 const bucket_definitions& bucketDefinitions,
340 bucket_values& bucketValues)
341 {
342 CheckBucketsSize(bucketDefinitions, bucketValues);
343
344 for (auto item = begin; item != end; ++item)
345 {
346 size_t bucketIndex{GetBucketIndex(*item, bucketDefinitions)};
347 bucketValues[bucketIndex].emplace_back(*item);
348 }
349 }
350
361 template <typename TIterator>
362 static void WriteBackBuckets(TIterator begin, const bucket_values& bucketValues)
363 {
364 TIterator pos{begin};
365
366 for (auto& bucket : bucketValues)
367 {
368 std::move(bucket.begin(), bucket.end(), pos);
369 pos += bucket.size();
370 }
371 }
372
382 template <typename TIterator> static void SortResult(TIterator begin, TIterator end)
383 {
384 Insertion<T, item_compare>::Sort(begin, end);
385 }
386 };
387
388 } // namespace sorting
389 } // namespace core_lib
390
391 #endif // GENERICSORTING
core_lib::sorting::Bucket::CheckBucketsSize
static void CheckBucketsSize(const bucket_definitions &bucketDefinitions, bucket_values &bucketValues)
Static function to check bucket values collection size.
Definition: GenericSorting.h:285
core_lib::sorting::Insertion::Sort
static void Sort(TIterator begin, TIterator end)
In-place static sort function.
Definition: GenericSorting.h:152
core_lib::sorting::Bubble::Sort
static void Sort(TIterator begin, TIterator end)
In-place static sort function.
Definition: GenericSorting.h:68
core_lib::sorting::Bucket::PutIntoBuckets
static void PutIntoBuckets(TIterator begin, TIterator end, const bucket_definitions &bucketDefinitions, bucket_values &bucketValues)
Static to put the items in to the correct buckets.
Definition: GenericSorting.h:338
core_lib::sorting::Quick
Templated static class to perform a quick sort.
Definition: GenericSorting.h:174
core_lib::sorting::Bucket::bucket_values
std::vector< std::list< T > > bucket_values
Public typedef for bucket values.
Definition: GenericSorting.h:222
core_lib::sorting::Bucket
Templated static class to perform a bucket sort.
Definition: GenericSorting.h:214
core_lib::sorting::Insertion::item_compare
Pred item_compare
Public typedef for predicate.
Definition: GenericSorting.h:141
core_lib
The core_lib namespace.
Definition: AsioDefines.h:59
core_lib::sorting::Selection::item_compare
Pred item_compare
Public typedef for predicate.
Definition: GenericSorting.h:100
core_lib::sorting::Selection
Templated static class to perform a selection sort.
Definition: GenericSorting.h:96
core_lib::sorting::Bucket::GetBucketIndex
static size_t GetBucketIndex(const T &value, const bucket_definitions &bucketDefinitions)
Static compute the correct bucket index for a given item.
Definition: GenericSorting.h:303
core_lib::sorting::Bucket::Sort
static void Sort(TIterator begin, TIterator end, const bucket_definitions &bucketDefinitions)
Static sort function.
Definition: GenericSorting.h:268
core_lib::sorting::Insertion
Templated static class to perform a insertion sort.
Definition: GenericSorting.h:137
core_lib::sorting::Selection::Sort
static void Sort(TIterator begin, TIterator end)
In-place static sort function.
Definition: GenericSorting.h:111
core_lib::sorting::Bubble
Templated static class to perform a bubble sort.
Definition: GenericSorting.h:53
core_lib::sorting::Bubble::item_compare
Pred item_compare
Public typedef for predicate.
Definition: GenericSorting.h:57
core_lib::sorting::Quick::item_compare
Pred item_compare
Public typedef for predicate.
Definition: GenericSorting.h:178
core_lib::sorting::Bucket::Sort
static void Sort(TIterator begin, TIterator end, const bucket_definitions &bucketDefinitions, bucket_values &bucketValues)
In-place static sort function.
Definition: GenericSorting.h:241
core_lib::sorting::Bucket::bucket_definitions
std::vector< std::pair< T, T > > bucket_definitions
Public typedef for bucket definitions.
Definition: GenericSorting.h:220
core_lib::sorting::Quick::Sort
static void Sort(TIterator begin, TIterator end)
In-place static sort function.
Definition: GenericSorting.h:189
core_lib::sorting::Bucket::SortResult
static void SortResult(TIterator begin, TIterator end)
Static method to perform a final sort on the collection.
Definition: GenericSorting.h:382
core_lib::sorting::Bucket::WriteBackBuckets
static void WriteBackBuckets(TIterator begin, const bucket_values &bucketValues)
Static to move the items from the buckets back into the original collection.
Definition: GenericSorting.h:362
core_lib::sorting::Bucket::item_compare
Pred item_compare
Public typedef for predicate.
Definition: GenericSorting.h:218