disjointSet.h

Go to the documentation of this file.

#ifndef DLR_COMPUTERVISION_DISJOINTSET_H
#define DLR_COMPUTERVISION_DISJOINTSET_H


// xxx
#include <iostream>

namespace dlr {

  namespace computerVision {

    namespace privateCode {
      
      template <class Type>
      class DisjointSet {
      public:

        DisjointSet()
          : m_parentPtr(this), m_rank(0), m_size(1), m_payload() {
          if(m_parentPtr != this) {
            std::cout << "Ack!!" << std::endl;
          }
        }


        DisjointSet(const Type& payload)
          : m_parentPtr(this), m_rank(0), m_size(1), m_payload(payload) {};


        virtual
        ~DisjointSet() {}

#if 0

        DisjointSet&
        find() {
          if(m_parentPtr == this) {
            return *this;
          }
          m_parentPtr = &(m_parentPtr->find());
          return *m_parentPtr;
        }

#elif 1
      
        DisjointSet&
        find() {
          // Follow parent pointers to find the head of the tree.
          DisjointSet* headPtr = this;
          while(headPtr->m_parentPtr != headPtr) {
            headPtr = headPtr->m_parentPtr;
          }

          // Now do the same thing again, but this time update all of
          // the parent pointers to point directly at the head.
          DisjointSet* updatePtr = this;
          while(updatePtr->m_parentPtr != updatePtr) {
            DisjointSet* tmpPtr = updatePtr->m_parentPtr;
            updatePtr->m_parentPtr = headPtr;
            updatePtr = tmpPtr;
          }
          return *m_parentPtr;
        }

#else
      
        DisjointSet&
        find() {
          DisjointSet* headPtr = this;
          while(headPtr->m_parentPtr != headPtr) {
            headPtr = headPtr->m_parentPtr;
          }
          m_parentPtr = headPtr;
          return *m_parentPtr;
        }

#endif
      
        void
        merge(DisjointSet& other) {
          DisjointSet& myParent = this->find();
          DisjointSet& otherParent = other.find();
          if(&myParent == &otherParent) {
            return;
          }
          if(myParent.m_rank > otherParent.m_rank) {
            otherParent.m_parentPtr = &myParent;
            myParent.m_size += otherParent.m_size;
          } else if(myParent.m_rank < otherParent.m_rank) {
            myParent.m_parentPtr = &otherParent;
            otherParent.m_size += myParent.m_size;
          } else {
            otherParent.m_parentPtr = &myParent;
            myParent.m_size += otherParent.m_size;
            ++(myParent.m_rank);
          }
        }
      

        const Type&
        getPayload() const {return m_payload;}
        

        size_t
        getSize() {return (this->find()).m_size;}


        void
        setPayload(const Type& payload) {m_payload = payload;}
        
      protected:

        DisjointSet* m_parentPtr;
        size_t m_rank;
        size_t m_size;

        Type m_payload;
      };
      
    } // namespace privateCode
    
  } // namespace computerVision
  
} // namespace dlr


/* ============ Definitions of inline & template functions ============ */


namespace dlr {

  namespace computerVision {


  } // namespace computerVision
  
} // namespace dlr

#endif /* #ifndef DLR_COMPUTERVISION_DISJOINTSET_H */