DataStructuresKit

🌐 Language: Deutsch | English | Español | Français

A comprehensive, production-ready collection of data structures for Swift, filling the gaps in the standard library with high-performance, well-documented implementations.

Features

• 🚀 High Performance: All operations meet or exceed documented complexity guarantees
• 📖 Fully Documented: DocC-compatible documentation with examples
• 🧪 Thoroughly Tested: Comprehensive test suite using Swift Testing
• 🔒 Type Safe: Generic implementations with full protocol conformances
• 📦 Zero Dependencies: Pure Swift implementation (except standard library)
• 🧵 Sendable Ready: Proper concurrency annotations for modern Swift

Installation

Swift Package Manager

Add to your Package.swift:

dependencies:[.package(url:"https://github.com/hoseiocean/DataStructuresKit.git", from:"1.0.0")]

Or in Xcode: File → Add Package Dependencies → Enter the repository URL:

https://github.com/hoseiocean/DataStructuresKit.git

Data Structures

Linear Structures

Structure	Description	Key Operations
Stack<T>	LIFO collection	push O(1), pop O(1)
Queue<T>	FIFO collection (circular buffer)	enqueue O(1), dequeue O(1)
Deque<T>	Double-ended queue	pushFront/Back O(1), popFront/Back O(1)
LinkedList<T>	Doubly-linked list	insert O(1), remove O(1)

Collections

Structure	Description	Key Operations
Bag<T>	Multiset (counts duplicates)	insert O(1), count(of:) O(1)

Trees

Structure	Description	Key Operations
BinarySearchTree<T>	BST with O(log n) average	insert, search, remove
AVLTree<T>	Self-balancing BST	insert O(log n) guaranteed
Trie	Prefix tree for strings	insert O(m), prefix search O(m)

Heaps & Priority Queues

Structure	Description	Key Operations
Heap<T>	Binary heap (min/max)	insert O(log n), extract O(log n)
PriorityQueue<T>	Priority queue wrapper	insert O(log n), extractTop O(log n)

Graphs

Structure	Description	Key Operations
Graph<T>	Adjacency list graph	BFS, DFS, Dijkstra O(V+E)

Caches

Structure	Description	Key Operations
LRUCache<K,V>	Least Recently Used cache	get O(1), set O(1)

Usage Examples

Stack

import DataStructuresKit
varstack=Stack<Int>()
stack.push(1)
stack.push(2)
stack.push(3)print(stack.peek) // Optional(3)
print(stack.pop()) // Optional(3)
print(stack.count) // 2
// Array literal initialization
letstack2:Stack=["a","b","c"]
// Iteration (LIFO order)
foritemin stack2 {print(item) // c, b, a
}

Queue

varqueue=Queue<String>()
queue.enqueue("first")
queue.enqueue("second")
queue.enqueue("third")print(queue.front) // Optional("first")
print(queue.dequeue()) // Optional("first")
// Circular buffer ensures O(1) dequeue

Deque

vardeque=Deque<Int>()
deque.pushBack(2)
deque.pushFront(1)
deque.pushBack(3)
// deque: [1, 2, 3]
print(deque.popFront()) // Optional(1)
print(deque.popBack()) // Optional(3)
// Random access
print(deque[0]) // 2

LinkedList

letlist=LinkedList<String>()letnodeA= list.append("A")letnodeB= list.append("B")
list.append("C")
list.insert("A.5", after: nodeA)
list.remove(nodeB)foritemin list {print(item) // A, A.5, C
}

Bag

// Count word frequencies
lettext="the quick brown fox jumps over the lazy dog the fox"letwords= text.split(separator:"").map(String.init)varbag=Bag(words)print(bag.count(of:"the")) // 3
print(bag.count(of:"fox")) // 2
print(bag.uniqueCount) // 9
print(bag.totalCount) // 11
// Get most common words
lettop3= bag.mostCommon(3)
// [("the", 3), ("fox", 2), ("quick", 1)]
// Inventory system
varinventory:Bag=["sword":2,"potion":5,"shield":1]
inventory.insert("potion", count:3)print(inventory.count(of:"potion")) // 8
inventory.remove("potion", count:2)print(inventory.count(of:"potion")) // 6

BinarySearchTree

varbst=BinarySearchTree<Int>()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)print(bst.contains(3)) // true
print(bst.min) // Optional(1)
print(bst.max) // Optional(9)
print(bst.sorted) // [1, 3, 5, 7, 9]

AVLTree

vartree=AVLTree<Int>()
// Even sorted insertion maintains O(log n) height
foriin1...1000{
tree.insert(i)}print(tree.height) // ~10 (vs 999 for unbalanced BST)

Trie

vartrie=Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("application")
trie.insert("banana")print(trie.contains("app")) // true
print(trie.hasPrefix("appl")) // true
print(trie.words(withPrefix:"app")) // ["app", "apple", "application"]
// Autocomplete support
letsuggestions= trie.words(withPrefix: userInput)

Heap

// Min heap (smallest first)
varminHeap= Heap<Int>.minHeap()
minHeap.insert(5)
minHeap.insert(3)
minHeap.insert(7)print(minHeap.extract()) // Optional(3)
print(minHeap.extract()) // Optional(5)
// Max heap (largest first)
varmaxHeap= Heap<Int>.maxHeap()
// Build from sequence in O(n)
letheap=Heap.minHeap([5,3,7,1,9])

PriorityQueue

vartasks=PriorityQueue<Int>()
tasks.insert(priority:5)
tasks.insert(priority:1)
tasks.insert(priority:3)whilelet next = tasks.extractTop(){print(next) // 1, 3, 5
}
// Max priority queue
varscores= PriorityQueue<Int>.maxPriorityQueue()

Graph

letgraph=Graph<String>(edgeType:.undirected)
graph.addEdge(from:"A", to:"B", weight:1)
graph.addEdge(from:"B", to:"C", weight:2)
graph.addEdge(from:"A", to:"C", weight:5)
// BFS traversal
graph.bfs(from:"A"){ vertex inprint("Visited: \(vertex)")returntrue // continue
}
// Shortest path (unweighted)
letpath= graph.shortestPath(from:"A", to:"C")print(path) // ["A", "B", "C"]
// Dijkstra's algorithm (weighted)
letdistances= graph.dijkstra(from:"A")print(distances["C"]?.distance) // 3.0 (via B)

LRUCache

letcache=LRUCache<String,Data>(capacity:100)
// Store
cache.set("image_123", value: imageData)
// Retrieve (marks as recently used)
iflet data = cache.get("image_123"){display(data)}
// Subscript syntax
cache["key"]= value
letretrieved=cache["key"]
// Auto-eviction when capacity reached

Design Principles

This library follows strict design principles documented in Architecture Decision Records (ADRs):

• ADR-001: Copy Semantics - Value types use Copy-on-Write; reference types for complex structures
• ADR-002: ABI Stability - Source compatibility guaranteed; binary compatibility not promised
• ADR-003: Performance Audit - All complexities verified with benchmarks

Protocol Conformances

All applicable types conform to:

• Sequence / Collection / RandomAccessCollection
• ExpressibleByArrayLiteral
• Equatable / Hashable (when Element conforms)
• Sendable (when Element is Sendable)
• CustomStringConvertible

Requirements

• Swift 5.9+
• iOS 15+ / macOS 12+ / tvOS 15+ / watchOS 8+ / visionOS 1+

Contributing

Contributions are welcome! Please read our Contributing Guide and the ADR documents in /Documentation/ADR/ before contributing to understand our development process and design decisions.

License

MIT License - see LICENSE for details.