hkUnionFind.h
上传用户:yisoukefu
上传日期:2020-08-09
资源大小:39506k
文件大小:4k
源码类别:

其他游戏

开发平台:

Visual C++

  1. /* 
  2.  * 
  3.  * Confidential Information of Telekinesys Research Limited (t/a Havok). Not for disclosure or distribution without Havok's
  4.  * prior written consent. This software contains code, techniques and know-how which is confidential and proprietary to Havok.
  5.  * Level 2 and Level 3 source code contains trade secrets of Havok. Havok Software (C) Copyright 1999-2009 Telekinesys Research Limited t/a Havok. All Rights Reserved. Use of this software is subject to the terms of an end user license agreement.
  6.  * 
  7.  */
  8. #ifndef HK_UNIONFIND_H
  9. #define HK_UNIONFIND_H
  10. #include <Common/Base/hkBase.h>
  11. #include <Common/Base/Container/LocalArray/hkLocalBuffer.h>
  12. /// A class for partitioning sets into connected subsets.
  13. /// This implementation uses the integers [0,n] as nodes
  14. /// and generates subsets all at once via the setEdges method.
  15. /// We can then query for (a) connected nodes or (b) the sets
  16. /// of edges which connect the nodes.
  17. ///
  18. /// Example use:n
  19. /// hkUnionFind unionFind;n
  20. /// hkUnionFind::EdgeVector edges;n
  21. /// // pushBack objects created using hk_make_pair(edgeStart,edgeEnd)n
  22. /// unionFind.setEdges(edges, numberOfVertices);n
  23. /// // Now we can extract all groups one at a time using getNextGroup()n
  24. class hkUnionFind
  25. {
  26. public:
  27. typedef hkFixedArray<int> IntArray;
  28. public:
  29. HK_DECLARE_NONVIRTUAL_CLASS_ALLOCATOR(HK_MEMORY_CLASS_BASE, hkUnionFind);
  30. /// Constructor which takes a pointer to a working buffer
  31. hkUnionFind( IntArray& parents, int numElements );
  32. /// Destructor.
  33. ~hkUnionFind(){}
  34. /// add an edge
  35. void addEdge( int i1, int i2 );
  36. /// replace each parent by the group number, also returns the number of elements in each group
  37. /// can only be called once
  38. void assignGroups( hkArray<int>& elementsPerGroup );
  39. HK_FORCE_INLINE hkBool isOneGroup() { return m_parents[0] == -m_numNodes; }
  40.             /// Produces an array of the elements of each group in order. If there are n0 members in group 0, and n1 in group 1 etc, then
  41.             /// first n0 elements will be the members of group 0 the next n1 will be elements of group2 and so forth
  42.             /// This method must be called after 'assignGroups'
  43.         void sortByGroupId(const hkArray<int>& elementsPerGroup,hkArray<int>& orderedGroups) const;
  44. /// reindex the parents end elementsPerGroup. Can only be called after assignGroups()
  45. void reindex( const hkFixedArray<int>& reindex, int numNewGroups, hkArray<int>& elementsPerGroup );
  46. /// reindex, so that the biggest group is now on index 0. returns the old index of the biggest group
  47. int moveBiggestGroupToIndexZero( hkArray<int>& elementsPerGroup );
  48. // Find the root node of node i
  49. int findRootOfNode(int i);
  50. // Merge two sets
  51. void unionRoots(int r1, int r2);
  52. private:
  53. HK_FORCE_INLINE int _findRootOfNode(int i);
  54. HK_FORCE_INLINE void _unionRoots(int r1, int r2);
  55. /// this flattens the tree.
  56. void collapseTree();
  57. public:
  58. // i'th element contains parent of node i
  59. IntArray& m_parents;
  60. int m_numNodes;
  61. };
  62. #endif //HAVOK_UNIONFIND_H
  63. /*
  64. * Havok SDK - NO SOURCE PC DOWNLOAD, BUILD(#20090216)
  65. * Confidential Information of Havok.  (C) Copyright 1999-2009
  66. * Telekinesys Research Limited t/a Havok. All Rights Reserved. The Havok
  67. * Logo, and the Havok buzzsaw logo are trademarks of Havok.  Title, ownership
  68. * rights, and intellectual property rights in the Havok software remain in
  69. * Havok and/or its suppliers.
  70. * Use of this software for evaluation purposes is subject to and indicates
  71. * acceptance of the End User licence Agreement for this product. A copy of
  72. * the license is included with this software and is also available at www.havok.com/tryhavok.
  73. */