field-collex

基于递归分块思想构造的集合库，致力于给需要有序集合中的大量最值查询的场景提供O(1)方案 A Rust collection library based on the recursive block-based idea, aimed to providing an O(1) solution for scenarios requiring extensive extremum queries in an ordered set

核心 Trait / Core Traits

• Collexetable<V>：定义「可被 FieldCollex 集合管理的元素」的核心行为（提取数值、比较、去重） Collexetable<V>：Define the core behavior of "elements that can be managed by FieldCollex" (extracting values, comparing, deduplicating)；
• FieldValue：约束数值类型的核心能力（零值、单位值、数值转换） FieldValue：Core capabilities for constraining numerical types (zero, unit value, conversion)；

核心模块 / Core Mods

1. collex

FieldCollex<E, V>：

• 存入 E ，从此 Collexetable Trait 的方法得到 V，根据 V 来顺序排序。 E 需要实现 Collexetable 来定义得到 V 的方法。 Store E , and use the method of Collexetable Trait to get V, then sort them in order based on V. E needs to impl 'Collexetable' to define the method for getting V.
• 内部有一些特殊的计算，因此 V 需要实现 FieldValue 来支持这些计算。整数原语类型已实现。 There are some special calculations internally, so V needs to impl 'FieldValue' to support these. The integer primitive type has been implemented.

2. set

FieldSet<V>：

• 基于 collex 模块封装的简易版本，使 E = V，省去了 Collexetable A simplified version based on the collex module, which makes E=V to eliminate Collexetable
• 但 FieldValue 依旧需要 But FieldValue still requires

核心概念 / Core Ideas

1. Span

依赖 span_core 库的 Span<V> 类型，定义集合的数值范围： The 'Span' type, which depends on the 'Span_comore' library, defines the numerical range of the collex:

• 有限区间：[start, end)（闭开区间，start <= v < end 视为有效）； Finite interval: [start, end) (closed open interval, start<=v<end is considered valid);
• 无限区间：[start, +∞)（闭区间，start <= v 视为有效）； Infinite interval: [start,+∞) (closed interval, start<=v is considered valid);
• 空区间：start >= end 的有限区间视为空，无法用于构造集合。 Empty interval: A finite interval with 'start>=end' is considered empty and cannot be used to construct a collex.

2. 分块思想 / Block-based

以 unit（块大小）为粒度，将 Span 划分为多个间隔相同的块，每个块可存储： Using 'unit' (block size) as the granularity, divide 'Span' into multiple blocks with same size, each of which can store:

• 单个数值（Field::Elem） Single value (Field: Elem)
• 子集合（Field::Collex）：块内多个数值时，递归创建子 FieldCollex 实现分层存储； Subcollex (Field: Collex): When there are multiple values in a block, recursively create a sub FieldCollex to achieve hierarchical storage;
• 空（详见 RawField）：若某个块为空，会存储前后一个非空块的索引。 Empty (see RawField for details): If a block is empty, the index of the preceding and following non-empty blocks will be stored.

这些设计使Collex可以通过任何值进行简单计算，O(1)地定位块的位置，从而快捷地进行查询与范围查询。 These designs enable Collex to perform simple calculations using any value, locate the position of blocks as O(1), to quickly perform getters and range queries.

3. FieldValue

约束数值类型的核心 Trait，需实现以下能力： The core Trait that constrains numerical types, requires the following capabilities to be implemented:

• 零值(num_traits::Zero)/单位值：zero()/min_positive()； zero(num_traits::Zero)/unit value
• 数值转换：into_usize()/from_usize()（块索引计算）； conversion: into_usize()/From_usize() (block index calculation);
• 区间计算：ceil()（块数量向上取整）。 Interval calculation: ceil() (rounding up to get number of blocks).

快速开始 / Let's Go

引入依赖 / Import

I don't want to say anymore.

cargo add field-collex