// Problem_2.__Social_Network.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <set>
#include <queue>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdlib.h>

struct Node {
    char id;
    std::vector<Node*> children;
};

std::set<Node*> friends;
std::set<Node*> adversaries;
std::queue<Node*> nodeQueue;

void printFSet(Node* n) {
    std::cout << "Friends: " << n->id << "\n";
}

void printASet(Node* n) {
    std::cout << "Adversaries: " << n->id << "\n";
}


void eachNode(Node* child) {
    if (friends.find(child) == friends.end() || adversaries.find(child) == adversaries.end()) {
        nodeQueue.push(child);
    }
}

//Node randomTree(int layers, int maxChildren) {
//  Node root;
//  Node lastRoot;
//
//  std::list<std::list<Node>> roots;
//
//  for (int i = 0; i < layers; i++)
//  {
//      std::list<Node> layerNodes;
//      roots.push_back(layerNodes);
//
//      int children = rand() % maxChildren;
//
//      for (int y = 0; y < children; y++)
//      {
//          Node child;
//          layerNodes.push_back(child);
//          lastRoot.children.push_back(child);
//      }
//
//      //lastRoot = subtree_root;
//  }
//}


void breadthFirst(Node* g) {
    int level = 0;

    // Initialize
    nodeQueue.push(g);

    // For each node on the current level expand and process, if no children
    // (leaf) then unwind
    while (!nodeQueue.empty())
    {
        Node* subtree_root = nodeQueue.front();
        nodeQueue.pop();

        for (Node* n : subtree_root->children) {
            eachNode(n);
        }
        // std::for_each(subtree_root->children.front(), subtree_root->children.back(), eachNode);

        if (level % 2 == 0) {
            friends.insert(subtree_root);
        }
        else
        {
            adversaries.insert(subtree_root);
        }

        level++;
    }
}

int main()
{
    Node* root = new Node();
    root->id = '0';
    Node n1;
    n1.id = '1';
    Node n2;
    n2.id = '2';
    Node n3;
    n3.id = '3';
    Node n4;
    n4.id = '4';
    Node n5;
    n5.id = '5';
    Node n6;
    n6.id = '6';
    Node n7;
    n7.id = '7';
    Node n8;
    n8.id = '8';
    Node n9;
    n9.id = '9';

    root->children.push_back(&n1);
    root->children.push_back(&n2);
    n1.children.push_back(&n3);
    n1.children.push_back(&n4);
    n2.children.push_back(&n5);
    n3.children.push_back(&n6);
    n6.children.push_back(&n7);
    n4.children.push_back(&n8);
    n7.children.push_back(&n9);

    breadthFirst(root);

    std::for_each(friends.begin(), friends.end(), printFSet);
    std::for_each(adversaries.begin(), adversaries.end(), printASet);
}