Rust区间映射库range_map_vec使用指南

range_map_vec是一个高效的Rust库，专门用于管理重叠区间和范围查询的数据结构。它提供了一种在内存中存储和查询区间数据的高效方式。

主要特性

• 高效存储和查询区间数据
• 支持重叠区间的管理
• 提供范围查询功能
• 基于Vec实现，内存效率高

安装

在Cargo.toml中添加依赖：

[dependencies]
range_map_vec = "0.1"

基本用法

创建区间映射

use range_map_vec::{RangeMap, RangeSet};

// 创建一个空的区间映射
let mut range_map: RangeMap<i32, String> = RangeMap::new();

// 插入区间
range_map.insert(0..10, "first".to_string());
range_map.insert(5..15, "second".to_string());

查询区间

// 查询特定点所在的区间
let values_at_7 = range_map.query(&7);
println!("Values at 7: {:?}", values_at_7); // 可能包含"first"和"second"

// 查询与给定区间重叠的所有区间
let overlapping = range_map.query_range(&(8..12));
println!("Overlapping with 8..12: {:?}", overlapping);

区间集合操作

let mut range_set = RangeSet::new();
range_set.insert(0..10);
range_set.insert(5..15);

// 检查区间是否包含某个点
println!("Contains 7? {}", range_set.contains(&7)); // true
println!("Contains 20? {}", range_set.contains(&20)); // false

高级用法

合并重叠区间

let mut range_map = RangeMap::new();
range_map.insert(0..5, "A".to_string());
range_map.insert(3..8, "B".to_string());

// 合并重叠区间
range_map.coalesce(|a, b| format!("{}, {}", a, b));

// 现在区间0..8将包含值"A, B"

区间运算

let mut set1 = RangeSet::new();
set1.insert(0..10);
set1.insert(20..30);

let mut set2 = RangeSet::new();
set2.insert(5..15);
set2.insert(25..35);

// 并集
let union = set1.union(&set2);
println!("Union: {:?}", union);

// 交集
let intersection = set1.intersection(&set2);
println!("Intersection: {:?}", intersection);

性能考虑

range_map_vec在内部使用排序的区间列表，这使得：

• 插入操作是O(n)
• 查询操作是O(log n)
• 内存使用紧凑

对于频繁更新的场景，可能需要考虑其他数据结构，但对于主要进行查询的操作，这是一个高效的选择。

完整示例代码

下面是一个完整的示例，展示了如何使用range_map_vec构建一个简单的日程管理系统：

use range_map_vec::RangeMap;
use chrono::{NaiveDateTime, Duration};

// 定义事件结构体
#[derive(Debug)]
struct Event {
    title: String,
    description: String,
}

fn main() {
    // 创建日程表
    let mut schedule = RangeMap::new();
    
    // 设置起始时间
    let start = NaiveDateTime::from_timestamp(0, 0);
    
    // 创建并插入几个事件
    let event1 = Event {
        title: "Team Meeting".to_string(),
        description: "Weekly sync".to_string(),
    };
    schedule.insert(start..start + Duration::hours(1), event1);
    
    let event2 = Event {
        title: "Lunch Break".to_string(),
        description: "Time to eat".to_string(),
    };
    schedule.insert(start + Duration::hours(1)..start + Duration::hours(2), event2);
    
    let event3 = Event {
        title: "Client Call".to_string(),
        description: "Discuss project".to_string(),
    };
    schedule.insert(start + Duration::minutes(45)..start + Duration::hours(1) + Duration::minutes(30), event3);
    
    // 查询特定时间点的事件
    let check_time = start + Duration::minutes(50);
    if let Some(events) = schedule.query(&check_time) {
        println!("At {:?}, you have:", check_time);
        for event in events {
            println!("- {}: {}", event.title, event.description);
        }
    }
    
    // 查询重叠区间
    let query_range = start + Duration::minutes(30)..start + Duration::hours(1) + Duration::minutes(15);
    println!("Events between 30-75 minutes:");
    for (range, event) in schedule.query_range(&query_range) {
        println!("{:?}: {} ({})", range, event.title, event.description);
    }
    
    // 合并重叠区间
    println!("\nBefore coalescing:");
    for (range, event) in schedule.iter() {
        println!("{:?}: {}", range, event.title);
    }
    
    schedule.coalesce(|a, b| Event {
        title: format!("{} + {}", a.title, b.title),
        description: format!("Combined: {} | {}", a.description, b.description),
    });
    
    println!("\nAfter coalescing:");
    for (range, event) in schedule.iter() {
        println!("{:?}: {} ({})", range, event.title, event.description);
    }
}

输出示例

运行上述代码可能会产生类似以下输出：

At 1970-01-01T00:50:00, you have:
- Team Meeting: Weekly sync
- Client Call: Discuss project

Events between 30-75 minutes:
1970-01-01T00:45:00..1970-01-01T01:30:00: Client Call (Discuss project)
1970-01-01T00:00:00..1970-01-01T01:00:00: Team Meeting (Weekly sync)

Before coalescing:
1970-01-01T00:45:00..1970-01-01T01:30:00: Client Call
1970-01-01T00:00:00..1970-01-01T01:00:00: Team Meeting
1970-01-01T01:00:00..1970-01-01T02:00:00: Lunch Break

After coalescing:
1970-01-01T00:00:00..1970-01-01T01:30:00: Team Meeting + Client Call (Combined: Weekly sync | Discuss project)
1970-01-01T01:00:00..1970-01-01T02:00:00: Lunch Break (Time to eat)

这个示例展示了如何创建、查询和合并区间数据，以及如何处理重叠的日程安排。range_map_vec非常适合这类需要处理时间区间或数值区间的应用场景。