fork(1) download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <set>
  4. #include <tuple>
  5. #include <vector>
  6.  
  7. struct Interval
  8. {
  9.     double start;
  10.     double end;
  11. };
  12.  
  13. //-----------------------------------------------------------------------------
  14. // Enum to qualify event: Start/End of "segment-line"
  15. enum class EIntervalState
  16. {
  17.     Start,
  18.     End
  19. };
  20.  
  21. //-----------------------------------------------------------------------------
  22. // Events used for collision detection
  23. struct Event
  24. {
  25.     double pos;
  26.     EIntervalState state;
  27.     std::size_t id;
  28. };
  29.  
  30. //-----------------------------------------------------------------------------
  31. // Comparator to use if {1, 2} and {2, 3} should overlap
  32. class LessIncludeLimit
  33. {
  34. public:
  35.     bool operator()(const Event& lhs, const Event& rhs) const
  36.     {
  37.         return std::tie(lhs.pos, lhs.state) < std::tie(rhs.pos, rhs.state);
  38.     }
  39. };
  40.  
  41. //-----------------------------------------------------------------------------
  42. // Comparator to use if {1, 2} and {2, 3} should not overlap
  43. class LessExcludeLimit
  44. {
  45. public:
  46.     bool operator()(const Event& lhs, const Event& rhs) const
  47.     {
  48.         return std::tie(lhs.pos, rhs.state) < std::tie(rhs.pos, lhs.state);
  49.     }
  50. };
  51.  
  52. //-----------------------------------------------------------------------------
  53. std::vector<Event> MakeEvents(const std::vector<Interval>& intervals)
  54. {
  55.     std::vector<Event> res;
  56.     std::size_t id = 0;
  57.     for (const auto& interval : intervals)
  58.     {
  59.         res.push_back({interval.start, EIntervalState::Start, id});
  60.         res.push_back({interval.end, EIntervalState::End, id});
  61.         ++id;
  62.     }
  63.     return res;
  64. }
  65.  
  66. //-----------------------------------------------------------------------------
  67. template <typename Less>
  68. std::vector<std::pair<std::size_t, std::size_t>>
  69. ComputeOverlappingIntervals(std::vector<Event>&& events, Less less)
  70. {
  71.     std::sort(events.begin(), events.end(), less);
  72.  
  73.     std::set<std::size_t> activeIds;
  74.     std::vector<std::pair<std::size_t, std::size_t>> res;
  75.  
  76.     for (const auto& event : events)
  77.     {
  78.         switch (event.state)
  79.         {
  80.             case EIntervalState::Start:
  81.             {
  82.                 for (const auto& id : activeIds)
  83.                 {
  84.                     res.emplace_back(std::minmax(event.id, id));
  85.                 }
  86.                 activeIds.emplace(event.id);
  87.                 break;
  88.             }
  89.             case EIntervalState::End:
  90.             {
  91.                 activeIds.erase(event.id);
  92.                 break;
  93.             }
  94.         }
  95.     }
  96.     return res;
  97. }
  98.  
  99. //-----------------------------------------------------------------------------
  100. int main()
  101. {
  102.     const std::vector<Interval> intervals = {
  103.         {1, 3},
  104.                        {12, 14},
  105.           {2, 4},
  106.                           {13, 15},
  107.                  {5, 10}
  108.     };
  109.  
  110.     for (const auto& p : ComputeOverlappingIntervals(MakeEvents(intervals), LessExcludeLimit{})) {
  111.        std::cout << "intervals " << p.first << " and " << p.second << " overlap\n";
  112.     }
  113.  
  114. }
  115.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin 
Standard input is empty
stdout 
intervals 0 and 2 overlap
intervals 1 and 3 overlap
https://ideone.com/ZZruOr
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!