slice_find/
lib.rs

1#![cfg_attr(not(test), no_std)]
2
3#![forbid(unsafe_code)]
4
5extern crate alloc;
6pub(crate) use alloc::vec::Vec;
7pub(crate) use alloc::collections::BTreeMap;
8
9pub mod kmp;
10pub mod raita;
11pub mod simple;
12
13#[cfg(test)]
14mod test;
15
16#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
17pub enum Algorithm {
18    KMP,
19    Raita,
20    Simple,
21}
22
23impl Algorithm {
24    pub fn slice_find<T: PartialEq + Ord>(&self, haystack: &[T], needle: &[T]) -> Option<usize> {
25        match self {
26            Self::KMP => kmp::slice_find(haystack, needle),
27            Self::Raita => raita::slice_find(haystack, needle),
28            Self::Simple => simple::slice_find(haystack, needle),
29        }
30    }
31    pub fn slice_contains<T: PartialEq + Ord>(&self, haystack: &[T], needle: &[T]) -> bool {
32        self.slice_find(haystack, needle).is_some()
33    }
34}
35
36pub fn slice_find<T: PartialEq + Ord>(algo: Algorithm, haystack: &[T], needle: &[T]) -> Option<usize> {
37    algo.slice_find(haystack, needle)
38}
39pub fn slice_contains<T: PartialEq + Ord>(algo: Algorithm, haystack: &[T], needle: &[T]) -> bool {
40    algo.slice_contains(haystack, needle)
41}
42
43pub trait SliceFind<T: PartialEq>: AsRef<[T]> {
44    fn find(&self, needle: impl AsRef<[T]>) -> Option<usize> {
45        kmp::slice_find(self.as_ref(), needle.as_ref())
46    }
47    fn contains(&self, needle: impl AsRef<[T]>) -> bool {
48        self.find(needle).is_some()
49    }
50}
51impl<T: PartialEq> SliceFind<T> for Vec<T> {}
52impl<T: PartialEq> SliceFind<T> for [T] {}
53impl<T: PartialEq, const N: usize> SliceFind<T> for [T; N] {}
54
55pub trait SliceReplace<T: PartialEq + Clone>: SliceFind<T> {
56    fn replace(&self, old: impl AsRef<[T]>, new: impl AsRef<[T]>) -> Vec<T> {
57        let mut this = self.as_ref().to_vec();
58        let old = old.as_ref();
59        let new = new.as_ref();
60
61        if old == new {
62            return this;
63        }
64
65        let old_len = old.len();
66        let new_len = new.len();
67
68        let mut part = &mut this[..];
69        let mut maybe_pos = part.find(old);
70        while let Some(pos) = maybe_pos {
71            if new_len == old_len {
72                part[pos .. pos+new_len].clone_from_slice(new);
73                part = &mut part[pos+new_len ..];
74            } else {
75                let prefix = &part[..pos];
76                let suffix = &part[pos+old_len ..];
77                this = prefix.iter().chain(new.iter()).chain(suffix).cloned().collect();
78                part = &mut this[pos+new_len ..];
79            }
80
81            maybe_pos = part.find(old);
82        }
83
84        this
85    }
86
87}
88
89impl<T: PartialEq+Clone> SliceReplace<T> for Vec<T> {}
90impl<T: PartialEq+Clone> SliceReplace<T> for [T] {}
91impl<T: PartialEq+Clone, const N: usize> SliceReplace<T> for [T; N] {}
92
slice_find/lib.rs

slice_find/
lib.rs
