#include "mpi.h"
#include <stdio.h>

/*****************************************************************************

 * Function: bcast_binomial_tree

 * Return: int

 * Inputs:
    buff: send input buffer
    count: number of elements to send
    data_type: data type of elements being sent
    root: source of data
    comm: communicator

 * Descrp: broadcasts using a bionomial tree.

 * Auther: MPICH / modified by Ahmad Faraj

 ****************************************************************************/

int
bcast_binomial_tree(void * buff, int count, MPI_Datatype data_type,
		    int root, MPI_Comm comm)
{
  MPI_Status status;
  int i, src, dst, rank, num_procs, mask, relative_rank;  
  int tag = 1, success = 0;

  MPI_Comm_rank(comm, &rank);
  MPI_Comm_size(comm, &num_procs);
  
  relative_rank = (rank >= root) ? rank - root : rank - root + num_procs;

  mask = 0x1;
  while (mask < num_procs) 
    {
      if (relative_rank & mask) 
	{
	  src = rank - mask; 
	  if (src < 0) src += num_procs;
	  MPIC_Recv(buff, count, data_type, src, tag, comm, MPI_STATUS_IGNORE);
	  break;
	}
      mask <<= 1;
    }

  mask >>= 1;
  while (mask > 0) 
    {
      if (relative_rank + mask < num_procs) 
	{
	  dst = rank + mask;
	  if (dst >= num_procs) dst -= num_procs;
	  MPIC_Send (buff, count, data_type, dst, tag, comm);
	}
      mask >>= 1;
    }

  return success;
}