cmAlgorithms.h 9.73 KB
Newer Older
1
2
/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file Copyright.txt or https://cmake.org/licensing for details.  */
3
4
5
#ifndef cmAlgorithms_h
#define cmAlgorithms_h

6
#include <cmConfigure.h> // IWYU pragma: keep
7

8
9
10
11
12
13
14
15
16
#include <algorithm>
#include <cm_kwiml.h>
#include <functional>
#include <iterator>
#include <sstream>
#include <string.h>
#include <string>
#include <utility>
#include <vector>
17

18
19
inline bool cmHasLiteralPrefixImpl(const std::string& str1, const char* str2,
                                   size_t N)
20
21
22
23
{
  return strncmp(str1.c_str(), str2, N) == 0;
}

24
25
inline bool cmHasLiteralPrefixImpl(const char* str1, const char* str2,
                                   size_t N)
26
27
28
29
{
  return strncmp(str1, str2, N) == 0;
}

30
inline bool cmHasLiteralSuffixImpl(const std::string& str1, const char* str2,
31
32
33
34
35
36
                                   size_t N)
{
  size_t len = str1.size();
  return len >= N && strcmp(str1.c_str() + len - N, str2) == 0;
}

37
inline bool cmHasLiteralSuffixImpl(const char* str1, const char* str2,
38
39
40
41
42
43
                                   size_t N)
{
  size_t len = strlen(str1);
  return len >= N && strcmp(str1 + len - N, str2) == 0;
}

44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
template <typename T, size_t N>
const T* cmArrayBegin(const T (&a)[N])
{
  return a;
}
template <typename T, size_t N>
const T* cmArrayEnd(const T (&a)[N])
{
  return a + N;
}
template <typename T, size_t N>
size_t cmArraySize(const T (&)[N])
{
  return N;
}
59

60
template <typename T, size_t N>
61
bool cmHasLiteralPrefix(const T& str1, const char (&str2)[N])
62
63
64
65
{
  return cmHasLiteralPrefixImpl(str1, str2, N - 1);
}

66
template <typename T, size_t N>
67
bool cmHasLiteralSuffix(const T& str1, const char (&str2)[N])
68
69
70
71
{
  return cmHasLiteralSuffixImpl(str1, str2, N - 1);
}

72
73
74
75
struct cmStrCmp
{
  cmStrCmp(const char* test)
    : m_test(test)
76
77
  {
  }
78
79
80
81
82
83
  cmStrCmp(const std::string& test)
    : m_test(test)
  {
  }

  bool operator()(const std::string& input) const { return m_test == input; }
84

85
  bool operator()(const char* input) const
86
87
88
89
90
91
92
93
  {
    return strcmp(input, m_test.c_str()) == 0;
  }

private:
  const std::string m_test;
};

94
template <typename FwdIt>
95
FwdIt cmRotate(FwdIt first, FwdIt middle, FwdIt last)
96
{
97
  const typename std::iterator_traits<FwdIt>::difference_type dist =
98
    std::distance(middle, last);
99
  std::rotate(first, middle, last);
100
101
  std::advance(first, dist);
  return first;
102
103
}

104
105
namespace ContainerAlgorithms {

106
template <typename T>
107
108
struct cmIsPair
{
109
110
111
112
  enum
  {
    value = false
  };
113
114
};

115
template <typename K, typename V>
116
117
struct cmIsPair<std::pair<K, V> >
{
118
119
120
121
  enum
  {
    value = true
  };
122
123
};

124
125
template <typename Range,
          bool valueTypeIsPair = cmIsPair<typename Range::value_type>::value>
126
127
struct DefaultDeleter
{
128
  void operator()(typename Range::value_type value) const { delete value; }
129
130
};

131
template <typename Range>
132
struct DefaultDeleter<Range, /* valueTypeIsPair = */ true>
133
{
134
135
  void operator()(typename Range::value_type value) const
  {
136
137
138
139
    delete value.second;
  }
};

140
template <typename FwdIt>
141
FwdIt RemoveN(FwdIt i1, FwdIt i2, size_t n)
142
{
143
  FwdIt m = i1;
144
145
  std::advance(m, n);
  return cmRotate(i1, m, i2);
146
147
}

148
template <typename Range>
149
150
151
152
153
154
155
156
struct BinarySearcher
{
  typedef typename Range::value_type argument_type;
  BinarySearcher(Range const& r)
    : m_range(r)
  {
  }

157
  bool operator()(argument_type const& item) const
158
159
160
  {
    return std::binary_search(m_range.begin(), m_range.end(), item);
  }
161

162
163
164
private:
  Range const& m_range;
};
165
166
}

167
template <typename const_iterator_>
168
169
170
171
172
173
174
struct cmRange
{
  typedef const_iterator_ const_iterator;
  typedef typename std::iterator_traits<const_iterator>::value_type value_type;
  typedef typename std::iterator_traits<const_iterator>::difference_type
    difference_type;
  cmRange(const_iterator begin_, const_iterator end_)
175
176
177
178
    : Begin(begin_)
    , End(end_)
  {
  }
179
180
181
182
  const_iterator begin() const { return Begin; }
  const_iterator end() const { return End; }
  bool empty() const { return std::distance(Begin, End) == 0; }
  difference_type size() const { return std::distance(Begin, End); }
Brad King's avatar
Brad King committed
183
  cmRange& advance(KWIML_INT_intptr_t amount)
184
185
186
187
188
  {
    std::advance(Begin, amount);
    return *this;
  }

Brad King's avatar
Brad King committed
189
  cmRange& retreat(KWIML_INT_intptr_t amount)
190
191
192
193
  {
    std::advance(End, -amount);
    return *this;
  }
194

195
196
197
198
199
private:
  const_iterator Begin;
  const_iterator End;
};

200
201
202
typedef cmRange<std::vector<std::string>::const_iterator> cmStringRange;

class cmListFileBacktrace;
203
204
typedef cmRange<std::vector<cmListFileBacktrace>::const_iterator>
  cmBacktraceRange;
205

206
template <typename Iter1, typename Iter2>
207
cmRange<Iter1> cmMakeRange(Iter1 begin, Iter2 end)
208
{
209
  return cmRange<Iter1>(begin, end);
210
211
}

212
213
template <typename Range>
cmRange<typename Range::const_iterator> cmMakeRange(Range const& range)
214
{
215
  return cmRange<typename Range::const_iterator>(range.begin(), range.end());
216
217
}

218
template <typename Range>
219
void cmDeleteAll(Range const& r)
220
{
221
222
  std::for_each(r.begin(), r.end(),
                ContainerAlgorithms::DefaultDeleter<Range>());
223
224
}

225
template <typename Range>
226
227
std::string cmJoin(Range const& r, const char* delimiter)
{
228
  if (r.empty()) {
229
    return std::string();
230
  }
231
232
233
  std::ostringstream os;
  typedef typename Range::value_type ValueType;
  typedef typename Range::const_iterator InputIt;
234
  const InputIt first = r.begin();
235
236
  InputIt last = r.end();
  --last;
237
  std::copy(first, last, std::ostream_iterator<ValueType>(os, delimiter));
238
239
240
241
242
243

  os << *last;

  return os.str();
}

244
template <typename Range>
245
246
247
std::string cmJoin(Range const& r, std::string delimiter)
{
  return cmJoin(r, delimiter.c_str());
248
}
249

250
template <typename Range>
251
252
253
254
255
typename Range::const_iterator cmRemoveN(Range& r, size_t n)
{
  return ContainerAlgorithms::RemoveN(r.begin(), r.end(), n);
}

256
template <typename Range, typename InputRange>
257
258
259
typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem)
{
  typename InputRange::const_iterator remIt = rem.begin();
260
  typename InputRange::const_iterator remEnd = rem.end();
261
  const typename Range::iterator rangeEnd = r.end();
262
  if (remIt == remEnd) {
263
    return rangeEnd;
264
  }
265

266
267
  typename Range::iterator writer = r.begin();
  std::advance(writer, *remIt);
268
269
  typename Range::iterator pivot = writer;
  typename InputRange::value_type prevRem = *remIt;
270
271
  ++remIt;
  size_t count = 1;
272
  for (; writer != rangeEnd && remIt != remEnd; ++count, ++remIt) {
273
274
    std::advance(pivot, *remIt - prevRem);
    prevRem = *remIt;
275
    writer = ContainerAlgorithms::RemoveN(writer, pivot, count);
276
  }
277
  return ContainerAlgorithms::RemoveN(writer, rangeEnd, count);
278
279
}

280
281
template <typename Range, typename MatchRange>
typename Range::const_iterator cmRemoveMatching(Range& r, MatchRange const& m)
282
283
284
285
286
{
  return std::remove_if(r.begin(), r.end(),
                        ContainerAlgorithms::BinarySearcher<MatchRange>(m));
}

287
288
namespace ContainerAlgorithms {

289
template <typename Range, typename T = typename Range::value_type>
290
291
292
293
294
295
296
struct RemoveDuplicatesAPI
{
  typedef typename Range::const_iterator const_iterator;
  typedef typename Range::const_iterator value_type;

  static bool lessThan(value_type a, value_type b) { return *a < *b; }
  static value_type uniqueValue(const_iterator a) { return a; }
297
298
299
300
301
  template <typename It>
  static bool valueCompare(It it, const_iterator it2)
  {
    return **it != *it2;
  }
302
303
};

304
template <typename Range, typename T>
305
306
307
308
309
310
311
struct RemoveDuplicatesAPI<Range, T*>
{
  typedef typename Range::const_iterator const_iterator;
  typedef T* value_type;

  static bool lessThan(value_type a, value_type b) { return a < b; }
  static value_type uniqueValue(const_iterator a) { return *a; }
312
313
314
315
316
  template <typename It>
  static bool valueCompare(It it, const_iterator it2)
  {
    return *it != *it2;
  }
317
};
318
319
}

320
template <typename Range>
321
322
typename Range::const_iterator cmRemoveDuplicates(Range& r)
{
323
324
  typedef typename ContainerAlgorithms::RemoveDuplicatesAPI<Range> API;
  typedef typename API::value_type T;
325
  std::vector<T> unique;
326
327
328
  unique.reserve(r.size());
  std::vector<size_t> indices;
  size_t count = 0;
329
  const typename Range::const_iterator end = r.end();
330
331
332
333
334
  for (typename Range::const_iterator it = r.begin(); it != end;
       ++it, ++count) {
    const typename std::vector<T>::iterator low = std::lower_bound(
      unique.begin(), unique.end(), API::uniqueValue(it), API::lessThan);
    if (low == unique.end() || API::valueCompare(low, it)) {
335
      unique.insert(low, API::uniqueValue(it));
336
    } else {
337
338
      indices.push_back(count);
    }
339
340
  }
  if (indices.empty()) {
341
    return end;
342
  }
343
344
345
  return cmRemoveIndices(r, indices);
}

346
template <typename Range>
Stephen Kelly's avatar
Stephen Kelly committed
347
348
349
std::string cmWrap(std::string prefix, Range const& r, std::string suffix,
                   std::string sep)
{
350
  if (r.empty()) {
Stephen Kelly's avatar
Stephen Kelly committed
351
    return std::string();
352
  }
Stephen Kelly's avatar
Stephen Kelly committed
353
354
355
  return prefix + cmJoin(r, (suffix + sep + prefix).c_str()) + suffix;
}

356
template <typename Range>
Stephen Kelly's avatar
Stephen Kelly committed
357
358
359
360
361
std::string cmWrap(char prefix, Range const& r, char suffix, std::string sep)
{
  return cmWrap(std::string(1, prefix), r, std::string(1, suffix), sep);
}

362
template <typename Range, typename T>
363
364
365
366
367
368
typename Range::const_iterator cmFindNot(Range const& r, T const& t)
{
  return std::find_if(r.begin(), r.end(),
                      std::bind1st(std::not_equal_to<T>(), t));
}

369
370
371
template <typename Range>
cmRange<typename Range::const_reverse_iterator> cmReverseRange(
  Range const& range)
372
{
373
374
  return cmRange<typename Range::const_reverse_iterator>(range.rbegin(),
                                                         range.rend());
375
376
}

377
378
379
380
381
382
template <class Iter>
std::reverse_iterator<Iter> cmMakeReverseIterator(Iter it)
{
  return std::reverse_iterator<Iter>(it);
}

383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
inline bool cmHasSuffix(const std::string& str, const std::string& suffix)
{
  if (str.size() < suffix.size()) {
    return false;
  }
  return str.compare(str.size() - suffix.size(), suffix.size(), suffix) == 0;
}

inline void cmStripSuffixIfExists(std::string& str, const std::string& suffix)
{
  if (cmHasSuffix(str, suffix)) {
    str.resize(str.size() - suffix.size());
  }
}

398
#endif