//----------------------------------------------------------------------------
//  EgalTech 2015-2015
//----------------------------------------------------------------------------
// File : TwoOpt.cpp        Data : 22.12.15        Versione : 1.6l4
// Contenuto : Miglioramento del percorso spezzandolo in 2 parti e 
//             ricollegando con una delle due parti invertite.
//
//                 K  Last              K  Last
//                 o  o--<-             o--o--<-
//                 |\/                  |
//                 |/\                  |
//                 o  o--->             o--o--->
//             First  K+1           First  K+1
//
// Modifiche : 22.12.15 DS Creazione modulo.
//
//
//----------------------------------------------------------------------------

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

// ----------------------------------------------------------------------------
static void
SwapNodesForTwoOpt( NODE* pFirst, NODE* pKth, NODE* pLast)
{
  // inverto il tratto intermedio
   for ( NODE* pCurr = pFirst ; pCurr != pKth ; ) {
      NODE* pSave = pCurr->pNext ;
      pCurr->pNext = pCurr->pPrev ;
      pCurr->pPrev = pSave ;
      pCurr = pSave ;
   }
  // sistemo gli estremi
   pFirst->pNext = pKth->pNext ;
   pKth->pNext->pPrev = pFirst ;
   pKth->pNext = pKth->pPrev ;
   pKth->pPrev = pLast ;
   pLast->pNext = pKth ;
   pFirst = pLast->pNext ;
   pKth = pFirst->pNext ;
}

// ----------------------------------------------------------------------------
long long unsigned
ShortestPath::TwoOpt( NODE* pPath)
{
   const int MAX_TRY = 2048 ;
   unsigned nTry = 1 ;
   unsigned nCount = 1 ;
   NODE* pFirst = pPath ;
   NODE* pFirstDep = m_pCheckDep ;
   do {
      NODE* pLast = pFirst->pPrev ;
      NODE* pKth = pFirst->pNext ;
      NODE* pLastDep = pFirstDep->pPrev ;
      NODE* pKthDep = pFirstDep->pNext ;
      do {
        // se non esistono dipendenze suggerite
         if ( ! ExistSuggDependences()) {
           // lunghezza originale dei tratti da scambiare
            unsigned nEXIST = ArcCost( pLast->nPos, pFirst->nPos) +
                     ArcCost( pKth->nPos, pKth->pNext->nPos) ;
           // nuova lunghezza dei tratti da scambiare
            unsigned nTEST = ArcCost( pFirst->nPos, pKth->pNext->nPos) +
                    ArcCost( pLast->nPos, pKth->nPos) ;
           // lunghezze originali e nuova del tratto intermedio che viene invertito
            for ( NODE* pCurr = pFirst ; pCurr != pKth ; pCurr = pCurr->pNext) {
               nEXIST += ArcCost( pCurr->nPos, pCurr->pNext->nPos) ;
               nTEST += ArcCost( pCurr->pNext->nPos, pCurr->nPos) ;
            }
           // se lo scambio fa risparmiare
            if ( nTEST < nEXIST) {
              // se non esistono vincoli, effettuo i cambi
               if ( ! ExistConstraints()) {
                  SwapNodesForTwoOpt( pFirst, pKth, pLast) ;
                  nCount = 0 ;
               }
              // se esistono i vincoli
               else {
                 // copio il Path e i puntatori sul Path di test per le dipendenze
                  CopyPathAdv( pPath, m_pCheckDep, pLast, pFirst, pKth, &pLastDep, &pFirstDep, &pKthDep) ;
                 // effettuo i cambi dei nodi sul path di test per le dipendenze
                  SwapNodesForTwoOpt( pFirstDep, pKthDep, pLastDep) ;
                 // se il path di test rispetta i vincoli, allora effettuo i cambi sul percorso vero
                  if ( IsPathRespectingContraints( m_pCheckDep)) {
                     SwapNodesForTwoOpt( pFirst, pKth, pLast) ;
                     nCount = 0 ;
                  }
                 // altrimenti passo al nodo successivo
                  else
                     pKth = pKth->pNext ;
               }
            }
            // altrimenti passo al nodo successivo
            else
               pKth = pKth->pNext ;
         }
        // se esistono dipendenze suggerite
         else {
            CopyPathAdv( pPath, m_pCheckDep, pLast, pFirst, pKth, &pLastDep, &pFirstDep, &pKthDep) ;
            SwapNodesForTwoOpt( pFirstDep, pKthDep, pLastDep) ;
            if ( IsPathRespectingContraints( m_pCheckDep)) {
               unsigned long long nEXIST = TotalCost( pPath) ;
               unsigned long long nTEST = TotalCost( m_pCheckDep) ;
               if ( nTEST < nEXIST) {
                  SwapNodesForTwoOpt( pFirst, pKth, pLast) ;
                  nCount = 0 ;
               }
               // altrimenti passo al nodo successivo
               else
                  pKth = pKth->pNext ;
            }
           // altrimenti passo al nodo successivo
            else
               pKth = pKth->pNext ;
         }
      } while ( pKth != pLast->pPrev->pPrev  &&  nCount != 0) ;
      if ( nCount != 0)
         pFirst = pFirst->pNext ;
      nCount ++ ;
      nTry ++ ;
   } while ( nCount < m_nNumPnts  &&  nTry < MAX_TRY) ;

  // ricalcolo il costo del percorso
   return TotalCost( pPath) ;
}