fork download
copy 
  1. #ifndef FUTILE_NNODE_H_INCLUDED
  2. #define FUTILE_NNODE_H_INCLUDED
  3.  
  4.  
  5. namespace Futile {
  6.  
  7.  
  8. /**
  9.  * NNode represents a node in an n-ary tree.
  10.  * T = data type
  11.  * N = number of children per node
  12.  * H = tree height
  13.  * D = node depth (distance from the root node)
  14.  *
  15.  * The entire tree is contained in a single segement of contiguous memory.
  16.  */
  17. template<typename T, unsigned N, unsigned H, unsigned D>
  18. struct NNode;
  19.  
  20.  
  21. namespace Private {
  22.  
  23.  
  24. template<typename T, unsigned N, unsigned H, unsigned D>
  25. struct NNodeWithParent
  26. {
  27.     typedef NNode<T, N, H, D - 1> Parent;
  28.  
  29.     NNodeWithParent() :
  30.         mParent()
  31.     {
  32.     }
  33.  
  34.     const Parent * parent() const { return mParent; }
  35.  
  36.     Parent * parent() { return mParent; }
  37.  
  38.     Parent * mParent;
  39. };
  40.  
  41.  
  42. template<typename T, unsigned N, unsigned H, unsigned D>
  43. struct NNodeWithChildren
  44. {
  45.     typedef NNode<T, N, H, D + 1> Child;
  46.     NNodeWithChildren()
  47.     {
  48.         for (std::size_t idx = 0; idx < N; ++idx)
  49.         {
  50.             Child & child = mChildren[idx];
  51.             child.mParent = static_cast< NNode<T, N, H, D>* >(this);
  52.         }
  53.     }
  54.  
  55.     const Child & getChild(unsigned idx) const { return mChildren[idx]; }
  56.  
  57.     Child mChildren[N];
  58. };
  59.  
  60.  
  61. template<unsigned D>
  62. struct NNodeCore
  63. {
  64.     enum
  65.     {
  66.         Depth = D
  67.     };
  68. };
  69.  
  70.  
  71. } // namespace Private
  72.  
  73.  
  74.  
  75. /**
  76.  * NNodeBase
  77.  */
  78. template<typename T, unsigned N, unsigned H>
  79. struct NNodeBase
  80. {
  81.     typedef T DataType;
  82.     enum {
  83.         ChildCount = N,
  84.         TreeHeight = H
  85.     };
  86.  
  87.     NNodeBase() :
  88.         mData()
  89.     {
  90.     }
  91.  
  92.     DataType mData;
  93. };
  94.  
  95.  
  96. /**
  97.  * Root node:
  98.  * -> node depth = 0
  99.  * -> no parent
  100.  */
  101. template<typename T, unsigned N, unsigned H>
  102. struct NNode<T, N, H, 0> : NNodeBase<T, N, H>,
  103.                            Private::NNodeCore<0>,
  104.                            Private::NNodeWithChildren<T, N, H, 0>
  105. {
  106.     NNode() :
  107.         Private::NNodeCore<0>(),
  108.         Private::NNodeWithChildren<T, N, H, 0>()
  109.     {
  110.     }
  111. };
  112.  
  113.  
  114. /**
  115.  * Leaf node:
  116.  * -> node depth = tree height
  117.  * -> no children
  118.  */
  119. template<typename T, unsigned N, unsigned H>
  120. struct NNode<T, N, H, H> : NNodeBase<T, N, H>,
  121.                            Private::NNodeWithParent<T, N, H, H>,
  122.                            Private::NNodeCore<H>
  123. {
  124.     typedef NNode<T, N, H, H - 1> Parent;
  125.     NNode() :
  126.         Private::NNodeWithParent<T, N, H, H>(),
  127.         Private::NNodeCore<H>()
  128.     {
  129.     }
  130. };
  131.  
  132.  
  133. /**
  134.  * NNode represents a node in an n-ary tree.
  135.  * T = data type
  136.  * N = number of children per node
  137.  * H = tree height
  138.  * D = node depth (distance from the root node)
  139.  *
  140.  * The entire tree is contained in a single segement of contiguous memory.
  141.  */
  142. template<typename T, unsigned N, unsigned H, unsigned D>
  143. struct NNode : NNodeBase<T, N, H>,
  144.                Private::NNodeWithParent<T, N, H, D>,
  145.                Private::NNodeCore<D>,
  146.                Private::NNodeWithChildren<T, N, H, D>
  147. {
  148.     typedef NNode<T, N, H, D - 1> Parent;
  149.  
  150.     NNode() :
  151.         Private::NNodeWithParent<T, N, H, D>(),
  152.         Private::NNodeCore<D>(),
  153.         Private::NNodeWithChildren<T, N, H, D>()
  154.     {
  155.     }
  156. };
  157.  
  158.  
  159. /**
  160.  * For the root node you can either use:
  161.  * - NNode<T, N, H, 0>
  162.  * - RootNode<T, N, H>
  163.  */
  164. template<typename T, unsigned N, unsigned H>
  165. struct RootNode : public NNode<T, N, H, 0>
  166. {
  167.  
  168. };
  169.  
  170.  
  171. } // namespace Futile
  172.  
  173.  
  174. #endif // FUTILE_NNODE_H_INCLUDED
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In constructor ‘Futile::Private::NNodeWithChildren<T, N, H, D>::NNodeWithChildren()’:
prog.cpp:48: error: ‘size_t’ is not a member of ‘std’
prog.cpp:48: error: expected `;' before ‘idx’
prog.cpp:48: error: ‘idx’ was not declared in this scope
stdout
copy 
Standard output is empty
https://ideone.com/pW6kz
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!