/src/CMake/Source/cmAlgorithms.h

Source
/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file LICENSE.rst or https://cmake.org/licensing for details.  */
#pragma once

#include "cmConfigure.h" // IWYU pragma: keep

#include <algorithm>
#include <functional>
#include <iterator>
#include <memory>
#include <unordered_set>
#include <utility>
#include <vector>

#include <cmext/algorithm>

#include "cmRange.h"

template <typename FwdIt>
FwdIt cmRotate(FwdIt first, FwdIt middle, FwdIt last)
{
  typename std::iterator_traits<FwdIt>::difference_type const dist =
    std::distance(middle, last);
  std::rotate(first, middle, last);
  std::advance(first, dist);
  return first;
}

namespace ContainerAlgorithms {

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
{
  using argument_type = typename Range::value_type;
  BinarySearcher(Range const& r)
    : m_range(r)
  {
  }

  bool operator()(argument_type const& item) const
  {
    return std::binary_search(this->m_range.begin(), this->m_range.end(),
                              item);
  }

private:
  Range const& m_range;
};
}

class cmListFileBacktrace;
using cmBacktraceRange =
  cmRange<std::vector<cmListFileBacktrace>::const_iterator>;

template <typename T>
class BT;
using cmBTStringRange = cmRange<std::vector<BT<std::string>>::const_iterator>;

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();
  auto const rangeEnd = r.end();
  if (remIt == remEnd) {
    return rangeEnd;
  }

  auto writer = r.begin();
  std::advance(writer, *remIt);
  auto 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>
auto cmRemoveMatching(Range& r, MatchRange const& m) -> decltype(r.begin())
{
  return std::remove_if(r.begin(), r.end(),
                        ContainerAlgorithms::BinarySearcher<MatchRange>(m));
}

template <typename ForwardIterator>
ForwardIterator cmRemoveDuplicates(ForwardIterator first, ForwardIterator last)
{
  using Value = typename std::iterator_traits<ForwardIterator>::value_type;
  struct Hash
  {
    std::size_t operator()(ForwardIterator it) const
    {
      return std::hash<Value>{}(*it);
    }
  };

  struct Equal
  {
    bool operator()(ForwardIterator it1, ForwardIterator it2) const
    {
      return *it1 == *it2;
    }
  };
  std::unordered_set<ForwardIterator, Hash, Equal> uniq;

  ForwardIterator result = first;
  while (first != last) {
    if (!cm::contains(uniq, first)) {
      if (result != first) {
        *result = std::move(*first);
      }
      uniq.insert(result);
      ++result;
    }
    ++first;
  }
  return result;
}

template <typename Range>
typename Range::iterator cmRemoveDuplicates(Range& r)
{
  return cmRemoveDuplicates(r.begin(), r.end());
}

template <typename Range>
typename Range::const_iterator cmRemoveDuplicates(Range const& r)
{
  return cmRemoveDuplicates(r.begin(), r.end());
}

template <typename Range, typename T>
typename Range::const_iterator cmFindNot(Range const& r, T const& t)
{
  return std::find_if(r.begin(), r.end(), [&t](T const& i) { return i != t; });
}

Line	Count	Source
1		/* Distributed under the OSI-approved BSD 3-Clause License. See accompanying
2		file LICENSE.rst 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	0	{
22	0	typename std::iterator_traits<FwdIt>::difference_type const dist =
23	0	std::distance(middle, last);
24	0	std::rotate(first, middle, last);
25	0	std::advance(first, dist);
26	0	return first;
27	0	}
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	0	: m_range(r)
45	0	{
46	0	}
47
48		bool operator()(argument_type const& item) const
49	0	{
50	0	return std::binary_search(this->m_range.begin(), this->m_range.end(),
51	0	item);
52	0	}
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		auto const 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		auto cmRemoveMatching(Range& r, MatchRange const& m) -> decltype(r.begin())
99	0	{
100	0	return std::remove_if(r.begin(), r.end(),
101	0	ContainerAlgorithms::BinarySearcher<MatchRange>(m));
102	0	}
103
104		template <typename ForwardIterator>
105		ForwardIterator cmRemoveDuplicates(ForwardIterator first, ForwardIterator last)
106	0	{
107	0	using Value = typename std::iterator_traits<ForwardIterator>::value_type;
108	0	struct Hash
109	0	{
110	0	std::size_t operator()(ForwardIterator it) const
111	0	{
112	0	return std::hash<Value>{}(*it);
113	0	} Unexecuted instantiation: cmRemoveDuplicates<std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo> >(std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo>, std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo>)::Hash::operator()(std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo>) const Unexecuted instantiation: cmRemoveDuplicates<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >> >(std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >>, std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >>)::Hash::operator()(std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >>) const Unexecuted instantiation: cmRemoveDuplicates<std::__1::__wrap_iter<cmSourceFile> >(std::__1::__wrap_iter<cmSourceFile>, std::__1::__wrap_iter<cmSourceFile>)::Hash::operator()(std::__1::__wrap_iter<cmSourceFile>) const
114	0	};
115
116	0	struct Equal
117	0	{
118	0	bool operator()(ForwardIterator it1, ForwardIterator it2) const
119	0	{
120	0	return it1 == it2;
121	0	} Unexecuted instantiation: cmRemoveDuplicates<std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo> >(std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo>, std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo>)::Equal::operator()(std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo>, std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo>) const Unexecuted instantiation: cmRemoveDuplicates<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >> >(std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >>, std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >>)::Equal::operator()(std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >>, std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >>) const Unexecuted instantiation: cmRemoveDuplicates<std::__1::__wrap_iter<cmSourceFile> >(std::__1::__wrap_iter<cmSourceFile>, std::__1::__wrap_iter<cmSourceFile>)::Equal::operator()(std::__1::__wrap_iter<cmSourceFile>, std::__1::__wrap_iter<cmSourceFile**>) const
122	0	};
123	0	std::unordered_set<ForwardIterator, Hash, Equal> uniq;
124
125	0	ForwardIterator result = first;
126	0	while (first != last) {
127	0	if (!cm::contains(uniq, first)) {
128	0	if (result != first) {
129	0	result = std::move(first);
130	0	}
131	0	uniq.insert(result);
132	0	++result;
133	0	}
134	0	++first;
135	0	}
136	0	return result;
137	0	} Unexecuted instantiation: std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo> cmRemoveDuplicates<std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo> >(std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo>, std::__1::__wrap_iter<cmFindPackageCommand::ConfigFileInfo>) Unexecuted instantiation: std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >> cmRemoveDuplicates<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >> >(std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >>, std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >>) Unexecuted instantiation: std::__1::__wrap_iter<cmSourceFile> cmRemoveDuplicates<std::__1::__wrap_iter<cmSourceFile> >(std::__1::__wrap_iter<cmSourceFile>, std::__1::__wrap_iter<cmSourceFile>)
138
139		template <typename Range>
140		typename Range::iterator cmRemoveDuplicates(Range& r)
141	0	{
142	0	return cmRemoveDuplicates(r.begin(), r.end());
143	0	} Unexecuted instantiation: std::__1::vector<cmFindPackageCommand::ConfigFileInfo, std::__1::allocator<cmFindPackageCommand::ConfigFileInfo> >::iterator cmRemoveDuplicates<std::__1::vector<cmFindPackageCommand::ConfigFileInfo, std::__1::allocator<cmFindPackageCommand::ConfigFileInfo> > >(std::__1::vector<cmFindPackageCommand::ConfigFileInfo, std::__1::allocator<cmFindPackageCommand::ConfigFileInfo> >&) Unexecuted instantiation: cmList::iterator cmRemoveDuplicates<cmList>(cmList&) Unexecuted instantiation: std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > >::iterator cmRemoveDuplicates<std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >(std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > >&) Unexecuted instantiation: std::__1::vector<cmSourceFile, std::__1::allocator<cmSourceFile> >::iterator cmRemoveDuplicates<std::__1::vector<cmSourceFile, std::__1::allocator<cmSourceFile> > >(std::__1::vector<cmSourceFile, std::__1::allocator<cmSourceFile> >&)
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	0	{
154	0	return std::find_if(r.begin(), r.end(), [&t](T const& i) { return i != t; }); Unexecuted instantiation: cmFindNot<std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >(std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&)::{lambda(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&)#1}::operator()(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) const Unexecuted instantiation: cmFindNot<cmRange<std::__1::reverse_iterator<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const> > >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >(cmRange<std::__1::reverse_iterator<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const> > > const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&)::{lambda(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&)#1}::operator()(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) const
155	0	} Unexecuted instantiation: std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > >::const_iterator cmFindNot<std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >(std::__1::vector<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) Unexecuted instantiation: cmRange<std::__1::reverse_iterator<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const> > >::const_iterator cmFindNot<cmRange<std::__1::reverse_iterator<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const> > >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >(cmRange<std::__1::reverse_iterator<std::__1::__wrap_iter<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const*> > > const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&)

Coverage Report

Created: 2026-02-09 06:05