Back to index

supertuxkart  0.5+dfsg1
Public Member Functions | Private Attributes
btUnionFind Class Reference

UnionFind calculates connected subsets. More...

#include <btUnionFind.h>

Collaboration diagram for btUnionFind:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 btUnionFind ()
 ~btUnionFind ()
void sortIslands ()
 this is a special operation, destroying the content of btUnionFind. it sorts the elements, based on island id, in order to make it easy to iterate over islands
void reset (int N)
SIMD_FORCE_INLINE int getNumElements () const
SIMD_FORCE_INLINE bool isRoot (int x) const
btElementgetElement (int index)
const btElementgetElement (int index) const
void allocate (int N)
void Free ()
int find (int p, int q)
void unite (int p, int q)
int find (int x)

Private Attributes

btAlignedObjectArray< btElementm_elements

Detailed Description

UnionFind calculates connected subsets.

Definition at line 32 of file btUnionFind.h.


Constructor & Destructor Documentation

Definition at line 28 of file btUnionFind.cpp.

{ 

}

Definition at line 22 of file btUnionFind.cpp.

{
       Free();

}

Here is the call graph for this function:


Member Function Documentation

void btUnionFind::allocate ( int  N)

Definition at line 33 of file btUnionFind.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

int btUnionFind::find ( int  p,
int  q 
) [inline]

Definition at line 73 of file btUnionFind.h.

              { 
                     return (find(p) == find(q)); 
              }

Here is the caller graph for this function:

int btUnionFind::find ( int  x) [inline]

Definition at line 99 of file btUnionFind.h.

              { 
                     //assert(x < m_N);
                     //assert(x >= 0);

                     while (x != m_elements[x].m_id) 
                     {
              //not really a reason not to use path compression, and it flattens the trees/improves find performance dramatically
       
              #ifdef USE_PATH_COMPRESSION
                            //
                            m_elements[x].m_id = m_elements[m_elements[x].m_id].m_id;
              #endif //
                            x = m_elements[x].m_id;
                            //assert(x < m_N);
                            //assert(x >= 0);

                     }
                     return x; 
              }

Definition at line 37 of file btUnionFind.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

btElement& btUnionFind::getElement ( int  index) [inline]

Definition at line 58 of file btUnionFind.h.

         {
                return m_elements[index];
         }

Here is the caller graph for this function:

const btElement& btUnionFind::getElement ( int  index) const [inline]

Definition at line 62 of file btUnionFind.h.

         {
                return m_elements[index];
         }

Definition at line 49 of file btUnionFind.h.

         {
                return int(m_elements.size());
         }

Here is the call graph for this function:

Here is the caller graph for this function:

SIMD_FORCE_INLINE bool btUnionFind::isRoot ( int  x) const [inline]

Definition at line 53 of file btUnionFind.h.

         {
                return (x == m_elements[x].m_id);
         }
void btUnionFind::reset ( int  N)

Definition at line 43 of file btUnionFind.cpp.

{
       allocate(N);

       for (int i = 0; i < N; i++) 
       { 
              m_elements[i].m_id = i; m_elements[i].m_sz = 1; 
       } 
}

Here is the call graph for this function:

Here is the caller graph for this function:

this is a special operation, destroying the content of btUnionFind. it sorts the elements, based on island id, in order to make it easy to iterate over islands

Definition at line 66 of file btUnionFind.cpp.

{

       //first store the original body index, and islandId
       int numElements = m_elements.size();
       
       for (int i=0;i<numElements;i++)
       {
              m_elements[i].m_id = find(i);
              m_elements[i].m_sz = i;
       }
       
        // Sort the vector using predicate and std::sort
         //std::sort(m_elements.begin(), m_elements.end(), btUnionFindElementSortPredicate);
         m_elements.quickSort(btUnionFindElementSortPredicate());

}

Here is the call graph for this function:

Here is the caller graph for this function:

void btUnionFind::unite ( int  p,
int  q 
) [inline]

Definition at line 78 of file btUnionFind.h.

              {
                     int i = find(p), j = find(q);
                     if (i == j) 
                            return;

#ifndef USE_PATH_COMPRESSION
                     //weighted quick union, this keeps the 'trees' balanced, and keeps performance of unite O( log(n) )
                     if (m_elements[i].m_sz < m_elements[j].m_sz)
                     { 
                            m_elements[i].m_id = j; m_elements[j].m_sz += m_elements[i].m_sz; 
                     }
                     else 
                     { 
                            m_elements[j].m_id = i; m_elements[i].m_sz += m_elements[j].m_sz; 
                     }
#else
                     m_elements[i].m_id = j; m_elements[j].m_sz += m_elements[i].m_sz; 
#endif //USE_PATH_COMPRESSION
              }

Here is the call graph for this function:

Here is the caller graph for this function:


Member Data Documentation

Definition at line 35 of file btUnionFind.h.


The documentation for this class was generated from the following files: