Drake
sorted_vectors_have_intersection.h
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 #include <type_traits>
5 #include <vector>
6 
8 
9 namespace drake {
10 
37 template <typename T>
38 bool SortedVectorsHaveIntersection(const std::vector<T>& a,
39  const std::vector<T>& b) {
40  // Asserts that T is either an integral type or a pointer type.
42  "Input vectors must hold integral types or pointers.");
43 
44  // Checks the precondition that the lists are sorted, only in debug builds.
45  // This means O(n) performance in Debug builds but it could also catch some
46  // very obscure errors.
47  DRAKE_ASSERT(std::is_sorted(a.cbegin(), a.cend()) &&
48  std::is_sorted(b.cbegin(), b.cend()));
49 
50  typename std::vector<T>::const_iterator ai = a.begin();
51  typename std::vector<T>::const_iterator bi = b.begin();
52 
53  // Quick checks first:
54  // Check if either of the ranges is empty:
55  if (ai == a.end() || bi == b.end()) return false;
56 
57  // Check for non-overlapping ranges:
58  if (a.front() > b.back() || b.front() > a.back()) return false;
59 
60  // Non-empty ranges with elements that overlap.
61  while (true) {
62  // Increments the range with the smaller first element.
63  if (*ai < *bi) {
64  if (++ai == a.end()) break;
65  } else if (*bi < *ai) {
66  if (++bi == b.end()) break;
67  } else {
68  // Found matching element.
69  return true;
70  }
71  }
72  // One of the ranges ran out of elements before a match was found.
73  return false;
74 }
75 
76 } // namespace drake
Definition: automotive_demo.cc:88
int b
Definition: rgbd_camera.cc:91
bool SortedVectorsHaveIntersection(const std::vector< T > &a, const std::vector< T > &b)
Checks for the existence of a non-empty intersection between two sorted std::vector&#39;s.
Definition: sorted_vectors_have_intersection.h:38
#define DRAKE_ASSERT(condition)
DRAKE_ASSERT(condition) is similar to the built-in assert(condition) from the C++ system header <cas...
Definition: drake_assert.h:39
int value
Definition: copyable_unique_ptr_test.cc:61
Provides Drake&#39;s assertion implementation.