#include <cstddef>
#include <list>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>

typedef std::size_t entity_id_t;
typedef long entity_pos_t;
typedef std::size_t entity_length_t;

struct Entity {
  entity_id_t id;
  entity_pos_t pos;
  entity_length_t length;
};

typedef std::pair<entity_id_t, entity_id_t> collision_t;

template<class EntityContainer>
std::list<collision_t> collision_check(const EntityContainer& entities) {
  struct Boundary {
    entity_id_t id;
    entity_pos_t pos;
    enum {
      StartBound,
      EndBound
    } type;
  };
  
  const std::size_t n = entities.size();
  std::vector<Boundary> boundaries(2 * n);
  {
    std::size_t i = 0;
    for(const Entity cur : entities) {
      boundaries[i] = {cur.id, cur.pos, Boundary::StartBound};
      boundaries[++i] = {cur.id, entity_pos_t(cur.pos + cur.length),
                         Boundary::EndBound};
      ++i;
    }
  }
  std::sort(boundaries.begin(), boundaries.end(),
            [](Boundary fst, Boundary snd) {
    return fst.pos < snd.pos ||
           (fst.pos == snd.pos && fst.type == Boundary::EndBound &&
            snd.type == Boundary::StartBound);
  });
  std::set<entity_id_t> unclosed;
  std::list<collision_t> collisions;
  for(const Boundary bound : boundaries) {
    if(bound.type == Boundary::StartBound) {
      for(const entity_id_t id : unclosed)
        collisions.push_back({id, bound.id});
      unclosed.insert(bound.id);
    }
    else
      unclosed.erase(bound.id);
  }
  return collisions;
}

int main() {
  /* entity 0: ....____
   * entity 1: ..___...
   * entity 2: __......
   * entity 3: .__.....
   */
  std::vector<Entity> entities({{0, 4, 4}, {1, 2, 3}, {2, 0, 2}, {3, 1, 2}});
  const auto collisions = collision_check(entities);
  for(collision_t cur : collisions)
    std::cout << "entities " << cur.first << " and " << cur.second
              << " collide\n";
}