text: /**CFile****************************************************************
  
    FileName    [cutMerge.c]
  
    SystemName  [ABC: Logic synthesis and verification system.]
  
    PackageName [K-feasible cut computation package.]
  
    Synopsis    [Procedure to merge two cuts.]
  
    Author      [Alan Mishchenko]
    
    Affiliation [UC Berkeley]
  
    Date        [Ver. 1.0. Started - June 20, 2005.]
  
    Revision    [$Id: cutMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
  
  ***********************************************************************/
  
  #include "cutInt.h"
  
  ABC_NAMESPACE_IMPL_START
  
  
  ////////////////////////////////////////////////////////////////////////
  ///                        DECLARATIONS                              ///
  ////////////////////////////////////////////////////////////////////////
  
  ////////////////////////////////////////////////////////////////////////
  ///                     FUNCTION DEFINITIONS                         ///
  ////////////////////////////////////////////////////////////////////////
  
  /**Function*************************************************************
  
    Synopsis    [Merges two cuts.]
  
    Description [This procedure works.]
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Cut_Cut_t * Cut_CutMergeTwo2( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
  { 
      static int M[7][3] = {{0},{0},{0},{0},{0},{0},{0}};
      Cut_Cut_t * pRes;
      int * pRow;
      int nLeaves0, nLeaves1, Limit;
      int i, k, Count, nNodes;
  
      assert( pCut0->nLeaves >= pCut1->nLeaves );
  
      // the case of the largest cut sizes
      Limit = p->pParams->nVarsMax;
      nLeaves0 = pCut0->nLeaves;
      nLeaves1 = pCut1->nLeaves;
      if ( nLeaves0 == Limit && nLeaves1 == Limit )
      {
          for ( i = 0; i < nLeaves0; i++ )
              if ( pCut0->pLeaves[i] != pCut1->pLeaves[i] )
                  return NULL;
          pRes = Cut_CutAlloc( p );
          for ( i = 0; i < nLeaves0; i++ )
              pRes->pLeaves[i] = pCut0->pLeaves[i];
          pRes->nLeaves = nLeaves0;
          return pRes;
      }
      // the case when one of the cuts is the largest
      if ( nLeaves0 == Limit )
      {
          for ( i = 0; i < nLeaves1; i++ )
          {
              for ( k = nLeaves0 - 1; k >= 0; k-- )
                  if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] )
                      break;
              if ( k == -1 ) // did not find
                  return NULL;
          }
          pRes = Cut_CutAlloc( p );
          for ( i = 0; i < nLeaves0; i++ )
              pRes->pLeaves[i] = pCut0->pLeaves[i];
          pRes->nLeaves = nLeaves0;
          return pRes;
      }
      // other cases
      nNodes = nLeaves0;
      for ( i = 0; i < nLeaves1; i++ )
      {
          for ( k = nLeaves0 - 1; k >= 0; k-- )
          {
              if ( pCut0->pLeaves[k] > pCut1->pLeaves[i] )
                  continue;
              if ( pCut0->pLeaves[k] < pCut1->pLeaves[i] )
              {
                  pRow = M[k+1];
                  if ( pRow[0] == 0 )
                      pRow[0] = pCut1->pLeaves[i], pRow[1] = 0;
                  else if ( pRow[1] == 0 )
                      pRow[1] = pCut1->pLeaves[i], pRow[2] = 0;
                  else if ( pRow[2] == 0 )
                      pRow[2] = pCut1->pLeaves[i];
                  else 
                      assert( 0 );
                  if ( ++nNodes > Limit )
                  {
                      for ( i = 0; i <= nLeaves0; i++ )
                          M[i][0] = 0;
                      return NULL;
                  }
              }
              break;
          }
          if ( k == -1 )
          {
              pRow = M[0];
              if ( pRow[0] == 0 )
                  pRow[0] = pCut1->pLeaves[i], pRow[1] = 0;
              else if ( pRow[1] == 0 )
                  pRow[1] = pCut1->pLeaves[i], pRow[2] = 0;
              else if ( pRow[2] == 0 )
                  pRow[2] = pCut1->pLeaves[i];
              else 
                  assert( 0 );
              if ( ++nNodes > Limit )
              {
                  for ( i = 0; i <= nLeaves0; i++ )
                      M[i][0] = 0;
                  return NULL;
              }
              continue;
          }
      }
  
      pRes = Cut_CutAlloc( p );
      for ( Count = 0, i = 0; i <= nLeaves0; i++ )
      {
          if ( i > 0 )
              pRes->pLeaves[Count++] = pCut0->pLeaves[i-1];
          pRow = M[i];
          if ( pRow[0] )
          {
              pRes->pLeaves[Count++] = pRow[0];
              if ( pRow[1] )
              {
                  pRes->pLeaves[Count++] = pRow[1];
                  if ( pRow[2] )
                      pRes->pLeaves[Count++] = pRow[2];
              }
              pRow[0] = 0;
          }
      }
      assert( Count == nNodes );
      pRes->nLeaves = nNodes;
      return pRes;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Merges two cuts.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Cut_Cut_t * Cut_CutMergeTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
  { 
      Cut_Cut_t * pRes;
      int * pLeaves;
      int Limit, nLeaves0, nLeaves1;
      int i, k, c;
  
      assert( pCut0->nLeaves >= pCut1->nLeaves );
  
      // consider two cuts
      nLeaves0 = pCut0->nLeaves;
      nLeaves1 = pCut1->nLeaves;
  
      // the case of the largest cut sizes
      Limit = p->pParams->nVarsMax;
      if ( nLeaves0 == Limit && nLeaves1 == Limit )
      {
          for ( i = 0; i < nLeaves0; i++ )
              if ( pCut0->pLeaves[i] != pCut1->pLeaves[i] )
                  return NULL;
          pRes = Cut_CutAlloc( p );
          for ( i = 0; i < nLeaves0; i++ )
              pRes->pLeaves[i] = pCut0->pLeaves[i];
          pRes->nLeaves = pCut0->nLeaves;
          return pRes;
      }
      // the case when one of the cuts is the largest
      if ( nLeaves0 == Limit )
      {
          for ( i = 0; i < nLeaves1; i++ )
          {
              for ( k = nLeaves0 - 1; k >= 0; k-- )
                  if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] )
                      break;
              if ( k == -1 ) // did not find
                  return NULL;
          }
          pRes = Cut_CutAlloc( p );
          for ( i = 0; i < nLeaves0; i++ )
              pRes->pLeaves[i] = pCut0->pLeaves[i];
          pRes->nLeaves = pCut0->nLeaves;
          return pRes;
      }
  
      // prepare the cut
      if ( p->pReady == NULL )
          p->pReady = Cut_CutAlloc( p );
      pLeaves = p->pReady->pLeaves;
  
      // compare two cuts with different numbers
      i = k = 0;
      for ( c = 0; c < Limit; c++ )
      {
          if ( k == nLeaves1 )
          {
              if ( i == nLeaves0 )
              {
                  p->pReady->nLeaves = c;
                  pRes = p->pReady;  p->pReady = NULL;
                  return pRes;
              }
              pLeaves[c] = pCut0->pLeaves[i++];
              continue;
          }
          if ( i == nLeaves0 )
          {
              if ( k == nLeaves1 )
              {
                  p->pReady->nLeaves = c;
                  pRes = p->pReady;  p->pReady = NULL;
                  return pRes;
              }
              pLeaves[c] = pCut1->pLeaves[k++];
              continue;
          }
          if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] )
          {
              pLeaves[c] = pCut0->pLeaves[i++];
              continue;
          }
          if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] )
          {
              pLeaves[c] = pCut1->pLeaves[k++];
              continue;
          }
          pLeaves[c] = pCut0->pLeaves[i++]; 
          k++;
      }
      if ( i < nLeaves0 || k < nLeaves1 )
          return NULL;
      p->pReady->nLeaves = c;
      pRes = p->pReady;  p->pReady = NULL;
      return pRes;
  }
  
  
  /**Function*************************************************************
  
    Synopsis    [Merges two cuts.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Cut_Cut_t * Cut_CutMergeTwo3( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
  { 
      Cut_Cut_t * pRes;
      int * pLeaves;
      int Limit, nLeaves0, nLeaves1;
      int i, k, c;
  
      assert( pCut0->nLeaves >= pCut1->nLeaves );
  
      // prepare the cut
      if ( p->pReady == NULL )
          p->pReady = Cut_CutAlloc( p );
      pLeaves = p->pReady->pLeaves;
  
      // consider two cuts
      Limit = p->pParams->nVarsMax;
      nLeaves0 = pCut0->nLeaves;
      nLeaves1 = pCut1->nLeaves;
      if ( nLeaves0 == Limit )
      { // the case when one of the cuts is the largest
          if ( nLeaves1 == Limit )
          { // the case when both cuts are the largest
              for ( i = 0; i < nLeaves0; i++ )
              {
                  pLeaves[i] = pCut0->pLeaves[i];
                  if ( pLeaves[i] != pCut1->pLeaves[i] )
                      return NULL;
              }
          }
          else
          {
              for ( i = k = 0; i < nLeaves0; i++ )
              {
                  pLeaves[i] = pCut0->pLeaves[i];
                  if ( k == (int)nLeaves1 )
                      continue;
                  if ( pLeaves[i] < pCut1->pLeaves[k] )
                      continue;
                  if ( pLeaves[i] == pCut1->pLeaves[k++] )
                      continue;
                  return NULL;
              }
              if ( k < nLeaves1 )
                  return NULL;
          }
          p->pReady->nLeaves = nLeaves0;
          pRes = p->pReady;  p->pReady = NULL;
          return pRes;
      }
  
      // compare two cuts with different numbers
      i = k = 0;
      for ( c = 0; c < Limit; c++ )
      {
          if ( k == nLeaves1 )
          {
              if ( i == nLeaves0 )
              {
                  p->pReady->nLeaves = c;
                  pRes = p->pReady;  p->pReady = NULL;
                  return pRes;
              }
              pLeaves[c] = pCut0->pLeaves[i++];
              continue;
          }
          if ( i == nLeaves0 )
          {
              if ( k == nLeaves1 )
              {
                  p->pReady->nLeaves = c;
                  pRes = p->pReady;  p->pReady = NULL;
                  return pRes;
              }
              pLeaves[c] = pCut1->pLeaves[k++];
              continue;
          }
          if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] )
          {
              pLeaves[c] = pCut0->pLeaves[i++];
              continue;
          }
          if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] )
          {
              pLeaves[c] = pCut1->pLeaves[k++];
              continue;
          }
          pLeaves[c] = pCut0->pLeaves[i++]; 
          k++;
      }
      if ( i < nLeaves0 || k < nLeaves1 )
          return NULL;
      p->pReady->nLeaves = c;
      pRes = p->pReady;  p->pReady = NULL;
      return pRes;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Merges two cuts.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Cut_Cut_t * Cut_CutMergeTwo4( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
  { 
      Cut_Cut_t * pRes;
      int * pLeaves;
      int i, k, min, NodeTemp, Limit, nTotal;
  
      assert( pCut0->nLeaves >= pCut1->nLeaves );
  
      // prepare the cut
      if ( p->pReady == NULL )
          p->pReady = Cut_CutAlloc( p );
      pLeaves = p->pReady->pLeaves;
  
      // consider two cuts
      Limit = p->pParams->nVarsMax;
      if ( pCut0->nLeaves == (unsigned)Limit )
      { // the case when one of the cuts is the largest
          if ( pCut1->nLeaves == (unsigned)Limit )
          { // the case when both cuts are the largest
              for ( i = 0; i < (int)pCut0->nLeaves; i++ )
              {
                  pLeaves[i] = pCut0->pLeaves[i];
                  if ( pLeaves[i] != pCut1->pLeaves[i] )
                      return NULL;
              }
          }
          else
          {
              for ( i = k = 0; i < (int)pCut0->nLeaves; i++ )
              {
                  pLeaves[i] = pCut0->pLeaves[i];
                  if ( k == (int)pCut1->nLeaves )
                      continue;
                  if ( pLeaves[i] < pCut1->pLeaves[k] )
                      continue;
                  if ( pLeaves[i] == pCut1->pLeaves[k++] )
                      continue;
                  return NULL;
              }
              if ( k < (int)pCut1->nLeaves )
                  return NULL;
          }
          p->pReady->nLeaves = pCut0->nLeaves;
          pRes = p->pReady;  p->pReady = NULL;
          return pRes;
      }
  
      // count the number of unique entries in pCut1
      nTotal = pCut0->nLeaves;
      for ( i = 0; i < (int)pCut1->nLeaves; i++ )
      {
          // try to find this entry among the leaves of pCut0
          for ( k = 0; k < (int)pCut0->nLeaves; k++ )
              if ( pCut1->pLeaves[i] == pCut0->pLeaves[k] )
                  break;
          if ( k < (int)pCut0->nLeaves ) // found
              continue;
          // we found a new entry to add
          if ( nTotal == Limit )
              return NULL;
          pLeaves[nTotal++] = pCut1->pLeaves[i];
      }
      // we know that the feasible cut exists
  
      // add the starting entries
      for ( k = 0; k < (int)pCut0->nLeaves; k++ )
          pLeaves[k] = pCut0->pLeaves[k];
  
      // selection-sort the entries
      for ( i = 0; i < nTotal - 1; i++ )
      {
          min = i;
          for ( k = i+1; k < nTotal; k++ )
              if ( pLeaves[k] < pLeaves[min] )
                  min = k;
          NodeTemp     = pLeaves[i];
          pLeaves[i]   = pLeaves[min];
          pLeaves[min] = NodeTemp;
      }
      p->pReady->nLeaves = nTotal;
      pRes = p->pReady;  p->pReady = NULL;
      return pRes;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Merges two cuts.]
  
    Description [This procedure works.]
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Cut_Cut_t * Cut_CutMergeTwo5( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
  { 
      static int M[7][3] = {{0},{0},{0},{0},{0},{0},{0}};
      Cut_Cut_t * pRes;
      int * pRow;
      unsigned uSign0, uSign1;
      int i, k, nNodes, Count;
      unsigned Limit = p->pParams->nVarsMax;
  
      assert( pCut0->nLeaves >= pCut1->nLeaves );
  
      // the case of the largest cut sizes
      if ( pCut0->nLeaves == Limit && pCut1->nLeaves == Limit )
      {
          for ( i = 0; i < (int)pCut0->nLeaves; i++ )
              if ( pCut0->pLeaves[i] != pCut1->pLeaves[i] )
                  return NULL;
          pRes = Cut_CutAlloc( p );
          for ( i = 0; i < (int)pCut0->nLeaves; i++ )
              pRes->pLeaves[i] = pCut0->pLeaves[i];
          pRes->nLeaves = pCut0->nLeaves;
          return pRes;
      }
      // the case when one of the cuts is the largest
      if ( pCut0->nLeaves == Limit )
      {
          if ( !p->pParams->fTruth )
          {
              for ( i = 0; i < (int)pCut1->nLeaves; i++ )
              {
                  for ( k = pCut0->nLeaves - 1; k >= 0; k-- )
                      if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] )
                          break;
                  if ( k == -1 ) // did not find
                      return NULL;
              }
              pRes = Cut_CutAlloc( p );
          }
          else
          {
              uSign1 = 0;
              for ( i = 0; i < (int)pCut1->nLeaves; i++ )
              {
                  for ( k = pCut0->nLeaves - 1; k >= 0; k-- )
                      if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] )
                      {
                          uSign1 |= (1 << i);
                          break;
                      }
                  if ( k == -1 ) // did not find
                      return NULL;
              }
              pRes = Cut_CutAlloc( p );
              pRes->Num1 = uSign1;
          }
          for ( i = 0; i < (int)pCut0->nLeaves; i++ )
              pRes->pLeaves[i] = pCut0->pLeaves[i];
          pRes->nLeaves = pCut0->nLeaves;
          return pRes;
      }
      // other cases
      nNodes = pCut0->nLeaves;
      for ( i = 0; i < (int)pCut1->nLeaves; i++ )
      {
          for ( k = pCut0->nLeaves - 1; k >= 0; k-- )
          {
              if ( pCut0->pLeaves[k] > pCut1->pLeaves[i] )
                  continue;
              if ( pCut0->pLeaves[k] < pCut1->pLeaves[i] )
              {
                  pRow = M[k+1];
                  if ( pRow[0] == 0 )
                      pRow[0] = pCut1->pLeaves[i], pRow[1] = 0;
                  else if ( pRow[1] == 0 )
                      pRow[1] = pCut1->pLeaves[i], pRow[2] = 0;
                  else if ( pRow[2] == 0 )
                      pRow[2] = pCut1->pLeaves[i];
                  else 
                      assert( 0 );
                  if ( ++nNodes > (int)Limit )
                  {
                      for ( i = 0; i <= (int)pCut0->nLeaves; i++ )
                          M[i][0] = 0;
                      return NULL;
                  }
              }
              break;
          }
          if ( k == -1 )
          {
              pRow = M[0];
              if ( pRow[0] == 0 )
                  pRow[0] = pCut1->pLeaves[i], pRow[1] = 0;
              else if ( pRow[1] == 0 )
                  pRow[1] = pCut1->pLeaves[i], pRow[2] = 0;
              else if ( pRow[2] == 0 )
                  pRow[2] = pCut1->pLeaves[i];
              else 
                  assert( 0 );
              if ( ++nNodes > (int)Limit )
              {
                  for ( i = 0; i <= (int)pCut0->nLeaves; i++ )
                      M[i][0] = 0;
                  return NULL;
              }
              continue;
          }
      }
  
      pRes = Cut_CutAlloc( p );
      if ( !p->pParams->fTruth )
      {
          for ( Count = 0, i = 0; i <= (int)pCut0->nLeaves; i++ )
          {
              if ( i > 0 )
                  pRes->pLeaves[Count++] = pCut0->pLeaves[i-1];
              pRow = M[i];
              if ( pRow[0] )
              {
                  pRes->pLeaves[Count++] = pRow[0];
                  if ( pRow[1] )
                  {
                      pRes->pLeaves[Count++] = pRow[1];
                      if ( pRow[2] )
                          pRes->pLeaves[Count++] = pRow[2];
                  }
                  pRow[0] = 0;
              }
          }
          assert( Count == nNodes );
          pRes->nLeaves = nNodes;
  /*
      // make sure that the cut is correct
      {
          for ( i = 1; i < (int)pRes->nLeaves; i++ )
              if ( pRes->pLeaves[i-1] >= pRes->pLeaves[i] )
              {
                  int v = 0;
              }
      }
  */
          return pRes;
      }
  
      uSign0 = uSign1 = 0;
      for ( Count = 0, i = 0; i <= (int)pCut0->nLeaves; i++ )
      {
          if ( i > 0 )
          {
              uSign0 |= (1 << Count);
              pRes->pLeaves[Count++] = pCut1->pLeaves[i-1];
          }
          pRow = M[i];
          if ( pRow[0] )
          {
              uSign1 |= (1 << Count);
              pRes->pLeaves[Count++] = pRow[0];
              if ( pRow[1] )
              {
                  uSign1 |= (1 << Count);
                  pRes->pLeaves[Count++] = pRow[1];
                  if ( pRow[2] )
                  {
                      uSign1 |= (1 << Count);
                      pRes->pLeaves[Count++] = pRow[2];
                  }
              }
              pRow[0] = 0;
          }
      }
      assert( Count == nNodes );
      pRes->nLeaves = nNodes;
      pRes->Num1 = uSign1;
      pRes->Num0 = uSign0;
      return pRes;
  }
  
  ////////////////////////////////////////////////////////////////////////
  ///                       END OF FILE                                ///
  ////////////////////////////////////////////////////////////////////////
  
  
  ABC_NAMESPACE_IMPL_END
  
  