OctTree.hpp

/*------------------------------------------------------------------------*/
/*                 Copyright 2010 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.  */
/*  Export of this program may require a license from the                 */
/*  United States Government.                                             */
/*------------------------------------------------------------------------*/

#ifndef stk_search_OctTree_hpp
#define stk_search_OctTree_hpp

#include <limits>
#include <iosfwd>
#include <stk_util/util/SimpleArrayOps.hpp>
#include <stk_util/util/StaticAssert.hpp>

namespace stk {

class OctTreeKey ;

}

namespace std {

ostream & operator << ( ostream & , const stk::OctTreeKey & otk);

}

namespace stk {

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() : m_value()
    { Copy<NWord>( m_value , 0u ); }

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

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

  unsigned depth() const ;

  unsigned index( const unsigned Depth ) const ;

  OctTreeKey & clear_index( const unsigned Depth );

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

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

  OctTreeKey & set_value( const value_type * val);

  bool intersect( const OctTreeKey & k ) const ;
};

inline bool operator == ( const OctTreeKey & l, const OctTreeKey & r ) 
  { return Compare<OctTreeKey::NWord>::equal( l.value() , r.value() ); }

inline bool operator != ( const OctTreeKey & l, const OctTreeKey & r ) 
  { return Compare<OctTreeKey::NWord>::not_equal( l.value() , r.value() ); }

inline bool operator < ( const OctTreeKey & l, const OctTreeKey & r ) 
  { return Compare<OctTreeKey::NWord>::less( l.value() , r.value()) ; }

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

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 & k);
}

#endif