Trait pattern_3::haystack::Hay

source · 
pub unsafe trait Hay {
    type Index: Copy + Debug + Eq;

    fn empty<'a>() -> &'a Self;
    fn start_index(&self) -> Self::Index;
    fn end_index(&self) -> Self::Index;
    unsafe fn next_index(&self, index: Self::Index) -> Self::Index;
    unsafe fn prev_index(&self, index: Self::Index) -> Self::Index;
    unsafe fn slice_unchecked(&self, range: Range<Self::Index>) -> &Self;
}
Expand description

Borrowed Haystack.

Every Haystack type can be borrowed as references to Hay types. This allows multiple similar types to share the same implementation (e.g. the haystacks &[T], &mut [T] and Vec<T> all have the same corresponding hay type [T]).

In the other words, a Haystack is a generalized reference to Hay. Hays are typically implemented on unsized slice types like str and [T].

Safety

This trait is unsafe as there are some unchecked requirements which the implementor must uphold. Failing to meet these requirements would lead to out-of-bound access. The safety requirements are written in each member of this trait.

Required Associated Types§

The index type of the haystack. Typically a usize.

Splitting a hay must be sublinear using this index type. For instance, if we implement Hay for a linked list, the index should not be an integer offset (usize) as this would require O(n) time to chase the pointer and find the split point. Instead, for a linked list we should directly use the node pointer as the index.

Safety

Valid indices of a single hay have a total order, even this type does not require an Ord bound — for instance, to order two linked list cursors, we need to chase the links and see if they meet; this is slow and not suitable for implementing Ord, but conceptually an ordering can be defined on linked list cursors.

Required Methods§

Creates an empty hay.

Safety

An empty hay’s start and end indices must be the same, e.g.

extern crate pattern_3;
use pattern_3::Hay;

let empty = <str>::empty();
assert_eq!(empty.start_index(), empty.end_index());

This also suggests that there is exactly one valid index for an empty hay.

There is no guarantee that two separate calls to .empty() will produce the same hay reference.

Obtains the index to the start of the hay.

Usually this method returns 0.

Safety

Implementation must ensure that the start index of hay is the first valid index, i.e. for all valid indices i of self, we have self.start_index() <= i.

Obtains the index to the end of the hay.

Usually this method returns the length of the hay.

Safety

Implementation must ensure that the end index of hay is the last valid index, i.e. for all valid indices i of self, we have i <= self.end_index().

Returns the next immediate index in this haystack.

Safety

The index must be a valid index, and also must not equal to self.end_index().

Implementation must ensure that if j = self.next_index(i), then j is also a valid index satisfying j > i.

Examples
use pattern_3::Hay;

let sample = "A→😀";
unsafe {
    assert_eq!(sample.next_index(0), 1);
    assert_eq!(sample.next_index(1), 4);
    assert_eq!(sample.next_index(4), 8);
}

Returns the previous immediate index in this haystack.

Safety

The index must be a valid index, and also must not equal to self.start_index().

Implementation must ensure that if j = self.prev_index(i), then j is also a valid index satisfying j < i.

Examples
use pattern_3::Hay;

let sample = "A→😀";
unsafe {
    assert_eq!(sample.prev_index(8), 4);
    assert_eq!(sample.prev_index(4), 1);
    assert_eq!(sample.prev_index(1), 0);
}

Obtains a child hay by slicing self.

Safety

The two ends of the range must be valid indices. The start of the range must be before the end of the range (range.start <= range.end).

Implementations on Foreign Types§

Implementors§