VRS - The Virtual Rendering System

version 3.3

spacetree.h

Go to the documentation of this file.

/******************************************************************************
 * VRS - The Virtual Rendering System
 * Copyright (C) 2002 Computer Graphics Systems Group at the 
 * Hasso-Plattner-Institute (HPI), Potsdam, Germany.
 *
 * This  library  is  free  software; you can redistribute it and/or  modify it
 * under the terms of the GNU Lesser General Public  License  as  published  by
 * the  Free  Software  Foundation;  either  version 2.1 of the License, or (at
 * your option) any later version. This library  is  distributed  in  the  hope
 * that  it will be useful, but  WITHOUT ANY WARRANTY; without even the implied
 * warranty of  MERCHANTABILITY or FITNESS FOR A PARTICULAR  PURPOSE.  See  the
 * GNU Lesser General Public License for more details. You should have received
 * a copy of the GNU Lesser+ General Public License along with this library; if
 * not, write to the FreeSoftware Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, MA, 02111-1307, USA.
 ******************************************************************************/

// $Id: spacetree.h 6136 2007-11-14 11:56:35Z Konstantin_Baumann $
// $Date: 2007-11-14 12:56:35 +0100 (Wed, 14 Nov 2007) $
// $Revision: 6136 $
// $State$
// $Author: Konstantin_Baumann $
//
// $Log$
// Revision 1.25  2005/12/20 10:27:56  buchholz
// SpaceTree::findNearMainCellPoint() added
//
// Revision 1.24  2005/06/21 08:56:47  baumann
// GCC-3.4 fixes
//
// Revision 1.23  2005/05/04 18:07:37  buchholz
// spacetrees are now serializable
// operator< defined for nodepointers
//
// Revision 1.22  2005/02/07 20:33:19  buchholz
// DynamicSpaceTree::getDepth() added
//
// Revision 1.21  2004/11/09 15:07:24  kirsch
// further changes to class comments due to doxygen
//
// Revision 1.20  2004/11/03 10:58:28  saar
// Class comment changed (Doxygen style)
//
// Revision 1.19  2004/10/03 17:16:48  baumann
// code cleanup
//
// Revision 1.18  2004/06/03 12:48:01  kirsch
// replaced vrs assertions with check args and internal error macros
//
// Revision 1.17  2004/05/24 14:33:25  buchholz
// SpaceTreePath::newSubTreeLevelIterator added.
// memory leak fixed.
//
// Revision 1.16  2004/03/12 16:28:39  baumann
// macros VRS_NAMESPACE_BEGIN/_END expanded and removed
//
// Revision 1.15  2004/01/19 17:07:21  baumann
// moved VRS::Document from vrs/ to vrs/io/
//
// Revision 1.14  2004/01/19 13:14:41  baumann
// #include <vrs/io/document.h> added or removed
//
// Revision 1.13  2003/12/11 16:46:28  buchholz
// getChild() and getParent() methods of SpaceTreePath changed.
//
// Revision 1.12  2003/11/25 18:54:38  buchholz
//  - leaf iterator for dynamic spacetree added
//
// Revision 1.11  2003/11/07 14:19:24  kirsch
// removed leading underscore from include guards
//
// Revision 1.10  2003/10/29 13:10:58  buchholz
// SpaceTreePath::operator== included
//
// Revision 1.9  2003/10/21 12:17:20  buchholz
// point constructors for one, two and three coordinates added.
//
// Revision 1.8  2003/07/18 10:12:12  baumann
// include for Array<T> added
//
// Revision 1.7  2003/06/30 15:14:18  kirsch
// explicitely declared namespace of streams
//
// Revision 1.6  2003/03/20 13:04:24  buchholz
// new: static method "newLevelIterator" of SpacetreePath. It enables to traverse particular levels of spacetrees.
//
// Revision 1.5  2003/01/27 18:13:39  buchholz
// Path typedef and protected constructor added in
// DynamicSpaceTree and StaticSpaceTree.
//
// Revision 1.4  2003/01/27 11:34:44  buchholz
// Comment extended. createNode() return type changed to NodePointer.
//
// Revision 1.3  2003/01/24 12:44:58  buchholz
// gcc compatible
//
// Revision 1.2  2003/01/23 12:38:57  buchholz
// comments changed
//

#ifndef VRS_SPACETREE_H_
#define VRS_SPACETREE_H_

#include <vrs/container/array.h>
#include <vrs/container/iterator.h>
#include <vrs/container/staticarray.h>
#include <vrs/transactionno.h>

namespace VRS {

template<UINT DIM> class Point;
template<UINT DIM> class Cell;
template<typename Content, UINT DIM> class StaticSpaceTree;
template<typename Content, UINT DIM> class DynamicSpaceTree;


template<UINT DIM> class Point {

public:

        Point();
    Point(double x);
    Point(double x, double y);
    Point(double x, double y, double z);

        double& operator[](UINT index);
        const double& operator[](UINT index) const;
        const Point& operator/(double d);
        Point operator+(const Point p) const;

        bool isContainedIn(const Cell<DIM>& cell) const;
        bool intersects(const Cell<DIM>& cell) const;

private:

        double coords_[DIM];
};

template<UINT DIM> std::ostream& operator<<(std::ostream& s, const Point<DIM>& p);


template<UINT DIM> class Cell {

public:

        Cell();
        Cell(const Point<DIM>& pmin, const Point<DIM>& pmax);
        
        void setCell(const Point<DIM>& pmin, const Point<DIM>& pmax);

        double getExtend(UINT index) const;
        Point<DIM> getExtend() const;
        const Point<DIM>& getMinPoint() const { return pmin_; }
        const Point<DIM>& getMaxPoint() const { return pmax_; }
        
        void setExtend(UINT index, double w);
        void setExtend(const Point<DIM>& p);
        void setMinPoint(const Point<DIM>& p) { pmin_ = p; }
        void setMaxPoint(const Point<DIM>& p) { pmax_ = p; }
        void setPosition(const Point<DIM>& p);
        Point<DIM> getMidpoint() const;
        
        const Cell& operator=(const Cell& other);
        bool isContainedIn(const Cell& cell) const;
        bool intersects(const Cell& cell) const;
        bool empty() const;

private:

        Point<DIM> pmin_;
        Point<DIM> pmax_;
};

template<UINT DIM> std::ostream& operator<<(std::ostream& out, const Cell<DIM>& cell);

typedef unsigned char ChildNumber; 
template<UINT DIM> class SpaceTreePath {
        
public:
        SpaceTreePath();
        SpaceTreePath(const SpaceTreePath<DIM>& other);
        SpaceTreePath(Iterator<ChildNumber>* childNumbers);
                
        SpaceTreePath getChild(ChildNumber childNumber) const;
        SpaceTreePath getParent() const;
        ChildNumber getChildNumber() const;
        bool getNeighbor(UINT directionBitCode); 
        Iterator<SpaceTreePath>* getNeighbors() const; 
        bool getMainAxisNeighbor(UINT direction);
        bool isRoot() const;
        UINT getLength() const;
        bool valid() const;
        
        Iterator<ChildNumber>* newIterator() const;     

        const SpaceTreePath& operator=(const SpaceTreePath& other);
    bool operator==(const SpaceTreePath& other) const;
    bool operator<(const SpaceTreePath& other) const;
    bool operator!=(const SpaceTreePath& other) const;

        static Iterator<SpaceTreePath>* newLevelIterator(UINT level);

    static SO<Iterator<SpaceTreePath> > newSubTreeLevelIterator(SpaceTreePath subTreeRoot, unsigned int level);
        static const UINT Left;         
        static const UINT Right;        
        static const UINT Down;         
        static const UINT Up;           
        static const UINT Front;    
        static const UINT Back;     

        static const ChildNumber MaxChilds;
        static const ChildNumber InvalidChildNumber;
        static const SpaceTreePath InvalidPath;

    static UINT MaxPathLength() { return (32/DIM)-1; }

        
        SpaceTreePath(UINT pathCode);
        UINT getPathCode() const;
        void setPathCode(UINT c);

private:

        UINT pathCode_;
};

template<UINT DIM> std::ostream& operator<<(std::ostream& s, const SpaceTreePath<DIM>& path);



template<typename NODE, UINT DIM> class SpaceTree : public SharedObj {
    
public:

    typedef SpaceTreePath<DIM> Path;




    virtual Point<DIM> findNearMainCellPoint(const Point<DIM>& p) const;


        class NodePointer;
        virtual NodePointer getRoot()                                                                                                   = 0;
        virtual NodePointer getParent(const NodePointer& node)                                                  = 0;
        virtual NodePointer getChild(const NodePointer& node, ChildNumber childNumber)  = 0;
        virtual ChildNumber getChildNumber(const NodePointer& node) const                               = 0;

        virtual SpaceTreePath<DIM> getPath(const NodePointer& node) const;
        virtual NodePointer getNode(const SpaceTreePath<DIM>& path);
        virtual SpaceTreePath<DIM> cropPath(const SpaceTreePath<DIM>& path) const;
        virtual Cell<DIM> getCell(const NodePointer& node) const;
        virtual Cell<DIM> getCell(const SpaceTreePath<DIM>& path) const;

        NodePointer getNeighbor(const NodePointer& node, UINT direction);
        Iterator<NodePointer>* getNeighbors(NodePointer node);

        const TransactionNo& getTransactionNumber() const;

    VRS_TYPEINFO(SpaceTree, SharedObj);
    VRS_SERIALIZABLE_ABSTRACT_CLASS(SpaceTree);

protected:
    SpaceTree() : m_transactionNo(0) { }

        const NodePointer getRoot() const;
        const NodePointer getParent(const NodePointer& node) const;
        const NodePointer getChild(const NodePointer& node, ChildNumber childNumber) const;
        
        NodePointer createNodePointer(NODE* node);
        NODE* getPointer(const NodePointer& pointer);
        const NODE* getPointer(const NodePointer& pointer) const;


        virtual Cell<DIM> getSubCell(const NodePointer& node, const Cell<DIM>& cell,
                                                                ChildNumber childNumber) const;
        Cell<DIM> mainCell_;

        static const ChildNumber MaxChilds;
        static const ChildNumber InvalidChildNumber;

        void invalidatePointers();
        TransactionNo m_transactionNo;

private:

        template<typename POINTSET> class DefaultInclusionTest {
        public:
                DefaultInclusionTest() {}
                bool operator()(const POINTSET& pointSet, const Cell<DIM>& cell) {
                        return pointSet.isContainedIn(cell);
                } 
        };

        template<typename POINTSET> class DefaultIntersectionTest {
        public:
                DefaultIntersectionTest() {}
                bool operator()(const POINTSET& pointSet, const Cell<DIM>& cell) {
                        return pointSet.intersects(cell);
                }
        };

/* ---------------------------------------------------------------------------------------------------------
   ---------------------------------------------------------------------------------------------------------
   ---------------------------------------------------------------------------------------------------------
   --- USERS DO NOT NEED TO READ THE REST OF THE FILE EXCEPT FROM THE TWO CLASS DECLARATIONS AT THE END ----
   ---------------------------------------------------------------------------------------------------------
   --- The code section beginning here is not of interested for the user interface and should be moved   ---
   --- to the implementation section. Unfortunately moving them would lead to problems with some         ---
   --- compilers because of template-related technical problems.                                         ---
   ---------------------------------------------------------------------------------------------------------
   ---------------------------------------------------------------------------------------------------------
   ---------------------------------------------------------------------------------------------------------*/
  
public:

    class NodePointer {
    public:
            NodePointer() : m_transactionNo(0), pointer_(0) { }
            const NodePointer& operator=(const NodePointer& other) {
                    m_transactionNo     = other.m_transactionNo;
                    pointer_            = other.pointer_;
                    tree_           = other.tree_;
                    return *this;
            }

        bool operator==(const NodePointer& other) const { return (m_transactionNo==other.m_transactionNo && pointer_==other.pointer_ && tree_==other.tree_); }
        bool operator!=(const NodePointer& other) const { return !operator==(other); }
        bool operator<(const NodePointer& other)  const { return pointer_<other.pointer_; }

        NODE& operator*() { VRS_InternalError(valid(), "invalid node pointer dereferenced"); return *pointer_; }
        NODE* operator->() { VRS_InternalError(valid(), "invalid node pointer dereferenced"); return pointer_; }
        const NODE& operator*() const { VRS_InternalError(valid(), "invalid node pointer dereferenced"); return *pointer_; }
        const NODE* operator->() const { VRS_InternalError(valid(), "invalid node pointer dereferenced"); return pointer_; }        
        bool valid() const { if (tree_==0 || pointer_==0) return false; return (m_transactionNo==tree_->getTransactionNumber()); }

        static const NodePointer& InvalidNodePointer() { static const NodePointer np = NodePointer(TransactionNo(0), 0, 0); return np; }

    private:
        friend class SpaceTree<NODE, DIM>;
        NodePointer(const TransactionNo& tn, NODE* p, SpaceTree* tree) : m_transactionNo(tn), pointer_(p), tree_(tree) {}
            mutable TransactionNo m_transactionNo;
            mutable NODE* pointer_;
            mutable SO<SpaceTree> tree_;
    };

        // spacial search methods
        template<typename POINTSET,typename INCLUSIONTEST> SpaceTreePath<DIM> findSmallestEnclosingNode(
                                                                                                        const POINTSET& pointSet, 
                                                                                                        UINT maxLevel,
                                                                                                        bool mustExist,                                                                                                 
                                                                                                        INCLUSIONTEST test) {
                // Returns the path of the node with the smallest cell with
                // the property that a given pointset is completely enclosed.
                // If the search is not succesful, the return value is an
                // invalid SpaceTreePath.
                // If the mustExist flag is set to true, only existing nodes are
                // considered, i.e. if the result is a valid path, it leads to 
                // an existing node. Otherwise the result can be a path leading
                // to a not yet existing node that would have the cell containng
                // the pointSet.
                VRS_InternalError(!mainCell_.empty(), "mainCell_ must not be empty");
        UINT maxLength = Path::MaxPathLength();
        if (maxLevel>maxLength) maxLevel = maxLength;

                // abort if the pointSet is not contained in the area supported by the tree
        if (!test.operator()(pointSet, mainCell_)) {
            return SpaceTreePath<DIM>::InvalidPath;
        }

                // start at the root node with an empty path and the main cell
                NodePointer node = (mustExist ? getRoot() : NodePointer::InvalidNodePointer());
        if (!node.valid() && mustExist) {
            return SpaceTreePath<DIM>::InvalidPath;
        }
                Cell<DIM> cell = mainCell_;
                SpaceTreePath<DIM> path;

                for (UINT i=0; i<maxLevel; i++) {
                        bool enclosingChildFound = false;

                        // check all childs of the current node
                        for (ChildNumber childNum=0; childNum<MaxChilds; childNum++) {
                                Cell<DIM> subCell = getSubCell(node, cell, childNum);
                                if (test.operator()(pointSet, subCell)) {
                                        // subCell contains the given pointSet
                                        if (mustExist) {
                                                NodePointer child = getChild(node, childNum);
                                                if (!child.valid()) {
                                                        continue;
                                                }
                                                else node = getChild(node, childNum);
                                        } 

                                        cell = subCell;
                                        path = path.getChild(childNum);
                                        enclosingChildFound = true;
                                        break;
                                }
                        }
                        
                        if (!enclosingChildFound) return path;
                }
                return path;
        }
        template<typename POINTSET> SpaceTreePath<DIM> findSmallestEnclosingNode(
                                                                                                        const POINTSET& pointSet, 
                                                    UINT maxLevel = 32, 
                                                                                                        bool mustExist = true) {
                return findSmallestEnclosingNode(pointSet, maxLevel, mustExist, DefaultInclusionTest<POINTSET>());
        }

                 
    struct STNODEInfo {
            STNODEInfo(const NodePointer& node, const Cell<DIM>& cell, const SpaceTreePath<DIM>& path) :
                           node_(node), cell_(cell), path_(path) {}
            NodePointer node_;
            Cell<DIM> cell_;
            SpaceTreePath<DIM> path_;
    };

        Iterator<SpaceTreePath<DIM> >* emptyIterator() {
                static SO<NonPersistentStaticArray<SpaceTreePath<DIM> > > empty = 
                                                                new NonPersistentStaticArray<SpaceTreePath<DIM> >(static_cast<UINT>(0));
                return empty->newIterator();
        }

        template<typename POINTSET, typename INTERSECTIONTEST> Iterator<SpaceTreePath<DIM> >* findIntersectingNodes(
                                                                                                        const POINTSET& pointSet, 
                                                                                                        UINT level,
                                                                                                        bool mustExist,
                                                                                                        INTERSECTIONTEST test) {
                VRS_InternalError(!mainCell_.empty(), "mainCell_ must not be 0");
        VRS_CheckArg(level<=Path::MaxPathLength(), "level must not exceed Path::maxPathLength");

                // abort if the pointSet is not contained in the area supported by the tree
                if (!test.operator()(pointSet, mainCell_)) return emptyIterator();

                // start at the root node with an empty path and the main cell
                NodePointer root = getRoot();
                if (!root.valid() && mustExist) return emptyIterator();
                
                SO<NonPersistentArray<STNODEInfo> > stack1 = new NonPersistentArray<STNODEInfo>;
                SO<NonPersistentArray<STNODEInfo> > stack2 = new NonPersistentArray<STNODEInfo>;
                NonPersistentArray<STNODEInfo>* sp1 = stack1;
                NonPersistentArray<STNODEInfo>* sp2 = stack2;
                stack1->append(STNODEInfo(root, mainCell_, SpaceTreePath<DIM>()));
                
                // in each cycle sp2 is filled with all intersecting child nodes of
                // nodes in sp1. Then sp1 and sp2 are swapped.
                for (UINT curLevel=0; curLevel<level; curLevel++) {
                        sp2->clear();
                        for(unsigned int i=0; i<sp1->size(); i++) {
                                // take a nodeInfo from sp1
                                STNODEInfo nwc = (*sp1)[i];
                                NodePointer node = nwc.node_;
                                const Cell<DIM>& cell = nwc.cell_;
                                SpaceTreePath<DIM> path = nwc.path_;

                                // check all childs of nwc
                                for (ChildNumber childNum = 0; childNum<MaxChilds; childNum++) {
                                        Cell<DIM> subCell = getSubCell(node, cell, childNum);
                                        
                                        if (test.operator()(pointSet, subCell)) {
                                                NodePointer childNode = (node.valid() ? 
                                                                                        getChild(node, childNum) : 
                                                                                        NodePointer::InvalidNodePointer());

                                                if (childNode.valid() || !mustExist) {
                                                        // append path
                                                        SpaceTreePath<DIM> childPath = path.getChild(childNum);                                                 
                                                        // add info for the child node
                                                        sp2->append(STNODEInfo(childNode, subCell, childPath));
                                                }
                                        }
                                }
                        }
                        if (sp2->isEmpty()) return emptyIterator();
                        std::swap(sp1, sp2);
                }

                // *sp1 contains NODE/Cell-Pairs for all intersecting nodes on the given level
                // so we only need to copy the result to a static array
                SO<Iterator<STNODEInfo> > infos = sp1->newIterator();
                NonPersistentStaticArray<SpaceTreePath<DIM> >* paths = new NonPersistentStaticArray<SpaceTreePath<DIM> >(sp1->size());

                for (UINT i=0; i<infos->size(); i++) {
                        (*paths)[i] = infos->get(i).path_;
                }

                return paths->newIterator();
        }
        template<typename POINTSET> Iterator<SpaceTreePath<DIM> >* findIntersectingNodes(
                const POINTSET& pointSet, 
                UINT level,
                bool mustExist = true) {
                return findIntersectingNodes(pointSet, level, mustExist, DefaultIntersectionTest<POINTSET>());
        }

        



        template<typename POINTSET, typename INCLUSIONTEST> Iterator<SpaceTreePath<DIM> >* findEnclosingNodes(
                                                                                                        const POINTSET& pointSet, 
                                                                                                        UINT level,
                                                                                                        bool mustExist,
                                                                                                        INCLUSIONTEST test) {
                // finding all nodes containing a given pointSet is simply achieved by finding 
                // all nodes intersecting this pointSet, if we replace the intersection 
                // function-object by the inclusion function-object.
        VRS_CheckArg(level<=Path::MaxPathLength(), "level must not exceed Path::maxPathLength");
                return findIntersectingNodes(pointSet, level, mustExist, test);
        }
        template<typename POINTSET> Iterator<SpaceTreePath<DIM> >* findEnclosingNodes(
                                                                                                        const POINTSET& cell, 
                                                                                                        UINT level,
                                                                                                        bool mustExist = true) {
                return findEnclosingNodes(cell, level, mustExist, DefaultInclusionTest<POINTSET>());
        }
};

template<typename CONTENT> class StaticNode {
    public:
        CONTENT content;
        VRS_SERIALIZABLE_NO_SO_CLASS(StaticNode);
};

template<typename CONTENT, UINT DIM> class DynamicNode {

public:

        CONTENT content;
    VRS_SERIALIZABLE_NO_SO_CLASS(DynamicNode);

private:

        DynamicNode(const DynamicNode* parent, ChildNumber childNumber);
        ~DynamicNode();
        DynamicNode* getChild(ChildNumber childNumber) const;
        ChildNumber getChildNumber() const;
        DynamicNode* getParent() const;
        bool createChild(ChildNumber childNumber) const;
        bool deleteChild(ChildNumber childNumber) const;
        UINT countChilds() const;
                // returns the total number of deleted nodes

        mutable DynamicNode* parent_;
        mutable DynamicNode* childs_[1<<DIM];
        ChildNumber childNumber_;

        friend class DynamicSpaceTree<CONTENT, DIM>;
    DynamicNode(); // serialization only
};

/* ---------------------------------------------------------------------------------------------------------
   ---------------------------------------------------------------------------------------------------------
   ---------------------------------------------------------------------------------------------------------
   -------------------------- USERS DO NOT NEED TO READ THE ABOVE CODE SECTION -----------------------------
   ---------------------------------------------------------------------------------------------------------
   --- The code section ending here is not of interested for the user interface and should be moved      ---
   --- to the implementation section. Unfortunately moving them would lead to problems with some         ---
   --- compilers because of template-related technical problems.                                         ---
   ---------------------------------------------------------------------------------------------------------
   ---------------------------------------------------------------------------------------------------------
   ---------------------------------------------------------------------------------------------------------*/
   

template<typename CONTENT, UINT DIM> class DynamicSpaceTree : 
                        public SpaceTree<DynamicNode<CONTENT, DIM>, DIM> {

public:
    typedef SpaceTree<DynamicNode<CONTENT, DIM>, DIM> BaseClass;
    VRS_TYPEINFO(DynamicSpaceTree, BaseClass);
    VRS_SERIALIZABLE(DynamicSpaceTree);

        typedef typename SpaceTree<DynamicNode<CONTENT, DIM>, DIM>::NodePointer NodePointer;
    typedef SpaceTreePath<DIM> Path;

        DynamicSpaceTree(const Cell<DIM>& mainCell);
    virtual ~DynamicSpaceTree();

        bool createChild(const NodePointer& node, ChildNumber childNumber);
        NodePointer createNode(const SpaceTreePath<DIM>& path);
        void deleteNode(const NodePointer& node);

        UINT getSize() const;
    int getDepth() const;

        virtual NodePointer getRoot();
        virtual NodePointer getParent(const NodePointer& node);
        virtual NodePointer getChild(const NodePointer& node, ChildNumber childNumber);
        virtual ChildNumber getChildNumber(const NodePointer& node) const;

    typedef DynamicNode<CONTENT, DIM> Node;
    Iterator<NodePointer>* leafIterator(Path path = Path()) const;
protected:
    DynamicSpaceTree();

private:        
        DynamicNode<CONTENT, DIM>* root_;
        UINT size_;
};

template<typename CONTENT, UINT DIM> class StaticSpaceTree : 
                        public SpaceTree<StaticNode<CONTENT>, DIM> {

public:
    typedef SpaceTree<StaticNode<CONTENT>, DIM> BaseClass;
    VRS_TYPEINFO(StaticSpaceTree, BaseClass);
    VRS_SERIALIZABLE(StaticSpaceTree);

        typedef typename SpaceTree<StaticNode<CONTENT>, DIM>::NodePointer NodePointer;
    typedef SpaceTreePath<DIM> Path;

        StaticSpaceTree(const Cell<DIM>& mainCell, UINT depth);
    virtual ~StaticSpaceTree();

        UINT getSize() const;
    UINT getDepth() const;

        virtual NodePointer getRoot();
        virtual NodePointer getParent(const NodePointer& node);
        virtual NodePointer getChild(const NodePointer& node, ChildNumber childNumber);
        virtual ChildNumber getChildNumber(const NodePointer& node) const;

        virtual SpaceTreePath<DIM> getPath(const NodePointer& node) const;
        virtual NodePointer getNode(const SpaceTreePath<DIM>& path);

    typedef StaticNode<CONTENT> Node;

protected:
    StaticSpaceTree(UINT depth);

private:

    StaticSpaceTree();

        int depth_;
        unsigned int size_;

        StaticNode<CONTENT>* nodes_;        
};
        
} // namespace VRS

#include "spacetree.tli"

#endif // VRS_SPACETREE_H_

---

Generated on Thu May 24 06:00:15 2012 by Doxygen 1.5.6

© 2001-2010 Hasso-Plattner-Institut | Impressum | Contact