CUFTree.hpp

Go to the documentation of this file.

/*
 * Copyright(c):
 * Signal Image and Communications (SIC) Department 
 * http://www.sic.sp2mi.univ-poitiers.fr/ 
 *  - University of Poitiers, France http://www.univ-poitiers.fr 
 *  - XLIM  Institute UMR CNRS 7252  http://www.xlim.fr/ 
 * 
 * and 
 * 
 * D2 Fluid, Thermic and Combustion 
 *  - University of Poitiers, France http://www.univ-poitiers.fr 
 *  - PPRIME Institute -  UPR CNRS 3346  http://www.pprime.fr
 *  - ISAE-ENSMA http://www.ensma.fr
 *
 * Contributor(s):
 * The SLIP team,
 * Benoit Tremblais <tremblais_AT_sic.univ-poitiers.fr>,
 * Laurent David <laurent.david_AT_lea.univ-poitiers.fr>, 
 * Ludovic Chatellier <ludovic.chatellier_AT_univ-poitiers.fr>, 
 * Lionel Thomas <lionel.thomas_AT_univ-poitiers.fr>, 
 * Denis Arrivault <arrivault_AT_sic.univ-poitiers.fr>, 
 * Julien Dombre <julien.dombre_AT_univ-poitiers.fr>.
 *
 * Description:
 * The Simple Library of Image Processing (SLIP) is a new image processing 
 * library. It is written in the C++ language following as much as possible 
 * the ISO/ANSI C++ standard. It is consequently compatible with any system  
 * satisfying the ANSI C++ complience. It works on different Unix , Linux ,  
 * Mircrosoft Windows and Mac OS X plateforms. SLIP is a research library that  
 * was created by the Signal, Image and Communications (SIC) departement of  
 * the XLIM, UMR 7252 CNRS Institute in collaboration with the Fluids, Thermic  
 * and Combustion departement of the P', UPR 3346 CNRS Institute of the  
 * University of Poitiers.
 * 
 * The SLIP Library source code has been registered to the APP (French Agency 
 * for the Protection of Programs) by the University of Poitiers and CNRS, 
 * under  registration number IDDN.FR.001.300034.000.S.P.2010.000.21000.

 * http://www.sic.sp2mi.univ-poitiers.fr/slip/
 *
 * This software is governed by the CeCILL-C license under French law and
 * abiding by the rules of distribution of free software.  You can  use, 
 * modify and/ or redistribute the software under the terms of the CeCILL-C 
 * license as circulated by CEA, CNRS and INRIA at the following URL 
 * http://www.cecill.info.
 * As a counterpart to the access to the source code and  rights to copy,
 * modify and redistribute granted by the license, users are provided only
 * with a limited warranty  and the software's author,  the holder of the
 * economic rights,  and the successive licensors  have only  limited
 * liability.
 * 
 * In this respect, the user's attention is drawn to the risks associated
 * with loading,  using,  modifying and/or developing or reproducing the
 * software by the user in light of its specific status of free software,
 * that may mean  that it is complicated to manipulate,  and  that  also
 * therefore means  that it is reserved for developers  and  experienced
 * professionals having in-depth computer knowledge. Users are therefore
 * encouraged to load and test the software's suitability as regards their
 * requirements in conditions enabling the security of their systems and/or
 * data to be ensured and,  more generally, to use and operate it in the 
 * same conditions as regards security. 
 *
 * The fact that you are presently reading this means that you have had
 * knowledge of the CeCILL-C license and that you accept its terms.
 */


#ifndef SLIP_CUFTREE_HPP
#define SLIP_CUFTREE_HPP

#include <cstdio>

namespace slip
{
  //  extern long int NbOfCrossedEdges(0);
  static long int NbOfCrossedEdges_(0);
  template<typename T>
  class CUFTree
  {
  public :
    
    typedef T value_type;
    typedef CUFTree<T> self;
    typedef self* self_pointer;
    
    typedef std::size_t size_type;
    
    typedef value_type& reference;
    typedef const value_type& const_reference;
 
    
    CUFTree();

    CUFTree( self_pointer ATree );

    ~CUFTree();

    self& operator=(const self & rsh);
    
    void set_Element(const_reference inel);

    value_type get_Element();

    void set_FFather(self_pointer inFFather);
 
 

    self_pointer find();
    
    void merge( self_pointer ATree );
    
  private:

    self_pointer FFather;      // the father adress
    size_type FHeight; // Sup value of the tree height
    value_type Element; //label if needed 
  };
    
}//slip::

namespace slip
{
  template <typename T>
  inline
  CUFTree<T>::CUFTree() :
    FFather (this),
    FHeight(0),
    Element()
  {}
  
  template <typename T>
  inline
  CUFTree<T>::CUFTree(CUFTree* ATree) :
    FFather (ATree),
    FHeight(0),
    Element(ATree->Element)
  {}

  template <typename T>
  inline
  CUFTree<T>::~CUFTree()
  {}

  template<typename T>
  inline
  CUFTree<T>& CUFTree<T>::operator=(const CUFTree<T> & rhs)
  {
    if(this != &rhs)
      {
                if(rhs.FFather == &rhs)
                  this->FFather = this;
                else
                  this->FFather = rhs.FFather;
                this->FHeight = rhs.FHeight;
                this->Element = rhs.Element;
      }
    return *this;
  }

  template <typename T>
  inline
  void CUFTree<T>::set_Element(const T & inel)
  {
     this->Element = inel;
  }

  template <typename T>
  inline
  T CUFTree<T>::get_Element()
  {
    return ((this->find())->Element);
    //   return (this->Element);
  }

  template <typename T>
  inline
  void CUFTree<T>::set_FFather(CUFTree* inFFather)
  {
    this->FFather = inFFather;
  }

 

  template <typename T>
  inline
  CUFTree<T>* CUFTree<T>::find()
  {
    CUFTree<T>* res = this->FFather;
    while ( res->FFather!=res )
      {
                ++NbOfCrossedEdges_; // The number of crossed edges is increased
                res = res->FFather;
      }
    
    CUFTree<T>* actu = this;
    CUFTree<T>* next = NULL;
    while ( actu!=res )
      {
                next = actu->FFather;
                actu->FFather = res;
                //              actu->Element = res->Element;
                actu = next;
      }
    return res;
  }

  template <typename T>
  inline
  void CUFTree<T>::merge( CUFTree<T>* ATree )
  {
    this->Element = ATree->Element;
    CUFTree<T>* tree1 = find();
    CUFTree<T>* tree2 = ATree->find();

    if ( tree1==tree2 ) 
      return; // Both trees are already merged
    
    // fusion.
    if ( tree1->FHeight < tree2->FHeight )
      {
                tree1->FFather=tree2;
      }
    else
      {
                tree2->FFather=tree1;
                if ( tree1->FHeight == tree2->FHeight )
                  ++tree1->FHeight; // the height is increased
      }
  }
  
}//slip::   

#endif //CUFTREE_HPP