Struct BinarySearchRLE 

pub struct BinarySearchRLE<T: Clone + Eq, S = usize> { /* private fields */ }

An ordered sequence of runs, searchable in O(lg(n)) time via binary search.

Implementations

impl<T: Clone + Eq, S: Copy + PartialEq + PartialOrd> BinarySearchRLE<T, S>

pub fn new() -> Self

Create a new, empty BinarySearchRLE.

pub fn append_run(&mut self, run: IndexedRLE<T, S>) -> bool

Appends the provided run to the sequence.

Returns true if the run was added to the end of the internal list, and returns false if it was instead merged into the last run.

Runs are expected to be inserted in ascending sorted order; this does no sorting.

pub fn append_token(&mut self, token: T, start: S) -> bool

Appends an individual token to the sequence as its own run.

Returns true if the token was added to the end of the internal list as its own run, and returns false if it was instead merged into the last run.

Tokens are expected to be inserted in ascending sorted order; this does no sorting.

pub fn find_token_at_index(&self, index: S) -> Option<T>

Search for the token value at a particular index in the sequence.

Returns None if:

• The sequence is empty (there are no runs)
• The sequence index requested is before the start of the first run

Otherwise, this returns the token value for the run that contains the requested index.

pub fn num_runs(&self) -> usize

Returns the total number of runs contained in the sequence.

pub fn memory_size(&self) -> usize

The amount of memory it takes to store this data.