AceCommon  1.6.1
Arduino library for low-level common functions and features with no external dependencies
isSorted.h
Go to the documentation of this file.
1 /*
2 MIT License
3 
4 Copyright (c) 2021 Brian T. Park
5 
6 Permission is hereby granted, free of charge, to any person obtaining a copy
7 of this software and associated documentation files (the "Software"), to deal
8 in the Software without restriction, including without limitation the rights
9 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 copies of the Software, and to permit persons to whom the Software is
11 furnished to do so, subject to the following conditions:
12 
13 The above copyright notice and this permission notice shall be included in all
14 copies or substantial portions of the Software.
15 
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 SOFTWARE.
23 */
24 
31 #ifndef ACE_COMMON_IS_SORTED_H
32 #define ACE_COMMON_IS_SORTED_H
33 
34 namespace ace_common {
35 
45 template<typename X>
46 bool isSorted(const X list[], size_t size) {
47  if (size == 0) return true;
48 
49  // Using prev and current temp variables saves about a few bytes of flash
50  // compared to using list[i] < list[i - 1].
51  X prev = list[0];
52  for (size_t i = 1; i < size; ++i) {
53  X current = list[i];
54  if (current < prev) return false;
55  prev = current;
56  }
57  return true;
58 }
59 
60 #if 0
61 // This shorter alternative runs a lot slower on many platforms because the
62 // compiler is not able to optimize away the lambda expression and so the
63 // isSortedByKey() makes a function call on each iteration.
64 template<typename X>
65 bool isSorted(const X list[], size_t size) {
66  return isSortedByKey(size,
67  [&list](size_t i) { return list[i]; } /*key*/);
68 }
69 #endif
70 
92 template <typename K>
93 bool isSortedByKey(size_t size, K&& key) {
94  if (size == 0) return true;
95 
96  auto prev = key(0);
97  for (size_t i = 1; i < size; ++i) {
98  auto current = key(i);
99  if (current < prev) return false;
100  prev = current;
101  }
102  return true;
103 }
104 
113 template<typename X>
114 bool isReverseSorted(const X list[], size_t size) {
115  if (size == 0) return true;
116 
117  // Using prev and current temp variables saves about a few bytes of flash
118  // compared to using list[i] < list[i - 1].
119  X prev = list[0];
120  for (size_t i = 1; i < size; ++i) {
121  X current = list[i];
122  if (current > prev) return false;
123  prev = current;
124  }
125  return true;
126 }
127 
140 template <typename K>
141 bool isReverseSortedByKey(size_t size, K&& key) {
142  if (size == 0) return true;
143 
144  auto prev = key(0);
145  for (size_t i = 1; i < size; ++i) {
146  auto current = key(i);
147  if (current > prev) return false;
148  prev = current;
149  }
150  return true;
151 }
152 
153 } // ace_common
154 
155 #endif
bool isReverseSortedByKey(size_t size, K &&key)
Same as isSortedByKey() but checks for reverse sorting.
Definition: isSorted.h:141
bool isSorted(const X list[], size_t size)
Determine if the elements of the array is sorted This function assumes that 'operator<()' for the val...
Definition: isSorted.h:46
bool isReverseSorted(const X list[], size_t size)
Same as isSorted() but checks for reverse sorting.
Definition: isSorted.h:114
bool isSortedByKey(size_t size, K &&key)
Determine if the abstract array is sorted according to its 'key'.
Definition: isSorted.h:93