tailcall_chunk/chunk.rs
1//! A Rust implementation of a persistent data structure for efficient append and concatenation operations.
2//!
3//! This crate provides the [`Chunk`] type, which implements a persistent data structure
4//! that allows O(1) append and concatenation operations through structural sharing.
5//!
6//! # Features
7//! - O(1) append operations
8//! - O(1) concatenation operations
9//! - Immutable/persistent data structure
10//! - Memory efficient through structural sharing
11//!
12//! # Example
13//! ```
14//! use tailcall_chunk::Chunk;
15//!
16//! let chunk1 = Chunk::default().append(1).append(2);
17//! let chunk2 = Chunk::default().append(3).append(4);
18//! let combined = chunk1.concat(chunk2);
19//!
20//! assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);
21//! ```
22
23use std::{cell::RefCell, rc::Rc};
24
25/// A persistent data structure that provides efficient append and concatenation operations.
26///
27/// # Overview
28/// `Chunk<A>` is an immutable data structure that allows O(1) complexity for append and
29/// concatenation operations through structural sharing. It uses [`Rc`] (Reference Counting)
30/// for efficient memory management.
31///
32/// # Performance
33/// - Append operation: O(1)
34/// - Concatenation operation: O(1)
35/// - Converting to Vec: O(n)
36///
37/// # Implementation Details
38/// The data structure is implemented as an enum with three variants:
39/// - `Empty`: Represents an empty chunk
40/// - `Append`: Represents a single element appended to another chunk
41/// - `Concat`: Represents the concatenation of two chunks
42///
43/// # Examples
44/// ```
45/// use tailcall_chunk::Chunk;
46///
47/// let mut chunk = Chunk::default();
48/// chunk = chunk.append(1);
49/// chunk = chunk.append(2);
50///
51/// let other_chunk = Chunk::default().append(3).append(4);
52/// let combined = chunk.concat(other_chunk);
53///
54/// assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);
55/// ```
56///
57/// # References
58/// - [Persistent Data Structures](https://en.wikipedia.org/wiki/Persistent_data_structure)
59/// - [Structural Sharing](https://hypirion.com/musings/understanding-persistent-vector-pt-1)
60#[derive(Clone)]
61pub enum Chunk<A> {
62 /// Represents an empty chunk with no elements
63 Empty,
64 /// Represents a chunk containing exactly one element
65 Single(A),
66 /// Represents the concatenation of two chunks, enabling O(1) concatenation
67 Concat(Rc<Chunk<A>>, Rc<Chunk<A>>),
68 /// Represents a collection of elements
69 Collect(Rc<RefCell<Vec<A>>>),
70 /// Represents a lazy transformation that flattens elements
71 TransformFlatten(Rc<Chunk<A>>, Rc<dyn Fn(A) -> Chunk<A>>),
72}
73
74impl<A> Default for Chunk<A> {
75 /// Creates a new empty chunk.
76 ///
77 /// This is equivalent to using [`Chunk::Empty`].
78 fn default() -> Self {
79 Chunk::Empty
80 }
81}
82
83impl<A> Chunk<A> {
84 /// Creates a new chunk containing a single element.
85 ///
86 /// # Arguments
87 /// * `a` - The element to store in the chunk
88 ///
89 /// # Examples
90 /// ```
91 /// use tailcall_chunk::Chunk;
92 ///
93 /// let chunk: Chunk<i32> = Chunk::new(100);
94 /// assert!(!chunk.is_null());
95 /// ```
96 pub fn new(a: A) -> Self {
97 Chunk::Single(a)
98 }
99
100 /// Returns `true` if the chunk is empty.
101 ///
102 /// # Examples
103 /// ```
104 /// use tailcall_chunk::Chunk;
105 ///
106 /// let chunk: Chunk<i32> = Chunk::default();
107 /// assert!(chunk.is_null());
108 ///
109 /// let non_empty = chunk.append(42);
110 /// assert!(!non_empty.is_null());
111 /// ```
112 pub fn is_null(&self) -> bool {
113 match self {
114 Chunk::Empty => true,
115 Chunk::Collect(vec) => vec.borrow().is_empty(),
116 _ => false,
117 }
118 }
119
120 /// Append a new element to the chunk.
121 ///
122 /// This operation has O(1) complexity as it creates a new `Append` variant
123 /// that references the existing chunk through an [`Rc`].
124 ///
125 /// # Examples
126 /// ```
127 /// use tailcall_chunk::Chunk;
128 ///
129 /// let chunk = Chunk::default().append(1).append(2);
130 /// assert_eq!(chunk.as_vec(), vec![1, 2]);
131 /// ```
132 pub fn append(self, a: A) -> Self {
133 self.concat(Chunk::new(a))
134 }
135
136 /// Prepend a new element to the beginning of the chunk.
137 ///
138 /// This operation has O(1) complexity as it creates a new `Concat` variant
139 /// that references the existing chunk through an [`Rc`].
140 ///
141 /// # Examples
142 /// ```
143 /// use tailcall_chunk::Chunk;
144 ///
145 /// let chunk = Chunk::default().prepend(1).prepend(2);
146 /// assert_eq!(chunk.as_vec(), vec![2, 1]);
147 /// ```
148 pub fn prepend(self, a: A) -> Self {
149 if self.is_null() {
150 Chunk::new(a)
151 } else {
152 Chunk::new(a).concat(self)
153 }
154 }
155
156 /// Concatenates this chunk with another chunk.
157 ///
158 /// This operation has O(1) complexity as it creates a new `Concat` variant
159 /// that references both chunks through [`Rc`]s.
160 ///
161 /// # Performance Optimization
162 /// If either chunk is empty, returns the other chunk instead of creating
163 /// a new `Concat` variant.
164 ///
165 /// # Examples
166 /// ```
167 /// use tailcall_chunk::Chunk;
168 ///
169 /// let chunk1 = Chunk::default().append(1).append(2);
170 /// let chunk2 = Chunk::default().append(3).append(4);
171 /// let combined = chunk1.concat(chunk2);
172 /// assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);
173 /// ```
174 pub fn concat(self, other: Chunk<A>) -> Chunk<A> {
175 match (self, other) {
176 // Handle null cases
177 (Chunk::Empty, other) => other,
178 (this, Chunk::Empty) => this,
179 (Chunk::Single(a), Chunk::Single(b)) => {
180 Chunk::Collect(Rc::new(RefCell::new(vec![a, b])))
181 }
182 (Chunk::Collect(vec), Chunk::Single(a)) => {
183 if Rc::strong_count(&vec) == 1 {
184 // Only clone if there are no other references
185 vec.borrow_mut().push(a);
186 Chunk::Collect(vec)
187 } else {
188 Chunk::Concat(Rc::new(Chunk::Collect(vec)), Rc::new(Chunk::Single(a)))
189 }
190 }
191 // Handle all other cases with Concat
192 (this, that) => Chunk::Concat(Rc::new(this), Rc::new(that)),
193 }
194 }
195
196 /// Transforms each element in the chunk using the provided function.
197 ///
198 /// This method creates a lazy representation of the transformation without actually
199 /// performing it. The transformation is only executed when [`as_vec`](Chunk::as_vec)
200 /// or [`as_vec_mut`](Chunk::as_vec_mut) is called.
201 ///
202 /// # Performance
203 /// - Creating the transformation: O(1)
204 /// - Executing the transformation (during [`as_vec`](Chunk::as_vec)): O(n)
205 ///
206 /// # Arguments
207 /// * `f` - A function that takes a reference to an element of type `A` and returns
208 /// a new element of type `A`
209 ///
210 /// # Examples
211 /// ```
212 /// use tailcall_chunk::Chunk;
213 ///
214 /// let chunk = Chunk::default().append(1).append(2).append(3);
215 /// // This operation is O(1) and doesn't actually transform the elements
216 /// let doubled = chunk.transform(|x| x * 2);
217 /// // The transformation happens here, when we call as_vec()
218 /// assert_eq!(doubled.as_vec(), vec![2, 4, 6]);
219 /// ```
220 pub fn transform(self, f: impl Fn(A) -> A + 'static) -> Self {
221 self.transform_flatten(move |a| Chunk::new(f(a)))
222 }
223
224 /// Materializes a chunk by converting it into a collected form.
225 ///
226 /// This method evaluates any lazy transformations and creates a new chunk containing
227 /// all elements in a `Collect` variant. This can be useful for performance when you
228 /// plan to reuse the chunk multiple times, as it prevents re-evaluation of transformations.
229 ///
230 /// # Performance
231 /// - Time complexity: O(n) where n is the number of elements
232 /// - Space complexity: O(n) as it creates a new vector containing all elements
233 ///
234 /// # Examples
235 /// ```
236 /// use tailcall_chunk::Chunk;
237 ///
238 /// let chunk = Chunk::default()
239 /// .append(1)
240 /// .append(2)
241 /// .transform(|x| x * 2); // Lazy transformation
242 ///
243 /// // Materialize the chunk to evaluate the transformation once
244 /// let materialized = chunk.materialize();
245 ///
246 /// assert_eq!(materialized.as_vec(), vec![2, 4]);
247 /// ```
248 pub fn materialize(self) -> Chunk<A>
249 where
250 A: Clone,
251 {
252 Chunk::Collect(Rc::new(RefCell::new(self.as_vec())))
253 }
254
255 /// Transforms each element in the chunk into a new chunk and flattens the result.
256 ///
257 /// This method creates a lazy representation of the transformation without actually
258 /// performing it. The transformation is only executed when [`as_vec`](Chunk::as_vec)
259 /// or [`as_vec_mut`](Chunk::as_vec_mut) is called.
260 ///
261 /// # Performance
262 /// - Creating the transformation: O(1)
263 /// - Executing the transformation (during [`as_vec`](Chunk::as_vec)): O(n)
264 ///
265 /// # Arguments
266 /// * `f` - A function that takes an element of type `A` and returns
267 /// a new `Chunk<A>`
268 ///
269 /// # Examples
270 /// ```
271 /// use tailcall_chunk::Chunk;
272 ///
273 /// let chunk = Chunk::default().append(1).append(2);
274 /// // Transform each number x into a chunk containing [x, x+1]
275 /// let expanded = chunk.transform_flatten(|x| {
276 /// Chunk::default().append(x).append(x + 1)
277 /// });
278 /// assert_eq!(expanded.as_vec(), vec![1, 2, 2, 3]);
279 /// ```
280 pub fn transform_flatten(self, f: impl Fn(A) -> Chunk<A> + 'static) -> Self {
281 Chunk::TransformFlatten(Rc::new(self), Rc::new(f))
282 }
283
284 /// Converts the chunk into a vector of references to its elements.
285 ///
286 /// This operation has O(n) complexity where n is the number of elements
287 /// in the chunk.
288 ///
289 /// # Examples
290 /// ```
291 /// use tailcall_chunk::Chunk;
292 ///
293 /// let chunk = Chunk::default().append(1).append(2).append(3);
294 /// assert_eq!(chunk.as_vec(), vec![1, 2, 3]);
295 /// ```
296 pub fn as_vec(&self) -> Vec<A>
297 where
298 A: Clone,
299 {
300 let mut vec = Vec::new();
301 self.as_vec_mut(&mut vec);
302 vec
303 }
304
305 /// Helper method that populates a vector with references to the chunk's elements.
306 ///
307 /// This method is used internally by [`as_vec`](Chunk::as_vec) to avoid
308 /// allocating multiple vectors during the traversal.
309 ///
310 /// # Arguments
311 /// * `buf` - A mutable reference to a vector that will be populated with
312 /// references to the chunk's elements
313 pub fn as_vec_mut(&self, buf: &mut Vec<A>)
314 where
315 A: Clone,
316 {
317 match self {
318 Chunk::Empty => {}
319 Chunk::Single(a) => {
320 buf.push(a.clone());
321 }
322 Chunk::Concat(a, b) => {
323 a.as_vec_mut(buf);
324 b.as_vec_mut(buf);
325 }
326 Chunk::TransformFlatten(a, f) => {
327 let mut tmp = Vec::new();
328 a.as_vec_mut(&mut tmp);
329 for elem in tmp.into_iter() {
330 f(elem).as_vec_mut(buf);
331 }
332 }
333 Chunk::Collect(vec) => {
334 buf.extend(vec.borrow().iter().cloned());
335 }
336 }
337 }
338}
339
340impl<A> FromIterator<A> for Chunk<A> {
341 /// Creates a chunk from an iterator.
342 ///
343 /// # Examples
344 /// ```
345 /// use tailcall_chunk::Chunk;
346 ///
347 /// let vec = vec![1, 2, 3];
348 /// let chunk: Chunk<_> = vec.into_iter().collect();
349 /// assert_eq!(chunk.as_vec(), vec![1, 2, 3]);
350 /// ```
351 fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self {
352 let vec: Vec<_> = iter.into_iter().collect();
353
354 Chunk::Collect(Rc::new(RefCell::new(vec)))
355 }
356}
357
358#[cfg(test)]
359mod tests {
360 use super::*;
361
362 #[test]
363 fn test_new() {
364 let chunk: Chunk<i32> = Chunk::default();
365 assert!(chunk.is_null());
366 }
367
368 #[test]
369 fn test_default() {
370 let chunk: Chunk<i32> = Chunk::default();
371 assert!(chunk.is_null());
372 }
373
374 #[test]
375 fn test_is_null() {
376 let empty: Chunk<i32> = Chunk::default();
377 assert!(empty.is_null());
378
379 let non_empty = empty.append(1);
380 assert!(!non_empty.is_null());
381 }
382
383 #[test]
384 fn test_append() {
385 let chunk = Chunk::default().append(1).append(2).append(3);
386 assert_eq!(chunk.as_vec(), vec![1, 2, 3]);
387
388 // Test that original chunk remains unchanged (persistence)
389 let chunk1 = Chunk::default().append(1);
390 let chunk2 = chunk1.clone().append(2);
391 assert_eq!(chunk1.as_vec(), vec![1]);
392 assert_eq!(chunk2.as_vec(), vec![1, 2]);
393 }
394
395 #[test]
396 fn test_concat() {
397 let chunk1 = Chunk::default().append(1).append(2);
398 let chunk2 = Chunk::default().append(3).append(4);
399 let combined = chunk1.clone().concat(chunk2.clone());
400
401 assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);
402
403 // Test concatenation with empty chunks
404 let empty = Chunk::default();
405 assert_eq!(
406 empty.clone().concat(chunk1.clone()).as_vec(),
407 chunk1.as_vec()
408 );
409 assert_eq!(
410 chunk1.clone().concat(empty.clone()).as_vec(),
411 chunk1.as_vec()
412 );
413 assert_eq!(empty.clone().concat(empty).as_vec(), Vec::<i32>::new());
414 }
415
416 #[test]
417 fn test_as_vec() {
418 // Test empty chunk
419 let empty: Chunk<i32> = Chunk::default();
420 assert_eq!(empty.as_vec(), Vec::<i32>::new());
421
422 // Test single element
423 let single = Chunk::default().append(42);
424 assert_eq!(single.as_vec(), vec![42]);
425
426 // Test multiple elements
427 let multiple = Chunk::default().append(1).append(2).append(3);
428 assert_eq!(multiple.as_vec(), vec![1, 2, 3]);
429
430 // Test complex structure with concatenation
431 let chunk1 = Chunk::default().append(1).append(2);
432 let chunk2 = Chunk::default().append(3).append(4);
433 let complex = chunk1.concat(chunk2);
434 assert_eq!(complex.as_vec(), vec![1, 2, 3, 4]);
435 }
436
437 #[test]
438 fn test_structural_sharing() {
439 let chunk1 = Chunk::default().append(1).append(2);
440 let chunk2 = chunk1.clone().append(3);
441 let chunk3 = chunk1.clone().append(4);
442
443 // Verify that modifications create new structures while preserving the original
444 assert_eq!(chunk1.as_vec(), vec![1, 2]);
445 assert_eq!(chunk2.as_vec(), vec![1, 2, 3]);
446 assert_eq!(chunk3.as_vec(), vec![1, 2, 4]);
447 }
448
449 #[test]
450 fn test_with_different_types() {
451 // Test with strings
452 let string_chunk = Chunk::default()
453 .append(String::from("hello"))
454 .append(String::from("world"));
455 assert_eq!(string_chunk.as_vec().len(), 2);
456
457 // Test with floating point numbers - using standard constants
458 let float_chunk = Chunk::default()
459 .append(std::f64::consts::PI)
460 .append(std::f64::consts::E);
461 assert_eq!(
462 float_chunk.as_vec(),
463 vec![std::f64::consts::PI, std::f64::consts::E]
464 );
465
466 // Test with boolean values
467 let bool_chunk = Chunk::default().append(true).append(false).append(true);
468 assert_eq!(bool_chunk.as_vec(), vec![true, false, true]);
469 }
470
471 #[test]
472 fn test_transform() {
473 // Test transform on empty chunk
474 let empty: Chunk<i32> = Chunk::default();
475 let transformed_empty = empty.transform(|x| x * 2);
476 assert_eq!(transformed_empty.as_vec(), Vec::<i32>::new());
477
478 // Test transform on single element
479 let single = Chunk::default().append(5);
480 let doubled = single.transform(|x| x * 2);
481 assert_eq!(doubled.as_vec(), vec![10]);
482
483 // Test transform on multiple elements
484 let multiple = Chunk::default().append(1).append(2).append(3);
485 let doubled = multiple.transform(|x| x * 2);
486 assert_eq!(doubled.as_vec(), vec![2, 4, 6]);
487
488 // Test transform with string manipulation
489 let string_chunk = Chunk::default()
490 .append(String::from("hello"))
491 .append(String::from("world"));
492 let uppercase = string_chunk.transform(|s| s.to_uppercase());
493 assert_eq!(uppercase.as_vec(), vec!["HELLO", "WORLD"]);
494
495 // Test chaining multiple transforms
496 let numbers = Chunk::default().append(1).append(2).append(3);
497 let result = numbers
498 .transform(|x| x * 2)
499 .transform(|x| x + 1)
500 .transform(|x| x * 3);
501 assert_eq!(result.as_vec(), vec![9, 15, 21]);
502 }
503
504 #[test]
505 fn test_transform_flatten() {
506 // Test transform_flatten on empty chunk
507 let empty: Chunk<i32> = Chunk::default();
508 let transformed_empty = empty.transform_flatten(|x| Chunk::new(x * 2));
509 assert_eq!(transformed_empty.as_vec(), Vec::<i32>::new());
510
511 // Test transform_flatten on single element
512 let single = Chunk::default().append(5);
513 let doubled = single.transform_flatten(|x| Chunk::new(x * 2));
514 assert_eq!(doubled.as_vec(), vec![10]);
515
516 // Test expanding each element into multiple elements
517 let numbers = Chunk::default().append(1).append(2);
518 let expanded = numbers.transform_flatten(|x| Chunk::default().append(x + 1).append(x));
519 assert_eq!(expanded.as_vec(), vec![2, 1, 3, 2]);
520
521 // Test with nested chunks
522 let chunk = Chunk::default().append(1).append(2).append(3);
523 let nested = chunk.transform_flatten(|x| {
524 if x % 2 == 0 {
525 // Even numbers expand to [x, x+1]
526 Chunk::default().append(x).append(x + 1)
527 } else {
528 // Odd numbers expand to [x]
529 Chunk::new(x)
530 }
531 });
532 assert_eq!(nested.as_vec(), vec![1, 2, 3, 3]);
533
534 // Test chaining transform_flatten operations
535 let numbers = Chunk::default().append(1).append(2);
536 let result = numbers
537 .transform_flatten(|x| Chunk::default().append(x).append(x))
538 .transform_flatten(|x| Chunk::default().append(x).append(x + 1));
539 assert_eq!(result.as_vec(), vec![1, 2, 1, 2, 2, 3, 2, 3]);
540
541 // Test with empty chunk results
542 let chunk = Chunk::default().append(1).append(2);
543 let filtered = chunk.transform_flatten(|x| {
544 if x % 2 == 0 {
545 Chunk::new(x)
546 } else {
547 Chunk::default() // Empty chunk for odd numbers
548 }
549 });
550 assert_eq!(filtered.as_vec(), vec![2]);
551 }
552
553 #[test]
554 fn test_prepend() {
555 let chunk = Chunk::default().prepend(1).prepend(2).prepend(3);
556 assert_eq!(chunk.as_vec(), vec![3, 2, 1]);
557
558 // Test that original chunk remains unchanged (persistence)
559 let chunk1 = Chunk::default().prepend(1);
560 let chunk2 = chunk1.clone().prepend(2);
561 assert_eq!(chunk1.as_vec(), vec![1]);
562 assert_eq!(chunk2.as_vec(), vec![2, 1]);
563
564 // Test mixing prepend and append
565 let mixed = Chunk::default()
566 .prepend(1) // [1]
567 .append(2) // [1, 2]
568 .prepend(3); // [3, 1, 2]
569 assert_eq!(mixed.as_vec(), vec![3, 1, 2]);
570 }
571
572 #[test]
573 fn test_from_iterator() {
574 // Test collecting from an empty iterator
575 let empty_vec: Vec<i32> = vec![];
576 let empty_chunk: Chunk<i32> = empty_vec.into_iter().collect();
577 assert!(empty_chunk.is_null());
578
579 // Test collecting from a vector
580 let vec = vec![1, 2, 3];
581 let chunk: Chunk<_> = vec.into_iter().collect();
582 assert_eq!(chunk.as_vec(), vec![1, 2, 3]);
583
584 // Test collecting from a range
585 let range_chunk: Chunk<_> = (1..=5).collect();
586 assert_eq!(range_chunk.as_vec(), vec![1, 2, 3, 4, 5]);
587
588 // Test collecting from map iterator
589 let doubled: Chunk<_> = vec![1, 2, 3].into_iter().map(|x| x * 2).collect();
590 assert_eq!(doubled.as_vec(), vec![2, 4, 6]);
591 }
592
593 #[test]
594 fn test_concat_optimization() {
595 // Create a collected chunk
596 let collected: Chunk<i32> = vec![1, 2, 3].into_iter().collect();
597
598 // Concat a single element
599 let result = collected.concat(Chunk::Single(4));
600
601 // Verify the result
602 assert_eq!(result.as_vec(), vec![1, 2, 3, 4]);
603
604 // Verify it's still a Collect variant (not a Concat)
605 match result {
606 Chunk::Collect(_) => (), // This is what we want
607 _ => panic!("Expected Collect variant after optimization"),
608 }
609 }
610}