include/LCUtility/QuickUnion.h

0001 /**
0002  *  @file   LCContent/include/LCUtility/QuickUnion.h
0003  *
0004  *  @brief  Header file for the quick union class
0005  *
0006  *  $Log: $
0007  */
0008 #ifndef LC_QUICK_UNION_H
0009 #define LC_QUICK_UNION_H 1
0010
0011 #include <vector>
0012
0013 namespace lc_content {
0014
0015 /**
0016  *  @brief  QuickUnion class
0017  */
0018 class QuickUnion {
0019 public:
0020   /**
0021    *  @brief  Constructor
0022    *
0023    *  @param  nBranches the number of original indices
0024    */
0025   QuickUnion(const unsigned nBranches);
0026
0027   /**
0028    *  @brief  Get the current number of target indices
0029    *
0030    *  @return the current number of target indices
0031    */
0032   int Count() const;
0033
0034   /**
0035    *  @brief  Find the current target index for provided index p
0036    *
0037    *  @param  p index p
0038    */
0039   unsigned int Find(unsigned p);
0040
0041   /**
0042    *  @brief  Whether two original indices are now connected
0043    *
0044    *  @param  p index p
0045    *  @param  q index q
0046    *
0047    *  @return boolean
0048    */
0049   bool Connected(unsigned p, unsigned q);
0050
0051   /**
0052    *  @brief  Unite two indices
0053    *
0054    *  @param  p index p
0055    *  @param  q index q
0056    */
0057   void Unite(unsigned p, unsigned q);
0058
0059 private:
0060   std::vector<unsigned> m_id; ///< Stores target index for each original index
0061   // std::vector<unsigned> m_size;     ///< Stores number of connected indices, used for book-keeping
0062   int m_count; ///< The current number of target indices
0063 };
0064
0065 //------------------------------------------------------------------------------------------------------------------------------------------
0066
0067 inline QuickUnion::QuickUnion(const unsigned int nBranches) {
0068   m_count = nBranches;
0069   m_id.resize(nBranches);
0070   // m_size.resize(nBranches);
0071
0072   for (unsigned int i = 0; i < nBranches; ++i) {
0073     m_id[i] = i;
0074     // m_size[i] = 1;
0075   }
0076 }
0077
0078 //------------------------------------------------------------------------------------------------------------------------------------------
0079
0080 inline int QuickUnion::Count() const { return m_count; }
0081
0082 //------------------------------------------------------------------------------------------------------------------------------------------
0083
0084 inline unsigned int QuickUnion::Find(unsigned int p) {
0085   while (p != m_id[p]) {
0086     m_id[p] = m_id[m_id[p]];
0087     p = m_id[p];
0088   }
0089
0090   return p;
0091 }
0092
0093 //------------------------------------------------------------------------------------------------------------------------------------------
0094
0095 inline bool QuickUnion::Connected(const unsigned int p, const unsigned int q) {
0096   return (this->Find(p) == this->Find(q));
0097 }
0098
0099 //------------------------------------------------------------------------------------------------------------------------------------------
0100
0101 inline void QuickUnion::Unite(const unsigned int p, const unsigned int q) {
0102   const unsigned int rootP(this->Find(p));
0103   const unsigned int rootQ(this->Find(q));
0104
0105   m_id[p] = q;
0106
0107   // TODO finalise implementation of Unite function
0108
0109   // if (m_size[rootP] < m_size[rootQ])
0110   //{
0111   m_id[rootP] = rootQ;
0112   //    m_size[rootQ] += m_size[rootP];
0113   //}
0114   // else
0115   //{
0116   //    m_id[rootQ] = rootP;
0117   //    m_size[rootP] += m_size[rootQ];
0118   //}
0119
0120   --m_count;
0121 }
0122
0123 } // namespace lc_content
0124
0125 #endif // LC_QUICK_UNION_H