Skip to main content

search_batch

competitive::data_structure::static_search

Function search_batch 

Source 
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,
Examples found in repository?
crates/competitive/src/data_structure/static_search.rs (lines 728-734)
721    fn lower_bound_batch<K: SimdKey>(&self, values: &[K], output: &mut [usize]) {
722        match self {
723            Self::Direct(search) => {
724                for (&value, position) in values.iter().zip(output) {
725                    *position = search.lower_bound(value.encode());
726                }
727            }
728            Self::U16(search) => search_batch(
729                values,
730                output,
731                |value| u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
732                |value| search.lower_bound(value),
733                |values| search.lower_bound_batch(values),
734            ),
735            Self::U32(search) => search_batch(
736                values,
737                output,
738                |value| u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
739                |value| search.lower_bound(value),
740                |values| search.lower_bound_batch(values),
741            ),
742            Self::U64(search) => search_batch(
743                values,
744                output,
745                |value| u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
746                |value| search.lower_bound(value),
747                |values| search.lower_bound_batch(values),
748            ),
749            Self::U128(search) => search_batch(
750                values,
751                output,
752                |value| value,
753                |value| search.lower_bound(value),
754                |values| search.lower_bound_batch(values),
755            ),
756        }
757    }
758
759    fn upper_bound_batch<K: SimdKey>(&self, values: &[K], output: &mut [usize]) {
760        match self {
761            Self::Direct(search) => {
762                for (&value, position) in values.iter().zip(output) {
763                    *position = search.upper_bound(value.encode());
764                }
765            }
766            Self::U16(search) => search_batch(
767                values,
768                output,
769                |value| u16::try_from(value).expect("SimdKey::encode exceeds its declared width"),
770                |value| search.upper_bound(value),
771                |values| search.upper_bound_batch(values),
772            ),
773            Self::U32(search) => search_batch(
774                values,
775                output,
776                |value| u32::try_from(value).expect("SimdKey::encode exceeds its declared width"),
777                |value| search.upper_bound(value),
778                |values| search.upper_bound_batch(values),
779            ),
780            Self::U64(search) => search_batch(
781                values,
782                output,
783                |value| u64::try_from(value).expect("SimdKey::encode exceeds its declared width"),
784                |value| search.upper_bound(value),
785                |values| search.upper_bound_batch(values),
786            ),
787            Self::U128(search) => search_batch(
788                values,
789                output,
790                |value| value,
791                |value| search.upper_bound(value),
792                |values| search.upper_bound_batch(values),
793            ),
794        }
795    }