is_interleaved.hxx
Go to the documentation of this file.
1 /*===========================================================================================================
2  *
3  * HUC - Hurna Core
4  *
5  * Copyright (c) Michael Jeulin-Lagarrigue
6  *
7  * Licensed under the MIT License, you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * https://github.com/Hurna/Hurna-Core/blob/master/LICENSE
11  *
12  * Unless required by applicable law or agreed to in writing, software distributed under the License is
13  * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and limitations under the License.
15  *
16  * The above copyright notice and this permission notice shall be included in all copies or
17  * substantial portions of the Software.
18  *
19  *=========================================================================================================*/
20 #ifndef MODULE_COMBINATORY_IS_INTERLEAVED_HXX
21 #define MODULE_COMBINATORY_IS_INTERLEAVED_HXX
22 
23 // STD includes
24 #include <map>
25 
26 namespace huc
27 {
28  namespace combinatory
29  {
39  template <typename IT>
40  bool IsInterleaved(const IT& beginFirst, const IT& endFirst,
41  const IT& beginSecond, const IT& endSecond,
42  const IT& beginFull, const IT& endFull)
43  {
44  // Lambda that count each element occurence within the map "count"
45  std::map<typename std::iterator_traits<IT>::value_type, int> count;
46  auto lCountElement = [&count](typename std::iterator_traits<IT>::value_type(val))
47  {
48  auto countIt = count.find(val);
49  if (countIt != count.end())
50  ++countIt->second;
51  else
52  count.emplace(val, 1);
53  };
54 
55  // Count both sequences
56  std::for_each(beginFirst, endFirst, lCountElement);
57  std::for_each(beginSecond, endSecond, lCountElement);
58 
59  // Decrease the count of each element given the full sequence
60  for (auto it = beginFull; it != endFull; ++it)
61  {
62  auto countIt = count.find(*it);
63  if (countIt == count.end())
64  return false;
65  if (--countIt->second < 0)
66  return false;
67  }
68 
69  // Fail if hte count is not equal to 0
70  for (auto it = count.begin(); it != count.end(); ++it)
71  if (it->second != 0)
72  return false;
73 
74  return true;
75  }
76  }
77 }
78 
79 #endif // MODULE_COMBINATORY_IS_INTERLEAVED_HXX
bool IsInterleaved(const IT &beginFirst, const IT &endFirst, const IT &beginSecond, const IT &endSecond, const IT &beginFull, const IT &endFull)