pointQTree.h

Go to the documentation of this file.

/*********************************************************************
** Copyright (c) 2001 MAK Technologies, Inc.
** All rights reserved.
*********************************************************************/
/*********************************************************************
** $RCSfile: pointQTree.h,v $ $Revision: 1.12 $ $State: Exp $
*********************************************************************/
// \file pointQTree.h 
// \brief Contains the DtPointQuadTreeNode class definition.

#ifndef pointQTree_H_
#define pointQTree_H_

#include "gdb/gdbDefines.h"
#include <stdio.h>
#include <vlutil/vlNetTypes.h>
#include <vlutil/vlConfig.h>
#include <list>

class DtNetworkNode;
class DtNetworkNodeMetric;

//
// DtPointQuadtreeNode is a node for a point quadtree.
class DT_DLL_gdb DtPointQuadtreeNode
{
public:

   // default constructor 
   DtPointQuadtreeNode();

   // constructor with network node
   DtPointQuadtreeNode(DtNetworkNode* networkNode);

   // destructor
   virtual ~DtPointQuadtreeNode();

private:

   // copy constructor (not implemented)
   DtPointQuadtreeNode(const DtPointQuadtreeNode& orig);

   // assignment operator (not implemented)
   DtPointQuadtreeNode& operator=(const DtPointQuadtreeNode& orig);

public:

   typedef std::list<const DtNetworkNode*> DtPtrConstNodeContainer;
   typedef DtPtrConstNodeContainer::const_iterator DtPtrConstNodeConstIter;
   typedef DtPtrConstNodeContainer::iterator DtPtrConstNodeIter;

   typedef std::list<DtNetworkNode*> DtPtrNodeContainer;
   typedef DtPtrNodeContainer::const_iterator DtPtrNodeConstIter;
   typedef DtPtrNodeContainer::iterator DtPtrNodeIter;

   // add a new network node (the lower and left boundaries in
   // each quad are closed)
   virtual void add(DtNetworkNode& newNetworkNode);

   // collect all nodes that are validated by the metric
   virtual void collectAllNodes(const DtNetworkNodeMetric& metric, 
      DtPtrConstNodeContainer& collectedNodes) const;
   virtual void collectAllNodes(const DtNetworkNodeMetric& metric, 
      DtPtrNodeContainer& collectedNodes);

   // find the best valid node in the tree as measured by the metric
   virtual const DtNetworkNode* findBestNode(const DtNetworkNodeMetric& metric) const;

   // resets the state of the quadtree to an empty, initial state.
   // (same as state resulting from *default constructor*)
   virtual void clear();

   virtual int size() const;

   virtual int sizeInBytes() const;

protected:

   // Adds the node to the specified quadrant.  If the quadrant is 0, then it is
   // allocated with the node as the construction parameter.
   void addToQuadrant(DtPointQuadtreeNode*& quadrant, DtNetworkNode& element);

   // find the best valid node in a subtree. pointer best must be valid.  Using
   // this prevents the metric from being re-evaluated on the same node.
   virtual const DtNetworkNode* findBestInSubtree(const DtNetworkNodeMetric& metric,
                                                  double& bestCost) const;
   
protected:

   DtNetworkNode*         myElement;
   DtPointQuadtreeNode*   mySW;
   DtPointQuadtreeNode*   mySE;
   DtPointQuadtreeNode*   myNE;
   DtPointQuadtreeNode*   myNW;
};

#endif