//----------------------------------------------------------------------------
//  EgalTech 2015-2015
//----------------------------------------------------------------------------
// File : NN.cpp      Data : 22.12.15        Versione : 1.6l4
// Contenuto : Calcolo del percorso minimo basandosi su punto pił vicino.
//
//
//
// Modifiche : 22.12.15 DS Creazione modulo.
//
//
//----------------------------------------------------------------------------

//--------------------------- Include ----------------------------------------
#include "stdafx.h"
#include "ShortestPath.h"

/* ------------------------------------------------------------------------- */
long long unsigned
ShortestPath::NearNeighbor( void)
{
  // abilito i collegamenti tra nodi diversi e disabilito gli auto-collegamenti
   for ( unsigned i = 0 ; i < m_nNumPnts ; ++ i) {
      for ( unsigned j = 0 ; j < m_nNumPnts ; ++ j)
         m_Available[ Index( i, j)] = true ;
      m_Available[ Index( i, i)] = false ;
   }

  // se non ho dipendenze
   if ( ! ExistConstraints()) {
    // cerco il nodo con il pił corto arco che se ne diparte
      unsigned nCurr = 0 ;
      unsigned nNew = CheapArc( nCurr) ;
      for ( unsigned i = 1 ; i < m_nNumPnts ; ++ i) {
         unsigned j = CheapArc( i) ;
         if ( ArcCost( i, j) < ArcCost( nCurr, nNew)) {
            nCurr = i ;
            nNew = j ;
         }
      }
     // imposto il nodo corrente come base del percorso
      NODE* pPath = m_pMain ;
      pPath->nPos = nCurr ;
     // ciclo
      do {
        // imposto tutti gli archi non disponibili al nodo corrente
         for ( unsigned i = 0 ; i < m_nNumPnts ; ++ i)
            m_Available[ Index( i, nCurr)] = false ;
        // aggiungo un nuovo nodo al percorso
         pPath = pPath->pNext ;
         pPath->nPos = nNew ;
        // imposto il nuovo nodo come nodo corrente
         nCurr = nNew ;
        // cerco il nuovo nodo all'estremo dell'arco pił corto dal nodo corrente
         nNew = CheapArc( nCurr) ;
      } while ( m_Available[ Index( nCurr, nNew)]) ;
   }
  // se esistono dipendenze
   else {
     // cerco il primo nodo da cui iniziare
      unsigned nNew = -1 ;
      if ( ! ChooseFirstNode( nNew))
         return MAXDIST ;
     // imposto il nodo corrente come base del percorso
      NODE* pPath = m_pMain ;
      pPath->nPos = nNew ;
      unsigned nSize = 1 ;
     // ciclo
      do {
        // imposto tutti gli archi non disponibili al nodo corrente
         for ( unsigned i = 0 ; i < m_nNumPnts ; ++ i)
            m_Available[ Index( i, nNew)] = false ;
        // cerco il nuovo nodo all'estremo dell'arco pił corto dal nodo corrente
         if ( ! ChooseNextNode( pPath, nSize, nNew, true))
            return MAXDIST ;
        // aggiungo un nuovo nodo al percorso
         pPath = pPath->pNext ;
         pPath->nPos = nNew ;
         ++ nSize ;
      } while ( nSize < m_nNumPnts) ;
   }

  // calcolo il costo del percorso
   return TotalCost( m_pMain) ;
}

/* ------------------------------------------------------------------------- */
unsigned
ShortestPath::CheapArc( unsigned i)
{
  // cerco la prima destinazione libera
   unsigned j = 0 ;
   for ( ; ( j < m_nNumPnts - 1  &&  ! m_Available[ Index( i, j)]) ; ++ j)
      ;
  // cerco la migliore destinazione libera
   for ( unsigned k = j + 1 ; k < m_nNumPnts - 1 ; ++ k) {
      if ( m_Available[ Index( i, k)])
         if ( ArcCost( i, k) < ArcCost( i, j))
            j = k ;
   }
   return j ;
}