dsa_rust/
lib.rs

1/*! # About
2This project contains mostly pedagogical implementations of classical data structures as a way to exemplify common patterns to deal with Rust's opinionated safety systems. This library exists as a companion piece to an entry-level suite of [narrative-based documentation](https://www.headyimage.com/cs/dsa/dsa-intro/) on data structures and algorithms, and is intended to provide examples of foundational in-memory data structures and provide implementation hints to common issues encountered when learning the Rust programming language. The material provides patters that (hopefully) address common issues when learning Rust such as the borrow checker, reference counting, complex lifetimes and elision, and even a bit of `unsafe` code when the need for performance and ergonomics eclipse guaranteed safety out-of-the-box.
3
4The material aims for a data-oriented design approach. For example, APIs favor returning iterators instead of copied/mutated collections, and representations prefer contiguous storage layouts. This is in line with Rust's general design approach.
5
6The designs presented here are not intended to compete directly with Rust's `std::collections` library. Even so, the included benchmarking harnesses illustrate that these simplified approaches stay well within acceptable performance envelopes, often indicating only 1-2x slower operational performance for tested workloads as compared to the highly optimized `std::collections` crate.
7
8The material avoids any optimization that obfuscates semantics. The intent is to present code that is easy to reason about, and only includes `unsafe` operations as a matter of example where explicitly necessary. The preference for safety is a conscious choice to appeal to conceptual illustration over niche application and raw performance.
9
10# Sequences
11These structures/modules represent a basic exploration of foundational, sequence-based structures. The concepts illustrated here can be used for more advanced data structures.
12
13- [Singly-linked list](crate::sequences::singly_linked_list): A singly-linked sequence structure of owned values written entirely in safe Rust. This implementation illustrates the basic `Box` pointer to heap-allocate node data and contains operations for simple stack and queue structures.
14
15- [Doubly-linked list](crate::sequences::doubly_linked_list): A doubly-linked sequence structure of owned values written with ample use of raw pointers (and hopefully enough [Miri](https://github.com/rust-lang/miri) testing to prove that its safe and sound). This list includes a cursor for a positional implementation that provides list splitting/splicing out of the box. These additions allow the list to support in-place sorting, if you choose to implement it.
16
17- [Vector-based circular queue](crate::sequences::queues::vec_circ_queue): This structure is a simple, fun illustration of a fixed-sized circular buffer. This list currently represents the only index-based list in the group, because its fun, but it's still just a `Vec` with capacity constraints and wrapping logic.
18
19- [Contigous Dynamic Array](crate::sequences::dyn_array): A minimal `Vec` clone that uses contiguous storage, indexing semantics, and dynamic (geometric) growth behavior. NOTE: Under construction
20
21- [Safe Indexed Skip List](crate::sequences::indexed_skip_list): A single-threaded skip list boasting _O(log(n))_ (expected) insert, lookup, and remove operations. This structure also contains functions for retrieving the Kth element and range queries with Rust's `RangeBounds` semantics.
22
23# Hierarchies
24Building off the lessons learned with Sequences, this section contains examples of hierarchical data structures.
25
26#### General Trees
27- [Linked n-ary tree](crate::hierarchies::safe_linked_gentree): A safe, undirected, unweighted, acyclic graph... err, tree. This implementation takes a traditional link-based approach to hierarchical structures. To avoid dangling pointers and reference cycles this implementation relies on [shared ownership with interior mutability](https://doc.rust-lang.org/book/ch15-05-interior-mutability.html?highlight=interior%20mutability#allowing-multiple-owners-of-mutable-data-with-rct-and-refcellt) via [Rc](std::rc) and [RefCell](std::cell), and utilizes [Weak](std::rc::Weak) parent pointers for proper drop semantics.
28
29- [Indexed n-ary tree](crate::hierarchies::arena_gentree): A safe, `Vec`-backed (indexed) general tree. This experiment is meant to be easier than using `Rc`/`RefCell`, which comes with its own cost. This implementation uses a "free list" to track node removal to ensure "leaked" arena nodes are kept to an absolute minimum.
30
31#### Heaps
32- [Indexed binary heap](crate::hierarchies::bin_heap): A simple Vec-backed (min) binary heap. All sifting happens in _O(log(n))_ time. The structure also contains a generalized heap sort operation that takes any (coercable) slice over orderable elements.
33
34#### Search Trees
35- [AVL tree](crate::hierarchies::avl_tree): A self-balancing, Vec-backed binary search tree with an [in-order](https://www.headyimage.com/cs/dsa/trees#depth-first-traversal) snapshot iterator. This structure guarantees _O(log(n))_ search, insert, and delete operations, and is used to implement this library's (sorted) [AVL tree map](crate::associative::avl_tree_map).
36
37# Associative Structures
38One of the most useful structures in the real world. Associative structures are essentially just lists of key-value pairs with potentially better expected asymptotics.
39
40#### Maps
41- [Chaining hash map](crate::associative::chaining_hash_table): Simple, easy, unsorted fun for the whole family. This hash map uses a Vec-based backing structure with a simple division compression and chaining scheme to address collisions.
42
43- [Probing hash map](crate::associative::probing_hash_table): A little more complex, still unsorted, but arguably more performant by taking advantage of cache locality through a flattened backing structure. This Vec-backed hash map uses MAD compression and quadratic probing as well as a fun little secondary byte mask to distinguish available, occupied, and defunct indexes.
44
45- [AVL tree map](crate::associative::avl_tree_map): A sorted map built on this library's [AVL tree](crate::hierarchies::avl_tree) implementation.
46
47#### Sets
48- [Simple Set](crate::associative::hash_set): A simple unsorted set based on this library's probing hash map. This structure includes basic mutating and non-mutation versions basic mathematical set operations, but is mostly an exercise in writing custom iterators.
49
50- [Sorted tree set](): Coming soon!
51
52# Composite Structures
53This category contains "miscelaneous" data structures that do not neatly fall into any of the other categories.
54
55- [Adaptable priority queue](crate::composite::priority_queue): The notoriously hard-to-categorize adaptable priority queue combines two implementations from in this library; the [binary heap](crate::hierarchies::bin_heap) and the [hash map](crate::associative::probing_hash_table). This structure provides the best of both worlds with fast _O(1)_ key-based lookups and _O(log(n))_ additions, removals, and key/value mutations.
56
57# Algorithms
58An exploration on some searching, sorting, and graph algorithms.
59
60- Heap sort
61- Binary search
62
63*/
64
65// Centralized module declaration
66// Declaring only what we want to surface
67pub mod sequences {
68    pub mod doubly_linked_list;
69    pub mod singly_linked_list;
70    pub mod queues {
71        pub mod vec_circ_queue;
72    }
73    pub mod concurrent_skip_list;
74    pub mod indexed_skip_list;
75    pub mod dyn_array;
76}
77pub mod hierarchies {
78    pub mod avl_tree;
79    pub mod linked_bst;
80    pub mod safe_linked_gentree;
81    pub mod safe_linked_gentree_builder;
82    pub mod traits; // Necessary for gen tree
83                    //pub mod unsafe_linked_general_tree;
84    pub mod arena_bst;
85    pub mod arena_gentree;
86    pub mod arena_gentree_builder;
87    pub mod bin_heap;
88}
89pub mod associative {
90    pub mod avl_tree_map;
91    pub mod chaining_hash_table;
92    pub mod hash_lib; // Necessary for maps
93    pub mod hash_set;
94    pub mod probing_hash_table;
95    pub mod sorted_map;
96    //pub mod skip_map;
97    //pub mod skip_set;
98}
99pub mod composite {
100    pub mod priority_queue;
101}
102pub mod graphs {
103    pub mod adjacency_list;
104    pub mod edge_list;
105}
106pub mod util {
107    pub mod bump_arena;
108}
109pub mod maw;
110pub mod tgg;
111
112pub mod algorithms{
113    pub mod list_processing;
114}
dsa_rust/lib.rs

dsa_rust/
lib.rs
