import java.util.concurrent.atomic.AtomicReference;

public class spanning_tree_atomic
{
  public static void main(String[] args) 
  {
    int global_num_neighbors = 100;
    int num_nodes = 500;
    if(args.length > 0) num_nodes = Integer.parseInt(args[0]);
    if(args.length > 1) global_num_neighbors = Integer.parseInt(args[1]);
    if(num_nodes < 2)
    {
      System.out.println("Error: number of nodes must be > 1");
      return;
    }
    if(global_num_neighbors < -1) 
    {
      System.out.println("Error: negative number of neighbors entered\n");
      return;
    }
    
    java.util.Random rand  = new java.util.Random(12399);
    Node[] nodes = new Node[num_nodes];
    for(int i = 0; i < nodes.length; i++) 
    {
      nodes[i] = new Node(Integer.toString(i));
    }
    for(int i = 0; i < nodes.length; i++)
    {
      int num_neighbors = ( (global_num_neighbors == -1) ? rand.nextInt(10) : global_num_neighbors);
      Node[] neighbors = new Node[num_neighbors];
      for(int j = 0; j < neighbors.length; j++)
      {
        int neighbor_index = rand.nextInt(nodes.length);
        if(neighbor_index == i) neighbor_index = (neighbor_index + 1) % num_nodes;
        neighbors[j] = nodes[neighbor_index];
      }
      nodes[i].SetNeighbors(neighbors);
    }
     
    for(int run_no = 0; run_no < 5; run_no++) {
      for(int i = 0; i < nodes.length; i++) nodes[i].parent.set(null);
      final Node root = nodes[0];
      root.parent.set(root);
      long start = System.currentTimeMillis();
      root.compute(0);
      long stop = System.currentTimeMillis();
      System.out.println("Time: "+(stop-start)+" ms");
    }
  }
}

class Node
{
  Node[] neighbors;
  public AtomicReference<Node> parent;
  String name;
  
  public Node(String set_name)
  {
    neighbors = new Node[0];
    name = set_name;
    parent = new AtomicReference<Node>(null);
  }
  
  public void SetNeighbors(Node[] n)
  {
    neighbors = n;
  }
  boolean tryLabeling(Node n)
  {
    return parent.compareAndSet(null, n);
  }
  void compute(final int depth)
  {
    Thread[] threads = new Thread[neighbors.length];
    for(int i = 0; i  < neighbors.length; i++) {
      final int final_i = i;
      final Node self = this;
      if (depth < 2) {
        threads[i] = new Thread(new Runnable() {
  	public void run() {
	  Node child = neighbors[final_i];
  	  if(child.tryLabeling(self))
  	  { 
  	    child.compute(depth + 1); 
	  }
	}
        });
        threads[i].start();
      } else {
        Node child = neighbors[final_i];
        if (child.tryLabeling(self)) child.compute(depth + 1);
      }
    }
    
    for (int i = 0; i < neighbors.length; i++) {
      try {
        if (threads[i] != null) threads[i].join();
      } catch (InterruptedException e) {
        System.out.println("InterruptedException thrown.");
      }
    }
  }
}