Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
insertion_sort.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/sort/strings/insertion_sort.hpp
3  *
4  * Base insertion string sort. This is an internal implementation header, see
5  * tlx/sort/strings.hpp for public front-end functions.
6  *
7  * Part of tlx - http://panthema.net/tlx
8  *
9  * Copyright (C) 2015-2018 Timo Bingmann <[email protected]>
10  *
11  * All rights reserved. Published under the Boost Software License, Version 1.0
12  ******************************************************************************/
13 
14 #ifndef TLX_SORT_STRINGS_INSERTION_SORT_HEADER
15 #define TLX_SORT_STRINGS_INSERTION_SORT_HEADER
16 
17 #include <tlx/define/likely.hpp>
19 
20 namespace tlx {
21 namespace sort_strings_detail {
22 
23 /******************************************************************************/
24 
25 //! Generic insertion sort for abstract string sets. This method only requires
26 //! O(1) additional memory for sorting n strings, but runs in time O(nD).
27 template <typename StringSet>
28 static inline void insertion_sort(
29  const StringSet& ss, size_t depth, size_t /* memory */) {
30  typedef typename StringSet::Iterator Iterator;
31  typedef typename StringSet::String String;
32  typedef typename StringSet::CharIterator CharIterator;
33 
34  // this stores the begin iterator and size n, making the loops faster
35  const Iterator begin = ss.begin();
36  Iterator j;
37  size_t n = ss.size();
38 
39  for (Iterator i = begin + 1; TLX_UNLIKELY(--n != 0); ++i)
40  {
41  String tmp = std::move(ss[i]);
42  j = i;
43 
44  while (TLX_LIKELY(j != begin))
45  {
46  CharIterator s = ss.get_chars(ss[j - 1], depth);
47  CharIterator t = ss.get_chars(tmp, depth);
48 
49  while (TLX_LIKELY(ss.is_equal(ss[j - 1], s, tmp, t)))
50  ++s, ++t;
51 
52  if (TLX_UNLIKELY(ss.is_leq(ss[j - 1], s, tmp, t))) {
53  break;
54  }
55 
56  ss[j] = std::move(ss[j - 1]);
57  --j;
58  }
59 
60  ss[j] = std::move(tmp);
61  }
62 }
63 
64 /******************************************************************************/
65 
66 } // namespace sort_strings_detail
67 } // namespace tlx
68 
69 #endif // !TLX_SORT_STRINGS_INSERTION_SORT_HEADER
70 
71 /******************************************************************************/
#define TLX_UNLIKELY(c)
Definition: likely.hpp:24
static void insertion_sort(const StringSet &ss, size_t depth, size_t)
#define TLX_LIKELY(c)
Definition: likely.hpp:23