Cornucopia.Net

---

The horn of plenty for .NET developers.

• Pure .NET (no unmanaged code)
• No dependencies (sometimes reinventing the wheel)
• Low-level functionality (instead of OO overhead)
• Focus on performance (instead of safety/conventions/usability)
• Use modern technology (instead of compatibility)

Data Structures

• For special (performance) needs
• Not implementing System.Collections.Generic.IEnumerable<T>
• Uses value types where appropriate

Design philosophy

The System.Collections namespace provides a great set of collections for day-to-day use. If you're looking beyond that you probably have performance issues and have already ditched System.Linq. Suddenly, implementing System.Collections.Generic.IEnumerable<T> becomes less important. Also consider that IEnumerable<T> is a great abstraction, but very difficult to implement efficiently in tree-like data structures.

If there's no need to implement an interface, it's also easier to diverge from common standards. For some collection types, null denotes an empty collection. Some collection types are value types, just providing a convenient API layer instead of adding another level of indirection.

These decisions focus on performance, but do not prevent creating a wrapper around the low-level data structures, providing behavior known from the System.Collections namespace.

Random Access List

Persistent data structure based on skew binary numbers.

• O(1) insert/delete on one end (like System.Collections.Immutable.ImmutableStack<T>)
• O(log(N)) get/set by index (like System.Collections.Immutable.ImmutableList<T>)

Finger Tree

Persistent data structure based on a 2-3-tree, combined with a zipper.

• O(1) amortized insert/delete on both ends
• O(log(N)) insert/delete/get/set by index (like System.Collections.Immutable.ImmutableList<T>)
• O(log(N)) concatenate (like System.Collections.Immutable.ImmutableList<T>)
• O(log(N)) split (in comparison to O(N*log(N)) for System.Collections.Immutable.ImmutableList<T>)

Space-Optimal Dynamic Array

Ephemeral data structure for dynamic arrays.

• O(1) amortized insert/delete on one end (like System.Collections.Generic.List<T>)
• data not copied when resizing (unlike System.Collections.Generic.List<T>)
• O(1) get/set by index
• O(sqrt(N)) wasted space (in comparison to O(n) for System.Collections.Generic.List<T>)

Binary Heap

Ephemeral data structure for priority queues.

• O(log(N)) insert (like System.Collections.Generic.SortedSet<T>)
• O(1) get minimum (in comparison to O(log(N)) for System.Collections.Generic.SortedSet<T>)
• O(log(N)) extract minimum (like System.Collections.Generic.SortedSet<T>)
• data can contain duplicates (unlike System.Collections.Generic.SortedSet<T>)

Pairing Heap

Ephemeral data structure for adressable priority queues.

• O(1) insert
• O(1) get minimum
• O(log(N)) amortized extract minimum
• O(log(N)) amortized delete
• O(log(N)) amortized decrease key
• O(1) merge

Dynamic Array

Ephemeral data structure for dynamic arrays, used internally.

• like System.Collections.Generic.List<T>
• access by ref and System.Span<T>
• value type allows embedding in other data types without too much performance penalties

Undirected / Directional / Bidirectional multigraph

Ephemeral data structure for graphs.

• stored in a compact array-based format
• Dijkstra's shortest path
• A* shortest path
• Tarjan's strongly connected components
• Prim's minimum spanning tree
• Edmonds–Karp maximum flow

Persistent Binary Tree

Persistent data structure for binary trees, used internally.

Persistent Singly Linked List

Persistent data structure for linked lists, used internally, similar to System.Collections.Immutable.ImmutableStack<T>.

Future Plans

Currently I'm thinking about these additions (in no particular order), many of which I've already implemented previously:

• Sorting algorithms (stable / adaptive)
• Disjoint Set (also known as Union-Find)
• (Persistent) Balanced Binary Trees (AVL / RedBlack / Splay)
• Persistent Queue
• Persistent Deque
• More Heaps (Binomial / Fibonacci / Weak / MinMax)
• (Persistent / Concurrent) Hash Array Mapped Trie
• RRB Vector
• Prefix Trie
• Suffix Tree

About the author

Hi there, my name is Simon Weinberger and I live in Germany. I enjoy developing software and do that professionally for my daytime job. My special interests are data structures, math, JIT code generation, parser generators, and everything related to .NET internals.

Cornucopia.Net is a hobby project of mine. Please reach out to me if you have questions or feedback.