OctTree.hpp

/*------------------------------------------------------------------------*/
/*      phdMesh : Parallel Heterogneous Dynamic unstructured Mesh         */
/*                Copyright (2007) Sandia Corporation                     */
/*                                                                        */
/*  Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive   */
/*  license for use of this work by or on behalf of the U.S. Government.  */
/*                                                                        */
/*  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 Free Software   */
/*  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301   */
/*  USA                                                                   */
/*------------------------------------------------------------------------*/
#ifndef pddgeom_OctTree_hpp
#define pddgeom_OctTree_hpp

#include <limits>
#include <iosfwd>
#include <util/Basics.hpp>
#include <util/SimpleArrayOps.hpp>

namespace phdmesh {

class OctTreeKey ;

}

namespace std {

ostream & operator << ( ostream & , const phdmesh::OctTreeKey & );

}

namespace phdmesh {

class OctTreeKey {
public:
  typedef unsigned value_type ;
  enum { MaxDepth     = 16 };
  enum { MaskIndex    = 0x0f };
  enum { BitsPerIndex = 4 };
  enum { BitsPerWord  = std::numeric_limits<value_type>::digits };
  enum { IndexPerWord = BitsPerWord / BitsPerIndex };
  enum { NWord        = MaxDepth / IndexPerWord };
  enum { OKBits = StaticAssert< 0 == BitsPerWord % BitsPerIndex >::OK };
  enum { OKWord = StaticAssert< 0 == MaxDepth    % IndexPerWord >::OK };
private:
  value_type m_value[ NWord ];
public:

  OctTreeKey()
    { Copy<NWord>( m_value , 0u ); }

  OctTreeKey( const OctTreeKey & k )
    { Copy<NWord>( m_value , k.m_value ); }

  OctTreeKey & operator = ( const OctTreeKey & k )
    { Copy<NWord>( m_value , k.m_value ); return *this ; }

  bool operator == ( const OctTreeKey & k ) const
    { return Equal<NWord>( m_value , k.m_value ); }

  bool operator != ( const OctTreeKey & k ) const
    { return Equal<NWord>( m_value , k.m_value ); }

  bool operator < ( const OctTreeKey & k ) const
    { return Less<NWord>( m_value , k.m_value ); }

  unsigned depth() const ;

  template<unsigned Depth> unsigned index() const ;

  unsigned index( const unsigned Depth ) const ;

  template<unsigned D> OctTreeKey & clear_index() ;

  OctTreeKey & clear_index( const unsigned Depth );

  template<unsigned D> OctTreeKey & set_index( const unsigned );

  OctTreeKey & set_index( const unsigned Depth , const unsigned );

  OctTreeKey & clear();

  OctTreeKey & set_maximum();

  const value_type * value() const { return m_value ; }

  OctTreeKey & set_value( const value_type * );

  bool intersect( const OctTreeKey & k ) const ;

private:
  void throw_depth( const unsigned ) const ;
  void throw_index( const unsigned , const unsigned ) const ;
};

//----------------------------------------------------------------------

OctTreeKey hsfc3d( const unsigned Depth , const unsigned * const coord );

//----------------------------------------------------------------------
//----------------------------------------------------------------------

template<unsigned Depth> struct OctTreeSize ;

template<>
struct OctTreeSize<0>
{ enum { value = 1 }; };

template<unsigned Depth>
struct OctTreeSize
{
  enum { MaxDepth = 10 , N = Depth }; // Size representable by an unsigned int

  enum { OK = StaticAssert< N <= MaxDepth >::OK };

  enum { value = 1 + 8 * OctTreeSize<Depth-1>::value };
};

unsigned oct_tree_size( const unsigned Depth );

unsigned oct_tree_offset( const unsigned Depth , const OctTreeKey & );

template<unsigned Depth>
inline
unsigned oct_tree_offset( const OctTreeKey & k )
{ return oct_tree_offset( Depth , k ); }

}

//----------------------------------------------------------------------
//----------------------------------------------------------------------

namespace phdmesh {

template<unsigned Depth>
inline
unsigned OctTreeKey::index() const
{
  enum { OK = StaticAssert< 0 < Depth && Depth <= MaxDepth >::OK };
  enum { which = ( Depth - 1 ) / IndexPerWord };
  enum { shift = BitsPerWord - BitsPerIndex * ( Depth % IndexPerWord ) };

  return ( m_value[ which ] >> shift ) & MaskIndex ;
}

template<unsigned Depth>
inline
OctTreeKey & OctTreeKey::clear_index()
{
  enum { OK = StaticAssert< 0 < Depth && Depth <= MaxDepth >::OK };
  enum { which = ( Depth - 1 ) / IndexPerWord };
  enum { shift = BitsPerWord - BitsPerIndex * ( Depth % IndexPerWord ) };

  const value_type m = MaskIndex ;

  m_value[ which ] &= ~( m << shift );

  return *this ;
}

template<unsigned Depth>
inline
OctTreeKey & OctTreeKey::set_index( const unsigned Index )
{
  enum { OK = StaticAssert< 0 < Depth && Depth <= MaxDepth >::OK };
  enum { which = ( Depth - 1 ) / IndexPerWord };
  enum { shift = BitsPerWord - BitsPerIndex * ( Depth % IndexPerWord ) };

  if ( 8 < Index ) { throw_index( Depth , Index ); }

  const value_type m = MaskIndex ;

  ( m_value[which] &= ~( m << shift ) ) |= Index << shift ;

  return *this ;
}

}

#endif