//-*-c++-*-
#ifndef _TreeReingoldOrhto_H
#define _TreeReingoldOrhto_H
#include <string>
#include <list>
#include <math.h> 
#include <tulip/TulipPlugin.h>

using namespace std;

struct LR {
  double L;
  double R;
};

/// TreeReingoldOrthogonal - An implementation of a orthogonal hierarchical tree layout.(left to right)
/** This plugin is an implementation of the hierarchical tree layout
 *  algorithm first published as:
 *
 *  E.M. Reingold and J.S. Tilford,
 *  "Tidier Drawings of Trees",
 *  "IEEE Transactions on Software Engineering"
 *  pages "223--228"
 *  1981
 *
 *  HISTORY:
 *
 *  06/12/2002 Verson 0.0.1: Initial release 
 *
  *
 *  NOTES:
 *
 *  This algorithm only work on trees.
 *  Let n be the number of nodes, the algorithm complexity is in O(n).
 *
 *  AUTHOR:
 *
 *  David Auber University Bordeaux I France: Email:auber@tulip-software.com
 *
 *  LICENCE:
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by  
 *  the Free Software Foundation; either version 2 of the License, or     
 *  (at your option) any later version.
 *
 */
class TreeReingoldOrhto:public Layout { 

public:
  TreeReingoldOrhto(PropertyContext *);
  ~TreeReingoldOrhto();
  
  bool run();
  bool check(std::string &);
  void reset();


private:
  void calcLayout(node, STL_EXT_NS::hash_map<node,double> *,double, double, int ,std::map<int,double> &);
  double  calcDecal(const std::list<LR>& , const std::list<LR>&);
  list<LR>* mergeLRList(std::list<LR>*,std::list<LR>*,double decal);
  list<LR>* TreePlace(node, STL_EXT_NS::hash_map<node,double>*);
  void TreeLevelSizing(node n,std::map<int,double> &maxSize,int level,std::map<node,int> &levels);
  SizesProxy *sizesProxy;
};

#endif