/Users/mourrain/Devel/mmx/shape/include/shape/node.hpp

Go to the documentation of this file.

/*****************************************************************************
 * M a t h e m a g i x
 *****************************************************************************
 * kdnode
 * 2009-05-18
 * Julien Wintz & Bernard Mourrain
 *****************************************************************************
 *               Copyright (C) 2009 INRIA Sophia-Antipolis
 *****************************************************************************
 * Comments :
 ****************************************************************************/
# ifndef shape_node_hpp
# define shape_node_hpp

# include <iostream>
# include <vector>
# define Node node<Object, CELL>
//====================================================================
namespace mmx {
namespace shape {

template <class _Object, class _CELL> class node
{
public:
  enum NODE_TYPE { LEFT, RIGHT } ;
  typedef _Object Object;
  typedef _CELL   CELL;
  typedef _CELL   Cell;

public:
  node(void) ;
  node(Object object, CELL cl) ;
  node(node<Object, CELL>* parent, CELL & cl, NODE_TYPE nodeType, int v=0) ;
  node(node<Object, CELL>* left, node<Object, CELL> * right, CELL cl, int v=0) ;

protected:
  node(Node& node) ;

public:    
  inline void set_cell(const CELL & c) { m_cell = c ; }
  inline void set_parent(Node * n)     { m_parent = n ; }
  
  inline void set_leftchild(node<Object, CELL> * n)  { m_left = n ; }
  inline void set_rightchild(node<Object, CELL> * n) { m_right = n ; }
  
  inline const CELL& get_cell(void) const { return m_cell; } 
  inline       CELL& get_cell(void)       { return m_cell ; }
  
  inline Object object(void) { return m_objects.front() ; }
  
  inline NODE_TYPE type(void) const { return m_type ; }
  inline int split_dir(void) const { return m_var; }
  
  inline node<Object, CELL> * left  (void) { return m_left ; }
  inline node<Object, CELL> * right (void) { return m_right ; }
  inline node<Object, CELL> * parent(void) { return m_parent ; }
  
  inline const node<Object, CELL> * left  (void) const { return m_left ; }
  inline const node<Object, CELL> * right (void) const { return m_right ; }
  inline const node<Object, CELL> * parent(void) const { return m_parent ; }
    
  int    var(void) const {return this->m_var;}
  bool   is_leaf(void) const;
  size_t leaf_distance() const;

public:   
  CELL                m_cell ;
  std::vector<Object> m_objects ;
  NODE_TYPE           m_type ;
  int                 m_var ;
    
  Node * m_parent  ;   
  Node * m_left ;
  Node * m_right ;

  int depth ;
  int index ;
} ;

//--------------------------------------------------------------------
template<class Object, class CELL> node<Object, CELL>::node(void)
{ 
    m_type   = LEFT ;
    m_var    = 0 ;

    m_parent = NULL ;
    m_left   = NULL;
    m_right  = NULL;

    m_cell   = NULL ;


    depth = 0;
    index = 0;
} 

template<class Object, class CELL> node<Object, CELL>::node(Object object, CELL cl)
{ 
    this->m_type   = LEFT ;
    this->m_var    = 0 ;

    this->m_parent = NULL ;
    this->m_left   = NULL;
    this->m_right  = NULL;

    this->m_cell   = cl ;
    m_objects.push_back(object) ;

    depth = 0;
    index = 0;
} 

template <class Object, class CELL> node<Object, CELL>::node(node<Object, CELL> * left, node<Object, CELL> * right, CELL cl, int v) {

    this->m_parent = NULL ;
    this->m_cell   = cl ;
    this->m_var    = v ;

    left->type  = LEFT ;  left->parent = this ; m_left = left; 
    right->type = RIGHT; right->parent = this ; m_right= right;

    depth = left->depth-1 ;
}

  template <class Object, class CELL> node<Object, CELL>::node(node<Object, CELL> * parent, CELL & cl, NODE_TYPE type, int v)
{  
    this->m_cell   = cl ;
    this->m_type   = type ; 
    this->m_var    = v ;
    this->m_parent = parent ;

    this->m_left   = NULL;
    this->m_right  = NULL;

    depth = parent->depth+1 ;

    switch(type) { 
    case LEFT : parent->set_leftchild(this) ; break ; 
    case RIGHT: parent->set_rightchild(this) ; break ;  
    default: std::cerr << "Error : the node's type isn't appropriate \n" ; break ;
    }
}

template<class Object, class CELL> bool node<Object, CELL>::is_leaf(void) const
{
    if((m_left == NULL) && (m_right == NULL) )
        return true; 
    return false; 
} 

template<class Object, class CELL> size_t node<Object, CELL>::leaf_distance(void) const
{
        if ( this->is_leaf() )
                return 0;

        struct inner {
                size_t operator()( const Node* node ) {
                        if ( node == 0 )
                                return 0;
                        else
                                return node->leaf_distance();
                }
        } I;

        size_t d = 0;
        d = std::min( d, I(m_left)  );
        d = std::min( d, I(m_right) );

        return d+1;
}


} ; // namespace shape
} ; // namespace mmx
//====================================================================
# undef Node
# endif // shape_node_hpp