/*
   * ASCLITE
   * Author: Jerome Ajot, Jon Fiscus, Nicolas Radde, Chris Laprun
   *
   * This software was developed at the National Institute of Standards and Technology by 
   * employees of the Federal Government in the course of their official duties. Pursuant
   * to title 17 Section 105 of the United States Code this software is not subject to
   * copyright protection and is in the public domain. ASCLITE is an experimental system.
   * NIST assumes no responsibility whatsoever for its use by other parties, and makes no
   * guarantees, expressed or implied, about its quality, reliability, or any other
   * characteristic. We would appreciate acknowledgement if the software is used.
   *
   * THIS SOFTWARE IS PROVIDED "AS IS."  With regard to this software, NIST MAKES NO EXPRESS
   * OR IMPLIED WARRANTY AS TO ANY MATTER WHATSOEVER, INCLUDING MERCHANTABILITY,
   * OR FITNESS FOR A PARTICULAR PURPOSE.
   */
   
  #ifndef GRAPH_H
  #define GRAPH_H
  
  #include "stdinc.h"
  
  #include "token.h"
  #include "segment.h"
  #include "graphalignedtoken.h"
  #include "graphalignedsegment.h"
  #include "segmentsgroup.h"
  #include "logger.h"
  
  #include "linestyle_inputparser.h"
  #include "graph_coordinate.h"
  #include "arraylevenshteinmatrix.h"
  #include "compressedlevenshteinmatrix.h"
  #include "speakermatch.h"
  
  /**
   * Inplementation of the Levenshtein Distance Algorithm in Multi-Dimension
   */
  class Graph
  {
      // Members
  	private:
  		
  		/**
  		 * Database for the optimization speaker alignment 
  		 */
  		SpeakerMatch* m_pSpeakerMatch;
  		
  		int m_typeCostModel; // 1: regular levenshtein
  							 // 2: time based
  
          int m_CostTransition;		
  		/** Cost Insertion and Deletion */
          int m_CostInsertion;
  		/** Cost Optionally Insertion and Deletion */
          int m_CostOptionally;
          /** Cost for Correct but not in the same speaker */
          int m_CostCorrectNonSpeaker;
  		/** Cost for Adaptive */
          int m_CostAdaptive;
          /** process or not optionnaly token for reference */
          bool m_useOptForRef;
          /** process or not optionnaly token for hypothesis */
          bool m_useOptForHyp;
          /** Number of dimension */
          bool m_bCompressedArray;
  		/** Cost Transition */
  		size_t m_Dimension;
  		/** Deep for each dimension, deep is the number of element on the dimension */
  		size_t* m_TabDimensionDeep;
  		/** Position of the first ref into the dimension array
  		 *  H ... H R R .... R
  		 *          ^
  	     *     m_IndexRef
  	     */		
  		size_t m_IndexRef;
  		/**
  		 *  true: not using optimization for Hyp and Ref cost computation
  		 *  false: using optimization for Hyp and Ref cost computation
  		 */
  		bool m_HypRefStatus;
  		
          
  		/** map associating nodes (via their coordinates) to cost */
  		LevenshteinMatrix* m_MapCost;
  		
  		/** Array of Hyps and Refs */
  		vector<Token*>* m_TabVecHypRef;
  		/** Map token to index into vector */
  		map<Token*, size_t>* m_TabMapTokenIndex;
          /** List of first tokens of the segments */
  		list<Token*>* m_TabFirstTokens;
  		/** List of last tokens of the segments */
  		list<Token*>* m_TabLastTokens;
  		/** Optimization for the graph */
  		bool m_bPruneOptimization;
  		bool m_bWordOptimization;
  		bool m_bSpeakerOptimization;
  		bool m_bAdaptiveCostOptimization;
  		bool m_bWordAlignCostOptimization;
  		
  		/** optimization gap */
  		int m_PruneOptimizationThreshold;
  		/** optimization Insert/Del */
  		int m_WordOptimizationThreshold;
  		
  		int m_EstimatedMaxCost;
  		
  		int m_MaxDurationSegmentGroup;
          
          /** Logger */
  		static Logger* logger;
          
          // Caching
          /** Caching for transition cost */
          list<size_t>*** m_TabCacheDimPreviousIndex;
  
  		int m_TimeBasedSafeDivider;
  		
  		size_t m_NbThreads;
          
      // Methods
  	public:
          /** Constructor */
  		Graph() {}
  		/** Constructor with the number of dimension */
  		Graph(SegmentsGroup* _segmentsGroup, SpeakerMatch* _pSpeakerMatch, const int& _typeCost, const int& _costTrans, const int& _costIns, const int& _costOpt, const int& _costCorrectNonSpeaker, const int& _costAdaptive, const bool& _optIns, const bool& _optDel, const bool& _bCompressedArray);
  		/** Destructor */
  		~Graph();
  		
  		/** Set the deep of one dimension */
  		void SetDimensionDeep(const size_t& dim, const size_t& deep);
  		/** Set the position of the first ref */
  		void SetIndexRef(const size_t& ind);
  		/** Set the dimension */
  		void SetDimension(const size_t& dim);
  	
          /** Returns the deep of one dimension */
  		size_t GetDimensionDeep(const size_t& d) { return m_TabDimensionDeep[d]; }
  		/** Returns the number of dimensions */
  		size_t GetDimension() { return m_Dimension; }
  		
  		/** Return true if the dimension is a reference, false if not */
  		bool IsReference(const size_t& dim) { return(dim >= m_IndexRef); }
  		/** Return true if the dimension is a hypothesis, false if not */
  		bool IsHypothesis(const size_t& dim) { return(dim < m_IndexRef); }
  		
  		// Debug methods
  		/** Size of the map */
  		size_t SizeMap() { return m_MapCost->GetNumberOfCalculatedCosts(); }
  		
  		/** returns cost of insertion */
  		int GetCostInsertion(const bool& optionally) { return optionally ? m_CostOptionally : m_CostInsertion; }
  		/** returns cost of transition */
  		int GetCostTransition() { return m_CostTransition; }
  		int GetCostTransitionWordBased(Token* pToken1, Token* pToken2);
  		int GetCostTransitionTimeBased(Token* pToken1, Token* pToken2);
  		
  		int GetCostAdaptive(Token* pToken1, Token* pToken2);
  		
  		int GetCostWordAlign(Token* pToken1, Token* pToken2);
  		
  		/** Calculate the cost for the coordinate */
          int CalculateCost(size_t* curcoord);
  		
  		/** Fill the graph with cost */
  		void FillGraph();
  		
  		/** Return the best (min) cost at the end of the graph */
  		int GetBestCost();
  		
  		/** Returns the alignment */
  		GraphAlignedSegment* RetrieveAlignment();
  		
  		/** Print the Levenshtein array */
  		void PrintLevenshteinArray();
  		
  	private:
  		/** Create the list of starting coordinates */
  		void StartingCoordinates(GraphCoordinateList& listStart);
  	
  		/** is the one of the last possible coordinates ? */
  		bool isEndingCoordinate(size_t* coord);
  	
  		/** List the previous coordinates */
  		void PreviousCoordinates(GraphCoordinateList& listPrev, size_t* coord) { m_HypRefStatus ? PreviousCoordinatesHypRef(listPrev, coord) : PreviousCoordinatesGeneric(listPrev, coord); }
  		/** List the previous coordinates optimized for Hyp-Ref constraints */
  		void PreviousCoordinatesHypRef(GraphCoordinateList& listPrev, size_t* coord);
  		/** List the previous coordinates generic way to compute */
  		void PreviousCoordinatesGeneric(GraphCoordinateList& listPrev, size_t* coord);
  	
          /** returns the list of previous indexes */
  		void PreviousIndexes(list<size_t>& listPrev, const size_t& dim, const size_t& index);
  		
  		/** returns the cost between 2 coordinates */
  		int GetTransitionCost(size_t* coordcurr, size_t* coordprev) { return m_HypRefStatus ? GetTransitionCostHypRef(coordcurr, coordprev) : GetTransitionCostGeneric(coordcurr, coordprev); }
  		/** returns the cost between 2 coordinates for Hyp-Ref constraints */
  		int GetTransitionCostHypRef(size_t* coordcurr, size_t* coordprev);
  		/** returns the cost between 2 coordinates generic way to compute */
  		int GetTransitionCostGeneric(size_t* coordcurr, size_t* coordprev);
  		
  		int GetTransitionCostHypRefWordBased(size_t* coordcurr, size_t* coordprev);
  		int GetTransitionCostGenericWordBased(size_t* coordcurr, size_t* coordprev);
  		int GetTransitionCostHypRefTimeBased(size_t* coordcurr, size_t* coordprev);
  		int GetTransitionCostGenericTimeBased(size_t* coordcurr, size_t* coordprev);
  		
  		
  		/** Returns the best previous coordinate */
  		size_t* GetBestCoordinateAndCost(size_t* coordcurr);
  		
  		/** Check if the Hyp or Ref is empty */
  		bool isHypRefEmpty(const size_t& hr) { return(m_TabLastTokens[hr].empty()); }
  		
  		/** Returns the number of coordinates which have changed */
  		size_t NumberChanged(size_t* coord1, size_t* coord2);
  		
  		/** returns true if the transition/Insertion/Deletion is allowed */
  		bool ValidateTransitionInsertionDeletion(size_t* coordcurr, size_t* coordprev);
  		
  		/** Use the optimization */
  		void SetGraphOptimization();
  		
  //		bool isMultiThreaded() { return(m_NbThreads>1); }
  };
  
  #endif