Struct StaticSearchTree 

struct StaticSearchTree<T, const B: usize> {
    values: Vec<SearchBlock<T, B>>,
    len: usize,
    maximum: T,
    levels: Vec<Vec<SearchBlock<T, B>>>,
    backend: SimdBackend,
}

Fields

values: Vec<SearchBlock<T, B>>

len: usize

maximum: T

levels: Vec<Vec<SearchBlock<T, B>>>

backend: SimdBackend

Implementations

impl<T: Copy + Ord, const B: usize> StaticSearchTree<T, B>

fn build<K>( values: &[K], sentinel: T, maximum_encoded: u128, convert: impl Fn(u128) -> T, backend: SimdBackend, ) -> Self

where K: SimdKey,

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 895-901)

    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 descend<F>(&self, value: T, position: F) -> usize

where F: FnMut(&[T; B], T) -> usize,

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 333-335)

    fn lower_bound_scalar(&self, value: T) -> usize {
        self.descend(value, |values, value| {
            values.partition_point(|&current| current < value)
        })
    }

    #[inline(always)]
    fn upper_bound_scalar(&self, value: T) -> usize {
        self.descend(value, |values, value| {
            values.partition_point(|&current| current <= value)
        })
    }

    #[inline(always)]
    fn lower_bound_batch_scalar(&self, values: &[T; 16]) -> [usize; 16] {
        self.descend_batch(values, |values, value| {
            values.partition_point(|&current| current < value)
        })
    }

    #[inline(always)]
    fn upper_bound_batch_scalar(&self, values: &[T; 16]) -> [usize; 16] {
        self.descend_batch(values, |values, value| {
            values.partition_point(|&current| current <= value)
        })
    }
}

macro_rules! impl_static_search_tree {
    (
        $value:ty,
        $branch:expr,
        $first_ge_avx2:ident,
        $first_gt_avx2:ident,
        $first_ge_avx512:ident,
        $first_gt_avx512:ident,
        $avx512_features:literal
    ) => {
        impl StaticSearchTree<$value, $branch> {
            #[inline]
            fn lower_bound(&self, value: $value) -> usize {
                if self.len == 0 || value > self.maximum {
                    return self.len;
                }
                #[cfg(target_arch = "x86_64")]
                return match self.backend {
                    SimdBackend::Scalar => self.lower_bound_scalar(value),
                    // SAFETY: `simd_backend` only selects supported instruction sets. Tests and
                    // standalone benchmarks pass supported backends to the private constructor.
                    SimdBackend::Avx2 => unsafe { self.lower_bound_avx2(value) },
                    // SAFETY: same as above.
                    SimdBackend::Avx512 => unsafe { self.lower_bound_avx512(value) },
                };
                #[cfg(not(target_arch = "x86_64"))]
                self.lower_bound_scalar(value)
            }

            #[inline]
            fn upper_bound(&self, value: $value) -> usize {
                if self.len == 0 {
                    return 0;
                }
                if value >= self.maximum {
                    return self.len;
                }
                #[cfg(target_arch = "x86_64")]
                return match self.backend {
                    SimdBackend::Scalar => self.upper_bound_scalar(value),
                    // SAFETY: `simd_backend` only selects supported instruction sets. Tests and
                    // standalone benchmarks pass supported backends to the private constructor.
                    SimdBackend::Avx2 => unsafe { self.upper_bound_avx2(value) },
                    // SAFETY: same as above.
                    SimdBackend::Avx512 => unsafe { self.upper_bound_avx512(value) },
                };
                #[cfg(not(target_arch = "x86_64"))]
                self.upper_bound_scalar(value)
            }

            #[inline]
            fn contains(&self, value: $value) -> bool {
                let index = self.lower_bound(value);
                index < self.len && self.get(index) == value
            }

            #[inline]
            fn lower_bound_batch(&self, values: &[$value; 16]) -> [usize; 16] {
                #[cfg(target_arch = "x86_64")]
                if self.backend == SimdBackend::Avx512 {
                    // SAFETY: construction selects a supported instruction set.
                    return unsafe { self.lower_bound_batch_avx512(values) };
                }
                bound_batch!(lower, self, values, {
                    #[cfg(target_arch = "x86_64")]
                    let result = if self.backend == SimdBackend::Avx2 {
                        // SAFETY: same as above.
                        unsafe { self.lower_bound_batch_avx2(&values) }
                    } else {
                        self.lower_bound_batch_scalar(&values)
                    };
                    #[cfg(not(target_arch = "x86_64"))]
                    let result = self.lower_bound_batch_scalar(&values);
                    result
                })
            }

            #[inline]
            fn upper_bound_batch(&self, values: &[$value; 16]) -> [usize; 16] {
                #[cfg(target_arch = "x86_64")]
                if self.backend == SimdBackend::Avx512 {
                    // SAFETY: construction selects a supported instruction set.
                    return unsafe { self.upper_bound_batch_avx512(values) };
                }
                bound_batch!(upper, self, values, {
                    #[cfg(target_arch = "x86_64")]
                    let result = if self.backend == SimdBackend::Avx2 {
                        // SAFETY: same as above.
                        unsafe { self.upper_bound_batch_avx2(&values) }
                    } else {
                        self.upper_bound_batch_scalar(&values)
                    };
                    #[cfg(not(target_arch = "x86_64"))]
                    let result = self.upper_bound_batch_scalar(&values);
                    result
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = "avx2")]
            unsafe fn lower_bound_avx2(&self, value: $value) -> usize {
                self.descend(value, |values, value| unsafe {
                    simd::$first_ge_avx2(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = "avx2")]
            unsafe fn upper_bound_avx2(&self, value: $value) -> usize {
                self.descend(value, |values, value| unsafe {
                    simd::$first_gt_avx2(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = "avx2")]
            unsafe fn lower_bound_batch_avx2(&self, values: &[$value; 16]) -> [usize; 16] {
                self.descend_batch(values, |values, value| unsafe {
                    simd::$first_ge_avx2(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = "avx2")]
            unsafe fn upper_bound_batch_avx2(&self, values: &[$value; 16]) -> [usize; 16] {
                self.descend_batch(values, |values, value| unsafe {
                    simd::$first_gt_avx2(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = $avx512_features)]
            unsafe fn lower_bound_avx512(&self, value: $value) -> usize {
                self.descend(value, |values, value| unsafe {
                    simd::$first_ge_avx512(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = $avx512_features)]
            unsafe fn upper_bound_avx512(&self, value: $value) -> usize {
                self.descend(value, |values, value| unsafe {
                    simd::$first_gt_avx512(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = $avx512_features)]
            unsafe fn lower_bound_batch_avx512(&self, values: &[$value; 16]) -> [usize; 16] {
                bound_batch!(
                    lower,
                    self,
                    values,
                    self.descend_batch(&values, |values, value| unsafe {
                        simd::$first_ge_avx512(values, value)
                    })
                )
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = $avx512_features)]
            unsafe fn upper_bound_batch_avx512(&self, values: &[$value; 16]) -> [usize; 16] {
                bound_batch!(
                    upper,
                    self,
                    values,
                    self.descend_batch(&values, |values, value| unsafe {
                        simd::$first_gt_avx512(values, value)
                    })
                )
            }
        }
    };
}

impl_static_search_tree!(
    u16,
    32,
    first_ge_u16x32_avx2,
    first_gt_u16x32_avx2,
    first_ge_u16x32_avx512,
    first_gt_u16x32_avx512,
    "avx512f,avx512bw"
);
impl_static_search_tree!(
    u32,
    16,
    first_ge_u32x16_avx2,
    first_gt_u32x16_avx2,
    first_ge_u32x16_avx512,
    first_gt_u32x16_avx512,
    "avx512f"
);
impl_static_search_tree!(
    u64,
    8,
    first_ge_u64x8_avx2,
    first_gt_u64x8_avx2,
    first_ge_u64x8_avx512,
    first_gt_u64x8_avx512,
    "avx512f"
);

impl StaticSearchTree<u128, 4> {
    #[inline]
    fn lower_bound(&self, value: u128) -> usize {
        if self.len == 0 || value > self.maximum {
            self.len
        } else {
            self.descend(value, |values, value| {
                (values[0] < value) as usize
                    + (values[1] < value) as usize
                    + (values[2] < value) as usize
                    + (values[3] < value) as usize
            })
        }
    }

    #[inline]
    fn upper_bound(&self, value: u128) -> usize {
        if self.len == 0 || value >= self.maximum {
            self.len
        } else {
            self.descend(value, |values, value| {
                (values[0] <= value) as usize
                    + (values[1] <= value) as usize
                    + (values[2] <= value) as usize
                    + (values[3] <= value) as usize
            })
        }
    }

fn get(&self, index: usize) -> T

Examples found in repository

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

    fn contains(&self, value: u128) -> bool {
        let index = self.lower_bound(value);
        index < self.len && self.get(index) == value
    }

fn descend_batch<F>(&self, values: &[T; 16], position: F) -> [usize; 16]

where F: FnMut(&[T; B], T) -> usize,

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 347-349)

    fn lower_bound_batch_scalar(&self, values: &[T; 16]) -> [usize; 16] {
        self.descend_batch(values, |values, value| {
            values.partition_point(|&current| current < value)
        })
    }

    #[inline(always)]
    fn upper_bound_batch_scalar(&self, values: &[T; 16]) -> [usize; 16] {
        self.descend_batch(values, |values, value| {
            values.partition_point(|&current| current <= value)
        })
    }
}

macro_rules! impl_static_search_tree {
    (
        $value:ty,
        $branch:expr,
        $first_ge_avx2:ident,
        $first_gt_avx2:ident,
        $first_ge_avx512:ident,
        $first_gt_avx512:ident,
        $avx512_features:literal
    ) => {
        impl StaticSearchTree<$value, $branch> {
            #[inline]
            fn lower_bound(&self, value: $value) -> usize {
                if self.len == 0 || value > self.maximum {
                    return self.len;
                }
                #[cfg(target_arch = "x86_64")]
                return match self.backend {
                    SimdBackend::Scalar => self.lower_bound_scalar(value),
                    // SAFETY: `simd_backend` only selects supported instruction sets. Tests and
                    // standalone benchmarks pass supported backends to the private constructor.
                    SimdBackend::Avx2 => unsafe { self.lower_bound_avx2(value) },
                    // SAFETY: same as above.
                    SimdBackend::Avx512 => unsafe { self.lower_bound_avx512(value) },
                };
                #[cfg(not(target_arch = "x86_64"))]
                self.lower_bound_scalar(value)
            }

            #[inline]
            fn upper_bound(&self, value: $value) -> usize {
                if self.len == 0 {
                    return 0;
                }
                if value >= self.maximum {
                    return self.len;
                }
                #[cfg(target_arch = "x86_64")]
                return match self.backend {
                    SimdBackend::Scalar => self.upper_bound_scalar(value),
                    // SAFETY: `simd_backend` only selects supported instruction sets. Tests and
                    // standalone benchmarks pass supported backends to the private constructor.
                    SimdBackend::Avx2 => unsafe { self.upper_bound_avx2(value) },
                    // SAFETY: same as above.
                    SimdBackend::Avx512 => unsafe { self.upper_bound_avx512(value) },
                };
                #[cfg(not(target_arch = "x86_64"))]
                self.upper_bound_scalar(value)
            }

            #[inline]
            fn contains(&self, value: $value) -> bool {
                let index = self.lower_bound(value);
                index < self.len && self.get(index) == value
            }

            #[inline]
            fn lower_bound_batch(&self, values: &[$value; 16]) -> [usize; 16] {
                #[cfg(target_arch = "x86_64")]
                if self.backend == SimdBackend::Avx512 {
                    // SAFETY: construction selects a supported instruction set.
                    return unsafe { self.lower_bound_batch_avx512(values) };
                }
                bound_batch!(lower, self, values, {
                    #[cfg(target_arch = "x86_64")]
                    let result = if self.backend == SimdBackend::Avx2 {
                        // SAFETY: same as above.
                        unsafe { self.lower_bound_batch_avx2(&values) }
                    } else {
                        self.lower_bound_batch_scalar(&values)
                    };
                    #[cfg(not(target_arch = "x86_64"))]
                    let result = self.lower_bound_batch_scalar(&values);
                    result
                })
            }

            #[inline]
            fn upper_bound_batch(&self, values: &[$value; 16]) -> [usize; 16] {
                #[cfg(target_arch = "x86_64")]
                if self.backend == SimdBackend::Avx512 {
                    // SAFETY: construction selects a supported instruction set.
                    return unsafe { self.upper_bound_batch_avx512(values) };
                }
                bound_batch!(upper, self, values, {
                    #[cfg(target_arch = "x86_64")]
                    let result = if self.backend == SimdBackend::Avx2 {
                        // SAFETY: same as above.
                        unsafe { self.upper_bound_batch_avx2(&values) }
                    } else {
                        self.upper_bound_batch_scalar(&values)
                    };
                    #[cfg(not(target_arch = "x86_64"))]
                    let result = self.upper_bound_batch_scalar(&values);
                    result
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = "avx2")]
            unsafe fn lower_bound_avx2(&self, value: $value) -> usize {
                self.descend(value, |values, value| unsafe {
                    simd::$first_ge_avx2(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = "avx2")]
            unsafe fn upper_bound_avx2(&self, value: $value) -> usize {
                self.descend(value, |values, value| unsafe {
                    simd::$first_gt_avx2(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = "avx2")]
            unsafe fn lower_bound_batch_avx2(&self, values: &[$value; 16]) -> [usize; 16] {
                self.descend_batch(values, |values, value| unsafe {
                    simd::$first_ge_avx2(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = "avx2")]
            unsafe fn upper_bound_batch_avx2(&self, values: &[$value; 16]) -> [usize; 16] {
                self.descend_batch(values, |values, value| unsafe {
                    simd::$first_gt_avx2(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = $avx512_features)]
            unsafe fn lower_bound_avx512(&self, value: $value) -> usize {
                self.descend(value, |values, value| unsafe {
                    simd::$first_ge_avx512(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = $avx512_features)]
            unsafe fn upper_bound_avx512(&self, value: $value) -> usize {
                self.descend(value, |values, value| unsafe {
                    simd::$first_gt_avx512(values, value)
                })
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = $avx512_features)]
            unsafe fn lower_bound_batch_avx512(&self, values: &[$value; 16]) -> [usize; 16] {
                bound_batch!(
                    lower,
                    self,
                    values,
                    self.descend_batch(&values, |values, value| unsafe {
                        simd::$first_ge_avx512(values, value)
                    })
                )
            }

            #[cfg(target_arch = "x86_64")]
            #[target_feature(enable = $avx512_features)]
            unsafe fn upper_bound_batch_avx512(&self, values: &[$value; 16]) -> [usize; 16] {
                bound_batch!(
                    upper,
                    self,
                    values,
                    self.descend_batch(&values, |values, value| unsafe {
                        simd::$first_gt_avx512(values, value)
                    })
                )
            }
        }
    };
}

impl_static_search_tree!(
    u16,
    32,
    first_ge_u16x32_avx2,
    first_gt_u16x32_avx2,
    first_ge_u16x32_avx512,
    first_gt_u16x32_avx512,
    "avx512f,avx512bw"
);
impl_static_search_tree!(
    u32,
    16,
    first_ge_u32x16_avx2,
    first_gt_u32x16_avx2,
    first_ge_u32x16_avx512,
    first_gt_u32x16_avx512,
    "avx512f"
);
impl_static_search_tree!(
    u64,
    8,
    first_ge_u64x8_avx2,
    first_gt_u64x8_avx2,
    first_ge_u64x8_avx512,
    first_gt_u64x8_avx512,
    "avx512f"
);

impl StaticSearchTree<u128, 4> {
    #[inline]
    fn lower_bound(&self, value: u128) -> usize {
        if self.len == 0 || value > self.maximum {
            self.len
        } else {
            self.descend(value, |values, value| {
                (values[0] < value) as usize
                    + (values[1] < value) as usize
                    + (values[2] < value) as usize
                    + (values[3] < value) as usize
            })
        }
    }

    #[inline]
    fn upper_bound(&self, value: u128) -> usize {
        if self.len == 0 || value >= self.maximum {
            self.len
        } else {
            self.descend(value, |values, value| {
                (values[0] <= value) as usize
                    + (values[1] <= value) as usize
                    + (values[2] <= value) as usize
                    + (values[3] <= value) as usize
            })
        }
    }

    #[inline]
    fn contains(&self, value: u128) -> bool {
        let index = self.lower_bound(value);
        index < self.len && self.get(index) == value
    }

    #[inline]
    fn lower_bound_batch(&self, values: &[u128; 16]) -> [usize; 16] {
        bound_batch!(
            lower,
            self,
            values,
            self.descend_batch(&values, |values, value| {
                (values[0] < value) as usize
                    + (values[1] < value) as usize
                    + (values[2] < value) as usize
                    + (values[3] < value) as usize
            })
        )
    }

    #[inline]
    fn upper_bound_batch(&self, values: &[u128; 16]) -> [usize; 16] {
        bound_batch!(
            upper,
            self,
            values,
            self.descend_batch(&values, |values, value| {
                (values[0] <= value) as usize
                    + (values[1] <= value) as usize
                    + (values[2] <= value) as usize
                    + (values[3] <= value) as usize
            })
        )
    }

fn lower_bound_scalar(&self, value: T) -> usize

fn upper_bound_scalar(&self, value: T) -> usize

fn lower_bound_batch_scalar(&self, values: &[T; 16]) -> [usize; 16]

fn upper_bound_batch_scalar(&self, values: &[T; 16]) -> [usize; 16]

impl StaticSearchTree<u16, 32>

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

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 674-676)

    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: u16) -> usize

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 691-693)

    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: u16) -> bool

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 708-710)

    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(&self, values: &[u16; 16]) -> [usize; 16]

Examples found in repository

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

    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(&self, values: &[u16; 16]) -> [usize; 16]

Examples found in repository

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

    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),
            ),
        }
    }

unsafe fn lower_bound_avx2(&self, value: u16) -> usize

unsafe fn upper_bound_avx2(&self, value: u16) -> usize

unsafe fn lower_bound_batch_avx2(&self, values: &[u16; 16]) -> [usize; 16]

unsafe fn upper_bound_batch_avx2(&self, values: &[u16; 16]) -> [usize; 16]

unsafe fn lower_bound_avx512(&self, value: u16) -> usize

unsafe fn upper_bound_avx512(&self, value: u16) -> usize

unsafe fn lower_bound_batch_avx512(&self, values: &[u16; 16]) -> [usize; 16]

unsafe fn upper_bound_batch_avx512(&self, values: &[u16; 16]) -> [usize; 16]

impl StaticSearchTree<u32, 16>

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

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 677-679)

    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: u32) -> usize

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 694-696)

    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: u32) -> bool

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 711-713)

    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(&self, values: &[u32; 16]) -> [usize; 16]

Examples found in repository

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

    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(&self, values: &[u32; 16]) -> [usize; 16]

Examples found in repository

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

    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),
            ),
        }
    }

unsafe fn lower_bound_avx2(&self, value: u32) -> usize

unsafe fn upper_bound_avx2(&self, value: u32) -> usize

unsafe fn lower_bound_batch_avx2(&self, values: &[u32; 16]) -> [usize; 16]

unsafe fn upper_bound_batch_avx2(&self, values: &[u32; 16]) -> [usize; 16]

unsafe fn lower_bound_avx512(&self, value: u32) -> usize

unsafe fn upper_bound_avx512(&self, value: u32) -> usize

unsafe fn lower_bound_batch_avx512(&self, values: &[u32; 16]) -> [usize; 16]

unsafe fn upper_bound_batch_avx512(&self, values: &[u32; 16]) -> [usize; 16]

impl StaticSearchTree<u64, 8>

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

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 680-682)

    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: u64) -> usize

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 697-699)

    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: u64) -> bool

Examples found in repository

crates/competitive/src/data_structure/static_search.rs (lines 714-716)

    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(&self, values: &[u64; 16]) -> [usize; 16]

Examples found in repository

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

    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(&self, values: &[u64; 16]) -> [usize; 16]

Examples found in repository

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

    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),
            ),
        }
    }

unsafe fn lower_bound_avx2(&self, value: u64) -> usize

unsafe fn upper_bound_avx2(&self, value: u64) -> usize

unsafe fn lower_bound_batch_avx2(&self, values: &[u64; 16]) -> [usize; 16]

unsafe fn upper_bound_batch_avx2(&self, values: &[u64; 16]) -> [usize; 16]

unsafe fn lower_bound_avx512(&self, value: u64) -> usize

unsafe fn upper_bound_avx512(&self, value: u64) -> usize

unsafe fn lower_bound_batch_avx512(&self, values: &[u64; 16]) -> [usize; 16]

unsafe fn upper_bound_batch_avx512(&self, values: &[u64; 16]) -> [usize; 16]

impl StaticSearchTree<u128, 4>

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

Examples found in repository

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

    fn contains(&self, value: u128) -> bool {
        let index = self.lower_bound(value);
        index < self.len && self.get(index) == value
    }

    #[inline]
    fn lower_bound_batch(&self, values: &[u128; 16]) -> [usize; 16] {
        bound_batch!(
            lower,
            self,
            values,
            self.descend_batch(&values, |values, value| {
                (values[0] < value) as usize
                    + (values[1] < value) as usize
                    + (values[2] < value) as usize
                    + (values[3] < value) as usize
            })
        )
    }

    #[inline]
    fn upper_bound_batch(&self, values: &[u128; 16]) -> [usize; 16] {
        bound_batch!(
            upper,
            self,
            values,
            self.descend_batch(&values, |values, value| {
                (values[0] <= value) as usize
                    + (values[1] <= value) as usize
                    + (values[2] <= value) as usize
                    + (values[3] <= value) as usize
            })
        )
    }
}

fn search_batch<K, T>(
    values: &[K],
    output: &mut [usize],
    convert: impl Fn(u128) -> T,
    single: impl Fn(T) -> usize,
    batch: impl Fn(&[T; 16]) -> [usize; 16],
) where
    K: SimdKey,
    T: Copy,
{
    let mut offset = 0;
    while offset + 16 <= values.len() {
        let values = std::array::from_fn(|index| convert(values[offset + index].encode()));
        output[offset..offset + 16].copy_from_slice(&batch(&values));
        offset += 16;
    }
    let remaining = values.len() - offset;
    if remaining >= 8 {
        let mut encoded = [convert(values[offset].encode()); 16];
        for index in 1..remaining {
            encoded[index] = convert(values[offset + index].encode());
        }
        let positions = batch(&encoded);
        output[offset..].copy_from_slice(&positions[..remaining]);
    } else {
        for (&value, position) in values[offset..].iter().zip(&mut output[offset..]) {
            *position = single(convert(value.encode()));
        }
    }
}

#[derive(Clone, Debug)]
enum StaticSearchStorage {
    Direct(DirectStaticSearch),
    U16(StaticSearchTree<u16, 32>),
    U32(StaticSearchTree<u32, 16>),
    U64(StaticSearchTree<u64, 8>),
    U128(StaticSearchTree<u128, 4>),
}

impl StaticSearchStorage {
    #[inline(always)]
    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 700)

    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 717)

    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(&self, values: &[u128; 16]) -> [usize; 16]

Examples found in repository

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

    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(&self, values: &[u128; 16]) -> [usize; 16]

Examples found in repository

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

    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),
            ),
        }
    }

Trait Implementations

impl<T: Clone, const B: usize> Clone for StaticSearchTree<T, B>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug, const B: usize> Debug for StaticSearchTree<T, B>

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

Formats the value using the given formatter.