TreapList

A Rust implementation of a treap-based list data structure that provides efficient operations for dynamic sequences.

Overview

TreapList combines the properties of a binary search tree and a heap to offer logarithmic time complexity for common operations on sequences. It's particularly useful for applications that require frequent modifications to ordered data, such as text editors, sequence alignment algorithms, and other dynamic programming problems.

Features

• Efficient Operations: O(log n) average time complexity for insert, delete, and range queries
• Range Summation: Quickly compute sums over arbitrary ranges of elements
• Dynamic Updates: Insert and remove elements or ranges of elements at any position
• Randomized Balancing: Self-balancing using randomized priorities (treap property)

Installation

Add this to your Cargo.toml:

[dependencies]
treaplist = "0.1.2"

Usage

use treaplist::TreapList;

// Create a new treap list
let mut list = TreapList::new();

// Add elements
list.push(1);
list.push(2);
list.push(3);

// Insert at specific position
list.insert_after_k_nodes(1, 10);  // Insert 10 after index 1

// Get elements
assert_eq!(list.get(0), Some(&1));
assert_eq!(list.get(2), Some(&10));

// Compute range sums
let sum = list.sum_range(1..3);  // Sum of elements at indices 1 and 2

// Remove a range of elements
list.remove_range(0..2);  // Remove elements at indices 0 and 1

Example: Dynamic Text Editor

The TreapList is well-suited for representing text in editors. See the included example:

// See examples/dyn_string.rs for a complete implementation
let mut text = DynText::new("Hello, world!\nThis is a test.");
text.apply_change(0, 7, 0, 12, "universe");

Performance

Operations have the following complexity:

• Insert: O(log n)
• Remove: O(log n)
• Access: O(log n)
• Range sum: O(log n)
• Length: O(1)

License

This project is licensed under the MIT License.