oaXYTree.h

Go to the documentation of this file.

// *****************************************************************************
// *****************************************************************************
// oaXYTree.h
//
// This file contains the definition for the oaXYTree, oaXYTreeNode, oaXYTreeRec,
// and oaXYTreeProd classes. These classes implement a 2-D region querying tree
// for quickly finding objects that are in a particular region.
// Capabilities they support include:
//
//  1)  The oaXYTree class is the container for the tree. It is an abstract base
//      class. It keeps objects by index, which must be passed in. Applications
//      are responsible for creating the sub-class, which must provide
//      information about the stored objects' bBoxes and provide a means to
//      link objects together.
//  2)  The oaXYTreeNode class implements a node in the tree. A node can be
//      either a leaf node or a branch node. To maximize efficiency, the nodes
//      of a tree are allocated through a pool maintained by the tree itself.
//      Note that this object is only to be allocated in arrays, so non-array
//      allocation (new/delete) is disallowed
//  3)  The oaXYTreeRec class implements a record in a treeNode. A record
//      contains the index of the object and its next object index. To maximize
//      efficiency, the records of a treeNode are allocated through a pool
//      maintained by the tree itself.
//      Note that this object is only to be allocated in arrays, so non-array
//      allocation (new/delete) is disallowed
//  4)  The oaXYTreeProd class implements a producer that walks a specified tree
//      and produces all objects that intersect a specified region. This is an
//      abstract class that must be overridden to provide specific
//      functionalities.
//
// *****************************************************************************
// Except as specified in the OpenAccess terms of use of Cadence or Silicon
// Integration Initiative, this material may not be copied, modified,
// re-published, uploaded, executed, or distributed in any way, in any medium,
// in whole or in part, without prior written permission from Cadence.
//
//                Copyright 2002-2005 Cadence Design Systems, Inc.
//                           All Rights Reserved.
//
//  $Author: icftcm $
//  $Revision: #1 $
//  $Date: 2010/08/09 $
//  $State: Exp $
// *****************************************************************************
// *****************************************************************************



#if !defined(oaXYTree_P)
#define oaXYTree_P



// *****************************************************************************
// Nested includes
// *****************************************************************************
#include "oaBox.h"



// *****************************************************************************
// Declare and define types in the OpenAccess namespace.
// *****************************************************************************
BEGIN_OA_NAMESPACE



// *****************************************************************************
// Forward Class Declarations
// *****************************************************************************
template<class T, class M, class UD>
class oaXYTree;
template<class T, class M, class UD>
class oaXYTreeProd;
class oaBox;


// *****************************************************************************
// Flag Bits, Masks, and Shifts
// *****************************************************************************
// Following are used with the 'flags' bits for xy-tree node. Those 'flags'
// bits are shared with the member 'midChild' and occupy the higher bits.
#define oavXYTreeNodeBBoxIsInvalid          0x80000000u
#define oavXYTreeNodeIsHorizontal           0x40000000u
#define oavXYTreeNodeSplitHasFailed         0x40000000u
#define oavXYTreeNodeMidChildMask           0x3fffffffu



// *****************************************************************************
// oaXYTreeRec
// *****************************************************************************
template<class T>
class oaXYTreeRec {
public:
    T                       object;
    oaUInt4                 next;

    void                    *operator new[](size_t size);
    void                    operator delete[](void *ptr);

private:
    void                    *operator new(size_t);
    void                    operator delete(void *);
};



// *****************************************************************************
// oaXYTreeNode
// *****************************************************************************
template<class T, class M, class UD>
class oaXYTreeNode {
public:
    typedef oaXYTree<T, M, UD>      treeType;
    typedef oaXYTreeNode<T, M, UD>  nodeType;
    typedef oaXYTreeRec<T>          recType;
    typedef oaXYTreeProd<T, M, UD>  prodType;

    void                            add(treeType    *tree,
                                        T           obj,
                                        const oaBox &objBBox,
                                        oaUInt4     depth = 0);
    void                            remove(treeType     *tree,
                                           T            obj,
                                           const oaBox  &objBBox);

    const oaBox                     &getBBox(const treeType *tree) const;

    oaUInt4                         getNumObjects() const;

    oaBoolean                       isLeaf() const;
    oaBoolean                       isUsed() const;

    nodeType                        *getLoChild(const treeType *tree) const;
    nodeType                        *getHiChild(const treeType *tree) const;
    nodeType                        *getMidChild(const treeType *tree) const;

    void                            split(treeType      *tree,
                                          const oaBox   &objBBoxLatest);

    void                            flatten(treeType    *tree,
                                            nodeType    *parent = NULL);

    void                            produce(const treeType  *tree,
                                            const oaBox     &region,
                                            prodType        *prod) const;
    void                            produce(const treeType  *tree,
                                            prodType        *prod) const;

    oaBoolean                       findNearestNeighborToObj(const treeType *tree,
                                                             T              to,
                                                             const oaBox    &toBBox,
                                                             oaDouble       &closestDistanceSoFar,
                                                             oaBox          &worstCaseBBox,
                                                             T              &result);
    oaBoolean                       findNearestNeighborToArea(const treeType    *tree,
                                                              const oaBox       &to,
                                                              oaDouble          &closestDistanceSoFar,
                                                              oaBox             &worstCaseBBox,
                                                              T                 &result);

    void                            *operator new[](size_t size);
    void                            operator delete[](void *ptr);

private:
    void                            init();

    void                            rawAdd(treeType     *tree,
                                           T            obj,
                                           const oaBox  &objBox,
                                           oaBoolean    doSplit = true);
    void                            balanceAdd(treeType     *tree,
                                               T            obj,
                                               const oaBox  &objBox);

    oaBoolean                       insertAtRoot(treeType       *tree,
                                                 T              obj,
                                                 const oaBox    &objBox);

    void                            addToList(treeType      *tree,
                                              T             obj,
                                              const oaBox   &objBBox);
    void                            removeFromList(treeType     *tree,
                                                   T            obj,
                                                   const oaBox  &objBBox);

    void                            *operator new(size_t size);
    void                            operator delete(void *ptr);

    oaUInt4                         numObjects;
    mutable oaBox                   bBox;
    oaInt4                          median;

    union {
        oaUInt4             loChild;
        oaUInt4             firstObj;
    };
    union {
        oaUInt4             midChild;
        oaUInt4             flags;
    };
    union {
        oaUInt4             hiChild;
        oaUInt4             nextDeleted;
    };

    friend class oaXYTree<T, M, UD>;
};



// *****************************************************************************
// oaXYTree
// *****************************************************************************
template<class T, class M, class UD>
class oaXYTree {
public:
    typedef oaXYTreeNode<T, M, UD>  nodeType;

                                    oaXYTree(UD         measurerArgIn,
                                             oaUInt4    numObjs = 0);
    virtual                         ~oaXYTree();

    oaBoolean                       add(T item);
    oaBoolean                       remove(T item);
    void                            clear();

    nodeType                        *getRoot() const;

    oaUInt4                         getNumObjects() const;
    virtual const oaBox             &getBBox();
    oaUInt4                         getNumDots() const;

    oaBoolean                       findNearestNeighborToObj(T  to,
                                                             T  &result);
    oaBoolean                       findNearestNeighborToArea(const oaBox   &to,
                                                              T             &result);

protected:
    typedef oaXYTreeRec<T>          recType;

    oaUInt4                         allocNode();
    void                            freeNode(oaUInt4 index);

    oaUInt4                         allocRec();
    void                            freeRec(oaUInt4 index);

    oaBoolean                       busy();

    oaUInt4                         getFirstUsedNode() const;
    oaUInt4                         getNextUsedNode(oaUInt4 index) const;

    void                            updateMaxDim(const oaUInt4 dimSize);
    oaUInt4                         getMaxDim() const;

    oaUInt8                         calcVMSize() const;

    oaUInt4                         root;

    oaUInt4                         nodeSize;
    oaUInt4                         numNodeUsed;
    oaUInt4                         numNodeDeleted;
    oaUInt4                         firstNodeDeleted;
    oaUInt4                         numDots;
    nodeType                        *nodes;

    oaUInt4                         recSize;
    oaUInt4                         numRecUsed;
    oaUInt4                         numRecDeleted;
    oaUInt4                         firstRecDeleted;
    recType                         *recs;

    oaUInt4                         maxDim;
    oaBoolean                       bBoxValid;
    UD                              measurerArg;

    oaXYTreeProd<T, M, UD>          *activeProds;

    enum {
        iniSize         = 1,
        threshold       = 16,
        thresholdResize = 4096,
        thresholdDepth  = 32
    };

    friend class oaXYTreeNode<T, M, UD>;
    friend class oaXYTreeProd<T, M, UD>;
};



// *****************************************************************************
// oaXYTreeProd
// *****************************************************************************
template<class T, class M, class UD>
class oaXYTreeProd {
public:
    typedef oaXYTree<T, M, UD>  treeType;

                                oaXYTreeProd(treeType   *treeIn,
                                             oaUInt4    thresholdIn = 0,
                                             oaBoolean  doDots = false);
    virtual                     ~oaXYTreeProd();

    void                        produce(const oaBox &region,
                                        oaBoolean   *isAbortedIn);
    void                        produce(oaBoolean *isAbortedIn);

    oaUInt4                     getThreshold() const;

protected:
    oaBoolean                   *isAborted;
    oaBoolean                   processDots;

private:
    virtual void                process(T item) = 0;

    treeType                    *tree;
    oaUInt4                     threshold;
    oaXYTreeProd                *nextActiveProd;

    friend class oaXYTreeNode<T, M, UD>;
    friend class oaXYTree<T, M, UD>;
};



END_OA_NAMESPACE

#endif

Return to top of page

Copyright © 2002 - 2010 Cadence Design Systems, Inc.
All Rights Reserved.