Collections

This assembly follows similar standard like unity collection package so it is important to check pages:

Native vs Unsafe

The Native types perform safety checks to ensure that indexes passed to their methods are in bounds, but the other types in most cases do not. Check page for more information https://docs.unity3d.com/Packages/com.unity.collections@1.3/manual/index.html.

NativeLinkedList/UnsafeLinkedList

An unmanaged, resizable linked list. Linked list is efficient at inserting and removing elements. However, not so efficient with cache usage. Linked list is implemented using double linked nodes, where each node knows its next-node link and previous-node link.

var list = new NativeLinkedList<int>(Allocator.Temp);

list.Add(0);
var itr = list.Add(1);
list.Add(2);

list.RemoveAt(itr);

Assert.AreEqual(list.Begin, 0);
Assert.AreEqual(list.Begin.Next, 2);

list.Dispose();

Note: Linked list is recommended to be used if you plan to keep added elements iteration position.

NativeStack/UnsafeStack

An managed, resizable stack. Limited version of NativeList that only operates with the last element at the time.

var stack = new NativeStack<int>(Allocator.Temp);

stack.Push(0);
stack.Push(1);
stack.Push(2);
stack.Push(3);
Assert.AreEqual(3, stack.Pop());
Assert.AreEqual(2, stack.Pop());
Assert.AreEqual(1, stack.Pop());
Assert.AreEqual(0, stack.Pop());

stack.Dispose();

NativeLinkedPriorityQueue/UnsafeLinkedPriorityQueue

An unmanaged, resizable priority queue. Priority queue main difference from regular queue that before element enqueue it executes insert sort. It is implemented using linked list. Peek = O(1), Enqueue = O(n), Dequeue = O(1).

struct AscendingOrder : IComparer<int>
{
    public int Compare(int x, int y) => x.CompareTo(y);
}

var queue = new NativeLinkedPriorityQueue<int, AscendingOrder>(Allocator.Temp, new AscendingOrder());

queue.Enqueue(2);
queue.Enqueue(1);

Assert.AreEqual(1, queue.Dequeue());
Assert.AreEqual(2, queue.Dequeue());

queue.Dispose();

NativeHeapPriorityQueue/UnsafeHeapPriorityQueue

An unmanaged, resizable priority queue. Priority queue main difference from regular queue that it is sorted. It is implemented using heap. Peek = O(1), Enqueue = O(log n), Dequeue = O(log n).

var queue = new NativeHeapPriorityQueue<int, int>(Allocator.Temp);

queue.Enqueue(2, 2);
queue.Enqueue(1, 1);

Assert.AreEqual(1, queue.Dequeue());
Assert.AreEqual(2, queue.Dequeue());

queue.Dispose();

NativeKdTree/UnsafeKdTree

K-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. K-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches) and creating point clouds. K-d trees are a special case of binary space partitioning trees.

struct TreeComparer : IKdTreeComparer<float2>
{
    public int Compare(float2 x, float2 y, int depth)
    {
        int axis = depth % 2;
        return x[axis].CompareTo(y[axis]);
    }

    public float DistanceSq(float2 x, float2 y)
    {
        return math.distancesq(x, y);
    }

    public float DistanceToSplitSq(float2 x, float2 y, int depth)
    {
        int axis = depth % 2;
        return (x[axis] - y[axis]) * (x[axis] - y[axis]);
    }
}

var tree = new NativeKdTree<float2, TreeComparer>(1, Allacator.Temp, new TreeComparer());

tree.Add(new float2(1, 1));
tree.Add(new float2(2, 2));

Assert.AreEqual(1, FindNearest(new float2(0, 0), out _).Value);

tree.Dispose();

Note: K-D tree operations like nearest neighbor search have overhead. As a result, it is recommended to use it when you have lots of points in space.

NativeAABBTree/UnsafeAABBTree

An unmanaged, resizable aabb tree. AABB tree (short for axis aligned bounding box tree) is a space-partitioning data structure for organizing bounding shapes in space. As structure uses generic it is not only usable for boxes, but any shape that implements interfaces. AABB trees are a useful data structure for fast searching bounding shapes in space. AABB trees are a special case of binary space partitioning trees. Based on https://box2d.org/files/ErinCatto_DynamicBVH_GDC2019.pdf.

struct AABRectangle : ISurfaceArea<AABRectangle>, IUnion<AABRectangle>, IOverlap<AABRectangle>
{
    public Rectangle Rectangle;

    public AABRectangle(Rectangle rectangle)
    {
        Rectangle = rectangle;
    }

    public float SurfaceArea() => Rectangle.Perimeter;
    public AABRectangle Union(AABRectangle value) => new AABRectangle(Rectangle.Union(Rectangle, value.Rectangle));
    public bool Overlap(AABRectangle value) => Rectangle.Overlap(value.Rectangle);
}

...

var tree = new UnsafeAABBTree<AABRectangle>(1, Allocator.Temp);

// Construct tree:
//            N
//          /   \
//         N     N
//        / \   / \
//       a   b  c  d

var a = tree.Add(new AABRectangle(new Rectangle(new float2(5, 5), new float2(1, 1))));
var b = tree.Add(new AABRectangle(new Rectangle(new float2(6, 6), new float2(1, 1))));

var c = tree.Add(new AABRectangle(new Rectangle(new float2(-5, -5), new float2(1, 1))));
var d = tree.Add(new AABRectangle(new Rectangle(new float2(-6, -6), new float2(1, 1))));

Assert.AreEqual(tree.Right(tree.Right(tree.Root)), d);
Assert.AreEqual(tree.Left(tree.Right(tree.Root)), c);
Assert.AreEqual(tree.Right(tree.Left(tree.Root)), b);
Assert.AreEqual(tree.Left(tree.Left(tree.Root)), a);

var result = new NativeList<AABRectangle>(2, Allocator.Temp);
tree.FindOverlap(new AABRectangle(new Rectangle(new float2(5, 5), new float2(2, 2))), ref result);

Assert.AreEqual(2, result.Length);
Assert.IsTrue(tree[a].Rectangle == result[0].Rectangle);
Assert.IsTrue(tree[b].Rectangle == result[1].Rectangle);

result.Dispose();

tree.Dispose();