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: 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<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<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.