simple-tree.h

模拟器提供了一个简单易用的平台

/**************************************************
 *
  File: simple-tree.h
  Author: Suman Banerjee <[e-mail]>
  Date: July 31, 2001
  Terms: GPL

  NICE implementation in myns

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 **************************************************/

#ifndef _SIMPLE_TREE_H_
#define _SIMPLE_TREE_H_

template <class TreeData>
struct TreeElement {

  TreeData m_data;
  int m_nChildrenCount;
  struct TreeElement ** m_pChildList;
  struct TreeElement * m_pParent;
  
  TreeElement ()
  {
    m_nChildrenCount = 0;
    m_pChildList = NULL;
    m_pParent = NULL;
  }
};

template <class TreeData>
class SimpleTree {

private:
  int m_nSize;
  TreeElement<TreeData> * m_pRoot;

  void SubtreeRemoveAll (TreeElement<TreeData> *te);

public:

  SimpleTree (void) { m_nSize = 0; m_pRoot = NULL; };
  ~SimpleTree (void) { RemoveAll(); };

  inline int GetSize (void) {return m_nSize;};

  inline TreeData GetAt (void * pos) {
    return ((TreeElement<TreeData>*)pos)->m_data;
  }

  inline void * GetRootPosition (void) { return (void *)m_pRoot; };

  inline TreeData GetRoot (void) { 
    if (m_pRoot == NULL)
      return NULL;
    return ((TreeElement<TreeData>*)m_pRoot)->m_data;
  };

  inline int GetChildCount (void * pos) {
    return ((TreeElement<TreeData>*)pos)->m_nChildrenCount;
  };

  void ** GetChildList (void * pos);

  inline void * GetParent (void * pos) {
    return ( (void*)(((TreeElement<TreeData>*)pos)->m_pParent) );
  };

  void * SetRoot (TreeData td);

  void * AddChild (TreeData td, void *parent_pos);
  // void DeleteChild (void *child_pos, void *parent_pos);

  void RemoveAll (void);
};

/* Assumes that pos is a valid tree element in the tree */
template <class TreeData>
void ** SimpleTree<TreeData>::GetChildList (void * pos) {

  TreeElement<TreeData> * te = (TreeElement<TreeData>*)pos;
  if (te->m_nChildrenCount == 0)
    return NULL;
  void ** ret_array = new void * [te->m_nChildrenCount];
  for (int i = 0; i < te->m_nChildrenCount; i++)
    ret_array[i] = (void*)(te->m_pChildList[i]);
  return ret_array;
}

template<class TreeData>
void * SimpleTree<TreeData>::SetRoot (TreeData td) {

  assert (m_pRoot == NULL);
  m_pRoot = new (TreeElement<TreeData>);
  m_pRoot->m_data = td;
  m_nSize ++;
  return (void *)m_pRoot;
}

/* Add a child to a given parent, which is assumed valid.
 * No duplicate checking is done
 */
template<class TreeData>
void * SimpleTree<TreeData>::AddChild (TreeData td, void * parent_pos) {

  if (parent_pos == NULL)
    return SetRoot(td);

  TreeElement<TreeData> * parent_te = (TreeElement<TreeData>*)parent_pos;
  TreeElement<TreeData> ** child_list_new = new (TreeElement<TreeData>*) [parent_te->m_nChildrenCount + 1];
  for (int i = 0; i < parent_te->m_nChildrenCount; i++)
    child_list_new[i] = parent_te->m_pChildList[i];

  TreeElement<TreeData> * child_te = new (TreeElement<TreeData>);
  child_te->m_data = td;
  child_te->m_pParent = parent_te;
  child_list_new[parent_te->m_nChildren_count] = child_te;

  if (parent_te->m_nChildrenCount > 0)
    delete [] parent_te->m_pChildList;
  parent_te->m_pChildList = child_list_new;
  parent_te->m_nChildrenCount ++;

  m_nSize ++;

  return (void *)child_te;
}

template<class TreeData>
void SimpleTree<TreeData>::RemoveAll (void) {

  if (m_nSize == 0)
    return;
  SubtreeRemoveAll(m_pRoot);
  m_pRoot = NULL;
  m_nSize = 0;
  return;
}

template<class TreeData>
void SimpleTree<TreeData>::SubtreeRemoveAll (TreeElement<TreeData> * te) {

  for (int i = 0; i < te->m_nChildrenCount; i++)
    SubtreeRemoveAll(te->m_pChildList[i]);
  delete te;
  return;
}

#endif