/*				                                          tab:8
 *
 *
 * 
 * "Copyright (c) 1994 The Regents of the University of California.
 * All rights reserved.
 * 
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose, without fee, and without written agreement is
 * hereby granted, provided that the above copyright notice and the following
 * two paragraphs appear in all copies of this software.
 * 
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
 *
 * Author:		Arvind
 * Version:		144
 * Creation Date:	Wed May 11 16:36:54 PDT 1994
 * Filename:		local.sc
 * History:
 */

#include <stdio.h>
#include <split-c/split-c.h>
#include "connect.h"

/* Use local NULL for unvisited marker--can't we just set local part? */
#define	    MARK_UNVISITED(x)		(x)->parent = NULL
#define	    MARK_VISITED(x, p)		(x)->parent = p
#define	    VISITEDP(x)			(tolocal ((x)->parent) != NULL)

/* returns the number of vertices in the component */
inline int
dfs (node_t* root)
{
    node_t* head;
    node_t* next = NULL;
    edge_t* edge;
    unsigned mp = MYPROC;
    int num = 1;

    MARK_VISITED (root, toglobal (mp, root));
    root->queue = NULL;
    edge = tolocal (root->edges);
    root->edges = NULL;		/* No need to remove edge lists from nodes
				   other than those in the local component
				   list. */
    while (edge != NULL) {
	if (toproc (edge->node) == mp) {
	    node_t* child = tolocal (edge->node);

	    if (!VISITEDP (child)) {
		MARK_VISITED (child, toglobal (mp, root));
		child->queue = next;
		next = child;
	    }
	    edge = tolocal (edge->next);
	} else {
	    edge_t* next_edge = tolocal (edge->next);

	    edge->next = root->edges;
	    root->edges = toglobal (mp, edge);
	    edge = next_edge;
	}
    }
    for (head = next; head != NULL; head = next, num++) {
	next = head->queue;
	edge = tolocal (head->edges);
	while (edge != NULL) {
	    if (toproc (edge->node) == mp) {
		node_t* child = tolocal (edge->node);

		if (!VISITEDP (child)) {
		    MARK_VISITED (child, toglobal (mp, root));
		    child->queue = next;
		    next = child;
		}
		edge = tolocal (edge->next);
	    } else {
		edge_t* next_edge = tolocal (edge->next);

		edge->next = root->edges;
		root->edges = toglobal (mp, edge);
		edge = next_edge;
	    }
	}
    }
    return num;
}

node_t* 
all_local_dfs (int num_nodes, node_t* nodes)
{
    node_t* stop = nodes + num_nodes;
    node_t* cur_node;
    node_t* conn_list = NULL;

    for (cur_node = nodes; cur_node != stop; cur_node++) {
	MARK_UNVISITED (cur_node);
	cur_node->stagnant = 1;
    }

    for (cur_node = nodes; cur_node != stop; cur_node++) {
	if (!VISITEDP (cur_node)) {
	    dfs (cur_node);
	    cur_node->queue = conn_list;
	    conn_list = cur_node;
	}
    }
    barrier();
    return conn_list;
}

static int n_comp;
node_t *max_comp;

node_t* 
all_local_dfs_global (int num_nodes, node_t* nodes)
{
    node_t* stop = nodes + num_nodes;
    node_t* cur_node;
    node_t* conn_list = NULL;
    int num;
    int max_size = 0;
    unsigned mp = MYPROC;
    
    for (cur_node = nodes; cur_node != stop; cur_node++)
	MARK_UNVISITED (cur_node);

    for (cur_node = nodes, num = 1; cur_node != stop; cur_node++) {
	cur_node->stagnant = 1;
	if (!VISITEDP (cur_node)) {
	    int size = dfs (cur_node);
	    if (size > max_size) {
		max_size = size;
		max_comp = cur_node;
	    }
	    cur_node->stagnant = 1;
	    cur_node->value = (num++) * PROCS + mp;
	    if (cur_node->edges != NULL) {
		cur_node->queue = conn_list;
		conn_list = cur_node;
	    }
	}
    }
    max_comp->value = mp;
    barrier();
#ifndef FAST
    n_comp = num;
#endif
    return conn_list;
}

/* Numbers the root vertices of the list of stars and returns the number of
   local components.  The connected component number is the concatenation of
   proc + local index. */

int 
all_number_components (node_t* conn_list)
{
    int num;
    node_t* comp;
    unsigned mp = MYPROC;
    
    for (comp = conn_list, num = 0; comp != NULL; comp = comp->queue, num++) {
	comp->value = num * PROCS + mp;
	comp->parent = toglobal (mp, comp);
    }
    barrier ();
    return num;
}

void 
all_update_edges (node_t* conn_list)
{
    node_t* node;
    edge_t* edge;

    for (node = conn_list; node != NULL; node = node->queue)
	for (edge = tolocal (node->edges); edge != NULL;
	     edge = tolocal (edge->next))
	    edge->node := edge->node->parent;
    sync ();
    barrier ();
}

node_t* 
all_local_traversal (int num_nodes)
{
    node_t* nodes = tolocal (node_list);
    node_t* conn_list;
    int i, j, k, num;
    double temp;

    barrier ();

    if (PROCS == 1) {
	timer = get_seconds ();
	conn_list = all_local_dfs (num_nodes, nodes);
	local_time = get_seconds () - timer;
	return conn_list;
    }

    timer = get_seconds ();
    conn_list = all_local_dfs_global (num_nodes, nodes);

#ifndef FAST
    {
	node_t* comp;
	edge_t* edge;

	local_time = get_seconds () - timer;
	num = all_reduce_to_one_add (n_comp);

	on_one {
	    fprintf (fp, "Local dfs took: %7.6f secs\n", local_time);
	    fprintf (fp, "Number of connected components: %d\n", num);
	}
	barrier ();

	update_time = get_seconds ();
	all_update_edges (conn_list);
	update_time = get_seconds () - update_time;
	
	for (comp = conn_list, num = 0; comp != NULL; comp = comp->queue)
	    for (edge = tolocal (comp->edges); edge != NULL;
		 edge = tolocal (edge->next), num++);

	num = all_reduce_to_one_add (num);
	on_one fprintf (fp, "Number of remaining global edges: %d\n", num / 2);
	barrier ();
    }
#else
    all_update_edges (conn_list);
#endif

    return conn_list;
}