/*****************************************************************************
  FILE           : cc_rcc_topo.c
  SHORTNAME      : 
  SNNS VERSION   : 3.2

  PURPOSE        : Functions of CC and RCC for topological check.
  NOTES          :

  AUTHOR         : Michael Schmalzl
  DATE           : 5.2.93

  CHANGED BY     : Michael Schmalzl
  IDENTIFICATION : @(#)cc_rcc_topo.c	1.8 3/15/94
  SCCS VERSION   : 1.8
  LAST CHANGE    : 3/15/94

             Copyright (c) 1990-1994  SNNS Group, IPVR, Univ. Stuttgart, FRG

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

#include <stdio.h>
#include <math.h>
#include <time.h>  
#include <memory.h>
#include <malloc.h>
#include <values.h>

#include "kr_typ.h"	
#include "kr_const.h"	 
#include "kr_def.h"	 
#include "kr_mac.h"
#include "kernel.h"
#include "cc_mac.h"	
#include "cc_rcc.h" 
#include "cc_rcc_topo.ph"


/*****************************************************************************
  FUNCTION : cc_clearFlags

  PURPOSE  : Clears all CC flags.
  NOTES    :

  UPDATE   : 5.2.93
******************************************************************************/

static void cc_clearFlags(void)
{
 struct Unit *unitPtr;

 FOR_ALL_UNITS(unitPtr){
   if(UNIT_IN_USE(unitPtr)){
     unitPtr->flags &= ~UFLAG_REFRESH;
     unitPtr->lln = 0;
     LINKS_LEAVING(unitPtr) = 0;
     LINKS_ARRIVEING(unitPtr) = 0;
     INPUT_LINKS(unitPtr) = 0;
   }
 }
} 

/*****************************************************************************
  FUNCTION : rcc_clearFlags

  PURPOSE  : Clears all RCC flags.
  NOTES    :

  UPDATE   : 5.2.93
******************************************************************************/

static void rcc_clearFlags(void)
{
 struct Unit *unitPtr;
 int flagMask;

 flagMask = RCC_FLAG | UFLAG_REFRESH;
 FOR_ALL_UNITS(unitPtr){
   if(UNIT_IN_USE(unitPtr)){
     unitPtr->flags &= ~flagMask;
     unitPtr->lln = 0;
     LINKS_LEAVING(unitPtr) = 0;
     LINKS_ARRIVEING(unitPtr) = 0;
     INPUT_LINKS(unitPtr) = 0;
   }
 }
} 

/*****************************************************************************
  FUNCTION : cc_quicksort

  PURPOSE  : Sorts  the units of the hidden layer by  the number of incomming
             links.
  NOTES    :

  UPDATE   : 5.2.93
******************************************************************************/

static void cc_quicksort(int left, int right)
{
 int i,last;
 struct Unit *temp;
 
 if(left >= right ){
   return;
 }
 temp = FirstHiddenUnitPtr[left]; 
 FirstHiddenUnitPtr[left] = FirstHiddenUnitPtr[(left+right)/2]; 
 FirstHiddenUnitPtr[(left+right)/2] = temp;  
 last = left; 
 for(i=left+1;i<=right;i++){
   if(LINKS_LEAVING(FirstHiddenUnitPtr[i]) < LINKS_LEAVING(FirstHiddenUnitPtr[left])) {
     temp = FirstHiddenUnitPtr[++last]; 
     FirstHiddenUnitPtr[last]=FirstHiddenUnitPtr[i]; 
     FirstHiddenUnitPtr[i]=temp;
   }
 }
 temp = FirstHiddenUnitPtr[left]; 
 FirstHiddenUnitPtr[left]=FirstHiddenUnitPtr[last]; 
 FirstHiddenUnitPtr[last] = temp;
 cc_quicksort(left,last);
 cc_quicksort(last+1,right);
}
 

/*****************************************************************************
  FUNCTION : DepthFirst4

  PURPOSE  : Depth search routine for topological sorting.
  NOTES    :

  UPDATE   : 5.2.93
******************************************************************************/

static void  DepthFirst4(struct Unit *unit_ptr, int depth )
{
  struct Site   *site_ptr;
  struct Link   *link_ptr;


  if (unit_ptr->flags & UFLAG_REFRESH)
    {  /*  the 'touch' flag is set: don't continue search  */
    topo_msg.src_error_unit = unit_ptr - unit_array; /*  store unit number  */

    if IS_OUTPUT_UNIT( unit_ptr )
      {  /*  this output unit has a output connection to another unit  */
      if (topo_msg.error_code == KRERR_NO_ERROR)
        topo_msg.error_code = KRERR_O_UNITS_CONNECT;
    }
    else
      if (unit_ptr->lln == 0)
        {  /*  logical layer no. isn't set => Cycle found  */
        topo_msg.no_of_cycles++;
        if (topo_msg.error_code == KRERR_NO_ERROR)
          topo_msg.error_code = KRERR_CYCLES;
      }

    return;
  }
  else
    /*  set the 'touch' flag  */
    unit_ptr->flags |= UFLAG_REFRESH;

  switch (unit_ptr->flags & UFLAG_INPUT_PAT)
    {
    case  UFLAG_DLINKS:   /*  unit has direct links  */
      FOR_ALL_LINKS(unit_ptr,link_ptr){
        DepthFirst4( link_ptr->to, depth + 1 );  /*  increase depth  */
        if(IS_INPUT_UNIT(link_ptr->to)){
          INPUT_LINKS(unit_ptr)++;
        }
        if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
          LINKS_LEAVING(link_ptr->to)++;
          LINKS_ARRIVEING(unit_ptr)++;
        }
      }
      break;
    case  UFLAG_SITES:  /*  unit has sites  */
      FOR_ALL_SITES_AND_LINKS(unit_ptr,site_ptr, link_ptr) {
        DepthFirst4( link_ptr->to, depth + 1 );  /*  increase depth  */
        if(IS_INPUT_UNIT(link_ptr->to)){
          INPUT_LINKS(unit_ptr)++;
        }
        if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
          LINKS_LEAVING(link_ptr->to)++;
          LINKS_ARRIVEING(unit_ptr)++;
        }
      }
      break;
  }

  /*  remember the depth (for cycle detection and statistics)  */
  unit_ptr->lln = depth;

  /*  store only hidden units  */
  if IS_HIDDEN_UNIT( unit_ptr )
    *global_topo_ptr++ = unit_ptr;  /*  store sorted unit pointer  */
}

/*****************************************************************************
  FUNCTION : DepthFirst5

  PURPOSE  : Depth search routine for topological sorting.
  NOTES    :

  UPDATE   : 5.2.93
******************************************************************************/

static void  DepthFirst5( unit_ptr, depth )
struct Unit   *unit_ptr;
int     depth;
{
  struct Site   *site_ptr;
  struct Link   *link_ptr;


  if (unit_ptr->flags & UFLAG_REFRESH)
    {  /*  the 'touch' flag is set: don't continue search  */
    topo_msg.src_error_unit = unit_ptr - unit_array; /*  store unit number  */

    if IS_OUTPUT_UNIT( unit_ptr )
      {  /*  this output unit has a output connection to another unit  */
      if (topo_msg.error_code == KRERR_NO_ERROR)
        topo_msg.error_code = KRERR_O_UNITS_CONNECT;
    }
    else
      if (unit_ptr->lln == 0)
        {  /*  logical layer no. isn't set => Cycle found  */
        topo_msg.no_of_cycles++;
        if (topo_msg.error_code == KRERR_NO_ERROR)
          topo_msg.error_code = KRERR_CYCLES;
      }

    return;
  }
  else
    /*  set the 'touch' flag  */
    unit_ptr->flags |= UFLAG_REFRESH;

  switch (unit_ptr->flags & UFLAG_INPUT_PAT)
    {
    case  UFLAG_DLINKS:   /*  unit has direct links  */
      FOR_ALL_LINKS(unit_ptr,link_ptr) {
        if((IS_HIDDEN_UNIT(unit_ptr)) && (link_ptr->to == unit_ptr)) {
          if(unit_ptr->flags & RCC_FLAG) {
            topo_msg.error_code = KRERR_CC_ERROR4; /* too manny recurent links */
          }
          else { 
            unit_ptr->flags |= RCC_FLAG;
          }
        }
        else { 
          DepthFirst5( link_ptr->to, depth + 1 );  /*  increase depth  */
          if(IS_INPUT_UNIT(link_ptr->to)){
            INPUT_LINKS(unit_ptr)++;
          }
          if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
            LINKS_LEAVING(link_ptr->to)++;
            LINKS_ARRIVEING(unit_ptr)++;
          }
        }
      }
      break;
    case  UFLAG_SITES:  /*  unit has sites  */
      FOR_ALL_SITES_AND_LINKS(unit_ptr,site_ptr, link_ptr) {
        if((IS_HIDDEN_UNIT(unit_ptr)) && (link_ptr->to == unit_ptr)) {
          if(unit_ptr->flags & RCC_FLAG) {
            topo_msg.error_code = KRERR_CC_ERROR4; /* too many recurent links */
          }
          else { 
            unit_ptr->flags |= RCC_FLAG;
          }
        }
        else { 
          DepthFirst5( link_ptr->to, depth + 1 );  /*  increase depth  */
          if(IS_INPUT_UNIT(link_ptr->to)){
            INPUT_LINKS(unit_ptr)++;
          }
          if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
            LINKS_LEAVING(link_ptr->to)++;
            LINKS_ARRIVEING(unit_ptr)++;
          }
        }
      }
      break;
    }

  /*  remember the depth (for cycle detection and statistics)  */
  unit_ptr->lln = depth;

  /*  store only hidden units  */
  if IS_HIDDEN_UNIT( unit_ptr )
    *global_topo_ptr++ = unit_ptr;  /*  store sorted unit pointer  */
}

/*****************************************************************************
  FUNCTION : cc_topoSort

  PURPOSE  : Main routine for topological sorting for CC and RCC.
  NOTES    :

  UPDATE   : 5.2.93
******************************************************************************/

krui_err cc_topoSort(int topoSortId)
{
  register struct Unit   *unit_ptr;
  int   io_units,h,counter=0,recurentLinkDetected;
  struct Link *link_ptr;
  
  KernelErrorCode = KRERR_NO_ERROR;  /*  reset return code  */
  if(topoSortId == TOPOLOGICAL_CC) {
    cc_clearFlags();    /*  reset units 'touch' flags  */
  }
  else {
    rcc_clearFlags();
  }
  global_topo_ptr = topo_ptr_array;  /*  initialize global pointer */

  /*  limit left side of the topological array with NULL pointer  */
  *global_topo_ptr++ = NULL;

  /*  put all input units in the topologic array  */
  io_units = 0;
  FOR_ALL_UNITS( unit_ptr ) 
    if (IS_INPUT_UNIT( unit_ptr ) && UNIT_IN_USE( unit_ptr ))
      {
      if UNIT_HAS_INPUTS( unit_ptr )
        {  /*  this input unit has a connection to another unit  */
        topo_msg.dest_error_unit = unit_ptr - unit_array;  /*  store the unit no.  */

        KernelErrorCode = KRERR_I_UNITS_CONNECT;  /*  input unit has input  */
        return( KernelErrorCode );
      }

      io_units++;       /*  there is a input unit  */
      *global_topo_ptr++ = unit_ptr;  /*  save input unit  */
    }
  
  if ((NoOfInputUnits = io_units) == 0)
    {  /*  no input units */
    KernelErrorCode = KRERR_NO_INPUT_UNITS;
    return( KernelErrorCode );
  }

  /*  limit input units in the topological array with NULL pointer  */
  *global_topo_ptr++ = NULL;

  /*  begin depth search at the first output unit  */
  io_units = 0;
  FOR_ALL_UNITS( unit_ptr )
    if (IS_OUTPUT_UNIT( unit_ptr ) && UNIT_IN_USE( unit_ptr ))
      {
      io_units++;       /*  there is a output unit  */
      if(topoSortId == TOPOLOGICAL_CC){
        DepthFirst4( unit_ptr, 1 );
      }
      else if (topoSortId == TOPOLOGICAL_RCC){
        DepthFirst5(unit_ptr,1);
      }
      else { /* topoSortId == TOPOLOGICAL_BCC */ 
        DepthFirst4(unit_ptr,1);
      }      
      if (topo_msg.error_code != KRERR_NO_ERROR)
        {  /*  stop if an error occured  */
        KernelErrorCode = topo_msg.error_code;
        return( KernelErrorCode );
      }
    }


  if ((NoOfOutputUnits = io_units) == 0)
    {  /*  no output units */
    KernelErrorCode = KRERR_NO_OUTPUT_UNITS;
    return( KernelErrorCode );
  }

  /*  limit hidden units in the topological array with NULL pointer  */
  *global_topo_ptr++ = NULL;

  /*  put all output units in the topological array  */
  FOR_ALL_UNITS( unit_ptr ) 
    if (IS_OUTPUT_UNIT(unit_ptr ) && UNIT_IN_USE( unit_ptr ))
      *global_topo_ptr++ = unit_ptr;  /*  save output unit  */

  /*  limit right side of the topologic array with NULL pointer  */
  *global_topo_ptr++ = NULL;
  
  FOR_ALL_UNITS( unit_ptr ) {
    if (IS_SPECIAL_UNIT(unit_ptr) && UNIT_IN_USE( unit_ptr )) {
      if(topoSortId == TOPOLOGICAL_RCC){
        link_ptr = (struct Link *) unit_ptr->sites;
        if(unit_ptr != link_ptr->to) {
          KernelErrorCode = KRERR_CC_ERROR9; /* the first link is not a recurent link */
          return(KernelErrorCode);
        }
        recurentLinkDetected = 0;
        if(topoSortId == TOPOLOGICAL_RCC) {   
          FOR_ALL_LINKS(unit_ptr,link_ptr){
            if(unit_ptr == link_ptr->to) {
              recurentLinkDetected++;
            }
          }
          if(recurentLinkDetected != 1) {   
            KernelErrorCode = KRERR_CC_ERROR8; /* the special unit has too many links */
            return( KernelErrorCode ); 
	  }
	}
      }
      *global_topo_ptr++ = unit_ptr;  /*  save output unit  */
      unit_ptr->flags |= UFLAG_REFRESH;
    }
  }
  /*  limit right side of the topologic array with NULL pointer  */
  *global_topo_ptr++ = NULL;

  /*  calc. no. of sorted units  */
  no_of_topo_units = (global_topo_ptr - topo_ptr_array) - 5;

  /*  search for dead units i.e. units without inputs  */
  FOR_ALL_UNITS( unit_ptr )
    if (!(unit_ptr->flags & UFLAG_REFRESH) && UNIT_IN_USE( unit_ptr ))
      {
      topo_msg.no_of_dead_units++;
      if (topo_msg.src_error_unit == 0)
        topo_msg.src_error_unit = unit_ptr - unit_array;  /*  store the unit no.  */
    }

  if (topo_msg.no_of_dead_units != 0)
    KernelErrorCode = KRERR_DEAD_UNITS;

  if(KernelErrorCode == KRERR_NO_ERROR){
    FirstHiddenUnitPtr = (struct Unit **)(&topo_ptr_array[1]) + NoOfInputUnits + 1;
    FOR_ALL_HIDDEN_UNITS(unit_ptr,h){
       switch(topoSortId){
         case TOPOLOGICAL_RCC : 
           if(!(unit_ptr->flags & RCC_FLAG)) {
             KernelErrorCode = KRERR_CC_ERROR5;
           }
           if((LINKS_LEAVING(unit_ptr)+LINKS_ARRIVEING(unit_ptr)+1)!=NoOfHiddenUnits) {
             KernelErrorCode = KRERR_CC_ERROR6;
             return(KernelErrorCode);
           }
           if(LINKS_ARRIVEING(unit_ptr) != counter++) {
             KernelErrorCode = KRERR_CC_ERROR6;
             return(KernelErrorCode);
           }
           link_ptr = (struct Link *) unit_ptr->sites;
           if(unit_ptr != link_ptr->to) {
             KernelErrorCode = KRERR_CC_ERROR7; /* the first link is not the recurent link */
             return(KernelErrorCode);
           }
         break;
         case TOPOLOGICAL_CC : 
           if((LINKS_LEAVING(unit_ptr)+LINKS_ARRIVEING(unit_ptr)+1)!=NoOfHiddenUnits) {
             fprintf(stderr,"111111 %d \n",NoOfHiddenUnits);
             KernelErrorCode = KRERR_CC_ERROR6;
             return(KernelErrorCode);
           }
           if(LINKS_ARRIVEING(unit_ptr) != counter++) {
             fprintf(stderr,"22222 %d \n",counter);
             KernelErrorCode = KRERR_CC_ERROR6;
             return(KernelErrorCode);
           }
         break;
         case TOPOLOGICAL_BCC : 
           if((LINKS_LEAVING(unit_ptr)+LINKS_ARRIVEING(unit_ptr)+1)!=NoOfHiddenUnits) {
             KernelErrorCode = KRERR_CC_ERROR6;
             return(KernelErrorCode);
           }
           if(LINKS_ARRIVEING(unit_ptr) != counter++) {
             KernelErrorCode = KRERR_CC_ERROR6;
             return(KernelErrorCode);
           }
           if(counter == NoOfHiddenUnits) {
             counter = 0;
           }
         break;
       }  
    }
  }
  return( KernelErrorCode );
}






