//-*-c++-*-
#ifndef _TreeReingoldAndTilford_H
#define _TreeReingoldAndTilford_H
#include <string>
#include <cmath> 
#include <tulip/TulipPlugin.h>

struct LR {
  int L;
  int R;
  unsigned int size;
};

/// TreeReingoldAndTilford - An implementation of a hierarchical tree layout.
/** 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:
 *
 *  21/02/2000 Verson 0.0.1: Initial release 
 *
 *  06/11/2002 Verson 0.0.2: Documentation and code clean up
 *
 *  06/01/2003 Verson 0.0.3: Remove dummy nodes when using edge length. Conform with
 *                           the algorithm presented in "Graph Drawing Software book".
 *
 *  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.org
 *
 *  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 TreeReingoldAndTilford:public Layout { 

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

private:

  void calcLayout(node ,IntProxy *,int, int);
  int  calcDecal(const std::list<LR>& , const std::list<LR>&);
  std::list<LR>* mergeLRList(std::list<LR>*,std::list<LR>*,int decal);
  std::list<LR>* TreePlace(node,IntProxy *);
  IntProxy *lengthMetric;
};

#endif