NTree.hh

Go to the documentation of this file.

/*
 * class NTree
 *
 * $Date$
 * $Revision$
 *
 */

#ifndef NTREE_HH__
#define NTREE_HH__

#include "WImage/miscdefs.h"
#include <stdexcept>

#ifndef _WIN32_WCE
#include <iostream>
#endif


template < class Type > class 
NTree 
{
public:
  NTree (int nChildren, NTree < Type > *parent = NULL, int position = -1);
  NTree (int nChildren, Type &data, 
         int position = -1, NTree < Type > *parent = NULL);
  ~NTree (void);
  inline bool isRoot (void) const { return m_parent == NULL; }
  inline int position (void) const { return m_position; }
  inline int aryness (void) const { return m_aryness; }
  inline bool hasLeftSibling (void) const { 
    return !isRoot () && m_position > 0 
      && m_parent->hasChildAt (m_position - 1); 
  }
  inline bool hasRightSibling (void) const { 
    return !isRoot () && m_position < m_aryness - 1 
      && m_parent->hasChildAt (m_position + 1); 
  }
  inline bool hasChildAt (int pos) const { 
    return indexOK (pos) && m_children[pos] != NULL; 
  }
  inline bool hasChildren (void) const {
    int i; for (i = 0; i < m_aryness && !hasChildAt (i); i++) { }
    return i != m_aryness;
  }
  int card (void) const;
  bool equals (const NTree &tree) const;
  NTree < Type > *clone (void) const; 
  inline void destroyAt (int pos) { DELETE (m_children[pos]); }
  void appendAt (int pos, NTree < Type > *tree); 
  void appendAt (int pos, const Type &data); 
  inline Type &data (void) { return m_data; }
  inline NTree < Type > &childAt (int pos) { 
    if (!indexOK (pos) || m_children[pos] == NULL)
      {
        throw std::invalid_argument ("childAt: no child at this position");
      }
    return *m_children[pos];
  } 
  NTree < Type > &leftSibling (void) {
    if (!hasLeftSibling ())
      {
        throw std::invalid_argument ("leftSibling: no left sibling");
      }
    return *m_parent->m_children[m_position - 1];
  }
  NTree < Type > &rightSibling (void) {
    if (!hasRightSibling ())
      {
        throw std::invalid_argument ("rightSibling: no right sibling");
      }
    return *m_parent->m_children[m_position + 1];
  }
  
protected:
  void init (int nChildren, int position, NTree < Type > *parent);
  void appendNGenerations (int levels); 
  inline bool indexOK (int pos) const { return pos >= 0 && pos < m_aryness; }
  void copyLeaves (NTree < Type > &dst, const NTree < Type > &src) const;
  
  NTree < Type > **m_children;

  NTree < Type > *m_parent;

  Type m_data;

  int m_aryness;
  int m_position;
}; /* class NTree */

#include "../NTree.cc"

#endif /* NTREE_HH__ */