AMRTreeBranch.h

Go to the documentation of this file.

//
//      $Id$
//
//***********************************************************************
//                                                                      *
//                      Copyright (C)  2006                         *
//          University Corporation for Atmospheric Research             *
//                      All Rights Reserved                             *
//                                                                      *
//***********************************************************************
//
//  File:       AMRTreeBranch.h
//
//  Author:     John Clyne
//          National Center for Atmospheric Research
//          PO 3000, Boulder, Colorado
//
//  Date:       Thu Jan 5 16:59:42 MST 2006
//
//  Description:    
//
//
#ifndef _AMRTreeBranch_h_
#define _AMRTreeBranch_h_

#include <vector>
#include <vapor/common.h>
#include <vapor/MyBase.h>
#include <vapor/EasyThreads.h>
#include <vapor/XmlNode.h>


namespace VAPoR {

//
//

class AMRTreeBranch : public VetsUtil::MyBase {

public:

 typedef long cid_t;

 //
 // Tag names for data stored in the XML tree
 //
 static const string _rootTag;          // root of the XML tree
 static const string _refinementLevelTag;   // max refinement depth of branch
 // List of parent cells in breath first traversal order
 static const string _parentTableTag;


 //
 // Attribute names for data stored in the XML tree
 //
 static const string _minExtentsAttr;   // min coord bounds of branch
 static const string _maxExtentsAttr;   // max coord bounds of branch
 static const string _locationAttr;     // toplogical coords of branch


 //
 AMRTreeBranch(
    XmlNode *parent,
    const double min[3],
    const double max[3],
    const size_t location[3]
 );

 virtual ~AMRTreeBranch();

 void Update();

 //
 int    DeleteCell(cid_t cellid);

 //
 cid_t  FindCell(const double ucoord[3], int ref_level = -1) const;

 bool ValidCell(cid_t cellid) const {
    return(cellid < _octree->get_num_cells(_octree->get_max_level())); 
 };

 int    GetCellBounds(
    cid_t cellid, double minu[3], double maxu[3]
 ) const;

 int    GetCellLocation(cid_t cellid, size_t xyz[3],int *reflevel) const;


 AMRTreeBranch::cid_t    GetCellID(const size_t xyz[3], int reflevel) const;


 //
 cid_t  GetCellChildren(cid_t cellid) const;

 //
 int    GetCellLevel(cid_t cellid) const;


 cid_t  GetCellNeighbor(cid_t cellid, int face) const;

 cid_t GetNumCells() const;

 cid_t GetNumCells(int ref_level) const;

 //
 cid_t  GetCellParent(cid_t cellid) const;

 //
 int    GetRefinementLevel() const {
    return ((int) (_octree->get_max_level()));
 };

 //
 cid_t  GetRoot() const {return(0);};

 //
 int    HasChildren(cid_t cellid) const;


 //
 AMRTreeBranch::cid_t   RefineCell(cid_t cellid);


 //
 void EndRefinement();

 //
 AMRTreeBranch::cid_t   GetNextCell(bool restart);

 //
 long GetCellOffset(cid_t cellid) const;

 int SetParentTable(const vector<long> &table);

private:

    //
    // cell ids indicate the order in which the cell was added to the 
    // tree via refinement. They also determine the octant that a cell 
    // occupies by virtue of the fact that refinement generates 8 new
    // cells, inserted into the tree in octant order. The root of the 
    // tree always has id==0
    //
 class octree {
 public:


    octree();
    void clear();
    cid_t refine_cell(cid_t cellid);
    void end_refinement();
    cid_t get_parent(cid_t cellid) const;

    //
    // returns the cellid of the child in the first octant. The
    // id's of the remaining children are numbered sequentially
    //
    cid_t get_children(cid_t cellid) const;

    bool has_children(cid_t cellid) const;
    // 
    // Get id of next child in a breadth first traversal of 
    // the tree. If 'restart' is true, traversal starts from the
    // top of the tree, else traversal starts from the cell returned
    // from the previous call. When the tree has been completely 
    // treversed a negative number is returned.
    //
    cid_t get_next(bool restart);

    long get_offset(cid_t cellid) const;

    // 
    // Return the octant occupied by 'cellid'. Octants are numbered
    // sequentially from 0 with X varying fastest, followed by y, than Z.
    //
    int get_octant(cid_t cellid) const;
    int get_max_level() const {return(_max_level); };


    // Get the cellid for the cell with the specified coordinates (if
    // it exists). The cartesian coordinates are respective
    // to the refinement level of the cell. Their range is from
    // 0..(2^j)-1, where j is the refinment level. If no cell
    // exists at (xyz, level) a negative int is returned.
    //
    cid_t get_cellid(const size_t xyz[3], int level) const;

    int get_location(cid_t cellid, size_t xyz[3], int *level) const;

    int get_level(cid_t cellid) const;

    cid_t get_num_cells(int ref_level) const;

 private:

    vector <cid_t> _bft_next;
    vector <cid_t>::iterator _bft_itr;
    vector <cid_t> _bft_children;
    vector <cid_t> _num_cells;
    int _max_level; // maximum refinment level in tree. Base level is 0

    vector <long> _offsets; // vector of offsets to speed breath-first search 

    typedef struct {
        cid_t parent;
        cid_t child;    // id of first child. Remaining children have
                        // consecutivie ids
    } _node_t;

    vector <_node_t> _tree; // interal octree representation.

    void _init();


 };


 octree *_octree;

 size_t _location[3];    // Topological coords of branch  in blocks
 double _minBounds[3];  // Min domain extents expressed in user coordinates
 double _maxBounds[3];  // Max domain extents expressed in user coordinates

 XmlNode    *_rootNode; // root of XML tree used to represent AMR tree


};

};

#endif  //  _AMRTreeBranch_h_