fork(1) download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <unordered_set>
  4. #include <cassert>
  5. #include <tuple>
  6.  
  7. struct Vector3
  8. {
  9.     float x, y, z;
  10.  
  11.     Vector3() {}
  12.  
  13.     Vector3(float xx, float yy, float zz)
  14.     {
  15.         x = xx, y = yy, z = zz;
  16.     }
  17.  
  18.     inline bool operator==(const Vector3& other) const
  19.     {
  20.         return x == other.x && y == other.y && z == other.z;
  21.     }
  22.  
  23.     inline bool operator<(const Vector3& other) const
  24.     {
  25.         return std::tie(x, y, z) < std::tie(other.x, other.y, other.z);
  26.     }
  27.  
  28.     friend std::ostream& operator<<(std::ostream& stream, const Vector3& vector);
  29. };
  30.  
  31. std::ostream& operator<<(std::ostream& stream, const Vector3& vector)
  32. {
  33.     return stream 
  34.         << "(" 
  35.         << std::setw(2) << std::setfill(' ') << vector.x << ", " 
  36.         << std::setw(2) << std::setfill(' ') << vector.y << ", " 
  37.         << std::setw(2) << std::setfill(' ') << vector.z 
  38.         << ")";
  39. }
  40.  
  41. struct Edge
  42. {
  43.     Vector3 EndPoints[2];
  44.  
  45.     Edge() {}
  46.  
  47.     Edge(Vector3 p, Vector3 q)
  48.     {
  49.         // swap order
  50.         if (q < p) { using std::swap; swap(p, q); } // the invariant
  51.         EndPoints[0] = p;
  52.         EndPoints[1] = q;
  53.     }
  54.  
  55.     inline bool operator==(const Edge& other) const {
  56.         return std::tie(EndPoints[0], EndPoints[1]) == std::tie(other.EndPoints[0], other.EndPoints[1]);
  57.     }
  58.  
  59.     friend std::ostream& operator<<(std::ostream& stream, const Edge& vector);
  60.     friend std::ostream& operator<<(std::ostream& stream, const Edge* vector);
  61. };
  62.  
  63. struct EdgePtrEqual {
  64.     bool operator()(Edge const* a, Edge const* b) const {
  65.         return *a == *b;
  66.     }
  67. };
  68.  
  69. std::ostream& operator<<(std::ostream& stream, const Edge& edge)
  70. {
  71.     return stream << edge.EndPoints[0] << " -- " << edge.EndPoints[1];
  72. }
  73.  
  74. std::ostream& operator<<(std::ostream& stream, const Edge* edge)
  75. {
  76.     return stream << edge->EndPoints[0] << " -- " << edge->EndPoints[1];
  77. }
  78.  
  79.  
  80. namespace std
  81. {
  82.     template <> struct hash<Edge>
  83.     {
  84.         std::size_t operator()(const Edge& edge) const {
  85.             Vector3 p0 = edge.EndPoints[0];
  86.             Vector3 p1 = edge.EndPoints[1];
  87.  
  88.             assert(p0 < p1); // the invariant
  89.  
  90.             auto hash_p = [](Vector3 const& p) { return (unsigned(p.x*73856093u) ^ unsigned(p.y*19349663u) ^ unsigned(p.z*83492791u)) % 1024u; };
  91.  
  92.             return hash_p(p0) ^ (hash_p(p1) << 3);
  93.         }
  94.     };
  95.  
  96.     template <> struct hash<Edge*> {
  97.         std::size_t operator()(const Edge* edge) const { 
  98.             return hash<Edge>()(*edge); 
  99.         }
  100.     };
  101. }
  102.  
  103. using EdgeSet    = std::unordered_set<Edge,  std::hash<Edge>>;
  104. using EdgePtrSet = std::unordered_set<Edge*, std::hash<Edge*>, EdgePtrEqual>;
  105.  
  106. void add_edge(EdgeSet& table, Edge edge)
  107. {
  108.     EdgeSet::const_iterator it = table.find(edge);
  109.     if (it == table.end()) table.insert(edge);
  110.     else std::cout << "Table already contains edge " << edge << std::endl;
  111. }
  112.  
  113. void add_edge(EdgePtrSet& table, Edge* edge)
  114. {
  115.     EdgePtrSet::const_iterator it = table.find(edge);
  116.     if (it == table.end()) table.insert(edge);
  117.     else std::cout << "Table already contains edge " << edge << std::endl;
  118. }
  119.  
  120.  
  121. void print_table(EdgeSet& table)
  122. {
  123.     std::cout << std::endl;
  124.     std::cout << "Table has " << table.size() << " elements:" << std::endl;
  125.  
  126.     for (auto it = table.begin(); it != table.end(); ++it)
  127.         std::cout << *it << std::endl;
  128.  
  129.     std::cout << std::endl;
  130. }
  131.  
  132. void print_table(EdgePtrSet& table)
  133. {
  134.     std::cout << std::endl;
  135.     std::cout << "Table has " << table.size() << " elements:" << std::endl;
  136.  
  137.     for (auto it = table.begin(); it != table.end(); ++it)
  138.         std::cout << *(*it) << std::endl;
  139.  
  140.     std::cout << std::endl;
  141. }
  142.  
  143.  
  144. int main()
  145. {
  146.     EdgeSet table;
  147.     EdgePtrSet ptable;
  148.  
  149.     Edge e0(Vector3( 1.f,  0.f,  0.f), Vector3(-1.f,  0.f,  0.f));
  150.     Edge e1(Vector3(-1.f,  0.f,  0.f), Vector3( 1.f,  0.f,  0.f));
  151.  
  152.     add_edge(table, e0);
  153.     add_edge(table, e1);
  154.  
  155.     print_table(table);
  156.  
  157.     add_edge(ptable, &e0);
  158.     add_edge(ptable, &e1);
  159.  
  160.     print_table(ptable);
  161.  
  162.     return 0;
  163. }
  164.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Table already contains edge (-1,  0,  0) -- ( 1,  0,  0)

Table has 1 elements:
(-1,  0,  0) -- ( 1,  0,  0)

Table already contains edge (-1,  0,  0) -- ( 1,  0,  0)

Table has 1 elements:
(-1,  0,  0) -- ( 1,  0,  0)
https://ideone.com/Yrp3ib
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!