//----------------------------------------------------------------------------
//  EgalTech 2015-2015
//----------------------------------------------------------------------------
// File : PntOpt.cpp        Data : 22.12.15        Versione : 1.6l4
// Contenuto : Miglioramento del percorso spostando un punto per volta.
//
//                 K  Last  L-1         K  Last  L-1
//                 o  o-----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::PointOpt( NODE* pPath)
{
  // ciclo di tentativi di spostamento di un punto
   unsigned nCount = 1 ;
   NODE* pFirst = pPath ;
   do {
      unsigned nBestImprove = 0 ;
      NODE* pBest = nullptr ;
      NODE* pLast = pFirst->pPrev ;
      for ( NODE* pKth = pFirst ; pKth != pLast->pPrev->pPrev ; pKth = pKth->pNext) {
         unsigned nEXIST = ArcCost( pLast->pPrev->nPos, pLast->nPos) +
                           ArcCost( pLast->nPos, pFirst->nPos) +
                           ArcCost( pKth->nPos, pKth->pNext->nPos) ;
         unsigned nTEST  = ArcCost( pLast->pPrev->nPos, pFirst->nPos) +
                           ArcCost( pKth->nPos, pLast->nPos) +
                           ArcCost( pLast->nPos, pKth->pNext->nPos) ;
         if ( nTEST < nEXIST  &&  ( nEXIST - nTEST) > nBestImprove) {
            nBestImprove = nEXIST - nTEST ;
            pBest = pKth ;              
         }
      }
      if ( nBestImprove == 0) {
         pFirst = pFirst->pNext ;
         nCount ++ ;
      } 
      else {
         pFirst->pPrev = pLast->pPrev ;
         pLast->pPrev->pNext = pFirst ;
         pLast->pPrev = pBest ;
         pLast->pNext = pBest->pNext ;
         pBest->pNext = pLast ;
         pLast->pNext->pPrev = pLast ;
         nCount = 1 ;
      }
   } while ( nCount < m_nNumPnts) ;

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