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

  FileName    [ordRoots.c]

  PackageName [ord]

  Synopsis    [Routines to order the roots of the network.]

  Description [Routines to order the roots of the network.  The nodes of the
  network are explored in DFS order from the roots, in the root order
  computed. To add a new method, create a new value for the Ord_RootMethod
  enumerated type, and add a call to the new procedure from
  Ord_NetworkOrderRoots.]

  Author      [Tom Shiple]

  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
  All rights reserved.

  Permission is hereby granted, without written agreement and without license
  or royalty fees, to use, copy, modify, and distribute this software and its
  documentation for any purpose, 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.]

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

#include "ordInt.h"

static char rcsid[] UNUSED = "$Id: ordRoots.c,v 1.7 2002/08/27 08:43:16 fabio Exp $";

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


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


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


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


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


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

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


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


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

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

  Synopsis    [Orders the roots of a network.]

  Description [Orders the combinational outputs of a network.  The data inputs
  of latches always precede the other combinational outputs.  This gives
  priority to finding the best ordering for the variables in the next state
  functions. <p>

  The different root ordering methods are documented in the static_order
  command. If rootMethod is Ord_RootsByDefault_c, then one of the ordering
  methods is called by default, depending on the number of latches in the
  network.<p>

  An arbitrary subset of roots can be specified in partialOrder. No check is
  made to determine if the nodes in partialOrder are contained within the set
  specified by orderType.  If partialOrder is non-NULL, then a total order on
  the roots is computed according to rootMethod (as described above), and then
  the computed order is merged into the partialOrder.]

  SideEffects []

  SeeAlso     [OrdNetworkOrderRootsByDepth OrdNetworkOrderRootsByPerm]

******************************************************************************/
lsList
Ord_NetworkOrderRoots(
  Ntk_Network_t *network,
  Ord_RootMethod rootMethod,
  lsList partialOrder,
  boolean verbose)
{
  lsList rootOrderList;
  
  switch (rootMethod) {
    case Ord_RootsByDepth_c:
      rootOrderList = OrdNetworkOrderRootsByDepth(network, verbose); 
      break;
    case Ord_RootsByPerm_c:
      rootOrderList = OrdNetworkOrderRootsByPerm(network, verbose);
      break;
    case Ord_RootsByDefault_c:
      /*
       * RootByPerm method is cubic in the number of latches, so use it by
       * default only if the number of latches is not too large (30 is somewhat
       * arbitrary).
       */
      if (Ntk_NetworkReadNumLatches(network) < 30) {
        rootOrderList = OrdNetworkOrderRootsByPerm(network, verbose);
      }
      else {
        rootOrderList = OrdNetworkOrderRootsByDepth(network, verbose);
      }
      break;
    default:
      fail("unrecognized root order method");
  }

  /*
   * If a partial order is supplied, merge (left, arbitrarily) the computed
   * order into the supplied order, to get a total ordering on all of the
   * roots.
   */
  if (partialOrder != (lsList) NULL) {
    lsList partialOrderCopy = lsCopy(partialOrder,
				     (lsGeneric (*) (lsGeneric)) NULL);

    Ord_ListMergeList(partialOrderCopy, rootOrderList, Ord_ListMergeLeft_c);
    (void) lsDestroy(rootOrderList, (void (*) (lsGeneric)) NULL);
    return partialOrderCopy;
  }
  else {
    return rootOrderList;
  }
}

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

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

  Synopsis [Computes a total ordering on the combinational outputs of a
  network.]

  Description [Computes a total ordering on the combinational outputs of a
  network.  First, the depth of each combinational output is calculated.  The
  depth of a node is the longest path (going backwards) to a combinational
  input or constant. Then, the algorithm creates two lists: 1) data inputs to
  latches, and 2) all remaining combinational outputs. Next, each list is
  sorted in order of decreasing depth.  Finally, the second list is appended
  to the first.]

  SideEffects []

  SeeAlso     [Ord_NetworkOrderRoots OrdNetworkComputeNodeDepths]

******************************************************************************/
lsList
OrdNetworkOrderRootsByDepth(
  Ntk_Network_t *network,
  boolean verbose)
{
  lsGen       gen;
  Ntk_Node_t *node;
  st_table   *processedTable = st_init_table(st_ptrcmp, st_ptrhash);
  lsList dataInputs = lsCreate();
  lsList otherCombOuts = lsCreate();
  lsList combOutputs = Ntk_NetworkReadCombOutputs(network);

  /*
   * A node can drive more than one latch data input, latch initial input,
   * or primary output. Use a hash table to ensure that no node appears twice
   * across the two lists.
   */
  Ntk_NetworkForEachCombOutput(network, gen, node) {
    if (Ntk_NodeTestIsLatchDataInput(node)) {
      OrdNodeAddToList(dataInputs, processedTable, node);
    }
    else {
      OrdNodeAddToList(otherCombOuts, processedTable, node);
    }
  }
  st_free_table(processedTable);

  /* Compute depth of all combinational outputs. */
  OrdNetworkComputeNodeDepths(network, combOutputs);

  /* Sort each list independently. */
  lsSort(dataInputs, OrdNodesFromListCompareDepth);
  lsSort(otherCombOuts, OrdNodesFromListCompareDepth);

  Ord_ListAppendList(dataInputs, otherCombOuts);
  (void) lsDestroy(otherCombOuts, (void (*) (lsGeneric)) NULL);
  
  return dataInputs;
}

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

  Synopsis    [Inserts a node into a list, unless it already appears in the list.]

  SideEffects []

******************************************************************************/
void
OrdNodeAddToList(
  lsList nodeList,
  st_table *nodeTable,
  Ntk_Node_t *node)
{
  if (!st_is_member(nodeTable, (char *) node)) {
    st_insert(nodeTable, (char *) node, NIL(char));
    (void) lsNewEnd(nodeList, (lsGeneric) node, LS_NH);
  }
}



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