fork(1) download
copy 
  1. #include <algorithm>
  2. #include <iomanip>
  3. #include <iostream>
  4. #include <memory>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. class Counter {
  9.     public:
  10.         Counter()  { ++count_; }
  11.         ~Counter() { --count_; }
  12.         static int count() { return count_; }
  13.     private:
  14.         static int count_;
  15. };
  16.  
  17. int Counter::count_ = 0;
  18.  
  19. /// Modified code starts here
  20. //
  21. class MyGraph {
  22.     public:
  23.         class Node : public Counter {
  24.             vector<shared_ptr<Node>> children;
  25.             vector<weak_ptr<Node>> others;
  26.             MyGraph * graph;
  27.             bool hasParent;
  28.             friend class MyGraph;
  29.  
  30.             void setGraph(MyGraph * g) {
  31.                 if (graph)
  32.                     return;
  33.                 graph = g;
  34.             }
  35.  
  36.             public:
  37.             Node() : graph(nullptr), hasParent(false) {}
  38.             void AddChild(const shared_ptr<Node>& node) {
  39.                 if(node->hasParent) {
  40.                     others.push_back(node);
  41.                 } else {
  42.                     node->hasParent = true;
  43.                     children.push_back(node);
  44.                 }
  45.                 node->setGraph(graph);
  46.             }
  47.  
  48.  
  49.             void RemoveChild(const shared_ptr<Node>& node) {
  50.                 auto it = std::find(children.begin(), children.end(), node);
  51.                 if(it == children.end()) {
  52.                     others.erase(std::remove_if(others.begin(), others.end(), [&node](weak_ptr<Node> & w) {
  53.                             if(auto n = w.lock()) {
  54.                                 return n == node;
  55.                             }
  56.                             return true;
  57.                     }));
  58.                 } else {
  59.                     children.erase(it);
  60.                     graph->Remove(node);
  61.                     node->hasParent = false;
  62.                 }
  63.             }
  64.         };
  65.  
  66.         void SetRoot(const shared_ptr<Node>& node) {
  67.             root = node;
  68.             node->setGraph(this);
  69.         }
  70.  
  71.         void Remove(const shared_ptr<Node>& node) {
  72.             garbage.push_back(node);
  73.         }
  74.  
  75.         void ShrinkToFit() {
  76.             // prevent stack overflow by queing the nodes
  77.             for(auto i = 0; i < garbage.size(); i++) {
  78.                 garbage.insert(garbage.end(), garbage[i]->children.begin(), garbage[i]->children.end());
  79.                 garbage[i]->children.clear();
  80.             }
  81.             garbage.clear();
  82.         }
  83.  
  84.         ~MyGraph() {
  85.             ShrinkToFit();
  86.         }
  87.  
  88.         static shared_ptr<MyGraph::Node> MakeNode() { 
  89.             return make_shared<MyGraph::Node>(); 
  90.         }
  91.  
  92.     private:
  93.         shared_ptr<Node> root;
  94.         vector<shared_ptr<Node>> garbage;
  95. };
  96.  
  97. /// End modified code
  98. bool TestCase1() {
  99.     MyGraph g;
  100.     {
  101.         auto a = MyGraph::MakeNode();
  102.         g.SetRoot(a);
  103.         auto b = MyGraph::MakeNode();
  104.         a->AddChild(b);
  105.         auto c = MyGraph::MakeNode();
  106.         b->AddChild(c);
  107.         a->RemoveChild(b);
  108.     }
  109.     g.ShrinkToFit();
  110.     return Counter::count() == 1;
  111. }
  112.  
  113. bool TestCase2() {
  114.     MyGraph g;
  115.     {
  116.         auto a = MyGraph::MakeNode();
  117.         g.SetRoot(a);
  118.         auto b = MyGraph::MakeNode();
  119.         a->AddChild(b);
  120.         auto c = MyGraph::MakeNode();
  121.         b->AddChild(c);
  122.         auto d = MyGraph::MakeNode();
  123.         b->AddChild(d);
  124.         d->AddChild(b);
  125.         a->RemoveChild(b);
  126.     }
  127.     g.ShrinkToFit();
  128.     return Counter::count() == 1;
  129. }
  130.  
  131. bool TestCase3() {
  132.     MyGraph g;
  133.     {
  134.         auto a = MyGraph::MakeNode();
  135.         g.SetRoot(a);
  136.         auto b = MyGraph::MakeNode();
  137.         a->AddChild(b);
  138.         auto c = MyGraph::MakeNode();
  139.         b->AddChild(c);
  140.         auto d = MyGraph::MakeNode();
  141.         b->AddChild(d);
  142.         d->AddChild(b);
  143.     }
  144.     g.ShrinkToFit();
  145.     return Counter::count() == 4;
  146. }
  147.  
  148.  
  149. bool TestCase4() { // New test case
  150.     MyGraph g;
  151.     {
  152.         auto a = MyGraph::MakeNode();
  153.         g.SetRoot(a);
  154.         auto b = MyGraph::MakeNode();
  155.         a->AddChild(b);
  156.         auto c = MyGraph::MakeNode();
  157.         b->AddChild(c);
  158.         auto d = MyGraph::MakeNode();
  159.         b->AddChild(d);
  160.         d->AddChild(b);
  161.         d->RemoveChild(b);
  162.     }
  163.     g.ShrinkToFit();
  164.     return Counter::count() == 4;
  165. }
  166.  
  167. bool TestCase5() { 
  168.     MyGraph g;
  169.     {
  170.         auto a = MyGraph::MakeNode();
  171.         g.SetRoot(a);
  172.         auto b = MyGraph::MakeNode();
  173.         a->AddChild(b);
  174.         auto c = MyGraph::MakeNode();
  175.         a->AddChild(c);
  176.         b->AddChild(c);
  177.         c->AddChild(b);
  178.         b->RemoveChild(c);
  179.         a->RemoveChild(b);
  180.     }
  181.     g.ShrinkToFit();
  182.     return Counter::count() == 2;
  183. }
  184.  
  185. int main() {
  186.     cout.setf(ios::boolalpha);
  187.     bool passed1 = TestCase1();
  188.     cout << passed1 << endl;
  189.     bool passed2 = TestCase2();
  190.     cout << passed2 << endl;
  191.     bool passed3 = TestCase3();
  192.     cout << passed3 << endl;
  193.  
  194.     bool passed4 = TestCase4();
  195.     cout << passed4 << endl;
  196.  
  197.     bool passed5 = TestCase5();
  198.     cout << passed5 << endl;
  199.     return 0;
  200. }
  201.  
Success #stdin #stdout 0s 3496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
true
true
true
true
https://ideone.com/ROcgcz
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!