Source/cmAlgorithms.h

   1 /* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   2    file Copyright.txt or https://cmake.org/licensing for details.  */
   3 #pragma once
   4
   5 #include "cmConfigure.h" // IWYU pragma: keep
   6
   7 #include <algorithm>
   8 #include <functional>
   9 #include <iterator>
  10 #include <memory>
  11 #include <unordered_set>
  12 #include <utility>
  13 #include <vector>
  14
  15 #include <cmext/algorithm>
  16
  17 #include "cmRange.h"
  18
  19 template <typename FwdIt>
  20 FwdIt cmRotate(FwdIt first, FwdIt middle, FwdIt last)
  21 {
  22   const typename std::iterator_traits<FwdIt>::difference_type dist =
  23     std::distance(middle, last);
  24   std::rotate(first, middle, last);
  25   std::advance(first, dist);
  26   return first;
  27 }
  28
  29 namespace ContainerAlgorithms {
  30
  31 template <typename FwdIt>
  32 FwdIt RemoveN(FwdIt i1, FwdIt i2, size_t n)
  33 {
  34   FwdIt m = i1;
  35   std::advance(m, n);
  36   return cmRotate(i1, m, i2);
  37 }
  38
  39 template <typename Range>
  40 struct BinarySearcher
  41 {
  42   using argument_type = typename Range::value_type;
  43   BinarySearcher(Range const& r)
  44     : m_range(r)
  45   {
  46   }
  47
  48   bool operator()(argument_type const& item) const
  49   {
  50     return std::binary_search(this->m_range.begin(), this->m_range.end(),
  51                               item);
  52   }
  53
  54 private:
  55   Range const& m_range;
  56 };
  57 }
  58
  59 class cmListFileBacktrace;
  60 using cmBacktraceRange =
  61   cmRange<std::vector<cmListFileBacktrace>::const_iterator>;
  62
  63 template <typename T>
  64 class BT;
  65 using cmBTStringRange = cmRange<std::vector<BT<std::string>>::const_iterator>;
  66
  67 template <typename Range>
  68 typename Range::const_iterator cmRemoveN(Range& r, size_t n)
  69 {
  70   return ContainerAlgorithms::RemoveN(r.begin(), r.end(), n);
  71 }
  72
  73 template <typename Range, typename InputRange>
  74 typename Range::const_iterator cmRemoveIndices(Range& r, InputRange const& rem)
  75 {
  76   typename InputRange::const_iterator remIt = rem.begin();
  77   typename InputRange::const_iterator remEnd = rem.end();
  78   const auto rangeEnd = r.end();
  79   if (remIt == remEnd) {
  80     return rangeEnd;
  81   }
  82
  83   auto writer = r.begin();
  84   std::advance(writer, *remIt);
  85   auto pivot = writer;
  86   typename InputRange::value_type prevRem = *remIt;
  87   ++remIt;
  88   size_t count = 1;
  89   for (; writer != rangeEnd && remIt != remEnd; ++count, ++remIt) {
  90     std::advance(pivot, *remIt - prevRem);
  91     prevRem = *remIt;
  92     writer = ContainerAlgorithms::RemoveN(writer, pivot, count);
  93   }
  94   return ContainerAlgorithms::RemoveN(writer, rangeEnd, count);
  95 }
  96
  97 template <typename Range, typename MatchRange>
  98 typename Range::const_iterator cmRemoveMatching(Range& r, MatchRange const& m)
  99 {
 100   return std::remove_if(r.begin(), r.end(),
 101                         ContainerAlgorithms::BinarySearcher<MatchRange>(m));
 102 }
 103
 104 template <typename ForwardIterator>
 105 ForwardIterator cmRemoveDuplicates(ForwardIterator first, ForwardIterator last)
 106 {
 107   using Value = typename std::iterator_traits<ForwardIterator>::value_type;
 108   struct Hash
 109   {
 110     std::size_t operator()(ForwardIterator it) const
 111     {
 112       return std::hash<Value>{}(*it);
 113     }
 114   };
 115
 116   struct Equal
 117   {
 118     bool operator()(ForwardIterator it1, ForwardIterator it2) const
 119     {
 120       return *it1 == *it2;
 121     }
 122   };
 123   std::unordered_set<ForwardIterator, Hash, Equal> uniq;
 124
 125   ForwardIterator result = first;
 126   while (first != last) {
 127     if (!cm::contains(uniq, first)) {
 128       if (result != first) {
 129         *result = std::move(*first);
 130       }
 131       uniq.insert(result);
 132       ++result;
 133     }
 134     ++first;
 135   }
 136   return result;
 137 }
 138
 139 template <typename Range>
 140 typename Range::iterator cmRemoveDuplicates(Range& r)
 141 {
 142   return cmRemoveDuplicates(r.begin(), r.end());
 143 }
 144
 145 template <typename Range>
 146 typename Range::const_iterator cmRemoveDuplicates(Range const& r)
 147 {
 148   return cmRemoveDuplicates(r.begin(), r.end());
 149 }
 150
 151 template <typename Range, typename T>
 152 typename Range::const_iterator cmFindNot(Range const& r, T const& t)
 153 {
 154   return std::find_if(r.begin(), r.end(), [&t](T const& i) { return i != t; });
 155 }