Trait pattern_3::haystack::Haystack[−][src]

pub trait Haystack: Deref + Sized where
    Self::Target: Hay, {
    fn empty() -> Self;

    unsafe fn split_around(
        self, 
        range: Range<<Self::Target as Hay>::Index>
    ) -> [Self; 3];

    unsafe fn slice_unchecked(
        self, 
        range: Range<<Self::Target as Hay>::Index>
    ) -> Self;

    fn restore_range(
        &self, 
        original: Range<<Self::Target as Hay>::Index>, 
        parent: Range<<Self::Target as Hay>::Index>
    ) -> Range<<Self::Target as Hay>::Index>;
}

Linear splittable structure.

A Haystack is implemented for reference and collection types such as &[T], &mut [T] and Vec<T>. Every haystack can be borrowed as an underlying representation call a Hay. Multiple haystacks may share the same hay type, and thus share the same implementation of pattern search algorithms.

Required Methods

Creates an empty haystack.

Splits the haystack into 3 slices around the given range.

This method splits self into 3 non-overlapping parts:

  1. Before the range (self[..range.start]),
  2. Inside the range (self[range]), and
  3. After the range (self[range.end..])

The returned array contains these 3 parts in order.

Safety

Caller should ensure that the starts and end indices of range are valid indices for the haystack self.

If the haystack is a mutable reference (&mut A), implementation must ensure that the 3 returned haystack are truly non-overlapping in memory. This is required to uphold the "Aliasing XOR Mutability" guarantee. If a haystack cannot be physically split into non-overlapping parts (e.g. in OsStr), then &mut A should not implement Haystack either.

Examples

use pattern_3::Haystack;

let haystack = &mut [0, 1, 2, 3, 4, 5, 6];
let [left, middle, right] = unsafe { haystack.split_around(2..6) };
assert_eq!(left, &mut [0, 1]);
assert_eq!(middle, &mut [2, 3, 4, 5]);
assert_eq!(right, &mut [6]);

Subslices this haystack.

Safety

The starts and end indices of range must be valid indices for the haystack self.

Transforms the range from relative to self's parent to the original haystack it was sliced from.

Typically this method can be simply implemented as

(original.start + parent.start)..(original.start + parent.end)

If this haystack is a SharedHaystack, this method would never be called.

Safety

The parent range should be a valid range relative to a hay a, which was used to slice out self: self == &a[parent].

Similarly, the original range should be a valid range relative to another hay b used to slice out a: a == &b[original].

The distance of parent must be consistent with the length of self.

This method should return a range which satisfies:

self == &b[parent][original] == &b[range]

Slicing can be destructive and invalidates some indices, in particular for owned type with a pointer-like index, e.g. linked list. In this case, one should derive an entirely new index range from self, e.g. returning self.start_index()..self.end_index().

Examples

use pattern_3::Haystack;

let hay = b"This is a sample haystack";
let this = hay[2..23][3..19].to_vec();
assert_eq!(&*this, &hay[this.restore_range(2..23, 3..19)]);

Implementations on Foreign Types

impl<'a, A: Hay + ?Sized + 'a> Haystack for &'a A
[src]

impl<'h, T: 'h> Haystack for &'h mut [T]
[src]

impl<T> Haystack for Vec<T>
[src]

impl<'h> Haystack for &'h mut str
[src]

Implementors