OctTree.hpp

00001 /*------------------------------------------------------------------------*/
00002 /*                 Copyright 2010 Sandia Corporation.                     */
00003 /*  Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive   */
00004 /*  license for use of this work by or on behalf of the U.S. Government.  */
00005 /*  Export of this program may require a license from the                 */
00006 /*  United States Government.                                             */
00007 /*------------------------------------------------------------------------*/
00008 
00009 #ifndef stk_search_OctTree_hpp
00010 #define stk_search_OctTree_hpp
00011 
00012 #include <limits>
00013 #include <iosfwd>
00014 #include <stk_util/util/SimpleArrayOps.hpp>
00015 #include <stk_util/util/StaticAssert.hpp>
00016 
00017 namespace stk {
00018 
00019 class OctTreeKey ;
00020 
00021 }
00022 
00023 namespace std {
00024 
00025 ostream & operator << ( ostream & , const stk::OctTreeKey & otk);
00026 
00027 }
00028 
00029 namespace stk {
00030 
00035 class OctTreeKey {
00036 public:
00038   typedef unsigned value_type ;
00039   enum { MaxDepth     = 16 };
00040   enum { MaskIndex    = 0x0f };
00041   enum { BitsPerIndex = 4 };
00042   enum { BitsPerWord  = std::numeric_limits<value_type>::digits };
00043   enum { IndexPerWord = BitsPerWord / BitsPerIndex };
00044   enum { NWord        = MaxDepth / IndexPerWord };
00045   enum { OKBits = StaticAssert< 0 == BitsPerWord % BitsPerIndex >::OK };
00046   enum { OKWord = StaticAssert< 0 == MaxDepth    % IndexPerWord >::OK };
00047 private:
00048   value_type m_value[ NWord ];
00049 public:
00050 
00052   OctTreeKey() : m_value()
00053     { Copy<NWord>( m_value , 0u ); }
00054 
00056   OctTreeKey( const OctTreeKey & k ) : m_value()
00057     { Copy<NWord>( m_value , k.m_value ); }
00058 
00060   OctTreeKey & operator = ( const OctTreeKey & k )
00061     { Copy<NWord>( m_value , k.m_value ); return *this ; }
00062 
00064   unsigned depth() const ;
00065 
00069   unsigned index( const unsigned Depth ) const ;
00070 
00072   OctTreeKey & clear_index( const unsigned Depth );
00073 
00075   OctTreeKey & set_index( const unsigned Depth , const unsigned Index);
00076 
00078   const value_type * value() const { return m_value ; }
00079 
00081   OctTreeKey & set_value( const value_type * val);
00082 
00084   bool intersect( const OctTreeKey & k ) const ;
00085 };
00086 
00088 inline bool operator == ( const OctTreeKey & l, const OctTreeKey & r ) 
00089   { return Compare<OctTreeKey::NWord>::equal( l.value() , r.value() ); }
00090 
00092 inline bool operator != ( const OctTreeKey & l, const OctTreeKey & r ) 
00093   { return Compare<OctTreeKey::NWord>::not_equal( l.value() , r.value() ); }
00094 
00096 inline bool operator < ( const OctTreeKey & l, const OctTreeKey & r ) 
00097   { return Compare<OctTreeKey::NWord>::less( l.value() , r.value()) ; }
00098 
00099 //----------------------------------------------------------------------
00100 
00107 OctTreeKey hsfc3d( const unsigned Depth , const unsigned * const coord );
00108 
00109 //----------------------------------------------------------------------
00110 //----------------------------------------------------------------------
00111 
00112 template<unsigned Depth> struct OctTreeSize ;
00113 
00114 template<>
00115 struct OctTreeSize<0>
00116 { enum { value = 1 }; };
00117 
00118 template<unsigned Depth>
00119 struct OctTreeSize
00120 {
00121   enum { MaxDepth = 10 , N = Depth }; // Size representable by an unsigned int
00122 
00123   enum { OK = StaticAssert< N <= MaxDepth >::OK };
00124 
00125   enum { value = 1 + 8 * OctTreeSize<Depth-1>::value };
00126 };
00127 
00129 unsigned oct_tree_size( const unsigned Depth );
00130 
00132 unsigned oct_tree_offset( const unsigned Depth , const OctTreeKey & k);
00133 }
00134 
00135 #endif
00136 

Generated on Tue Jul 13 09:27:32 2010 for Sierra Toolkit by  doxygen 1.4.7