diff options
Diffstat (limited to 'Source/cmAlgorithms.h')
-rw-r--r-- | Source/cmAlgorithms.h | 372 |
1 files changed, 372 insertions, 0 deletions
diff --git a/Source/cmAlgorithms.h b/Source/cmAlgorithms.h new file mode 100644 index 0000000..bda933b --- /dev/null +++ b/Source/cmAlgorithms.h @@ -0,0 +1,372 @@ +/*============================================================================ + CMake - Cross Platform Makefile Generator + Copyright 2015 Stephen Kelly <steveire@gmail.com> + + Distributed under the OSI-approved BSD License (the "License"); + see accompanying file Copyright.txt for details. + + This software is distributed WITHOUT ANY WARRANTY; without even the + implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the License for more information. +============================================================================*/ +#ifndef cmAlgorithms_h +#define cmAlgorithms_h + +#include "cmStandardIncludes.h" + +inline bool cmHasLiteralPrefixImpl(const std::string &str1, + const char *str2, + size_t N) +{ + return strncmp(str1.c_str(), str2, N) == 0; +} + +inline bool cmHasLiteralPrefixImpl(const char* str1, + const char *str2, + size_t N) +{ + return strncmp(str1, str2, N) == 0; +} + +inline bool cmHasLiteralSuffixImpl(const std::string &str1, + const char *str2, + size_t N) +{ + size_t len = str1.size(); + return len >= N && strcmp(str1.c_str() + len - N, str2) == 0; +} + +inline bool cmHasLiteralSuffixImpl(const char* str1, + const char* str2, + size_t N) +{ + size_t len = strlen(str1); + return len >= N && strcmp(str1 + len - N, str2) == 0; +} + +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; } + +template<typename T, size_t N> +bool cmHasLiteralPrefix(T str1, const char (&str2)[N]) +{ + return cmHasLiteralPrefixImpl(str1, str2, N - 1); +} + +template<typename T, size_t N> +bool cmHasLiteralSuffix(T str1, const char (&str2)[N]) +{ + return cmHasLiteralSuffixImpl(str1, str2, N - 1); +} + +struct cmStrCmp { + cmStrCmp(const char *test) : m_test(test) {} + cmStrCmp(const std::string &test) : m_test(test) {} + + bool operator()(const std::string& input) const + { + return m_test == input; + } + + bool operator()(const char * input) const + { + return strcmp(input, m_test.c_str()) == 0; + } + +private: + const std::string m_test; +}; + +template<typename FwdIt> +FwdIt cmRotate(FwdIt first, FwdIt middle, FwdIt last) +{ + const typename std::iterator_traits<FwdIt>::difference_type dist = + std::distance(middle, last); + std::rotate(first, middle, last); + std::advance(first, dist); + return first; +} + +namespace ContainerAlgorithms { + +template<typename T> +struct cmIsPair +{ + enum { value = false }; +}; + +template<typename K, typename V> +struct cmIsPair<std::pair<K, V> > +{ + enum { value = true }; +}; + +template<typename Range, + bool valueTypeIsPair = cmIsPair<typename Range::value_type>::value> +struct DefaultDeleter +{ + void operator()(typename Range::value_type value) const { + delete value; + } +}; + +template<typename Range> +struct DefaultDeleter<Range, /* valueTypeIsPair = */ true> +{ + void operator()(typename Range::value_type value) const { + delete value.second; + } +}; + +template<typename FwdIt> +FwdIt RemoveN(FwdIt i1, FwdIt i2, size_t n) +{ + FwdIt m = i1; + std::advance(m, n); + return cmRotate(i1, m, i2); +} + +template<typename Range> +struct BinarySearcher +{ + typedef typename Range::value_type argument_type; + BinarySearcher(Range const& r) + : m_range(r) + { + } + + bool operator()(argument_type const& item) const + { + return std::binary_search(m_range.begin(), m_range.end(), item); + } +private: + Range const& m_range; +}; + +} + +template<typename const_iterator_> +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_) + : Begin(begin_), End(end_) {} + 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); } + cmRange& advance(cmIML_INT_intptr_t amount) + { + std::advance(Begin, amount); + return *this; + } + + cmRange& retreat(cmIML_INT_intptr_t amount) + { + std::advance(End, -amount); + return *this; + } +private: + const_iterator Begin; + const_iterator End; +}; + +typedef cmRange<std::vector<std::string>::const_iterator> cmStringRange; + +class cmListFileBacktrace; +typedef +cmRange<std::vector<cmListFileBacktrace>::const_iterator> cmBacktraceRange; + +template<typename Iter1, typename Iter2> +cmRange<Iter1> cmMakeRange(Iter1 begin, Iter2 end) +{ + return cmRange<Iter1>(begin, end); +} + +template<typename Range> +cmRange<typename Range::const_iterator> +cmMakeRange(Range const& range) +{ + return cmRange<typename Range::const_iterator>( + range.begin(), range.end()); +} + +template<typename Range> +void cmDeleteAll(Range const& r) +{ + std::for_each(r.begin(), r.end(), + ContainerAlgorithms::DefaultDeleter<Range>()); +} + +template<typename Range> +std::string cmJoin(Range const& r, const char* delimiter) +{ + if (r.empty()) + { + return std::string(); + } + std::ostringstream os; + typedef typename Range::value_type ValueType; + typedef typename Range::const_iterator InputIt; + const InputIt first = r.begin(); + InputIt last = r.end(); + --last; + std::copy(first, last, + std::ostream_iterator<ValueType>(os, delimiter)); + + os << *last; + + return os.str(); +} + +template<typename Range> +std::string cmJoin(Range const& r, std::string delimiter) +{ + return cmJoin(r, delimiter.c_str()); +}; + +template<typename Range> +typename Range::const_iterator cmRemoveN(Range& r, size_t n) +{ + return ContainerAlgorithms::RemoveN(r.begin(), r.end(), n); +} + +template<typename Range, typename InputRange> +typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem) +{ + typename InputRange::const_iterator remIt = rem.begin(); + typename InputRange::const_iterator remEnd = rem.end(); + const typename Range::iterator rangeEnd = r.end(); + if (remIt == remEnd) + { + return rangeEnd; + } + + typename Range::iterator writer = r.begin(); + std::advance(writer, *remIt); + typename Range::iterator pivot = writer; + typename InputRange::value_type prevRem = *remIt; + ++remIt; + size_t count = 1; + for ( ; writer != rangeEnd && remIt != remEnd; ++count, ++remIt) + { + std::advance(pivot, *remIt - prevRem); + prevRem = *remIt; + writer = ContainerAlgorithms::RemoveN(writer, pivot, count); + } + return ContainerAlgorithms::RemoveN(writer, rangeEnd, count); +} + +template<typename Range, typename MatchRange> +typename Range::const_iterator cmRemoveMatching(Range &r, MatchRange const& m) +{ + return std::remove_if(r.begin(), r.end(), + ContainerAlgorithms::BinarySearcher<MatchRange>(m)); +} + +namespace ContainerAlgorithms { + +template<typename Range, typename T = typename Range::value_type> +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; } + template<typename It> + static bool valueCompare(It it, const_iterator it2) { return **it != *it2; } +}; + +template<typename Range, typename T> +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; } + template<typename It> + static bool valueCompare(It it, const_iterator it2) { return *it != *it2; } +}; + +} + +template<typename Range> +typename Range::const_iterator cmRemoveDuplicates(Range& r) +{ + typedef typename ContainerAlgorithms::RemoveDuplicatesAPI<Range> API; + typedef typename API::value_type T; + std::vector<T> unique; + unique.reserve(r.size()); + std::vector<size_t> indices; + size_t count = 0; + const typename Range::const_iterator end = r.end(); + 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)) + { + unique.insert(low, API::uniqueValue(it)); + } + else + { + indices.push_back(count); + } + } + if (indices.empty()) + { + return end; + } + return cmRemoveIndices(r, indices); +} + +template<typename Range> +std::string cmWrap(std::string prefix, Range const& r, std::string suffix, + std::string sep) +{ + if (r.empty()) + { + return std::string(); + } + return prefix + cmJoin(r, (suffix + sep + prefix).c_str()) + suffix; +} + +template<typename Range> +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); +} + +template<typename Range, typename T> +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)); +} + +template<typename Range> +cmRange<typename Range::const_reverse_iterator> +cmReverseRange(Range const& range) +{ + return cmRange<typename Range::const_reverse_iterator>( + range.rbegin(), range.rend()); +} + +template <class Iter> +std::reverse_iterator<Iter> cmMakeReverseIterator(Iter it) +{ + return std::reverse_iterator<Iter>(it); +} + +#endif |