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: Indexable> Archive for Static<T>

where usize: Archive, Vec<usize>: Archive, Vec<Segment<T::Key>>: Archive,

type Archived = ArchivedStatic<T>

The archived representation of this type.

type Resolver = StaticResolver<T>

The resolver for this type. It must contain all the additional information from serializing needed to make the archived type from the normal type.

fn resolve(&self, resolver: Self::Resolver, out: Place<Self::Archived>)

Creates the archived version of this value at the given position and writes it to the given output.

const COPY_OPTIMIZATION: CopyOptimization<Self> = _

An optimization flag that allows the bytes of this type to be copied directly to a writer instead of calling serialize.

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<__D: Fallible + ?Sized, T: Indexable> Deserialize<Static<T>, __D> for Archived<Static<T>>

where usize: Archive, <usize as Archive>::Archived: Deserialize<usize, __D>, Vec<usize>: Archive, <Vec<usize> as Archive>::Archived: Deserialize<Vec<usize>, __D>, Vec<Segment<T::Key>>: Archive, <Vec<Segment<T::Key>> as Archive>::Archived: Deserialize<Vec<Segment<T::Key>>, __D>,

fn deserialize( &self, deserializer: &mut __D, ) -> Result<Static<T>, <__D as Fallible>::Error>

Deserializes using the given 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: PartialEq + Indexable> PartialEq for Static<T>

where T::Key: PartialEq,

fn eq(&self, other: &Static<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<__S: Fallible + ?Sized, T: Indexable> Serialize<__S> for Static<T>

where usize: Serialize<__S>, Vec<usize>: Serialize<__S>, Vec<Segment<T::Key>>: Serialize<__S>,

fn serialize( &self, serializer: &mut __S, ) -> Result<<Self as Archive>::Resolver, <__S as Fallible>::Error>

Writes the dependencies for the object and returns a resolver that can create the archived 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.

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