Struct OneLevel 

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

A single-level PGM-Index.

This is a simpler variant of the multi-level index that uses only one level of segments. It’s suitable for smaller datasets or when you want to minimize memory usage at the cost of slightly longer segment search time.

Example

use pgm_extra::index::external::OneLevel;

let keys: Vec<u64> = (0..1000).collect();
let index = OneLevel::new(&keys, 8).unwrap();

assert!(index.contains(&keys, &500));

Implementations

impl<T: Indexable> OneLevel<T>

where T::Key: Ord,

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

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

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

pub fn is_empty(&self) -> bool

pub fn segments_count(&self) -> usize

pub fn epsilon(&self) -> usize

pub fn size_in_bytes(&self) -> usize

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 OneLevel<T>

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

type Archived = ArchivedOneLevel<T>

The archived representation of this type.

type Resolver = OneLevelResolver<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 OneLevel<T>

where T::Key: Clone,

fn clone(&self) -> OneLevel<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 OneLevel<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 OneLevel<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<OneLevel<T>, __D> for Archived<OneLevel<T>>

where usize: Archive, <usize as Archive>::Archived: Deserialize<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<OneLevel<T>, <__D as Fallible>::Error>

Deserializes using the given deserializer

impl<T: Indexable> External<T> for OneLevel<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<__S: Fallible + ?Sized, T: Indexable> Serialize<__S> for OneLevel<T>

where 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 OneLevel<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.