gqlforge_chunk/lib.rs
1//! A Rust implementation of a persistent data structure that provides O(1)
2//! append and concatenation operations through structural sharing.
3//!
4//! # Overview
5//! `Chunk` is a persistent data structure that offers:
6//! - **O(1) Append Operations**: Add elements to your chunk in constant time
7//! - **O(1) Concatenation**: Combine two chunks efficiently
8//! - **Immutable/Persistent**: All operations create new versions while
9//! preserving the original
10//! - **Memory Efficient**: Uses structural sharing via reference counting
11//! - **Safe Rust**: Implemented using 100% safe Rust
12//!
13//! # Theoretical Background
14//!
15//! This implementation is inspired by the concepts presented in Hinze and
16//! Paterson's work on [Finger Trees](https://en.wikipedia.org/wiki/Finger_tree), though simplified for our specific use case.
17//! While our implementation differs in structure, it shares similar performance
18//! goals and theoretical foundations.
19//!
20//! ## Relationship to Finger Trees
21//!
22//! Finger Trees are a functional data structure that supports:
23//! - Access to both ends in amortized constant time
24//! - Concatenation in logarithmic time
25//! - Persistence through structural sharing
26//!
27//! Our `Chunk` implementation achieves similar goals through a simplified
28//! approach:
29//! - We use `Append` nodes for constant-time additions
30//! - The `Concat` variant enables efficient concatenation
31//! - `Rc` (Reference Counting) provides persistence and structural sharing
32//!
33//! # Example Usage
34//! ```rust
35//! use gqlforge_chunk::Chunk;
36//!
37//! // Create a new chunk and append some elements
38//! let chunk1 = Chunk::default()
39//! .append(1)
40//! .append(2);
41//!
42//! // Create another chunk
43//! let chunk2 = Chunk::default()
44//! .append(3)
45//! .append(4);
46//!
47//! // Concatenate chunks in O(1) time
48//! let combined = chunk1.concat(chunk2);
49//!
50//! // Convert to vector when needed
51//! assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);
52//! ```
53//!
54//! # Performance Characteristics
55//!
56//! ## Time Complexity Analysis
57//!
58//! | Operation | Worst Case | Amortized | Space |
59//! | --------------------- | ---------- | ------------ | ------------ |
60//! | `new()` | O(1) | O(1) | O(1) |
61//! | `append()` | O(1) | O(1) | O(1) |
62//! | `concat()` | O(1) | O(1) | O(1) |
63//! | `transform()` | O(1) | O(1) | O(1) |
64//! | `transform_flatten()` | O(1) | O(1) | O(1) |
65//! | `as_vec()` | O(n) | O(n) | O(n) |
66//! | `clone()` | O(1) | O(1) | O(1) |
67//!
68//! ## Amortized Analysis Details
69//!
70//! ### Append Operation
71//! The `append` operation is O(1) amortized because:
72//! - The actual append is always O(1) as it only creates a new `Append` node
73//! - No rebalancing is required
74//! - Memory allocation is constant time
75//!
76//! ### Concat Operation
77//! The `concat` operation achieves O(1) amortized time through:
78//! - Lazy evaluation: immediate concatenation is O(1)
79//! - The actual work is deferred until `as_vec()` is called
80//! - No immediate copying or restructuring of data
81//!
82//! ### Transform Operations
83//! Both `transform` and `transform_flatten` are O(1) amortized because:
84//! - They create a new node with a transformation function
85//! - Actual transformation is deferred until materialization
86//! - No immediate computation is performed on elements
87//!
88//! ### `as_vec` Operation
89//! The `as_vec` operation is O(n) because:
90//! - It must process all elements to create the final vector
91//! - For a chunk with n elements:
92//! - Basic traversal: O(n)
93//! - Applying deferred transformations: O(n)
94//! - Memory allocation and copying: O(n)
95//!
96//! ### Memory Usage Patterns
97//!
98//! The space complexity has interesting properties:
99//! - Immediate space usage for operations is O(1)
100//! - Deferred space cost accumulates with operations
101//! - Final materialization requires O(n) space
102//! - Structural sharing reduces memory overhead for clones and versions
103//!
104//! ```rust
105//! use gqlforge_chunk::Chunk;
106//!
107//! // Each operation has O(1) immediate cost
108//! let chunk = Chunk::default()
109//! .append(1) // O(1) time and space
110//! .append(2) // O(1) time and space
111//! .transform(|x| x + 1); // O(1) time and space
112//!
113//! // O(n) cost is paid here
114//! let vec = chunk.as_vec();
115//! ```
116//!
117//! # Implementation Details
118//!
119//! The `Chunk<A>` type is implemented as an enum with four variants:
120//! - `Empty`: Represents an empty chunk
121//! - `Append`: Represents a single element appended to another chunk
122//! - `Concat`: Represents the concatenation of two chunks
123//! - `TransformFlatten`: Represents a lazy transformation and flattening of
124//! elements
125//!
126//! The data structure achieves its performance characteristics through:
127//! - Structural sharing using `Rc`
128//! - Lazy evaluation of concatenation and transformations
129//! - Immutable operations that preserve previous versions
130//!
131//! # Memory Efficiency
132//!
133//! The `Chunk` type uses structural sharing through reference counting (`Rc`),
134//! which means:
135//! - Appending or concatenating chunks doesn't copy the existing elements
136//! - Memory is automatically freed when no references remain
137//! - Multiple versions of the data structure can coexist efficiently
138//!
139//! ```rust
140//! use gqlforge_chunk::Chunk;
141//!
142//! let original = Chunk::default().append(1).append(2);
143//! let version1 = original.clone().append(3); // Efficient cloning
144//! let version2 = original.clone().append(4); // Both versions share data
145//! ```
146//!
147//! # References
148//!
149//! 1. Ralf Hinze and Ross Paterson. "Finger Trees: A Simple General-purpose
150//! Data Structure", Journal of Functional Programming 16(2):197-217, 2006.
151//! 2. Chris Okasaki. "Purely Functional Data Structures", Cambridge University
152//! Press, 1998.
153
154mod chunk;
155pub use chunk::*;