pie_core/
lib.rs

1//! A high-performance, index-based data structure toolkit.
2//!
3//! `pie_core` provides data structures built on a central, contiguous
4//! `ElemPool`. This design offers several key advantages over traditional
5//! 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//! # list_b.clear(&mut pool);
72//! ```
73
74#![deny(unsafe_code)]
75#![cfg_attr(not(feature = "std"), no_std)]
76
77// We need 'alloc' to be available unconditionally because we use
78// 'alloc::vec::Vec' in pool.rs to support both std and no_std targets.
79extern crate alloc;
80extern crate core;
81
82// Central type alias for the map used in shrink_to_fit.
83// This ensures pool, list, and heap all use the same type.
84#[cfg(feature = "std")]
85pub(crate) type IndexMap<K, V> = std::collections::HashMap<K, V>;
86
87#[cfg(not(feature = "std"))]
88pub(crate) type IndexMap<K, V> = alloc::collections::BTreeMap<K, V>;
89
90// --- Module Declarations ---
91mod cursor;
92mod cursor_mut;
93mod elem;
94pub mod generation;
95mod index;
96mod list;
97mod pool;
98mod heap;
99pub mod slot;
100#[cfg(feature = "petgraph")]
101mod petgraph;
102mod view;
103mod view_mut;
104
105// --- Public API Re-exports ---
106pub use cursor::Cursor;
107pub use cursor_mut::CursorMut;
108pub use elem::Elem;
109pub use index::Index;
110pub use list::PieList;
111pub use view::PieView;
112pub use view_mut::PieViewMut;
113pub use pool::{ElemPool, IndexError};
114pub use heap::{FibHeap, FibHandle, Node, DecreaseKeyError};
115#[cfg(feature = "petgraph")]
116pub use petgraph::dijkstra_pie_core;
pie_core/lib.rs

pie_core/
lib.rs
