Struct Cached 

pub struct Cached<T: Indexable>
where
    T::Key: FastHash + Default,
{ /* private fields */ }

A PGM-Index wrapper with a small hot-key cache.

This struct uses interior mutability (Cell) to update the cache on read operations. Therefore, it is !Sync and cannot be shared across threads without synchronization (e.g., Mutex<Cached>).

Note: When serialized with serde, only the inner index is saved. The cache is recreated empty on deserialization.

Example

use pgm_extra::index::external::Cached;

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

// First lookup - cache miss, populates cache
assert!(index.contains(&keys, &5000));

// Second lookup - cache hit
assert!(index.contains(&keys, &5000));

Implementations

impl<T: Indexable> Cached<T>

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

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

Build a new cached PGM-Index from sorted data.

pub fn from_index(index: Static<T>) -> Self

Wrap an existing index with a cache.

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

Get an approximate position for the given value.

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 height(&self) -> usize

pub fn epsilon(&self) -> usize

pub fn epsilon_recursive(&self) -> usize

pub fn size_in_bytes(&self) -> usize

pub fn clear_cache(&self)

Clear all cached entries.

pub fn inner(&self) -> &Static<T>

Get a reference to the inner index.

pub fn into_inner(self) -> Static<T>

Consume and return the inner index.

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: Debug + Indexable> Debug for Cached<T>

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

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

Formats the value using the given formatter.

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

where T::Key: FastHash + Default + 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 Cached<T>

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

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

where T::Key: FastHash + Default + Serialize + DeserializeOwned,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.