// 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);
}