Tree Data Structure Struct

I have a hypothetical Tree<T> struct in mind. Before I begin implementing it I'm wondering if I traveling down a correct path. One thing I'm not sure how to do is initialize the protected datas. Open to alternative solutions.

Code (CSharp):

1. using System;
2. using Unity.Collections;
3. using Unity.Entities;
4.  
5. public struct Tree<T>
6. {      
7.     // nodeKey, nodeValue                                      
8.     protected NativeHashMap<int, T> nodes;        
9.  
10.     // child->parent relationship model: (childKey, parentKey)
11.     // parent->children alternative: NativeMultiHashmap<int, int> parentChildrenMap (parentKey, childrenKeys)
12.     protected NativeHashMap<int, int> childParentMap;
13.                                                      
14.     // list of nodeKeys formerly used by deleted nodeValues
15.     protected NativeList<int> recycledKeys;
16.     // number of node key:value pairs      
17.     protected int nodeCount;
18.     // the only nodeKey that isn't a value in childParentMap (root has no parent)                          
19.     protected int rootKey;
20.  
21.  
22.  
23.     // return nodeKey, nodeCount++
24.     public int AddNode(T value, int parentKey){...}  
25.     public void RemoveNode(int nodeKey){...}
26.  
27.     public int GetNodeKey(T value) {...}
28.     public NativeArray<int> GetNodeKeys(NativeArray<T> nodeValues){...}
29.  
30.     public int GetNodeValue(int nodeKey) {...}
31.     public NativeArray<T> GetNodeValues(NativeArray<int> nodeKeys){...}
32.  
33.     public int GetParentKey(int childKey){...}
34.     public T GetParentValue (int childKey){...}
35.  
36.     public NativeArray<int> GetChildrenKeys(int parentKey){...}
37.     public NativeArray<T> GetChildrenValues (int parentKey){...}
38.  
39.     // return root nodeKey
40.     // if oldRootNodeNewParentKey is null and an old Root Node exists, the old root node is removed.
41.     public int SetRootNode(T nodeValue, int? oldRootNodeNewParentKey){}
42.     public void SetRootNode(int nodeKey, int? oldRootNodeNewParentKey){}
43.  
44.     // return a recycled key after removing it from list, or nodeCount + 1
45.     protected int GetNewKey(){...}
46.  
47.     public int GetNodeCount(){ return nodeCount; }
48. }
49.  
50.  
51.  
52.  
53. // example use cases:
54.  
55. /* Doesn't work, reasoning in comments:
56. public struct SomeBuffer : IBufferElementData
57. {
58.     public Tree<Float3> treeGraph;
59. }*/
60.  
61. public struct SomeComponent : IComponentData
62. {
63.     public Tree<Float3> treeGraph;
64. }
65.  
66. public class SomeSystem : ComponentSystem
67. {
68.     Tree<Float3> treeGraph;
69.  
70.     protected override void OnCreate(){}
71.     protected override void OnUpdate(){}
72. }

 

I have similar compound data structures. A few points to help you out:

• No need to use protected for fields in a struct. Make them private or internal.
• Make your Tree an IDisposable and allow it to dispose the native container fields.
• Add a constructor that takes an Allocator type so that you can allocate the native container fields with the correct Allocator.
• An IBufferElementData can't contain a native container nor any recursively nested field containing a native container.
• ICloneable and some alternate constructors might be useful.

 

I'm struggling with the constructor, how would you go about it?

 

Code (CSharp):

1. public Tree(Allocator allocator)
2. {
3.     nodes = new NativeHashMap<int, T>(16, allocator);
4.     //...

Also, IComponentData has the same restriction as IBufferElementData.

 

Ah, my trouble was Implementing an interface and a generic constraint. Natives need non-nullable types:

Spoiler

Code (CSharp):

1. using System;
2. using Unity.Collections;
3. using Unity.Entities;
4.  
5. public struct Tree<T>  : IDisposable
6. where T : struct
7. {          
8.     // nodeKey, nodeValue                                          
9.     private NativeHashMap<int, T> nodes;              
10.     // child->parent relationship model: (childKey, parentKey)
11.     // parent->children alternative: NativeMultiHashmap<int, int> parentChildrenMap (parentKey, childrenKeys)
12.    private NativeHashMap<int, int> childParentMap;      
13.                                                            
14.     // list of nodeKeys formerly used by deleted nodeValues
15.    private NativeList<int> recycledKeys;
16.     // number of node key:value pairs            
17.    private int nodeCount;
18.     // the only nodeKey that isn't a value in childParentMap (root has no parent)                              
19.    private int rootKey;
20.  
21.  
22.     public Tree(Allocator allocator) : this()
23.     {
24.         nodes = new NativeHashMap <int, T> (0, allocator);
25.         childParentMap = new NativeHashMap<int, int> (0, allocator);
26.         recycledKeys = new NativeList<int> (0, allocator);
27.         nodeCount = 0;
28.     }
29.  
30.     public void Dispose()
31.     {
32.         nodes.Dispose();
33.     }
34. }

 

Hah! I missed that too.

You're missing a couple of native containers in your Dispose. And you probably don't want to set your NativeHashMap and NativeList capacities to 0. Capacity is not the same as Count. It just tells the constructor how much memory to allocate, so setting it to a value greater than 0 will save yourself some reallocations later. Also, nodeCount might already be tracked by nodes, so I would just make that a property (might even be worth making it a public property called Count for consistency). But otherwise I think you are on a good track now!