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/docs/dsa_rust/index.html) on data structures and algorithms, and is intended to cover both the basics of data structures and some of the intermediate edges of 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
4Many of the structures in this library rely on [Vec]-based storage instead of raw or reference-counted pointers. This allows the implementations to remain inherently safe without the added runtime checks and/or complexity of reference counting and `unsafe` code. Highly optimized `unsafe` code may be required for the most performance-critical cases, but it is tricky and can add serious complexity for often minimal gains.
5
6# Sequences
7These structures/modules represent a basic exploration of foundational, sequence-based structures. The concepts illustrated here can be used for more advanced data structures.
8
9- [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.
10
11- [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.
12
13- [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
14
15# Hierarchies
16Building off the lessons learned with Sequences, this section contains examples of hierarchical data structures.
17
18#### General Trees
19- [Linked n-ary tree](crate::hierarchies::safe_linked_gentree): A safe, undirected, unweighted, unconnected 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) pointers for proper drop semantics.
20
21- [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.
22
23#### Heaps
24- [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.
25
26#### Search Trees
27- [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).
28
29# Associative Structures
30One of the most useful structures in the real world. Associative structures are essentially just lists of key-value pairs with potentially better expected asymptotics.
31
32#### Maps
33- [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.
34
35- [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.
36
37- [AVL tree map](crate::associative::avl_tree_map): A sorted map built on this library's [AVL tree](crate::hierarchies::avl_tree) implementation. 
38
39#### Sets
40- [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.
41
42- [Sorted tree set](): Coming soon!
43
44# Composite Structures
45This category contains "miscelaneous" data structures that do not neatly fall into any of the other categories.
46
47- [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.
48
49# Algorithms
50An exploration on some searching, sorting, and graph algorithms.
51
52- Heap sort
53- Binary search
54
55*/
56
57// Declaring only what we want to surface
58pub mod sequences {
59    pub mod doubly_linked_list;
60    pub mod singly_linked_list;
61    pub mod queues {
62        pub mod vec_circ_queue;
63    }
64    //pub mod skip_list;
65}
66pub mod hierarchies {
67    pub mod avl_tree;
68    pub mod linked_bst;
69    pub mod safe_linked_gentree;
70    pub mod safe_linked_gentree_builder;
71    pub mod traits; // Necessary for gen tree
72                    //pub mod unsafe_linked_general_tree;
73    pub mod arena_bst;
74    pub mod arena_gentree;
75    pub mod arena_gentree_builder;
76    pub mod bin_heap;
77}
78pub mod associative {
79    pub mod avl_tree_map;
80    pub mod chaining_hash_table;
81    pub mod hash_lib; // Necessary for maps
82    pub mod probing_hash_table;
83    pub mod skip_list;
84    pub mod sorted_map;
85    pub mod hash_set;
86    //pub mod skip_map;
87    //pub mod skip_set;
88}
89pub mod composite {
90    pub mod priority_queue;
91}
92pub mod maw;
93pub mod tgg;
dsa_rust/lib.rs

dsa_rust/
lib.rs
