treeBalancer.h

Go to the documentation of this file.

/*********************************************************************
** Copyright (c) 2001 MAK Technologies, Inc.
** All rights reserved.
*********************************************************************/
/*********************************************************************
** $RCSfile: treeBalancer.h,v $ $Revision: 1.11 $ $State: Exp $
*********************************************************************/
#ifndef treeBalancer_H_
#define treeBalancer_H_

#include "gdb/gdbDefines.h"
#include "gdb/gdbNode.h"
#include "geometry/extent.h"
#include <vlutil/vlConfig.h>
#include <vector>

// forward declarations
class DtGroup;
class DtBaseCoordinateSystem;

//
// DtTreeBalancer defines a tool for balancing GDB node trees.
class DT_DLL_gdb DtTreeBalancer 
{
public:
   typedef std::vector<DtGdbNode*> DtNodeContainer;
   typedef DtNodeContainer::iterator DtNodeIterator;
   typedef DtNodeContainer::const_iterator DtNodeConstIterator;


   // default constructor
   DtTreeBalancer();

   // constructor with max number of children
   DtTreeBalancer(unsigned int maxChildren);

   // constructor with max branching and maximum number of leaves
   DtTreeBalancer(unsigned int maxBranching, unsigned int maxNumLeaves);

   // destructor
   virtual ~DtTreeBalancer();

   // copy constructor
   DtTreeBalancer(const DtTreeBalancer& orig);

   // assignment operator
   DtTreeBalancer& operator=(const DtTreeBalancer& orig);

   // This method returns a balanced tree corresponding to the group.  It
   // uses the original leaves and builds a tree using new groups.  The groups
   // in the old tree are purged.
   virtual DtGroup* balanceGroupAndPurge(DtGroup* originalGroup);

   // This method returns a balanced tree corresponding to the group.  It
   // uses the original leaves and builds a tree using new groups.  The old
   // tree is left intact.
   virtual DtGroup* balanceGroup(DtGroup* originalGroup);

   // Get/set maximum branching
   virtual void setMaxBranching(unsigned int value);
   virtual unsigned int maxBranching() const;

   // Get/set maximum number of leaves
   virtual void setMaxNumLeaves(unsigned int value);
   virtual unsigned int maxNumLeaves() const;

protected:

   // The following method adds all the GDB nodes in a list to group
   virtual void addNodesToGroup(const DtNodeContainer& nodeContainer, DtGroup& group) const;

   // The following prints out extents for debugging
   virtual void printExtents(const DtNodeContainer& nodeContainer) const;

   // Pack the nodes in the *from* list into the *to* list with at
   // most groupSize nodes in each package.
   virtual void packNodes(DtNodeContainer& toContainer, 
      DtNodeContainer& fromContainer, 
      unsigned int groupSize) const;

   // the following finds the node in a container of nodes that minimally 
   // increases the x-y area of the extent of a separate node.
   virtual void findBestNode(DtGdbNode* comparator, DtNodeContainer& nodeContainer, 
      double& cost, DtGdbNode*& bestNode) const;

   // the following finds the north-west-most node in a list 
   // increases the x-y area of the extent of a separate node.
   virtual DtGdbNode* findNorthWestNode(DtNodeContainer& nodeContainer) const;

   // the following balances the tree beneath each coordinate system
   // in a list of coordinate systems. 
   virtual void balanceCoordinateSystems(DtGdbNode::DtFoundInstancesContainer& nodeInstances);

   // Balances the tree beneath a coordinate system node.
   virtual void balanceCoordinateSystemNode(DtBaseCoordinateSystem* coordSys);

protected:

   unsigned int myMaxBranching;
   unsigned int myMaxNumLeaves;
   bool myPurgeFlag;
   DtExtent myExtent;

   static const unsigned int groupSizeMultiplier;
};

#endif