fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. // --- GEOMETRIC STRUCTURES ---
  6.  
  7. class Rectangle {
  8. 	public:
  9.     int id;
  10.     double minX, minY, maxX, maxY;
  11.  
  12.     // The core geometric relation check
  13.     bool intersects(const Rectangle& other) const {
  14.         return !(minX > other.maxX || maxX < other.minX || 
  15.                  minY > other.maxY || maxY < other.minY);
  16.     }
  17. };
  18.  
  19. // --- PROVIDED TREE LIBRARY (Simulated with Vector) ---
  20.  
  21. class GeoTree {
  22. private:
  23.     // Internal storage simulating the Tree's dataset
  24.     vector<Rectangle> treeData;
  25.  
  26. public:
  27.     /**
  28.      * Requirement: Add operation takes O(log n) in a real tree.
  29.      * Here we use push_back for the simulation.
  30.      */
  31.     void addRectangle(int id, Rectangle r) {
  32.         r.id = id;
  33.         treeData.push_back(r);
  34.     }
  35.  
  36.     /**
  37.      * Requirement: Query operation takes O(log n) in a real tree.
  38.      * In a real library, this would only visit branches that overlap with q.
  39.      */
  40.     vector<int> queryRectangle(Rectangle q) {
  41.         vector<int> results;
  42.         for (const auto& rect : treeData) {
  43.             if (rect.intersects(q)) {
  44.                 results.push_back(rect.id);
  45.             }
  46.         }
  47.         return results;
  48.     }
  49. };
  50.  
  51. class ComplexPolygon
  52. {
  53. 	public:
  54. 	int id;
  55. 	Rectangle bBox;
  56. 	vector<pair<int,int>> vertices;
  57. };
  58.  
  59. bool performPreciseIntersection(const ComplexPolygon& polyA, const ComplexPolygon& polyB) {
  60.     // Simulation: returning true for precise intersection
  61.     return true; 
  62. }
  63.  
  64. void mapCase1 (vector<Rectangle> uscities,vector<Rectangle> largeTableBPartition)
  65. {
  66. 	GeoTree geotree;
  67. 	for(auto city :uscities )
  68. 	{
  69. 		geotree.addRectangle(city.id,city);
  70. 	}
  71.  
  72. 	for(auto trip :largeTableBPartition )
  73. 	{
  74. 		vector<int> visitedCities = 	geotree.queryRectangle(trip);
  75. 		for(auto city : visitedCities )
  76. 		{
  77. 			cout<<"Intersecting cities for trip :"<<trip.id<<" are :" <<city<<"\n";
  78. 		}
  79.  
  80. 	}
  81. }
  82. //Case 2:
  83. vector<pair<int, int>> runFilterJob( vector<Rectangle>& broadcastBBoxesA, 
  84.                                      vector<ComplexPolygon>& partitionB) {
  85.     GeoTree geotree;
  86.  
  87.     // Build the tree using only Bounding Boxes to stay within memory limits
  88.     for( auto box : broadcastBBoxesA) {
  89.         geotree.addRectangle(box.id, box);
  90.     }
  91.  
  92.  
  93.  
  94.     vector<pair<int, int>> candidates;
  95.     for( auto polyB : partitionB) {
  96.         // Fast search in the tree
  97.         vector<int> matches = geotree.queryRectangle(polyB.bBox);
  98.         for(int idA : matches) {
  99.             candidates.push_back({idA, polyB.id});
  100.         }
  101.     }
  102.     return candidates;
  103. }
  104. //CASe 2
  105. /**
  106.  * JOB 2: REFINEMENT
  107.  * This version only loads objects into memory if they are in the candidate list.
  108.  */
  109. void runRefineJob(vector<pair<int, int>> candidates, 
  110.                   vector<ComplexPolygon> tableA_Storage, 
  111.                   vector<ComplexPolygon> tableB_Storage) {
  112.  
  113.     // 1. Identify which IDs we actually need to load (The Filtered Set)
  114.     unordered_set<int> requiredA;
  115.     unordered_set<int> requiredB;
  116.     for (auto pair : candidates) {
  117.         requiredA.insert(pair.first);
  118.         requiredB.insert(pair.second);
  119.     }
  120.  
  121.     // 2. Load ONLY the required heavy objects into our maps
  122.     // In a real system, this is the "Shuffle" where only specific rows move over the network.
  123.     unordered_map<int, ComplexPolygon> mapA;
  124.     unordered_map<int, ComplexPolygon> mapB;
  125.  
  126.     for (auto a : tableA_Storage) {
  127.         if (requiredA.count(a.id)) mapA[a.id] = a;
  128.     }
  129.     for (auto b : tableB_Storage) {
  130.         if (requiredB.count(b.id)) mapB[b.id] = b;
  131.     }
  132.  
  133.  
  134.  
  135.     cout << "\n--- Starting Refine Job (Candidate-Only Memory) ---" << endl;
  136.     cout << "Memory Usage: Loaded " << mapA.size() << " objects from A instead of " << tableA_Storage.size() << endl;
  137.  
  138.     // 3. Perform the heavy math only on the filtered candidates
  139.     for (auto pair : candidates) {
  140.         // Double check existence in map (safety)
  141.         if (mapA.count(pair.first) && mapB.count(pair.second)) {
  142.             if (performPreciseIntersection(mapA[pair.first], mapB[pair.second])) {
  143.                 cout << ">>> CONFIRMED: City " << pair.first << " intersects Trip " << pair.second << endl;
  144.             }
  145.         }
  146.     }
  147. }
  148. int main() {
  149.     // TABLE A: Small Table (e.g., US City Boundaries)
  150.     vector<Rectangle> cities1 = {
  151.         {1, 0.0, 0.0, 5.0, 5.0},   
  152.         {2, 10.0, 10.0, 15.0, 15.0} 
  153.     };
  154.  
  155.     // TABLE B: Large Table Partition (e.g., Uber Trips on local node)
  156.     vector<Rectangle> trips1 = {
  157.         {101, 2.0, 2.0, 3.0, 3.0},   
  158.         {102, 4.0, 4.0, 6.0, 6.0},   
  159.         {103, 12.0, 12.0, 18.0, 18.0}, 
  160.         {104, 20.0, 20.0, 25.0, 25.0}  
  161.     };
  162.  
  163.     mapCase1(cities1, trips1);
  164.     vector<ComplexPolygon> cities = {
  165.         {1, {1, 0.0, 0.0, 5.0, 5.0}, {{0.0, 0.0}, {5.0, 5.0}}}, 
  166.         {2, {2, 10.0, 10.0, 15.0, 15.0}, {{10.0, 10.0}, {15.0, 15.0}}}
  167.     };
  168.  
  169.     // TABLE B: Large Partition of complex objects
  170.     vector<ComplexPolygon> trips = {
  171.         {101, {101, 2.0, 2.0, 3.0, 3.0}, {{2.0, 2.0}, {3.0, 3.0}}},
  172.         {102, {102, 12.0, 12.0, 14.0, 14.0}, {{12.0, 12.0}, {14.0, 14.0}}}
  173.     };
  174.  
  175.     // 1. EXECUTE FILTER JOB
  176.     // Extracting just the Bounding Boxes to broadcast them to mappers
  177.     vector<Rectangle> bboxes;
  178.     for (auto c : cities) bboxes.push_back(c.bBox);
  179.  
  180.     vector<pair<int, int>> candidates = runFilterJob(bboxes, trips);
  181.  
  182.  
  183.  
  184.     // 2. EXECUTE REFINE JOB
  185.     // Perform heavy math only on candidate pairs
  186.     runRefineJob(candidates, cities, trips);
  187.  
  188.     return 0;
  189. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Intersecting cities for trip :101 are :1
Intersecting cities for trip :102 are :1
Intersecting cities for trip :103 are :2

--- Starting Refine Job (Candidate-Only Memory) ---
Memory Usage: Loaded 2 objects from A instead of 2
>>> CONFIRMED: City 1 intersects Trip 101
>>> CONFIRMED: City 2 intersects Trip 102
https://ideone.com/egkRFU
language:
C++ (gcc 8.3)
created:
21 hours 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!