/**CFile***********************************************************************

  FileName    [spfdReg.c]

  PackageName [spfd]

  Synopsis [Routines to compute a cluster of nodes for optimization.]

  Description [Routines to compute a cluster of nodes for optimization.]

  SeeAlso     [spfdOpt.c]

  Author      [Balakrishna Kumthekar]

  Copyright [This file was created at the University of Colorado at Boulder.
  The University of Colorado at Boulder makes no warranty about the suitability
  of this software for any purpose.  It is presented on an AS IS basis.]

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

#include "spfdInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/


/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/
/**Function********************************************************************

  Synopsis [Find a cluster of nodes that are within regionDepth of
  startNode.]

  SideEffects        [None]

******************************************************************************/
array_t *
SpfdNodeComputeFanoutRegion(
  SpfdApplData_t *applData,
  Ntk_Node_t *startNode,
  int regionDepth)
{
  Ntk_Node_t *fanout,*ntkNode;
  st_table *reached;
  st_generator *stGen;
  array_t *regionArray,*from,*new_;
  int bound,i,j,k;

  reached = st_init_table(st_ptrcmp,st_ptrhash);
  if (Ntk_NodeTestIsPrimaryOutput(startNode)) {
    st_insert(reached,(char *)startNode,(char *)1);
  } else {
    /* Sort the fanout array of startNode according to depth */
    from = array_dup(Ntk_NodeReadFanouts(startNode));
    array_sort(from,SpfdDepthCompare);
    /* Put fanoutArray into reached */
    arrayForEachItem(Ntk_Node_t *,from,i,fanout) {
      if (!Ntk_NodeTestIsPrimaryOutput(fanout)) {
	bound = 0;
      } else {
	bound = 1;
      }
      st_insert(reached,(char *)fanout,(char *)(long)bound);
    }

    /* Proceed for depth regionDepth */
    for (i = 0; i < regionDepth; i++) {
      new_ = array_alloc(Ntk_Node_t *,0);
      arrayForEachItem(Ntk_Node_t *,from,j,ntkNode) {
	st_lookup(reached,(char *)ntkNode,&bound);
	if (!bound) {
	  Ntk_NodeForEachFanout(ntkNode,k,fanout) {
	    if (!st_lookup(reached,(char *)fanout,&bound)) {
	      if (Ntk_NodeTestIsPrimaryOutput(fanout) ||
		  Ntk_NodeReadNumFanouts(fanout) < 1 || /* Just to be safe */
		  i == regionDepth - 1) {
		bound = 1;
	      } else {
		bound = 0;
	      }
	      st_insert(reached,(char *)fanout,(char *)(long)bound);
	      array_insert_last(Ntk_Node_t *,new_,fanout);
	    }
	  }
	}
      }
      array_free(from);
      from = new_;
      array_sort(from,SpfdDepthCompare);
    }
    array_free(from);
  
    /* Finally make the startNode an internal node */
    st_insert(reached,(char *)startNode,(char *)0);
  }  

  /* Put the nodes in reached according to their depth */
  regionArray = array_alloc(Ntk_Node_t *,0);
  st_foreach_item_int(reached,stGen,&fanout,&bound) {
    array_insert_last(Ntk_Node_t *,regionArray,fanout);
  }
  array_sort(regionArray,SpfdDepthCompare);

  if (applData->currRegionNodes) {
    (void) fprintf(vis_stdout,
		   "** spfd warning: Possible memory leak.\n");
  }
  applData->currRegionNodes = reached;
  
  return regionArray;
  
} /* End of SpfdNodeComputeFanoutRegion */


/**Function********************************************************************

  Synopsis [The returned array contains the nodes in TFI of startNode,
  except the immediate fanin of startNode.]

  SideEffects        [None]

******************************************************************************/
array_t *
SpfdNodeComputeTFIUntilDepth(
  Ntk_Node_t *startNode,
  int regionDepth)
{
  Ntk_Node_t *fanin,*ntkNode;
  st_table *reached,*faninTable;
  st_generator *stGen;
  array_t *regionArray,*from,*new_;
  char *dummy;
  int i,j,k;

  /* Make sure that startNode is not a PI to start with. */

  if (Ntk_NodeTestIsPrimaryInput(startNode))
    return NIL(array_t);

  reached = st_init_table(st_ptrcmp,st_ptrhash);
  faninTable = st_init_table(st_ptrcmp,st_ptrhash);
  
  /* Put the fanin array of startNode in faninTable */
  from = array_dup(Ntk_NodeReadFanins(startNode));
  arrayForEachItem(Ntk_Node_t *,from,i,ntkNode) {
    st_insert(faninTable,(char *)ntkNode,(char *)1);
  }

  /* Proceed for depth regionDepth */
  for (i = 0; i < regionDepth; i++) {
    new_ = array_alloc(Ntk_Node_t *,0);
    arrayForEachItem(Ntk_Node_t *,from,j,ntkNode) {
      Ntk_NodeForEachFanin(ntkNode,k,fanin) {
	if (!st_lookup(reached,(char *)fanin,&dummy) &&
	    !st_lookup(faninTable,(char *)fanin,&dummy)) {
	  st_insert(reached,(char *)fanin,(char *)1);
	  array_insert_last(Ntk_Node_t *,new_,fanin);
	}
      }
    }
    array_free(from);
    from = new_;
  }
  array_free(from);
  st_free_table(faninTable);
  
  /* Put the nodes in reached according to their depth */
  regionArray = array_alloc(Ntk_Node_t *,0);
  st_foreach_item(reached,stGen,&ntkNode,&dummy) {
    array_insert_last(Ntk_Node_t *,regionArray,ntkNode);
  }
  array_sort(regionArray,SpfdDepthCompare);

  st_free_table(reached);
  return regionArray;
  
} /* End of SpfdNodeComputeTFIUntilDepth */


/**Function********************************************************************

  Synopsis [Returns in tfoNodes, the nodes in the transitive fanout of
  node.]

  SideEffects        [None]

******************************************************************************/
void
SpfdNodesInTFO(
  Ntk_Network_t *network,
  Ntk_Node_t *node,
  st_table *tfoNodes)
{
  int i;
  Ntk_Node_t *fanout;
  
  st_insert(tfoNodes,(char *)node,(char *)0);
  Ntk_NodeForEachFanout(node,i,fanout) {
    SpfdNodesInTFO(network,fanout,tfoNodes);
  }

  return;
} /* End of SpfdNodesInTFO */


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/