xrange 0.1.1

Efficient range overlap detection and search / 高效范围重叠检测与搜索
Documentation

English | 中文

xrange : Efficient range overlap detection and search

Table of Contents

Project Overview

xrange provides efficient utilities for detecting range overlaps and searching overlapping items in sorted collections. The library supports various range types including bounded, unbounded, inclusive, and exclusive bounds, with optimized performance using binary search.

Usage

Check Range Overlap

use xrange::is_overlap;

// Basic overlap check
assert!(is_overlap(&(1..10), &(5..15)));

// Boundary handling
assert!(!is_overlap(&(1..10), &(10..20)));

// Unbounded ranges
assert!(is_overlap(&(..10), &(5..15)));
assert!(is_overlap(&(5..), &(1..10)));

Search Overlapping Ranges

use xrange::search_overlap;

let ranges: Vec<std::ops::RangeInclusive<i32>> = vec![
  1..=5,
  6..=10,
  11..=15,
  16..=20,
];

// Find overlapping ranges
let result: Vec<_> = search_overlap(&ranges, 8..=12).collect();
assert_eq!(result.len(), 2);

// Unbounded query
let result: Vec<_> = search_overlap(&ranges, ..=10).collect();
assert_eq!(result.len(), 2);

Byte Slice Support

use xrange::search_overlap;

let ranges: Vec<std::ops::RangeInclusive<&[u8]>> = vec![
  &b"apple"[..]..=&b"banana"[..],
  &b"cherry"[..]..=&b"date"[..],
  &b"elder"[..]..=&b"fig"[..],
];

let result: Vec<_> = search_overlap(&ranges, &b"coconut"[..]..=&b"dragon"[..]).collect();
assert_eq!(result.len(), 1);

Features

  • Flexible Range Types: Supports all standard range types (Range, RangeInclusive, RangeFrom, RangeTo, RangeToInclusive, RangeFull)
  • Generic Design: Works with any type implementing PartialOrd
  • Zero-Cost Abstractions: No runtime overhead, compile-time optimized
  • Unsized Type Support: Handles dynamically-sized types like [u8]
  • Borrow Pattern: Efficient memory usage without ownership transfer
  • Binary Search Optimization: O(log n) search performance for sorted collections

Design

Core Components

xrange consists of two main functions with distinct responsibilities:

graph TD
  A[is_overlap] --> B{Compare Bounds}
  B --> C[Check r1.start <= r2.end]
  B --> D[Check r2.start <= r1.end]
  C --> E[Return Result]
  D --> E

  F[search_overlap] --> G[Binary Search Start]
  G --> H[Binary Search End]
  H --> I[Filter Overlapping]
  I --> J[Return Iterator]

  I --> A

Flow Diagram

graph TD
  A[Input: Slice & Query] --> B{Is Slice Sorted?}
  B -->|Yes| C[partition_point: Find Start]
  B -->|No| D[Linear Scan]
  C --> E[partition_point: Find End]
  D --> E
  E --> F[Filter with is_overlap]
  F --> G[Return Iterator]

Module Interaction

The search_overlap function leverages is_overlap for final filtering, ensuring consistent overlap detection logic across both APIs.

Technology Stack

  • Language: Rust 2024 Edition
  • Core Dependencies: None (std only)
  • Key Traits: PartialOrd, RangeBounds, Borrow
  • Optimization: Binary search via partition_point

Project Structure

xrange/
├── src/
│   ├── lib.rs           # Public API exports
│   ├── is_overlap.rs    # Range overlap detection
│   └── search_overlap.rs # Overlap search in sorted slices
├── tests/
│   ├── is_overlap.rs    # Overlap detection tests
│   └── search_overlap.rs # Search function tests
├── Cargo.toml
└── README.md

API Documentation

is_overlap

Checks if two ranges overlap.

pub fn is_overlap<T, Q, R1, R2>(r1: &R1, r2: &R2) -> bool
where
  T: PartialOrd + ?Sized,
  Q: Borrow<T> + ?Sized,
  R1: RangeBounds<Q>,
  R2: RangeBounds<Q>

Parameters:

  • r1: First range reference
  • r2: Second range reference

Returns: true if ranges overlap, false otherwise

Examples:

// Inclusive ranges
assert!(is_overlap(&(1..=10), &(5..=15)));

// Exclusive ranges
assert!(!is_overlap(&(1..10), &(10..20)));

// Mixed bounds
assert!(is_overlap(&(1..=10), &(10..15)));

search_overlap

Finds all items in a sorted slice that overlap with the given range.

pub fn search_overlap<T, B, R1, R2>(slice: &[T], range: R2) -> impl Iterator<Item = &T>
where
  B: PartialOrd + ?Sized,
  T: Borrow<R1>,
  R1: RangeBounds<B>,
  R2: RangeBounds<B>

Parameters:

  • slice: Sorted slice of range items
  • range: Query range to find overlaps with

Returns: Iterator over references to overlapping items

Performance: O(log n) for binary search + O(k) for filtering, where k is the number of overlapping items

Examples:

let ranges = vec![1..=5, 6..=10, 11..=15];
let overlaps: Vec<_> = search_overlap(&ranges, 8..=12).collect();

History

Range operations have been fundamental in computer science since the early days of programming. The concept of interval arithmetic dates back to the 1950s, initially developed for error analysis in numerical computations. Modern implementations leverage binary search techniques pioneered in the 1960s, achieving logarithmic time complexity for sorted data structures.

The borrow pattern used in xrange reflects Rust's ownership model, introduced in 2010 to provide memory safety without garbage collection. This approach allows efficient range comparisons while maintaining zero-cost abstractions.

Range overlap detection is widely used in database systems (for temporal queries), graphics programming (for bounding box collisions), and scheduling algorithms (for time slot management).

About

This project is an open-source component of js0.site ⋅ Refactoring the Internet Plan.

We are redefining the development paradigm of the Internet in a componentized way. Welcome to follow us:

xrange : 高效范围重叠检测与搜索

目录

项目概述

xrange 提供高效的范围重叠检测和有序集合重叠项搜索功能。库支持多种范围类型，包括有界、无界、包含和排除边界，通过二分查找实现性能优化。

使用示例

检测范围重叠

use xrange::is_overlap;

// 基本重叠检测
assert!(is_overlap(&(1..10), &(5..15)));

// 边界处理
assert!(!is_overlap(&(1..10), &(10..20)));

// 无边界范围
assert!(is_overlap(&(..10), &(5..15)));
assert!(is_overlap(&(5..), &(1..10)));

搜索重叠范围

use xrange::search_overlap;

let ranges: Vec<std::ops::RangeInclusive<i32>> = vec![
  1..=5,
  6..=10,
  11..=15,
  16..=20,
];

// 查找重叠范围
let result: Vec<_> = search_overlap(&ranges, 8..=12).collect();
assert_eq!(result.len(), 2);

// 无边界查询
let result: Vec<_> = search_overlap(&ranges, ..=10).collect();
assert_eq!(result.len(), 2);

字节切片支持

use xrange::search_overlap;

let ranges: Vec<std::ops::RangeInclusive<&[u8]>> = vec![
  &b"apple"[..]..=&b"banana"[..],
  &b"cherry"[..]..=&b"date"[..],
  &b"elder"[..]..=&b"fig"[..],
];

let result: Vec<_> = search_overlap(&ranges, &b"coconut"[..]..=&b"dragon"[..]).collect();
assert_eq!(result.len(), 1);

特性

  • 灵活的范围类型：支持所有标准范围类型
  • 泛型设计：适用于任何实现 PartialOrd 的类型
  • 零成本抽象：无运行时开销，编译时优化
  • 不定长类型支持：处理动态大小类型如 [u8]
  • 借用模式：高效内存使用，无需所有权转移
  • 二分查找优化：有序集合 O(log n) 搜索性能

设计思路

核心组件

xrange 包含两个主要函数，各自承担不同职责：

graph TD
  A[is_overlap] --> B{比较边界}
  B --> C[检查 r1.start <= r2.end]
  B --> D[检查 r2.start <= r1.end]
  C --> E[返回结果]
  D --> E

  F[search_overlap] --> G[二分查找起始位置]
  G --> H[二分查找结束位置]
  H --> I[过滤重叠项]
  I --> J[返回迭代器]

  I --> A

流程图

graph TD
  A[输入: 切片与查询范围] --> B{切片是否有序?}
  B -->|是| C[partition_point: 查找起始位置]
  B -->|否| D[线性扫描]
  C --> E[partition_point: 查找结束位置]
  D --> E
  E --> F[使用 is_overlap 过滤]
  F --> G[返回迭代器]

模块交互

search_overlap 函数利用 is_overlap 进行最终过滤，确保两个 API 的重叠检测逻辑一致。

技术栈

  • 语言：Rust 2024 Edition
  • 核心依赖：无（仅使用标准库）
  • 关键 Trait：PartialOrd、RangeBounds、Borrow
  • 优化：通过 partition_point 实现二分查找

目录结构

xrange/
├── src/
│   ├── lib.rs           # 公共 API 导出
│   ├── is_overlap.rs    # 范围重叠检测
│   └── search_overlap.rs # 有序切片重叠搜索
├── tests/
│   ├── is_overlap.rs    # 重叠检测测试
│   └── search_overlap.rs # 搜索函数测试
├── Cargo.toml
└── README.md

API 说明

is_overlap

检查两个范围是否重叠。

pub fn is_overlap<T, Q, R1, R2>(r1: &R1, r2: &R2) -> bool
where
  T: PartialOrd + ?Sized,
  Q: Borrow<T> + ?Sized,
  R1: RangeBounds<Q>,
  R2: RangeBounds<Q>

参数：

  • r1：第一个范围引用
  • r2：第二个范围引用

返回值：范围重叠返回 true，否则返回 false

示例：

// 包含边界
assert!(is_overlap(&(1..=10), &(5..=15)));

// 排除边界
assert!(!is_overlap(&(1..10), &(10..20)));

// 混合边界
assert!(is_overlap(&(1..=10), &(10..15)));

search_overlap

在有序切片中查找与给定范围重叠的所有项。

pub fn search_overlap<T, B, R1, R2>(slice: &[T], range: R2) -> impl Iterator<Item = &T>
where
  B: PartialOrd + ?Sized,
  T: Borrow<R1>,
  R1: RangeBounds<B>,
  R2: RangeBounds<B>

参数：

  • slice：有序范围项切片
  • range：查询范围

返回值：重叠项引用的迭代器

性能：二分查找 O(log n) + 过滤 O(k)，k 为重叠项数量

示例：

let ranges = vec![1..=5, 6..=10, 11..=15];
let overlaps: Vec<_> = search_overlap(&ranges, 8..=12).collect();

历史背景

范围操作自编程早期便成为计算机科学的核心概念。区间算术概念可追溯至 1950 年代，最初用于数值计算中的误差分析。现代实现利用 1960 年代开创的二分查找技术，在有序数据结构上实现对数时间复杂度。

xrange 采用的借用模式体现了 Rust 的所有权模型，该模型于 2010 年引入，在无垃圾回收的情况下提供内存安全。这种方法允许高效的范围比较，同时保持零成本抽象。

范围重叠检测广泛应用于数据库系统（时态查询）、图形编程（边界框碰撞检测）和调度算法（时间段管理）。

关于

本项目为 js0.site ⋅ 重构互联网计划 的开源组件。

我们正在以组件化的方式重新定义互联网的开发范式，欢迎关注：