pie_core/
lib.rs

1//! A high-performance, index-based data structure toolkit.
2//!
3//! `pie_core` (formerly `pielist`) provides data structures built on a central,
4//! contiguous `ElemPool`. This design offers several key advantages over
5//! traditional pointer-based collections:
6//!
7//! - **Cache-Friendly:** By storing nodes in a `Vec`, traversals are significantly
8//!   faster due to improved data locality.
9//! - **No Alloc/Dealloc Churn:** The pool manages memory, reusing freed nodes.
10//!   This eliminates the overhead of frequent calls to the system allocator, making
11//!   insertions and removals very fast.
12//! - **Multi-Structure Support:** A single `ElemPool` can manage the memory for many
13//!   separate `PieList` and `FibHeap` instances, making it ideal for managing
14//!   numerous small data structures efficiently.
15//! - **Safe Cursors:** The library provides a `CursorMut` API for complex, efficient
16//!   in-place list mutations like splitting and splicing.
17//! - **Efficient Priority Queue:** Includes a `FibHeap` implementation with O(1)
18//!   amortized `decrease_key`, ideal for graph algorithms.
19//!
20//! This crate is a "Pie" library because it stores the data (`T`) *directly inside* the
21//! element structure, which is efficient for smaller `T`. This avoids an extra
22//! layer of indirection.
23//!
24//! # Core Concepts
25//!
26//! - [`ElemPool`]: The memory arena that owns all elements. All operations on a
27//!   structure require a reference to the pool.
28//! - [`PieList<T>`]: A lightweight handle representing a single doubly-linked list.
29//! - [`FibHeap<K, V>`]: A Fibonacci heap (priority queue) optimized for
30//!   fast `decrease_key` operations.
31//! - [`Index<T>`]: A type-safe, copyable handle to a specific element within the pool.
32//!   It acts as a "safe pointer".
33//! - [`CursorMut<'a, T>`]: A mutable cursor for efficient `PieList` navigation
34//!   and modification.
35//! - [`FibHandle<K, V>`]: A type-safe handle to a node in a `FibHeap`,
36//!   required for `decrease_key`.
37//!
38//! # Example
39//!
40//! ```
41//! use pie_core::{ElemPool, PieList};
42//!
43//! // 1. Create a pool to manage memory for all our lists.
44//! // The pool can only hold one type of data. Here, we choose &'static str.
45//! let mut pool: ElemPool<&'static str> = ElemPool::new();
46//!
47//! // 2. Create two separate list handles.
48//! let mut list_a = PieList::new(&mut pool);
49//! let mut list_b = PieList::new(&mut pool);
50//!
51//! // 3. Push data into the lists.
52//! list_a.push_back("Apple", &mut pool).unwrap();
53//! list_a.push_back("Banana", &mut pool).unwrap();
54//!
55//! list_b.push_front("Cat", &mut pool).unwrap();
56//! list_b.push_front("Dog", &mut pool).unwrap();
57//!
58//! // 4. The pool now contains all 4 elements.
59//! assert_eq!(pool.len(), 4);
60//! assert_eq!(list_a.len(), 2);
61//! assert_eq!(list_b.len(), 2);
62//!
63//! // 5. Iterate and access data.
64//! let fruits: Vec<_> = list_a.iter(&pool).copied().collect();
65//! assert_eq!(fruits, vec!["Apple", "Banana"]);
66//!
67//! // 6. When a list is no longer needed, clear it to return its
68//! //    elements to the pool's free list for reuse.
69//! list_a.clear(&mut pool);
70//! assert_eq!(pool.len(), 2); // Only list_b's elements remain.
71//! ```
72
73#![deny(unsafe_code)]
74
75// --- Module Declarations ---
76mod cursor;
77mod elem;
78mod index;
79mod list;
80mod pool;
81mod heap;
82
83// --- Public API Re-exports ---
84pub use cursor::CursorMut;
85pub use elem::ListElem;
86pub use index::Index;
87pub use list::PieList;
88pub use pool::{ElemPool, IndexError};
89pub use heap::{FibHeap, FibHandle, DecreaseKeyError};
pie_core/lib.rs

pie_core/
lib.rs
