//----------------------------------------------------------------------------
//  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"

// ----------------------------------------------------------------------------
long long unsigned
ShortestPath::TwoOpt( NODE* pPath)
{
   const int MAX_TRY = 2048 ;
   unsigned nTry = 1 ;
   unsigned nCount = 1 ;
   NODE* pFirst = pPath ;
   do {
      NODE* pLast = pFirst->pPrev ;
      NODE* pKth = pFirst->pNext ;
      do {
        // 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) {
           // 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 ;
           // faccio ripartire il conto
            nCount = 0 ;
         }
        // 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) ;
}