Struct Static 

pub struct Static<T: Indexable> { /* private fields */ }

A multi-level recursive PGM-Index.

This index builds multiple levels of linear models for efficient lookups. It does not own the data; the keys must be stored separately and passed to query methods.

Type Parameters

• T: The value type that implements Indexable. The index internally stores segments of T::Key for the linear models.

Example

use pgm_extra::index::external::Static;

let keys: Vec<u64> = (0..10000).collect();
let index = Static::new(&keys, 64, 4).unwrap();

assert!(index.contains(&keys, &5000));
assert_eq!(index.lower_bound(&keys, &5000), 5000);

Implementations

impl<T: Indexable> Static<T>

where T::Key: Ord,

pub fn new( data: &[T], epsilon: usize, epsilon_recursive: usize, ) -> Result<Self, Error>

Build a new multi-level PGM-Index from sorted data.

Parameters

• data: A sorted slice of values
• epsilon: Error bound for the bottom level (larger = fewer segments)
• epsilon_recursive: Error bound for upper levels

Errors

Returns an error if data is empty or epsilon is 0.

pub fn new_parallel( data: &[T], epsilon: usize, epsilon_recursive: usize, ) -> Result<Self, Error>

pub fn search(&self, value: &T) -> ApproxPos

Get an approximate position for the given value.

pub fn search_by_key(&self, key: &T::Key) -> ApproxPos

Get an approximate position for the given key.

pub fn lower_bound(&self, data: &[T], value: &T) -> usize

where T: Ord,

Find the first position where data[pos] >= value.

pub fn upper_bound(&self, data: &[T], value: &T) -> usize

where T: Ord,

Find the first position where data[pos] > value.

pub fn contains(&self, data: &[T], value: &T) -> bool

where T: Ord,

Check if the value exists in the data.

pub fn len(&self) -> usize

Number of elements the index was built for.

pub fn is_empty(&self) -> bool

pub fn segments_count(&self) -> usize

Number of segments across all levels.

pub fn height(&self) -> usize

Number of levels in the index.

pub fn epsilon(&self) -> usize

pub fn epsilon_recursive(&self) -> usize

pub fn size_in_bytes(&self) -> usize

Approximate memory usage in bytes.

pub fn range_indices<R>(&self, data: &[T], range: R) -> (usize, usize)

where T: Ord, R: RangeBounds<T>,

Returns the (start, end) indices for iterating over data in the given range.

pub fn range<'a, R>( &self, data: &'a [T], range: R, ) -> impl DoubleEndedIterator<Item = &'a T>

where T: Ord, R: RangeBounds<T>,

Returns an iterator over data in the given range.

Trait Implementations

impl<T: Clone + Indexable> Clone for Static<T>

where T::Key: Clone,

fn clone(&self) -> Static<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Indexable> Debug for Static<T>

where T::Key: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de, T: Indexable> Deserialize<'de> for Static<T>

where T::Key: Serialize + DeserializeOwned,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T: Indexable> External<T> for Static<T>

where T::Key: Ord,

fn search(&self, value: &T) -> ApproxPos

Get an approximate position for the value.

fn lower_bound(&self, data: &[T], value: &T) -> usize

where T: Ord,

Find the first position where data[pos] >= value.

fn upper_bound(&self, data: &[T], value: &T) -> usize

where T: Ord,

Find the first position where data[pos] > value.

fn contains(&self, data: &[T], value: &T) -> bool

where T: Ord,

Check if the value exists in the sorted slice.

fn len(&self) -> usize

Number of elements the index was built for.

fn segments_count(&self) -> usize

Number of segments in the index.

fn epsilon(&self) -> usize

Epsilon value used for the bottom level.

fn size_in_bytes(&self) -> usize

Approximate memory usage in bytes.

fn is_empty(&self) -> bool

Whether the index is empty.

impl<T: Indexable> From<Cached<T>> for Static<T>

where T::Key: Ord + FastHash + Default,

fn from(cached: Cached<T>) -> Self

Converts to this type from the input type.

impl<T: Indexable> From<Static<T>> for Cached<T>

where T::Key: Ord + FastHash + Default,

fn from(index: Static<T>) -> Self

Converts to this type from the input type.

impl<T: Indexable> Serialize for Static<T>

where T::Key: Serialize + DeserializeOwned,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.