Enum DirectStaticSearch 

enum DirectStaticSearch {
    U16(Vec<u16>),
    U32(Vec<u32>),
}

Variants

U16(Vec<u16>)

U32(Vec<u32>)

Implementations

impl DirectStaticSearch

fn build<K: SimdKey>(values: &[K], bits: u32) -> Self

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (line 890)

    fn build(values: &[K], backend: SimdBackend, direct: bool) -> Self {
        assert!(matches!(K::BITS, 8 | 16 | 32 | 64 | 128));
        assert!(values.windows(2).all(|pair| pair[0] <= pair[1]));
        let len = values.len();
        let storage = match K::BITS {
            8 => StaticSearchStorage::Direct(DirectStaticSearch::build(values, K::BITS)),
            16 => {
                if direct {
                    StaticSearchStorage::Direct(DirectStaticSearch::build(values, K::BITS))
                } else {
                    StaticSearchStorage::U16(StaticSearchTree::build(
                        values,
                        u16::MAX,
                        u16::MAX as u128,
                        |value| value as u16,
                        backend,
                    ))
                }
            }
            32 => StaticSearchStorage::U32(StaticSearchTree::build(
                values,
                u32::MAX,
                u32::MAX as u128,
                |value| value as u32,
                backend,
            )),
            64 => StaticSearchStorage::U64(StaticSearchTree::build(
                values,
                u64::MAX,
                u64::MAX as u128,
                |value| value as u64,
                backend,
            )),
            128 => StaticSearchStorage::U128(StaticSearchTree::build(
                values,
                u128::MAX,
                u128::MAX,
                |value| value,
                backend,
            )),
            _ => unreachable!(),
        };
        Self {
            storage,
            len,
            marker: PhantomData,
        }
    }

fn lower_bound(&self, value: u128) -> usize

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (line 673)

    fn lower_bound(&self, value: u128) -> usize {
        match self {
            Self::Direct(search) => search.lower_bound(value),
            Self::U16(search) => search.lower_bound(
                u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U32(search) => search.lower_bound(
                u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U64(search) => search.lower_bound(
                u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U128(search) => search.lower_bound(value),
        }
    }

    #[inline(always)]
    fn upper_bound(&self, value: u128) -> usize {
        match self {
            Self::Direct(search) => search.upper_bound(value),
            Self::U16(search) => search.upper_bound(
                u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U32(search) => search.upper_bound(
                u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U64(search) => search.upper_bound(
                u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U128(search) => search.upper_bound(value),
        }
    }

    #[inline(always)]
    fn contains(&self, value: u128) -> bool {
        match self {
            Self::Direct(search) => search.contains(value),
            Self::U16(search) => search.contains(
                u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U32(search) => search.contains(
                u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U64(search) => search.contains(
                u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U128(search) => search.contains(value),
        }
    }

    fn lower_bound_batch<K: SimdKey>(&self, values: &[K], output: &mut [usize]) {
        match self {
            Self::Direct(search) => {
                for (&value, position) in values.iter().zip(output) {
                    *position = search.lower_bound(value.encode());
                }
            }
            Self::U16(search) => search_batch(
                values,
                output,
                |value| u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
                |value| search.lower_bound(value),
                |values| search.lower_bound_batch(values),
            ),
            Self::U32(search) => search_batch(
                values,
                output,
                |value| u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
                |value| search.lower_bound(value),
                |values| search.lower_bound_batch(values),
            ),
            Self::U64(search) => search_batch(
                values,
                output,
                |value| u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
                |value| search.lower_bound(value),
                |values| search.lower_bound_batch(values),
            ),
            Self::U128(search) => search_batch(
                values,
                output,
                |value| value,
                |value| search.lower_bound(value),
                |values| search.lower_bound_batch(values),
            ),
        }
    }

fn upper_bound(&self, value: u128) -> usize

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (line 690)

    fn upper_bound(&self, value: u128) -> usize {
        match self {
            Self::Direct(search) => search.upper_bound(value),
            Self::U16(search) => search.upper_bound(
                u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U32(search) => search.upper_bound(
                u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U64(search) => search.upper_bound(
                u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U128(search) => search.upper_bound(value),
        }
    }

    #[inline(always)]
    fn contains(&self, value: u128) -> bool {
        match self {
            Self::Direct(search) => search.contains(value),
            Self::U16(search) => search.contains(
                u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U32(search) => search.contains(
                u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U64(search) => search.contains(
                u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U128(search) => search.contains(value),
        }
    }

    fn lower_bound_batch<K: SimdKey>(&self, values: &[K], output: &mut [usize]) {
        match self {
            Self::Direct(search) => {
                for (&value, position) in values.iter().zip(output) {
                    *position = search.lower_bound(value.encode());
                }
            }
            Self::U16(search) => search_batch(
                values,
                output,
                |value| u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
                |value| search.lower_bound(value),
                |values| search.lower_bound_batch(values),
            ),
            Self::U32(search) => search_batch(
                values,
                output,
                |value| u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
                |value| search.lower_bound(value),
                |values| search.lower_bound_batch(values),
            ),
            Self::U64(search) => search_batch(
                values,
                output,
                |value| u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
                |value| search.lower_bound(value),
                |values| search.lower_bound_batch(values),
            ),
            Self::U128(search) => search_batch(
                values,
                output,
                |value| value,
                |value| search.lower_bound(value),
                |values| search.lower_bound_batch(values),
            ),
        }
    }

    fn upper_bound_batch<K: SimdKey>(&self, values: &[K], output: &mut [usize]) {
        match self {
            Self::Direct(search) => {
                for (&value, position) in values.iter().zip(output) {
                    *position = search.upper_bound(value.encode());
                }
            }
            Self::U16(search) => search_batch(
                values,
                output,
                |value| u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
                |value| search.upper_bound(value),
                |values| search.upper_bound_batch(values),
            ),
            Self::U32(search) => search_batch(
                values,
                output,
                |value| u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
                |value| search.upper_bound(value),
                |values| search.upper_bound_batch(values),
            ),
            Self::U64(search) => search_batch(
                values,
                output,
                |value| u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
                |value| search.upper_bound(value),
                |values| search.upper_bound_batch(values),
            ),
            Self::U128(search) => search_batch(
                values,
                output,
                |value| value,
                |value| search.upper_bound(value),
                |values| search.upper_bound_batch(values),
            ),
        }
    }

fn contains(&self, value: u128) -> bool

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (line 707)

    fn contains(&self, value: u128) -> bool {
        match self {
            Self::Direct(search) => search.contains(value),
            Self::U16(search) => search.contains(
                u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U32(search) => search.contains(
                u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U64(search) => search.contains(
                u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
            ),
            Self::U128(search) => search.contains(value),
        }
    }

Trait Implementations

impl Clone for DirectStaticSearch

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DirectStaticSearch

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

Formats the value using the given formatter.