TreeIntVectSet.H

Go to the documentation of this file.

/*   _______              __
    / ___/ /  ___  __ _  / /  ___
   / /__/ _ \/ _ \/  V \/ _ \/ _ \
   \___/_//_/\___/_/_/_/_.__/\___/
*/
// CHOMBO Copyright (c) 2000-2004, The Regents of the University of
// California, through Lawrence Berkeley National Laboratory (subject to
// receipt of any required approvals from U.S. Dept. of Energy).  All
// rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// (1) Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// (2) Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// (3) Neither the name of Lawrence Berkeley National Laboratory, U.S.
// Dept. of Energy nor the names of its contributors may be used to endorse
// or promote products derived from this software without specific prior
// written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
// OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// You are under no obligation whatsoever to provide any bug fixes,
// patches, or upgrades to the features, functionality or performance of
// the source code ("Enhancements") to anyone; however, if you choose to
// make your Enhancements available either publicly, or directly to
// Lawrence Berkeley National Laboratory, without imposing a separate
// written license agreement for such Enhancements, then you hereby grant
// the following license: a non-exclusive, royalty-free perpetual license
// to install, use, modify, prepare derivative works, incorporate into
// other computer software, distribute, and sublicense such Enhancements or
// derivative works thereof, in binary and source code form.
//
// TRADEMARKS. Product and company names mentioned herein may be the
// trademarks of their respective owners.  Any rights not expressly granted
// herein are reserved.
//

#ifndef _TREEINTVECTSET_H_
#define _TREEINTVECTSET_H_

#include "Box.H"
#include "Pool.H"

class IntVectSet;
class ProblemDomain;

// xlC doesn't like the static const int inside this class.
// so instead of a nice variable we have a macro: TIVS_NODESIZE
// Currently, this only affects two files:  this one and the .cpp
#if (CH_SPACEDIM==2)
#define TIVS_NODESIZE 4
#elif (CH_SPACEDIM==3)
#define TIVS_NODESIZE 8
#else
//error -- only tested for dimensions 2 and 3 (ndk)
#error TIVS_NODESIZE is only defined for 2D and 3D
#endif


class TreeIntVectSet
{
public:
  inline TreeIntVectSet();

  TreeIntVectSet(const Box&);

  TreeIntVectSet(const TreeIntVectSet& a_sivs);

  ~TreeIntVectSet();

  void define(const Box&);

  void define(const TreeIntVectSet& a_sivs);

  TreeIntVectSet& operator=(const TreeIntVectSet& a_sivs);

  TreeIntVectSet& operator|=(const TreeIntVectSet& a_sivs);

  TreeIntVectSet& operator|=(const IntVect& a_iv);

  TreeIntVectSet& operator|=(const Box& a_box);

  TreeIntVectSet& operator&=(const TreeIntVectSet& s_sivs);

  TreeIntVectSet& operator&=(const Box& a_box);

  TreeIntVectSet& operator&=(const ProblemDomain& a_domain);

  TreeIntVectSet& operator-=(const TreeIntVectSet& a_sivs);

  TreeIntVectSet& operator-=(const IntVect& a_iv);

  TreeIntVectSet& operator-=(const Box& a_box);

  bool operator==(const TreeIntVectSet& lhs) const;

  bool operator<(const TreeIntVectSet& a_sivs) const;


  Vector<Box> createBoxes() const;


  void createBoxes(Vector<Box>& boxes, int& size) const;

  bool contains(const IntVect& iv) const;

  bool contains(const Box& box) const;


  TreeIntVectSet chop(int idir, int chop_pnt);


  void grow(int igrow);


  void grow(int idir, int igrow);


  void refine(int iref = 2);


  void coarsen(int iref = 2);


  void shift(const IntVect& iv);

  void clear();

  void nestingRegion(int a_radius, const Box& a_domain, int granularity);

  void nestingRegion(int a_radius, const ProblemDomain& a_domain, int granularity);

  inline const Box& minBox() const;

  bool isEmpty() const;

  int numPts() const;

  friend void dumpTree(const TreeIntVectSet* set);

  void compact() const;  // logically const operation;

  void recalcMinBox() const;

  int linearSize() const;

  void linearIn(const void* const inBuf);

  void linearOut(void* const a_outBuf) const;
private:

  friend class TreeIntVectSetIterator;

#ifndef DOXYGEN
  struct TreeNode {
    TreeNode* nodes;
    TreeNode():nodes(0)
    {}
  };
#endif

  TreeNode m_tree;
  Box m_minBox, m_spanBox;
  int m_depth;

  void trimCoarsen(int icoarse);

  //===============
  static Pool treeNodePool;

  static void   quadrantBox(const Box& inputBox, int quadrant, Box& outputQuadrant);
  static void clearTree(TreeNode& tree);
  static void expandNode(TreeNode& node);
  void growTree();

  static int  oppositeQuadrant(int index);
  static bool nextIntVect(const Box& box, IntVect& iv);
  static void nextNode(int& currentDepth);
  static void cloneNode(const TreeNode& src, TreeNode& dest);
  // data structures that are needed again and again in the routines
  // that only change their size during grow() operations.  Keep them
  // around so that we don't have to create and destroy them on every function
  // call
  static Vector<int> index, bufferOffset;
  static Vector<TreeNode*> parents;
  static Vector<Box> boxes;

  // xlC wasn't like this
  // so instead of a nice const static integer, we have a MACRO TIVS_NODESIZE
  //const static int  nodeSize = D_TERM(2,*2,*2);
  static TreeNode full;
  friend struct Flag;
  friend class IntVectSet;
};

class TreeIntVectSetIterator
{
public:
  TreeIntVectSetIterator();
  TreeIntVectSetIterator(const TreeIntVectSet& ivs);
  void define(const TreeIntVectSet& ivs);
  const IntVect& operator()() const ;
  bool ok() const;
  void operator++();
  void begin();
  void end();
  void clear();
private:
  const TreeIntVectSet* m_ivs;
  Vector<const TreeIntVectSet::TreeNode*> nodes;
  Vector<Box>   boxes;
  Vector<int>   index;
  int           m_depth;
  IntVect       m_current;

  void findNextNode();
  void findNext(); // parse tree, starting at [depth, index], set m_current
  //when you find an entry, might run to end of iterator.
};

inline
TreeIntVectSetIterator::TreeIntVectSetIterator():m_ivs(0), m_depth(-1)
{}

inline
TreeIntVectSetIterator::TreeIntVectSetIterator(const TreeIntVectSet& ivs)
{
  define(ivs);
}

inline
void TreeIntVectSetIterator::clear()
{
  m_depth = -1;
  m_ivs = 0;
}

inline
void TreeIntVectSetIterator::define(const TreeIntVectSet& ivs)
{
  m_ivs = &ivs;
  int max = ivs.index.size();
  //  if(max==10) printf("max=10 \n");
  if(boxes.size() < max)
    {
      boxes.resize(max);
      index.resize(max);
      nodes.resize(max);
    }
  begin();
}

inline
bool TreeIntVectSetIterator::ok() const
{
  return m_depth >= 0;
}

inline
void TreeIntVectSetIterator::end()
{
  m_depth = -1;
}

inline
TreeIntVectSet& TreeIntVectSet::operator|=(const IntVect& iv)
{
  return *this|=Box(iv, iv);
}

inline
TreeIntVectSet& TreeIntVectSet::operator-=(const IntVect& iv)
{
  return *this-=Box(iv, iv);
}

inline
void TreeIntVectSetIterator::operator++()
{
  findNext();
}

inline
const IntVect& TreeIntVectSetIterator::operator()() const
{
  return m_current;
}

//=======================================================

inline
TreeIntVectSet::~TreeIntVectSet()
{
  clearTree(m_tree);
}
inline
TreeIntVectSet::TreeIntVectSet(const TreeIntVectSet& a_tivs)
{
  define(a_tivs);
}

inline
TreeIntVectSet::TreeIntVectSet(const Box& a_box)
{
  define(a_box);
}

inline
TreeIntVectSet::TreeIntVectSet()
{
  m_tree.nodes = 0;
  m_depth=1;

}

inline
const Box&
TreeIntVectSet::minBox() const
{
  return m_minBox;
}

inline void TreeIntVectSet::nextNode(int& depth)
{
  index[0] = 0;
  index[depth]++;
  while(index[depth] == TIVS_NODESIZE)
    {
      index[depth] = 0;
      depth--;
      index[depth]++;
    }
}

#endif //  TREEINTVECTSET_H

---