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 
11 /** Checks for the existence of a non-empty intersection between two sorted
12 `std::vector`'s.
13 
14 @param[in] a First vector.
15 @param[in] b Second vector.
16 @tparam T The type of the elements in the input vectors @p a and @p b. This is
17 expected to be an integral type or a pointer type.
18 @returns `true` if there is a non-empty intersection between vectors;
19 `false` otherwise.
20 
21 Elements are compared using `operator<` and the vectors must be sorted with
22 respect to the same operator.
23 
24 This algorithm only works on `std::vector`'s to take advantage of their fast
25 and random access.
26 
27 Entries can be repeated as long as they are sorted. For vector `a` of size `Na`
28 and vector `b` of size `Nb` the complexity is at most Order(Na + Nb).
29 The algorithm executes in constant time for vectors with disjoint entries.
30 An example of the worst case scenario is given below:
31 @verbatim
32  a = (10, 20, 30)
33  b = (15, 25, 35)
34 @endverbatim
35 
36 In this case the algorithm needs to scan both vectors from start to end. **/
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
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:37
int value
Definition: copyable_unique_ptr_test.cc:61
Provides Drake&#39;s assertion implementation.