pub trait Pattern: Sealed {
type Output;
type Owned: Pattern;
type FindAllImpl<A>: Iterator<Item = (Range<usize>, Self::Output)> + FusedIterator
where A: Accessor;
type RFindAllImpl<A>: Iterator<Item = (Range<usize>, Self::Output)> + FusedIterator
where A: Accessor;
}Expand description
Trait for types that can be matched on.
This sealed trait provides ad-hoc polymorphism for methods such as
find which involve searching a rope for a substring,
Similarly to the standard library trait std::str::pattern::Pattern, the
type of Pattern provided determines the match condition:
| Pattern type | Match condition |
|---|---|
&str | is substring |
String, &String | is substring |
Rope, &Rope | is substring |
char | is contained in rope |
&[char], Vec<char> | any char in slice is contained in rope |
F: Fn(char) -> bool | F returns true for a char in rope |
The type of pattern likewise determines the complexity of the search. In the
following table, N represents the length of the needle, or when the needle
is a predicate, its execution time. H represents the length of the hasystack.
Note most search algorithms allocate O(N) temprorary storage regardless of
whether the needle is borrowed or owned.
| Pattern type | Time complexity | Space complexity |
|---|---|---|
&str | O(N + H log H) | O(N) |
String, &String | O(N + H log H) | O(N) |
Rope, &Rope | O(N + H log H) | O(N) |
char | O(H log H) | O(1) |
&[char] | O(N log N + H log H log N) | O(N) |
Vec<char> | O(N log N + H log H log N) | O(1) |
F: Fn(char) -> bool | O(NH log H) | O(1) |
All of this trait’s methods are #[doc(hidden)] and are excluded from this
crate’s semantic versioning contract.
Required Associated Types§
Sourcetype Output
type Output
For some patterns, this type is returned along with the match range to
indicate what was matched. Patterns that match on character predicates
or sets of characters have an output of char. Patterns that match on
a single string just output ().
Sourcetype Owned: Pattern
type Owned: Pattern
The equivalent owned version of this pattern. This type appears in the
signature of FindAll::into_owning but
is otherwise uninteresting for consumers of this crate.
Sourcetype FindAllImpl<A>: Iterator<Item = (Range<usize>, Self::Output)> + FusedIterator
where
A: Accessor
type FindAllImpl<A>: Iterator<Item = (Range<usize>, Self::Output)> + FusedIterator where A: Accessor
The type which implements forward search for this pattern. This type
in bounds on iterator implementations on FindAll but is otherwise
uninteresting for consumers of this crate.
Sourcetype RFindAllImpl<A>: Iterator<Item = (Range<usize>, Self::Output)> + FusedIterator
where
A: Accessor
type RFindAllImpl<A>: Iterator<Item = (Range<usize>, Self::Output)> + FusedIterator where A: Accessor
The type which implements reverse search for this pattern. This type
in bounds on iterator implementations on RFindAll but is otherwise
uninteresting for consumers of this crate.
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.