VRope - Rope Data Structure Implementation for V
A comprehensive rope data structure implementation in V-lang, designed for efficient text manipulation and demonstrating different string handling approaches.
📚 Table of Contents
🎯 Overview
A rope is a binary tree data structure used for efficiently storing and manipulating very long strings. This project provides:
-
Full Rope Implementation
( rope.v) - Complete tree-based rope with all operations -
Simple Rope Demo
( simple_rope.v) - String-based implementation for comparison -
Comprehensive Benchmarks
- Performance comparison with native V string operations -
Test Suite
- Extensive testing of all rope operations
When to Use Ropes
✅ Best for:
- Large documents (>10KB)
- Frequent insertions/deletions
- Text editors and IDEs
- Undo/redo systems
- Collaborative editing
❌ Not ideal for:
- Small strings (<1KB)
- Read-only operations
- Simple concatenations
- Memory-constrained environments
## ✨ Features
### Core Operations
- **Create**: Build ropes from strings or create empty ropes
- **Access**: O(log n) character access by index
- **Insert**: O(log n) insertion at any position
- **Delete**: O(log n) deletion of ranges
- **Concatenate**: O(1) rope concatenation
- **Split**: O(log n) rope splitting
- **Substring**: O(log n) substring extraction
### Advanced Features
- **Search**: Find first/all occurrences of substrings
- **Replace**: Replace all occurrences of patterns
- **Iterator**: Efficient character-by-character traversal
- **Rebalancing**: Tree optimization for performance
- **Memory Efficient**: Optimized memory usage
- **Error Handling**: Comprehensive bounds checking
## 🚀 Installation
Clone the repository:
```bash
v install rope
💡 Quick Start
Basic Usage
import rope
fn main() {
// Create a rope from a string
mut r := rope.from_string('Hello, World!')
// Basic operations
println(r.to_string()) // "Hello, World!"
println(r.length()) // 13
// Character access
ch := r.char_at(7) or { panic('Index error') }
println('Character at 7: ${ch.ascii_str()}') // "W"
// Text editing
r.insert(7, 'Beautiful ') or { panic('Insert failed') }
println(r.to_string()) // "Hello, Beautiful World!"
// Substring extraction
hello := r.substring(0, 5) or { panic('Substring failed') }
println('First 5 chars: ${hello}') // "Hello"
}
📊 Benchmarks
Run performance benchmarks comparing rope operations against native V string operations:
v run benchmarks/rope_benchmark.v
Sample Benchmark Results
Concatenation: 1000000
Operation | Duration | Ops/sec | Memory(KB)
------------------------- | ------------ | ------------ | ------------
String Concatenation | 2008.00 ms | 498 | 1953 KB
StringBuilder Concat | 1138.00 ms | 879 | 976 KB
Rope Concatenation | 349.00 ms | 2865 | 976 KB
Character Access: 1000000
Operation | Duration | Ops/sec | Memory(KB)
------------------------- | ------------ | ------------ | ------------
String Char Access | 0.00 ms | +inf | 976 KB
Rope Char Access | 0.00 ms | +inf | 976 KB
Substring: 1000000
Operation | Duration | Ops/sec | Memory(KB)
------------------------- | ------------ | ------------ | ------------
String Substring | 170.00 ms | 5882 | 976 KB
Rope Substring | 157.00 ms | 6369 | 976 KB
Append: 1000000
Operation | Duration | Ops/sec | Memory(KB)
------------------------- | ------------ | ------------ | ------------
String Append | 1946.00 ms | 1028 | 19531 KB
StringBuilder Append | 1536.00 ms | 1302 | 976 KB
Rope Append | 1682.00 ms | 1189 | 976 KB
Prepend: 1000000
Operation | Duration | Ops/sec | Memory(KB)
------------------------- | ------------ | ------------ | ------------
String Prepend | 2365.00 ms | 846 | 1953 KB
Rope Prepend | 1558.00 ms | 1284 | 976 KB
Insertion: 1000000
Operation | Duration | Ops/sec | Memory(KB)
------------------------- | ------------ | ------------ | ------------
String Insertion | 459.00 ms | 2179 | 1953 KB
Rope Insertion | 112.00 ms | 8929 | 976 KB
Deletion: 1000000
Operation | Duration | Ops/sec | Memory(KB)
------------------------- | ------------ | ------------ | ------------
String Deletion | 412.00 ms | 2427 | 976 KB
Rope Deletion | 64.00 ms | 15625 | 976 KB
Search: 1000000
Operation | Duration | Ops/sec | Memory(KB)
------------------------- | ------------ | ------------ | ------------
String Search | 2077.00 ms | 481 | 976 KB
Rope Search | 64.00 ms | 15625 | 1953 KB
📖 API Reference
Creating Ropes
// Create empty rope
r := rope.new_rope()
// Create from string
r := rope.from_string('Hello, World!')
Basic Operations
// Length and status
len := r.length()
empty := r.is_empty()
// Character access
ch := r.char_at(index) or { return error('Index out of bounds') }
// Convert to string
s := r.to_string()
// Substring extraction
substr := r.substring(start, end) or { return error('Invalid bounds') }
Modification Operations
// Insert text at position
r.insert(index, 'text to insert') or { return error('Insert failed') }
// Delete range
r.delete(start, end) or { return error('Delete failed') }
// Concatenate ropes
r.concat(&other_rope)
// Split rope at position
left, right := r.split(index) or { return error('Split failed') }
Search and Replace
// Find first occurrence
index := r.find_first('search term') or { -1 }
// Find all occurrences
indices := r.find_all('search term')
// Replace all occurrences
r.replace_all('old text', 'new text')
Advanced Operations
// Tree depth (for performance monitoring)
depth := r.depth()
// Rebalance tree for optimal performance
r.rebalance()
// Iterator for character-by-character processing
mut iter := r.iterator()
for iter.has_next() {
ch := iter.next() or { break }
// Process character
}
🎨 Usage Patterns
Text Editor Simulation
mut document := rope.new_rope()
// User types at beginning
document.insert(0, 'Hello') or { panic('Insert failed') }
// User adds more text
document.insert(5, ' World') or { panic('Insert failed') }
// User inserts text in middle
document.insert(5, ' Beautiful') or { panic('Insert failed') }
// User deletes word
document.delete(6, 15) or { panic('Delete failed') }
println(document.to_string()) // "Hello World"
Large Document Processing
// Build large document incrementally
mut doc := rope.new_rope()
for i in 0..10000 {
doc.insert(doc.length(), 'Line ${i}: Sample content\n') or {
panic('Failed to add line ${i}')
}
}
// Efficient operations on large document
header := 'DOCUMENT HEADER\n\n'
doc.insert(0, header) or { panic('Failed to add header') }
// Extract sections efficiently
first_page := doc.substring(0, 2000) or { panic('Failed to extract') }
📜 License
MIT License - see LICENSE file for details.
About
A comprehensive Rope data structure implementation in V
0
0
last Oct 22
Author
