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

static void
SwapNodesForPntOpt( NODE* pFirst, NODE* pLast, NODE* pBest)
{
   pFirst->pPrev = pLast->pPrev ;
   pLast->pPrev->pNext = pFirst ;
   pLast->pPrev = pBest ;
   pLast->pNext = pBest->pNext ;
   pBest->pNext = pLast ;
   pLast->pNext->pPrev = pLast ;
}

/* ------------------------------------------------------------------------- */
long long unsigned
ShortestPath::PointOpt( NODE* pPath)
{
  // ciclo di tentativi di spostamento di un punto
   unsigned nCount = 1 ;
   NODE* pFirst = pPath ;
   NODE* pFirstDep = m_pCheckDep ;
   do {
      unsigned nBestImprove = 0 ;
      NODE* pBest = nullptr ;
      NODE* pLast = pFirst->pPrev ;
      NODE* pLastDep = pFirstDep->pPrev ;
      NODE* pKthDep = pFirstDep ;
      for ( NODE* pKth = pFirst ; pKth != pLast->pPrev->pPrev ; pKth = pKth->pNext) {
        // se non esistono dipendenze suggerite
         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 ( ! ExistSuggDependences()) {
            if ( nTEST < nEXIST  &&  ( nEXIST - nTEST) > nBestImprove) {
              // nel caso di assenza di dipendenze
               if ( ! ExistConstraints()) {
                  nBestImprove = nEXIST - nTEST ;
                  pBest = pKth ;
               }
              // nel caso di dipendenze
               else {
                  CopyPathAdv( pPath, m_pCheckDep, pLast, pFirst, pKth, &pLastDep, &pFirstDep, &pKthDep) ;
                  SwapNodesForPntOpt( pFirstDep, pLastDep, pKthDep) ;
                  if ( IsPathRespectingContraints( m_pCheckDep)) {
                     nBestImprove = nEXIST - nTEST ;
                     pBest = pKth ;
                  }
               }
            }
         }
        // se esistono dipendenze suggerite
         else {
            CopyPathAdv( pPath, m_pCheckDep, pLast, pFirst, pKth, &pLastDep, &pFirstDep, &pKthDep) ;
            SwapNodesForPntOpt( pFirstDep, pLastDep, pKthDep) ;
            if ( IsPathRespectingContraints( m_pCheckDep)) {
               int nBreak ;
               IsPathRespectingSuggestedDependences( pPath, nBreak) ;
               nEXIST += m_nMaxDistSuggDep * nBreak ;
               IsPathRespectingSuggestedDependences( m_pCheckDep, nBreak) ;
               nTEST += m_nMaxDistSuggDep * nBreak ;
               if ( nTEST < nEXIST  &&  ( nEXIST - nTEST) > nBestImprove) {
                  nBestImprove = nEXIST - nTEST ;
                  pBest = pKth ;
               }
            }
         }
      }
      if ( nBestImprove == 0) {
         pFirst = pFirst->pNext ;
         nCount ++ ;
      }
      else {
         SwapNodesForPntOpt( pFirst, pLast, pBest) ;
         nCount = 1 ;
      }
   } while ( nCount < m_nNumPnts) ;

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