segMxCifTree.h

Go to the documentation of this file.

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

// \file segMxDifTree.h
// \brief Contains the DtSegmentMxCifTree class declaration.

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

class DtNetworkSegment;
class DtNetworkSegmentMetric;


//
// DtSegmentMxCifTree is a node for an MX-CIF Quadtree.  The intended use is to
// spatially sort collection of network segments.  It's depth is limited to prevent
// degenerate cases from causing excessive memory usage.  Segments can be added
// and removed from the tree, but adding and removing will, over time, degrade
// the searching efficiency of the structure.
//
class DT_DLL_gdb DtSegmentMxCifTree
{
public:

   // enumerations for locale 
   enum DtLocale
   {
      SOUTHWEST,
      SOUTHEAST,
      NORTHEAST,
      NORTHWEST,
      MULTIPLE
   };

   // default constructor 
   DtSegmentMxCifTree(unsigned int depth);

   // constructor with an extent
   DtSegmentMxCifTree(double lowX, double highX, double lowY, double highY, unsigned int depth);

   // destructor
   virtual ~DtSegmentMxCifTree();

private:

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

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

public:

   typedef std::list<const DtNetworkSegment*> DtPtrConstSegmentContainer;
   typedef DtPtrConstSegmentContainer::const_iterator DtPtrConstSegmentConstIter;
   typedef DtPtrConstSegmentContainer::iterator DtPtrConstSegmentIter;

   typedef std::list<DtNetworkSegment*> DtPtrSegmentContainer;
   typedef DtPtrSegmentContainer::const_iterator DtPtrSegmentConstIter;
   typedef DtPtrSegmentContainer::iterator DtPtrSegmentIter;


   // add a new element (the lower and left boundaries in
   // each quad are closed)
   virtual void add(DtNetworkSegment& segmentToAdd);

   // Remove the specified element, if it is contained.
   virtual bool remove(const DtNetworkSegment& segmentToRemove);

   // collect all segments that are validated by the metric
   virtual void collectAllSegments(const DtNetworkSegmentMetric& metric, 
                                   DtPtrConstSegmentContainer& segments) const;
   virtual void collectAllSegments(const DtNetworkSegmentMetric& metric, 
                                   DtPtrSegmentContainer& segments);

   // find the best valid segment in the tree as measured by the metric
   virtual const DtNetworkSegment* findBestSegment(const DtNetworkSegmentMetric& metric) const;

   // expand the extent.  Only changes the pivot if there are no children.
   virtual void expandXY(double lowX, double highX, double lowY, double highY);

   // Clears the instance, returning it to the same state as the *default constructor*.
   virtual void clear();

   // \return A boolean indicating whether or not any elements are currently sorted
   // in the structure or not.
   virtual bool empty() const;

   virtual int size() const;

   virtual int sizeInBytes() const;

protected:
   
   // Add the element to the specified destination.  If the destination doesn't
   // exist, create it using the specified boundaries.
   void addElement(DtSegmentMxCifTree*& destination, double lowX, double highX, 
      double lowY, double highY, DtNetworkSegment& elementToAdd);

   // Remove the element from the specified destination, if it exists.
   // \return True if the element was found and removed, and false otherwise.
   bool removeElement(DtSegmentMxCifTree*& destination, const DtNetworkSegment& elementToRemove);

   // find the best valid segment in a subtree. pointer best must be valid.  
   virtual const DtNetworkSegment* findBestInSubtree(const DtNetworkSegmentMetric& metric,
      double& bestCost) const;

   // calculate a segment's locale
   DtLocale findLocale(const DtNetworkSegment& newNetworkSegment) const;


protected:

   DtPtrSegmentContainer myElements;
   DtSegmentMxCifTree*   mySW;
   DtSegmentMxCifTree*   mySE;
   DtSegmentMxCifTree*   myNE;
   DtSegmentMxCifTree*   myNW;
   double                myPivotX;
   double                myPivotY;
   double                myLowY;
   double                myHighY;
   double                myLowX;
   double                myHighX;

   // If this is non-zero, then child segment trees will be created as appropriate 
   // for all locales, each one with a depth of one less.
   // If it is zero, no child segment trees will be created.
   unsigned int          myDepth;
};

#endif