Back to index

supertuxkart  0.5+dfsg1
btUnionFind.h
Go to the documentation of this file.
00001 /*
00002 Bullet Continuous Collision Detection and Physics Library
00003 Copyright (c) 2003-2006 Erwin Coumans  http://continuousphysics.com/Bullet/
00004 
00005 This software is provided 'as-is', without any express or implied warranty.
00006 In no event will the authors be held liable for any damages arising from the use of this software.
00007 Permission is granted to anyone to use this software for any purpose, 
00008 including commercial applications, and to alter it and redistribute it freely, 
00009 subject to the following restrictions:
00010 
00011 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
00012 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
00013 3. This notice may not be removed or altered from any source distribution.
00014 */
00015 
00016 #ifndef UNION_FIND_H
00017 #define UNION_FIND_H
00018 
00019 #include "LinearMath/btAlignedObjectArray.h"
00020 
00021        #define USE_PATH_COMPRESSION 1
00022 
00023 struct btElement
00024 {
00025        int    m_id;
00026        int    m_sz;
00027 };
00028 
00030 // Implements weighted Quick Union with path compression
00031 // optimization: could use short ints instead of ints (halving memory, would limit the number of rigid bodies to 64k, sounds reasonable)
00032 class btUnionFind
00033   {
00034     private:
00035               btAlignedObjectArray<btElement>    m_elements;
00036 
00037     public:
00038          
00039               btUnionFind();
00040               ~btUnionFind();
00041 
00042        
00043               //this is a special operation, destroying the content of btUnionFind.
00044               //it sorts the elements, based on island id, in order to make it easy to iterate over islands
00045               void   sortIslands();
00046 
00047          void reset(int N);
00048 
00049          SIMD_FORCE_INLINE int     getNumElements() const
00050          {
00051                 return int(m_elements.size());
00052          }
00053          SIMD_FORCE_INLINE bool  isRoot(int x) const
00054          {
00055                 return (x == m_elements[x].m_id);
00056          }
00057 
00058          btElement&  getElement(int index)
00059          {
00060                 return m_elements[index];
00061          }
00062          const btElement& getElement(int index) const
00063          {
00064                 return m_elements[index];
00065          }
00066    
00067          void allocate(int N);
00068          void Free();
00069 
00070 
00071 
00072 
00073          int find(int p, int q)
00074               { 
00075                      return (find(p) == find(q)); 
00076               }
00077 
00078               void unite(int p, int q)
00079               {
00080                      int i = find(p), j = find(q);
00081                      if (i == j) 
00082                             return;
00083 
00084 #ifndef USE_PATH_COMPRESSION
00085                      //weighted quick union, this keeps the 'trees' balanced, and keeps performance of unite O( log(n) )
00086                      if (m_elements[i].m_sz < m_elements[j].m_sz)
00087                      { 
00088                             m_elements[i].m_id = j; m_elements[j].m_sz += m_elements[i].m_sz; 
00089                      }
00090                      else 
00091                      { 
00092                             m_elements[j].m_id = i; m_elements[i].m_sz += m_elements[j].m_sz; 
00093                      }
00094 #else
00095                      m_elements[i].m_id = j; m_elements[j].m_sz += m_elements[i].m_sz; 
00096 #endif //USE_PATH_COMPRESSION
00097               }
00098 
00099               int find(int x)
00100               { 
00101                      //assert(x < m_N);
00102                      //assert(x >= 0);
00103 
00104                      while (x != m_elements[x].m_id) 
00105                      {
00106               //not really a reason not to use path compression, and it flattens the trees/improves find performance dramatically
00107        
00108               #ifdef USE_PATH_COMPRESSION
00109                             //
00110                             m_elements[x].m_id = m_elements[m_elements[x].m_id].m_id;
00111               #endif //
00112                             x = m_elements[x].m_id;
00113                             //assert(x < m_N);
00114                             //assert(x >= 0);
00115 
00116                      }
00117                      return x; 
00118               }
00119 
00120 
00121   };
00122 
00123 
00124 #endif //UNION_FIND_H