intersection.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_INTERSECTION_HXX
21 #define MODULE_COMBINATORY_INTERSECTION_HXX
22 
23 // STD includes
24 #include <set>
25 
26 namespace huc
27 {
28  namespace combinatory
29  {
41  template <typename Container, typename IT>
42  Container Intersection(const IT& beginFirst, const IT& endFirst,
43  const IT& beginSecond, const IT& endSecond)
44  {
45  // Take the smallest sequence for initial count
46  const auto kFirstSize = std::distance(beginFirst, endFirst);
47  const auto kSecondSize = std::distance(beginSecond, endSecond);
48  const bool kIsFirstSmaller = (kFirstSize <= kSecondSize);
49 
50  // Create and set enough capacity for the intersection
51  Container intersection;
52  intersection.reserve((kIsFirstSmaller) ? kFirstSize : kSecondSize);
53 
54  // Count each element of the smaller array
55  std::multiset<typename std::iterator_traits<IT>::value_type> count;
56  const auto kCountEndIt = (kIsFirstSmaller) ? endFirst : endSecond;
57  for (auto it = (kIsFirstSmaller) ? beginFirst : beginSecond; it != kCountEndIt; ++it)
58  count.insert(*it);
59 
60  // Push the element if find into the multiset and delete its instance from the counter
61  auto kIntersectEndIt = (kIsFirstSmaller) ? endSecond : endFirst;
62  for (auto it = (kIsFirstSmaller) ? beginSecond : beginFirst; it != kIntersectEndIt; ++it)
63  {
64  // Move element from count to intersection if found
65  auto foundIt = count.find(*it);
66  if (foundIt != count.end())
67  {
68  intersection.push_back(*it);
69  count.erase(foundIt);
70  }
71  }
72 
73  return intersection;
74  }
75  }
76 }
77 
78 #endif // MODULE_COMBINATORY_INTERSECTION_HXX
Container Intersection(const IT &beginFirst, const IT &endFirst, const IT &beginSecond, const IT &endSecond)