//----------------------------------------------------------------------------
//  EgalTech 2015-2015
//----------------------------------------------------------------------------
// File : ShortestPath.h      Data : 22.12.15        Versione : 1.6l3
// Contenuto : Classe per calcolo del percorso minimo di visita di 
//             un insieme di oggetti.
//
//
// Modifiche : 22.12.15 DS Creazione modulo.
//
//
//----------------------------------------------------------------------------

#pragma once

#include "/EgtDev/Include/ENkShortestPath.h"

//----------------------------------------------------------------------------
#define MAXDIST         1073741823U    // 2^30 - 1 per evitare overflow 

//----------------------------------------------------------------------------
struct SpPoint {
   double dXi ;
   double dYi ;
   double dZi ;
   double dHi ;
   double dVi ;
   double dXf ;
   double dYf ;
   double dZf ;
   double dHf ;
   double dVf ;
} ;

struct OpenBound {
   int    nF ;
   double dX ;
   double dY ;
   double dZ ;
   double dH ;
   double dV ;
} ;

struct NODE {
   NODE*    pPrev ;
   unsigned nPos ;
   NODE*    pNext ;
} ;

//----------------------------------------------------------------------------
class ShortestPath : public IShortestPath
{
   public :
      ~ShortestPath( void) override ;
      bool AddPoint( double dX, double dY) override ;
      bool AddPoint( double dXi, double dYi, double dXf, double dYf) override ;
      bool AddPoint( double dXi, double dYi, double dZi, double dHi, double dVi,
                     double dXf, double dYf, double dZf, double dHf, double dVf) override ;
      bool SetOpenBound( bool bStartVsEnd, int nFlag, double dX, double dY) override ;
      bool SetOpenBound( bool bStartVsEnd, int nFlag, double dX, double dY, double dZ, double dH, double dV) override ;
      bool SetAngularParams( double dAngHAdd, double dAngHMul, double dAngVAdd, double dAngVMul) override ;
      bool SetZzOwStep( double dStep) override ;
      bool Calculate( int nType) override ;
      bool GetOrder( INTVECTOR& vOrder) override ;
      bool GetMinLength( double& dMinLen) override ;

   public :
      ShortestPath( void) ;

   private :
      bool Tsp( void) ;
      bool CalculateImprovements( NODE* pPath) ;
      void CalcDistances( void) ;
      unsigned GetDistance( float dDx, float dDy, float dDz, float dDh, float dDv) ;
      void PreparePath( NODE* pPath) ;
      void SavePath( NODE* pPath) ;
      void RestorePath( NODE* pPath) ;
      long long unsigned TotalCost( NODE* pPath) ;
      void UpdateOrder( NODE* pPath) ;
      unsigned Index( unsigned i, unsigned j)
                  { return ( i * m_nNumPnts + j) ; }
      unsigned ArcCost( unsigned i, unsigned j)
                  { return m_Dists[ Index( i, j)] ; }
      long long unsigned NearNeighbor( void) ;
      unsigned CheapArc( unsigned i) ;
      long long unsigned FarNeighbor( void) ;
      unsigned HighArc( unsigned i) ;
      long long unsigned PointOpt( NODE* pPath) ;
      long long unsigned TwoOpt( NODE* pPath) ;
      long long unsigned Hybrid( NODE* pPath) ;
      bool ZigZag( void) ;
      long long unsigned TotalCost( void) ;

   private :
      static const int MAX_SPPS = 32766 ;   // 2^15-2 per evitare problemi nell'allocazione di m_Dists a 32bit 

   private :
      int       m_nType ;
      bool      m_bSolved ;
      float     m_dAngHAdd ;
      float     m_dAngHMul ;
      float     m_dAngVAdd ;
      float     m_dAngVMul ;
      float     m_dStep ;
      unsigned  m_nNumPnts ;
      SpPoint   m_Points[MAX_SPPS+1] ;
      unsigned  m_nOrder[MAX_SPPS+1] ;
      OpenBound m_ObStart ;
      OpenBound m_ObEnd ;
      unsigned* m_Dists ;
      bool*     m_Available ;
      NODE*     m_pMain ;
      NODE*     m_pDupl ;
      long long unsigned  m_nTotMin ;
      long long unsigned  m_nMinCost ;
} ;