xrange 0.1.1

[English](#en) | [中文](#zh)

---

<a id="en"></a>

# xrange : Efficient range overlap detection and search

## Table of Contents

- [Project Overview](#project-overview)
- [Usage](#usage)
- [Features](#features)
- [Design](#design)
- [Technology Stack](#technology-stack)
- [Project Structure](#project-structure)
- [API Documentation](#api-documentation)
- [History](#history)

## 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

```rust
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

```rust
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

```rust
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:

```mermaid
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

```mermaid
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.

```rust
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**:

```rust
// 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.

```rust
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**:

```rust
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](https://js0.site).

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

* [Google Group](https://groups.google.com/g/js0-site)
* [js0site.bsky.social](https://bsky.app/profile/js0site.bsky.social)

---

<a id="zh"></a>

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

## 目录

- [项目概述](#项目概述)
- [使用示例](#使用示例)
- [特性](#特性)
- [设计思路](#设计思路)
- [技术栈](#技术栈)
- [目录结构](#目录结构)
- [API 说明](#api-说明)
- [历史背景](#历史背景)

## 项目概述

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

## 使用示例

### 检测范围重叠

```rust
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)));
```

### 搜索重叠范围

```rust
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);
```

### 字节切片支持

```rust
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 包含两个主要函数，各自承担不同职责：

```mermaid
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
```

### 流程图

```mermaid
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`

检查两个范围是否重叠。

```rust
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`

**示例**：

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

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

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

### `search_overlap`

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

```rust
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 为重叠项数量

**示例**：

```rust
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 ⋅ 重构互联网计划](https://js0.site) 的开源组件。

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

* [谷歌邮件列表](https://groups.google.com/g/js0-site)
* [js0site.bsky.social](https://bsky.app/profile/js0site.bsky.social)