/*********************************************************
** Copyright (c) 2005
** University of Washington
** Licensed under the terms set forth by University of
** Washington. If you did not sign such a license, you
** are using this software/code illegally and you do not
** have permission to use, modify, or redistribute
** this or any files in this software package.
**
** File: OptimalOrdering.h
**
**********************************************************/
#ifndef OPTIMALORDERING_H
#define OPTIMALORDERING_H

#include "Ordering.h"
#include "ClusterNode.h"
#include "CostMap.h"
#include <map>

using namespace std;

/* Class that does optimal leaf ordering on clustering data */
class COptimalOrdering : public COrdering
{
 public:
  COptimalOrdering();
  virtual ~COptimalOrdering();

  void OrderLeaves(CClusterNode* pCluster, CMatrix* pDistances);
  uintmax_t GetMemoryRequirement(CClusterNode* pCluster, CMatrix* pDistances);

 private:
  void CreateInternals(CClusterNode* pRoot, CMatrix* pDistances);
  void DeleteInternals();

  void SetCost(CClusterNode* u, CClusterNode* w, double cost);
  void SetCost(int uIndex, int wIndex, double cost);
  double GetCost(CClusterNode* u, CClusterNode* w);
  double GetCost(int uIndex, int wIndex);

  CClusterNode* GetBestWforU(CClusterNode* pCluster, CClusterNode* u);
  CClusterNode* GetBestUforW(CClusterNode* pCluster, CClusterNode* w);

  void ComputeCosts(CClusterNode* pCluster);
  void _ComputeCost(int uIndex, int wIndex, CCostMap* pMapM, CCostMap* pMapK, double C);

  void GetBestPair(CClusterNode* pRoot, CClusterNode** ppU, CClusterNode **ppW);
  void Backtrack(CClusterNode* pCluster, CClusterNode* u, CClusterNode* w);
  void BacktrackDescendLeft(CClusterNode* pCluster, CClusterNode* u);
  void BacktrackDescendRight(CClusterNode* pCluster, CClusterNode* w);

 private: //data members
  double** m_ppCosts;
  int m_iLeafCount;
  CClusterNode* m_pNode;
  CMatrix* m_pDistances;
  int m_iNodeCount, m_iNodeTracker, m_iNodeTrackerMax; // used for DoCallback in recursive functions
};

#endif

