Non-allocating search for a word in a stream by rotate-and-read

rotate_and_read_search.rs

use std::io::Read;

fn fill(buf: &mut [u8]) {
  for (i, n) in buf.iter_mut().enumerate() {
    *n = i as u8;
  }
}

fn rotate<T: Copy + Default>(buf: &mut [T], at: usize) -> usize {

  let num = buf.len() - at;
  let ptr = buf[at..].as_ptr(); // as *const T;

  unsafe {
    std::ptr::copy(ptr, buf[0..].as_mut_ptr(), num);
  }

//  for n in at..buf.len() {
//    let tmp = std::mem::replace(&mut buf[n], T::default());
//    std::mem::replace(&mut buf[n-at], tmp);
//  }

  num
}

fn position<T: PartialEq>(buf: &[T], comp: &[T]) -> Option<usize> {
  let mut matches = 0;
  let result = buf.iter().position(|v| {
    if *v == comp[matches] {
      matches += 1;
    }
    else {
      matches = 0;
    }

    if matches == comp.len() {
      true
    }
    else {
      false
    }
  });

  match result {
    Some(n) => Some(n + 1 - matches),
    _ => None
  }
}

fn find_in_stream<T: Read>(mut buf: Vec<u8>, mut stream: T, phrase: &[u8]) 
  -> Option<usize> {

  let mut consumed = 0;
  let mut read_from = 0;
  let mut pos = None;

  loop {
    match stream.read(&mut buf[read_from..]) {
      Ok(0) | Err(_) => break,
      Ok(_) => {}
    }

    if let Some(n) = position(&buf, phrase) {
      pos = Some(n + consumed);
      break;
    }
  
    read_from = buf.len() / 2;
    consumed += rotate(&mut buf, read_from);
  }

  pos
}

fn main() {
    println!("Hello, world!");
}

#[cfg(test)]
mod tests {

  extern crate std;
  use std::vec::Vec;
  use std::io::Cursor;
  use super::{fill, rotate, find_in_stream};

  const PHRASE: &'static [u8] 
    = b"The quick brown fox jumps over the lazy dog";
  
  #[test]
  fn should_rotate() {

    let mut buf: Vec<u8> = Vec::with_capacity(10);
    buf.resize(10, 0x00);
    fill(&mut buf);
 
    let i = rotate(&mut buf, 8);

    assert_eq!(&buf[..i], &[8, 9]);
  }

  #[test]
  fn should_find_word_at_correct_position() {

    const BUFFER_SIZE: usize = 16;
    let mut buf = Vec::<u8>::with_capacity(BUFFER_SIZE);
    buf.resize(BUFFER_SIZE, 0x00);

    let reader = Cursor::new(PHRASE);

    assert_eq!(Some(20), find_in_stream(buf, reader, b"jumps"));
  }
}