TsPytham.DotNet.AdvancedCollections 1.1.0

DotNet.AdvancedCollections

Advanced and complementary data structures for modern .NET.

TsPytham.DotNet.AdvancedCollections provides production-ready data structures that are not included in System.Collections, designed with clean APIs, modern C# features, and performance in mind.

This project is the successor of GenericCollectionsExtension, rewritten to target modern .NET and improve design, safety, and maintainability.

Documentation

** View Full Documentation**

The documentation includes:

• Getting Started Guide - Introduction and basic usage
• API Reference - Complete API documentation with examples
• Detailed Guides - Lists, Queues, Stacks, Trees, and Graphs

Why this library?

.NET already offers excellent general-purpose collections, but some data structures are intentionally left out of the BCL.

This library focuses on:

• Advanced and specialized data structures
• Clean and explicit APIs
• Nullable reference types enabled
• Modern .NET (net8.0)
• Practical usage (not academic demos)

If you need trees, graphs, priority-based collections, or custom list variants, this library is for you.

Target framework

• .NET 8.0

The library targets modern .NET only.
Older frameworks and .NET Standard are intentionally not supported.

Included data structures

New data structures were added that are derived from the traditional data structures:

• Deque - Double-ended queue
• PriorityQueue - Priority-based queue
• PriorityStack - Priority-based stack
• Binary Search Tree - Standard BST (not self-balancing)
• SortedList - Automatically sorted list
• DoublyLinkedList - Two-way linked list
• LRUCache - Least Recently Used cache with fixed capacity
• Graph (Adjacency List) - Dictionary-based graph for sparse graphs
• AdjacencyMatrixGraph - Matrix-based graph for dense graphs and fast edge lookups

Queue

A queue is a data structure that stores and retrieves items in a first-in-first-out (FIFO) manner. This means that the first item that is added to the queue is also the first item that is removed from the queue. Queues are useful for storing and managing data in applications where items need to be processed in the order in which they are received. For example, a queue could be used to hold tasks that need to be executed in the order in which they are received, or to hold messages that need to be sent in the order in which they were received.

Queue Type:

• Deque: A double-ended queue, which is a type of data structure that allows items to be added and removed from either end of the queue. This means that items can be added to the front or back of the queue, and can also be removed from the front or back of the queue.

Example in code:

Deque<int> deque = new();
deque.PushFirst(1);
deque.PushFirst(2);
deque.PushFirst(5);

Console.WriteLine($"Count: {deque.Count}");
foreach(var item in deque)
{
    Console.WriteLine(item);
}

/*
Output:
Count: 3
5
2
1
*/

• Priority Queue: A data structure in which each item has a priority associated with it, and items are stored and retrieved in order of their priority. This means that when items are added to the queue, they are automatically placed in the correct position based on their priority, and when items are removed from the queue, the item with the highest priority is always selected first.

Example in code:

PriorityQueue<int> priorityQueue = new();
priorityQueue.Enqueue(10, 5);
priorityQueue.Enqueue(50, 2);
priorityQueue.Enqueue(55, 2);
priorityQueue.Enqueue(20, 3);

foreach (int item in priorityQueue)
{
    Console.WriteLine(item);
}

Console.WriteLine($"Peek: {priorityQueue.Peek()}");
int contains = 51;
Console.WriteLine($"Contains: {contains}, {priorityQueue.Contains(contains)}");


/*
Output:
10
20
50
55
Peek: 10
Contains: 51, False

*/

Stack

A stack is a data structure that stores and retrieves items in a last-in-first-out (LIFO) manner. This means that the last item that is added to the stack is also the first item that is removed from the stack. Stacks are useful for storing and managing data in applications where items need to be processed in the reverse order in which they are received.

• Priority Stack: A type of data structure that combines the characteristics of a stack and a priority queue. Like a stack, a priority stack stores and retrieves items in a last-in-first-out (LIFO) manner, but also allows items to be added and removed based on their priority. This means that items can be added to the top of the stack in any order, but when items are removed from the stack, the item with the highest priority is always selected first.

Example in code:

PriorityStack<int> stack = new()
{
    4, 5, 3, 5
};

Console.WriteLine($"Count: {stack.Count}");

Console.WriteLine($"Value: {stack.Peek()}");

foreach(var item in stack)
{
    Console.WriteLine(item);
}

/*
Count: 4
Value: 5
5
3
5
4
*/

List

A list is a data structure that stores a collection of items in a specific order. Lists allow items to be added, removed, and accessed by their position in the list. They are often used to store collections of data that need to be organized and accessed in a specific order.

• Sorted List: A data structure that is similar to a regular list, but maintains its items in a sorted order. This means that when items are added to the list, they are automatically placed in the correct position based on their sorting order. Sorted lists are useful in situations where it is necessary to access items in a specific order, such as in applications that require efficient search and retrieval of data.

• DoublyLinkedList: A data structure that consists of a set of nodes, where each node has two pointers: one pointing to the previous node in the list and one pointing to the next node in the list. This allows for efficient insertion and deletion of elements from the list, as well as the ability to traverse the list in both directions (from the beginning to the end and from the end to the beginning).

Example of SortedList in code:

//Descending

SortedList<int> sortedList = new(Criterion.Descending)
{
    1,
    0,
    -1,
    495,
    1,
    19,
    5
};

Console.WriteLine($"total items: {sortedList.Count}");
sortedList.ToList().ForEach(Console.WriteLine);

/*
total items: 7
495
19
5
1
1
0
-1
*/

//Ascending

SortedList<int> sortedList = new()
{
    1,
    0,
    -1,
    495,
    1,
    19,
    5
};

Console.WriteLine($"total items: {sortedList.Count}");
sortedList.ToList().ForEach(Console.WriteLine);

/*
total items: 7
-1
0
1
1
5
19
495
*/

NOTE

This implementation is different from the one implemented in System.Collections.Generic because this implementation does not use a key, and any class to be used must implement the IComparable interface. It is very important to review this implementation and documentation.

Cache

A cache is a high-speed data storage layer that stores a subset of data, typically transient in nature, so that future requests for that data are served faster. Caches are used to improve application performance and reduce latency.

• LRUCache: A Least Recently Used (LRU) cache is a fixed-capacity cache that evicts the least recently accessed items when it reaches its capacity limit. This ensures that frequently accessed items remain in the cache while rarely used items are removed, making it ideal for scenarios like API response caching, session data, or database query results.

Example in code:

// Create a cache with capacity of 3
LRUCache<int, string> cache = new(capacity: 3);

// Add items
cache.Put(1, "one");
cache.Put(2, "two");
cache.Put(3, "three");

Console.WriteLine($"Cache count: {cache.Count}");

// Access an item (makes it "recently used")
if (cache.TryGet(1, out var value))
{
    Console.WriteLine($"Key 1: {value}");
}

// Add another item - will evict the least recently used (key 2)
cache.Put(4, "four");

Console.WriteLine($"Contains key 2: {cache.ContainsKey(2)}"); // False - was evicted
Console.WriteLine($"Contains key 1: {cache.ContainsKey(1)}"); // True - was recently accessed

/*
Output:
Cache count: 3
Key 1: one
Contains key 2: False
Contains key 1: True
*/

Key Features:

• Fixed capacity with automatic eviction
• O(1) time complexity for Put, Get, and Contains operations
• Thread-unsafe (external synchronization required for concurrent access)
• Generic implementation supporting any non-null key and value types

Tree

A tree is a data structure consisting of linked nodes. Nodes can have one or more children and each node can have a relationship with other nodes in the tree.

• Binary search tree: A type of tree in which each node has a value that is smaller than all the values in its left subtree and larger than all the values in its right subtree. This allows for fast and efficient search in the tree.

Example in code:

BinarySearchTree<int> tree = new() { 5, 3, 4, 7, 6, 9, 8, 1, 2, 0, 14, 15};

Console.WriteLine($"Count: {tree.Count}");
Console.WriteLine($"Contains 5: {tree.Contains(5)}");
Console.WriteLine($"Contains 12: {tree.Contains(12)}");
var inOrder = tree.InOrder();
Console.WriteLine($"Count InOrder: {inOrder.Count()}");

foreach(var item in inOrder)
{
    Console.WriteLine(item);
}

/*
Count: 12
Contains 5: True
Contains 12: False
Count InOrder: 12
0
1
2
3
4
5
6
7
8
9
14
15
*/

Graph

A graph is a data structure that consists of a finite set of vertices (also known as nodes) and a set of edges connecting these vertices. The vertices represent the entities being modeled, and the edges represent the relationships between them. Graphs are often used to represent networks, such as social networks, communication networks, and transportation networks. They are also used in computer science to represent data structures such as trees and maps.

Graph Implementations

This library provides two graph implementations, each optimized for different use cases:

1. Graph (Adjacency List)

Uses a dictionary-based adjacency list representation. Best for sparse graphs (few edges relative to vertices).

Advantages:

• ? Memory efficient: O(V + E) space
• ? Fast neighbor iteration: O(degree)
• ? Ideal for traversal algorithms (BFS, DFS)

Use when:

• Your graph is sparse (E < V�/4)
• You iterate neighbors frequently
• Memory is a concern

2. AdjacencyMatrixGraph

Uses a matrix with bidirectional vertex-to-index mapping. Best for dense graphs or when edge lookups are frequent.

Advantages:

• ? Ultra-fast edge checking: O(1)
• ? Fast edge addition/removal: O(1)
• ? Ideal for algorithms requiring frequent edge queries

Use when:

• Your graph is dense (E > V�/3)
• You check edge existence frequently
• You know the vertex count in advance

Example in code (Adjacency List):

var graph = new Graph<char, int>
{
    new Vertex<char, int>('A'),
    new Vertex<char, int>('B'),
    new Vertex<char, int>('C')
};

graph.AddEdge('A', 'B', 10);
graph.AddEdge('A', 'C', 5);

foreach(var vertex in graph)
{
    Console.WriteLine($"{vertex.VertexName}: {string.Join(" ", graph.Successors(vertex.VertexName).Select(x => x.VertexName))}");
}

/*
A: B C
B:
C:
*/

Example in code (Adjacency Matrix):

var graph = new AdjacencyMatrixGraph<char, int>(initialCapacity: 10);

graph.AddVertex('A');
graph.AddVertex('B');
graph.AddVertex('C');

graph.AddEdge('A', 'B', 10);
graph.AddEdge('A', 'C', 5);

// O(1) edge checking
if (graph.HasEdge('A', 'B'))
{
    Console.WriteLine("A is connected to B");
}

// Get all neighbors
foreach(var neighbor in graph.GetNeighbors('A'))
{
    Console.WriteLine($"Neighbor: {neighbor}");
}

/*
A is connected to B
Neighbor: B
Neighbor: C
*/

Performance Comparison:

*Requires resize when capacity exceeded

?? Choosing the right implementation:

• Use Graph for sparse graphs and traversal-heavy workloads
• Use AdjacencyMatrixGraph for dense graphs and edge-lookup-heavy workloads

Roadmap

The following features and improvements are planned for future releases:

?? Upcoming Data Structures

• AVL Tree - Self-balancing binary search tree with strict height balance
• Skip List - Probabilistic data structure for fast search, insertion, and deletion (O(log n) average)
• Indexed Priority Queue - Priority queue with efficient index-based access and priority updates

?? Thread-Safe Variants

Selected data structures will receive thread-safe implementations:

• Thread-safe collections wrapper/decorators
• Concurrent-optimized variants for high-performance scenarios
• Lock-free implementations where applicable

Note: These features are planned but not yet scheduled for specific releases.
Contributions and feedback are welcome!

Project status

This project is under active development.
Public APIs may evolve until the first stable release (v1.0).

History

This project is the modern successor of GenericCollectionsExtension.