/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkConeLayoutStrategy.h

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

  This software is distributed WITHOUT ANY WARRANTY; without even
  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  PURPOSE.  See the above copyright notice for more information.

=========================================================================*/
//-------------------------------------------------------------------------
//Copyright 2008 Sandia Corporation.
//Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
//the U.S. Government retains certain rights in this software.
//-------------------------------------------------------------------------

// .NAME vtkConeLayoutStrategy - produce a cone-tree layout for a forest
// .SECTION Description
// vtkConeLayoutStrategy positions the nodes of a tree(forest) in 3D 
// space based on the cone-tree approach first described by 
// Robertson, Mackinlay and Card in Proc. CHI'91.  This
// implementation incorporates refinements to the layout 
// developed by Carriere and Kazman, and by Auber.
//
// The input graph must be a forest (i.e. a set of trees, or a 
// single tree); in the case of a forest, the input will be
// converted to a single tree by introducing a new root node, 
// and connecting each root in the input forest to the meta-root. 
// The tree is then laid out, after which the meta-root is removed.  
//
// The cones are positioned so that children lie in planes parallel
// to the X-Y plane, with the axis of cones parallel to Z, and
// with Z coordinate increasing with distance of nodes from the root.
//
// .SECTION Thanks
// Thanks to David Duke from the University of Leeds for providing this 
// implementation.


#ifndef __vtkConeLayoutStrategy_h
#define __vtkConeLayoutStrategy_h

#include "vtkGraphLayoutStrategy.h"

class vtkPoints;

class VTK_INFOVIS_EXPORT vtkConeLayoutStrategy : public vtkGraphLayoutStrategy 
{
public:
  static vtkConeLayoutStrategy *New();

  vtkTypeRevisionMacro(vtkConeLayoutStrategy, vtkGraphLayoutStrategy);
  void PrintSelf(ostream& os, vtkIndent indent);

  // Description:
  // Determine the compactness, the ratio between the
  // average width of a cone in the tree, and the 
  // height of the cone.  The default setting is 0.75
  // which (empirically) seems reasonable, but this
  // will need adapting depending on the data.
  vtkSetMacro(Compactness, float);
  vtkGetMacro(Compactness, float);

  // Description:
  // Determine if layout should be compressed, i.e. the 
  // layout puts children closer together, possibly allowing
  // sub-trees to overlap.  This is useful if the tree is 
  // actually the spanning tree of a graph.  For "real" trees, 
  // non-compressed layout is best, and is the default.
  vtkSetMacro(Compression, int);
  vtkGetMacro(Compression, int);
  vtkBooleanMacro(Compression, int);

  // Description:
  // Set the spacing parameter that affects space between
  // layers of the tree.  If compression is on, Spacing is the
  // actual distance between layers.  If compression is off, 
  // actual distance also includes a factor of the compactness
  // and maximum cone radius.
  vtkSetMacro(Spacing, float);
  vtkGetMacro(Spacing, float);


  // Description:
  // Perform the layout.
  void Layout();
  
protected:
  vtkConeLayoutStrategy();
  ~vtkConeLayoutStrategy();

  // Description:
  // Helper operations for tree layout.  Layout is performed
  // in two traversals of the tree.  The first traversal finds
  // the position of child nodes relative to their parent. The
  // second traversal positions each node absolutely, working
  // from the initial position of the root node.

  double LocalPlacement(vtkIdType root, vtkPoints *points);
            
  void GlobalPlacement(
    vtkIdType root,
    vtkPoints *points,
    double refX,         // absolute x-y coordinate of
    double refY,         // parent node; z coordinate
    double level );      // derived from level.

  float Compactness;     // factor used in mapping layer to Z
  int   Compression;     // force a compact layout?
  float Spacing;         // Scale vertical spacing of cones.

  // Values accumulated for possible statistical use
  double MinRadius;
  double MaxRadius;
  int   NrCones;
  double SumOfRadii;
  
private:
  vtkConeLayoutStrategy(const vtkConeLayoutStrategy&);  // Not implemented.
  void operator=(const vtkConeLayoutStrategy&);  // Not implemented.
};

#endif

