pub trait Search {
fn search<'a, P: SearchIn<'a>>(&'a self, needle: P) -> Option<usize>;
fn rsearch<'a, P: SearchIn<'a>>(&'a self, needle: P) -> Option<usize>;
fn search_indices<'a, P: SearchIn<'a>>(&'a self, needle: P) -> SearchIndices<'a, P>;
fn rsearch_indices<'a, P: SearchIn<'a>>(&'a self, needle: P) -> RevSearchIndices<'a, P>;
fn includes<'a, P: SearchIn<'a>>(&'a self, needle: P) -> bool;
}
impl<'c> Search for &'c str {
#[inline]
fn search<'a, P: SearchIn<'a>>(&'a self, needle: P) -> Option<usize> {
needle.search_in(self)
}
#[inline]
fn rsearch<'a, P: SearchIn<'a>>(&'a self, needle: P) -> Option<usize> {
needle.rsearch_in(self)
}
#[inline]
fn search_indices<'a, P: SearchIn<'a>>(&'a self, needle: P) -> SearchIndices<'a, P> {
SearchIndices::new(self, needle)
}
#[inline]
fn rsearch_indices<'a, P: SearchIn<'a>>(&'a self, needle: P) -> RevSearchIndices<'a, P> {
RevSearchIndices::new(self, needle)
}
#[inline]
fn includes<'a, P: SearchIn<'a>>(&'a self, needle: P) -> bool {
needle.includes_in(self)
}
}
impl<'c> Search for String {
#[inline]
fn search<'a, P: SearchIn<'a>>(&'a self, needle: P) -> Option<usize> {
needle.search_in(self.as_str())
}
#[inline]
fn rsearch<'a, P: SearchIn<'a>>(&'a self, needle: P) -> Option<usize> {
needle.rsearch_in(self.as_str())
}
#[inline]
fn search_indices<'a, P: SearchIn<'a>>(&'a self, needle: P) -> SearchIndices<'a, P> {
SearchIndices::new(self.as_str(), needle)
}
#[inline]
fn rsearch_indices<'a, P: SearchIn<'a>>(&'a self, needle: P) -> RevSearchIndices<'a, P> {
RevSearchIndices::new(self.as_str(), needle)
}
#[inline]
fn includes<'a, P: SearchIn<'a>>(&'a self, needle: P) -> bool {
needle.includes_in(self)
}
}
pub trait SearchBytes {
fn search_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> Option<usize>;
fn rsearch_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> Option<usize>;
fn search_indices_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> SearchIndicesBytes<'a, P>;
fn rsearch_indices_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> RevSearchIndicesBytes<'a, P>;
fn includes_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> bool;
}
impl<'c> SearchBytes for &'c [u8] {
#[inline]
fn search_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> Option<usize> {
needle.search_in(self)
}
#[inline]
fn rsearch_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> Option<usize> {
needle.rsearch_in(self)
}
#[inline]
fn search_indices_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> SearchIndicesBytes<'a, P> {
SearchIndicesBytes::new(self, needle)
}
#[inline]
fn rsearch_indices_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> RevSearchIndicesBytes<'a, P> {
RevSearchIndicesBytes::new(self, needle)
}
#[inline]
fn includes_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> bool {
needle.includes_in(self)
}
}
impl<'c> SearchBytes for &'c str {
#[inline]
fn search_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> Option<usize> {
needle.search_in(self.as_bytes())
}
#[inline]
fn rsearch_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> Option<usize> {
needle.rsearch_in(self.as_bytes())
}
#[inline]
fn search_indices_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> SearchIndicesBytes<'a, P> {
SearchIndicesBytes::new(self.as_bytes(), needle)
}
#[inline]
fn rsearch_indices_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> RevSearchIndicesBytes<'a, P> {
RevSearchIndicesBytes::new(self.as_bytes(), needle)
}
#[inline]
fn includes_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> bool {
needle.includes_in(self.as_bytes())
}
}
impl<'c> SearchBytes for String {
#[inline]
fn search_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> Option<usize> {
needle.search_in(self.as_bytes())
}
#[inline]
fn rsearch_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> Option<usize> {
needle.rsearch_in(self.as_bytes())
}
#[inline]
fn search_indices_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> SearchIndicesBytes<'a, P> {
SearchIndicesBytes::new(self.as_bytes(), needle)
}
#[inline]
fn rsearch_indices_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> RevSearchIndicesBytes<'a, P> {
RevSearchIndicesBytes::new(self.as_bytes(), needle)
}
#[inline]
fn includes_bytes<'a, P: SearchInBytes<'a>>(&'a self, needle: P) -> bool {
needle.includes_in(self.as_bytes())
}
}
pub struct SearchIndices<'a, P: SearchIn<'a>> {
curr_idx: usize,
haystack: &'a str,
needle: P,
}
impl<'a, P: SearchIn<'a>> SearchIndices<'a, P> {
fn new(a_haystack: &'a str, a_needle: P) -> SearchIndices<'a, P> {
SearchIndices {
curr_idx: 0,
haystack: a_haystack,
needle: a_needle,
}
}
}
impl<'a, P: SearchIn<'a>> Iterator for SearchIndices<'a, P> {
type Item = (usize, &'a str);
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
match self.needle.search_in(&self.haystack[self.curr_idx..]) {
Some(idx) => {
self.curr_idx += idx;
let st = self.curr_idx;
let ed = st + self.needle.len();
self.curr_idx = ed;
Some((st, &self.haystack[st..ed]))
}
None => None,
}
}
}
pub struct SearchIndicesBytes<'a, P: SearchInBytes<'a>> {
curr_idx: usize,
haystack: &'a [u8],
needle: P,
}
impl<'a, P: SearchInBytes<'a>> SearchIndicesBytes<'a, P> {
fn new(a_haystack: &'a [u8], a_needle: P) -> SearchIndicesBytes<'a, P> {
SearchIndicesBytes {
curr_idx: 0,
haystack: a_haystack,
needle: a_needle,
}
}
}
impl<'a, P: SearchInBytes<'a>> Iterator for SearchIndicesBytes<'a, P> {
type Item = (usize, &'a [u8]);
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
match self.needle.search_in(&self.haystack[self.curr_idx..]) {
Some(idx) => {
self.curr_idx += idx;
let st = self.curr_idx;
let ed = st + self.needle.len();
self.curr_idx = ed;
Some((st, &self.haystack[st..ed]))
}
None => None,
}
}
}
pub struct RevSearchIndices<'a, P: SearchIn<'a>> {
curr_ed: usize,
haystack: &'a str,
needle: P,
}
impl<'a, P: SearchIn<'a>> RevSearchIndices<'a, P> {
fn new(a_haystack: &'a str, a_needle: P) -> RevSearchIndices<'a, P> {
RevSearchIndices {
curr_ed: a_haystack.len(),
haystack: a_haystack,
needle: a_needle,
}
}
}
impl<'a, P: SearchIn<'a>> Iterator for RevSearchIndices<'a, P> {
type Item = (usize, &'a str);
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
match self.needle.rsearch_in(&self.haystack[0..self.curr_ed]) {
Some(idx) => {
let st = idx;
let ed = st + self.needle.len();
self.curr_ed = st;
Some((st, &self.haystack[st..ed]))
}
None => None,
}
}
}
pub struct RevSearchIndicesBytes<'a, P: SearchInBytes<'a>> {
curr_ed: usize,
haystack: &'a [u8],
needle: P,
}
impl<'a, P: SearchInBytes<'a>> RevSearchIndicesBytes<'a, P> {
fn new(a_haystack: &'a [u8], a_needle: P) -> RevSearchIndicesBytes<'a, P> {
RevSearchIndicesBytes {
curr_ed: a_haystack.len(),
haystack: a_haystack,
needle: a_needle,
}
}
}
impl<'a, P: SearchInBytes<'a>> Iterator for RevSearchIndicesBytes<'a, P> {
type Item = (usize, &'a [u8]);
#[inline(always)]
fn next(&mut self) -> Option<Self::Item> {
match self.needle.rsearch_in(&self.haystack[0..self.curr_ed]) {
Some(idx) => {
let st = idx;
let ed = st + self.needle.len();
self.curr_ed = st;
Some((st, &self.haystack[st..ed]))
}
None => None,
}
}
}
pub trait SearchIn<'a>: Sized {
fn search_in(&self, haystack: &'a str) -> Option<usize>;
fn rsearch_in(&self, haystack: &'a str) -> Option<usize>;
fn len(&self) -> usize;
fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
fn includes_in(&self, haystack: &'a str) -> bool {
self.search_in(haystack).is_some()
}
}
impl<'a, 'b> SearchIn<'a> for &'b str {
#[inline]
fn search_in(&self, haystack: &'a str) -> Option<usize> {
naive_opt_mc_last(haystack, self)
}
#[inline]
fn rsearch_in(&self, haystack: &'a str) -> Option<usize> {
naive_opt_mc_last_rev(haystack, self)
}
#[inline]
fn len(&self) -> usize {
self.as_bytes().len()
}
}
impl<'a, 'b> SearchIn<'a> for &'b String {
#[inline]
fn search_in(&self, haystack: &'a str) -> Option<usize> {
naive_opt_mc_last(haystack, self.as_str())
}
#[inline]
fn rsearch_in(&self, haystack: &'a str) -> Option<usize> {
naive_opt_mc_last_rev(haystack, self.as_str())
}
#[inline]
fn len(&self) -> usize {
self.as_str().len()
}
}
impl<'a, 'b> SearchIn<'a> for char {
#[inline]
fn search_in(&self, haystack: &'a str) -> Option<usize> {
naive_opt_mc_last(haystack, self.to_string().as_str())
}
#[inline]
fn rsearch_in(&self, haystack: &'a str) -> Option<usize> {
naive_opt_mc_last_rev(haystack, self.to_string().as_str())
}
#[inline]
fn len(&self) -> usize {
self.to_string().as_bytes().len()
}
}
pub trait SearchInBytes<'a>: Sized {
fn search_in(&self, haystack: &'a [u8]) -> Option<usize>;
fn rsearch_in(&self, haystack: &'a [u8]) -> Option<usize>;
fn len(&self) -> usize;
fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
fn includes_in(&self, haystack: &'a [u8]) -> bool {
self.search_in(haystack).is_some()
}
}
impl<'a, 'b> SearchInBytes<'a> for &'b [u8] {
#[inline]
fn search_in(&self, haystack: &'a [u8]) -> Option<usize> {
naive_opt_mc_last_bytes(haystack, self)
}
#[inline]
fn rsearch_in(&self, haystack: &'a [u8]) -> Option<usize> {
naive_opt_mc_last_rev_bytes(haystack, self)
}
#[inline]
fn len(&self) -> usize {
u8_len(self)
}
}
#[inline(always)]
fn u8_len(a: &[u8]) -> usize {
a.len()
}
impl<'a, 'b> SearchInBytes<'a> for &'b str {
#[inline]
fn search_in(&self, haystack: &'a [u8]) -> Option<usize> {
naive_opt_mc_last_bytes(haystack, self.as_bytes())
}
#[inline]
fn rsearch_in(&self, haystack: &'a [u8]) -> Option<usize> {
naive_opt_mc_last_rev_bytes(haystack, self.as_bytes())
}
#[inline]
fn len(&self) -> usize {
self.as_bytes().len()
}
}
impl<'a, 'b> SearchInBytes<'a> for &'b String {
#[inline]
fn search_in(&self, haystack: &'a [u8]) -> Option<usize> {
naive_opt_mc_last_bytes(haystack, self.as_bytes())
}
#[inline]
fn rsearch_in(&self, haystack: &'a [u8]) -> Option<usize> {
naive_opt_mc_last_rev_bytes(haystack, self.as_bytes())
}
#[inline]
fn len(&self) -> usize {
self.as_str().len()
}
}
impl<'a, 'b> SearchInBytes<'a> for char {
#[inline]
fn search_in(&self, haystack: &'a [u8]) -> Option<usize> {
naive_opt_mc_last_bytes(haystack, self.to_string().as_bytes())
}
#[inline]
fn rsearch_in(&self, haystack: &'a [u8]) -> Option<usize> {
naive_opt_mc_last_rev_bytes(haystack, self.to_string().as_bytes())
}
#[inline]
fn len(&self) -> usize {
self.to_string().as_bytes().len()
}
}
pub fn string_search(haystack: &str, needle: &str) -> Option<usize> {
naive_opt_mc_last(haystack, needle)
}
pub fn string_rsearch(haystack: &str, needle: &str) -> Option<usize> {
naive_opt_mc_last_rev(haystack, needle)
}
pub fn string_search_bytes(haystack: &[u8], needle: &[u8]) -> Option<usize> {
naive_opt_mc_last_bytes(haystack, needle)
}
pub fn string_rsearch_bytes(haystack: &[u8], needle: &[u8]) -> Option<usize> {
naive_opt_mc_last_rev_bytes(haystack, needle)
}
pub fn string_search_indices<'a, P: SearchIn<'a>>(
haystack: &'a str,
needle: P,
) -> SearchIndices<'a, P> {
SearchIndices::new(haystack, needle)
}
pub fn string_search_indices_bytes<'a, P: SearchInBytes<'a>>(
haystack: &'a [u8],
needle: P,
) -> SearchIndicesBytes<'a, P> {
SearchIndicesBytes::new(haystack, needle)
}
pub fn string_rsearch_indices<'a, P: SearchIn<'a>>(
haystack: &'a str,
needle: P,
) -> RevSearchIndices<'a, P> {
RevSearchIndices::new(haystack, needle)
}
pub fn string_rsearch_indices_bytes<'a, P: SearchInBytes<'a>>(
haystack: &'a [u8],
needle: P,
) -> RevSearchIndicesBytes<'a, P> {
RevSearchIndicesBytes::new(haystack, needle)
}
#[inline(always)]
fn naive_opt_mc_last(haystack: &str, needle: &str) -> Option<usize> {
naive_opt_mc_last_bytes(haystack.as_bytes(), needle.as_bytes())
}
#[inline(always)]
fn naive_opt_mc_last_bytes(hay_bytes: &[u8], nee_bytes: &[u8]) -> Option<usize> {
let hay_len = hay_bytes.len();
let nee_len = nee_bytes.len();
if nee_len == 0 {
return Some(0);
}
let last_idx = nee_len - 1;
let last_byte = nee_bytes[last_idx];
if hay_len <= last_idx {
return None;
}
for m in my_memchr_iter(last_byte, &hay_bytes[last_idx..]) {
let st = m;
let ed = st + nee_len;
if ed > hay_len {
break;
}
if nee_bytes == &hay_bytes[st..ed] {
return Some(st);
}
}
None
}
#[inline(always)]
fn naive_opt_mc_last_rev(haystack: &str, needle: &str) -> Option<usize> {
naive_opt_mc_last_rev_bytes(haystack.as_bytes(), needle.as_bytes())
}
#[inline(always)]
fn naive_opt_mc_last_rev_bytes(hay_bytes: &[u8], nee_bytes: &[u8]) -> Option<usize> {
let hay_len = hay_bytes.len();
let nee_len = nee_bytes.len();
if nee_len == 0 {
return Some(hay_len);
}
let last_idx = nee_len - 1;
let last_byte = nee_bytes[last_idx];
if hay_len <= last_idx {
return None;
}
for m in my_memrchr_iter(last_byte, &hay_bytes[last_idx..]) {
let st = m;
let ed = st + nee_len;
if ed > hay_len {
break;
}
if nee_bytes == &hay_bytes[st..ed] {
return Some(st);
}
}
None
}
#[cfg(target_arch = "x86_64")]
#[inline(always)]
fn my_memchr_iter(needle: u8, haystack: &[u8]) -> memchr::Memchr {
memchr::memchr_iter(needle, haystack)
}
#[cfg(target_arch = "x86_64")]
#[inline(always)]
fn my_memrchr_iter(needle: u8, haystack: &[u8]) -> core::iter::Rev<memchr::Memchr> {
memchr::memrchr_iter(needle, haystack)
}
#[cfg(not(target_arch = "x86_64"))]
#[inline(always)]
fn my_memchr_iter(needle: u8, haystack: &[u8]) -> iter::Memchr {
iter::memchr_iter(needle, haystack)
}
#[cfg(not(target_arch = "x86_64"))]
#[inline(always)]
fn my_memrchr_iter(needle: u8, haystack: &[u8]) -> core::iter::Rev<iter::Memchr> {
iter::memrchr_iter(needle, haystack)
}
#[cfg(not(target_arch = "x86_64"))]
mod iter {
#[inline]
pub fn memchr_iter(needle: u8, haystack: &[u8]) -> Memchr {
Memchr::new(needle, haystack)
}
#[inline]
pub fn memrchr_iter(needle: u8, haystack: &[u8]) -> core::iter::Rev<Memchr> {
Memchr::new(needle, haystack).rev()
}
pub struct Memchr<'a> {
needle: u8,
haystack: &'a [u8],
position: usize,
}
impl<'a> Memchr<'a> {
#[inline]
pub fn new(needle: u8, haystack: &[u8]) -> Memchr {
Memchr {
needle: needle,
haystack: haystack,
position: 0,
}
}
}
impl<'a> Iterator for Memchr<'a> {
type Item = usize;
#[inline]
fn next(&mut self) -> Option<usize> {
memchr(self.needle, self.haystack).map(move |idx| {
self.haystack = self.haystack.split_at(idx + 1).1;
let found = self.position + idx;
self.position = found + 1;
found
})
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(self.haystack.len()))
}
}
impl<'a> DoubleEndedIterator for Memchr<'a> {
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
memrchr(self.needle, self.haystack).map(move |idx| {
self.haystack = self.haystack.split_at(idx).0;
self.position + idx
})
}
}
fn memchr(n1: u8, haystack: &[u8]) -> Option<usize> {
let haystack_len = haystack.len();
let haystack = haystack.as_ptr() as *const libc::c_void;
let n1 = n1 as i32;
unsafe {
let p = libc::memchr(haystack, n1, haystack_len);
if p.is_null() {
None
} else {
Some(p as usize - haystack as usize)
}
}
}
fn memrchr(n1: u8, haystack: &[u8]) -> Option<usize> {
let haystack_len = haystack.len();
let haystack = haystack.as_ptr() as *const libc::c_void;
let n1 = n1 as i32;
unsafe {
let p = libc::memrchr(haystack, n1, haystack_len);
if p.is_null() {
None
} else {
Some(p as usize - haystack as usize)
}
}
}
}