It's a data structure for maintaining an ordered set of unsigned 32 bit integers. The key features:
- Unmanaged memory -- The DynTree operates on unmanaged memory. Many and/or large trees will not have any impact on GC.
- Immutability -- You may mark a DynTree as immutable. Subsequent modifications (inserts/removals) will copy affected parts of the tree, unmodified parts will just be referenced.
- Ref-counting -- Users need to take care of releasing trees properly
- Efficiency -- The tree structure adapts to the actual density and size, supporting different representations of individual tree leaves (e.g. a bitset)
- 9-byte struct -- The tree structure itself is a struct with a size of 9 bytes. This allows other data structures to include a large amount of DynTree instances.
// The default allocator uses Marshal.AllocHGlobal() and
// Marshal.FreeHGlobal to allocate/free unmanaged memory
IAllocator allocator = new DefaultAllocator();
// Create a tree from a pre-defined set. The integers must be in ascending order.
DynTree tree = DynTree.Create(allocator, [90, 112]);
// Do something with the tree
// Free unmanaged memory. A reference to the allocator is not part of the tree struct.
tree.Release(allocator);
IAllocator allocator = new DefaultAllocator();
// Start with an empty tree.
DynTree tree = DynTree.Empty;
// Add some integers
foreach (uint id in [112, 90])
{
// Adding an integer creates a new tree, which must be released by the caller.
DynTree newTree = tree.Add(allocator, id);
tree.Release(allocator);
tree = newTree;
}
// Remove some integers
foreach (uint id in [112, 90])
{
// Removing an integer creates a new tree, too.
DynTree newTree = tree.Remove(allocator, id);
tree.Release(allocator);
tree = newTree;
}
// Free unmanaged memory.
tree.Release(allocator);
IAllocator allocator = new DefaultAllocator();
DynTree tree = DynTree.Create(allocator, [16, 18, 90, 112]);
tree.Contains(90); // true
tree.Contains(19); // false
tree.Release(allocator);
IAllocator allocator = new DefaultAllocator();
DynTree tree = DynTree.Create(allocator, [16, 18, 90, 112]);
// The returned tree is not a new instance, it's just flagged as immutable.
tree = tree.MakeImmutable();
// Add an integer.
DynTree newTree = tree.Add(allocator, 20);
newTree.Contains(20); // true
tree.Contains(20); // false
newTree.Release(allocator);
tree.Release(allocator);