//! # space-search
//!
//! A library providing basic generic depth-first, breadth-first, heuristic-guided, and A* based search space exploration algorithms.
//!
//! Implement [`Searchable`] + [`SolutionIdentifiable`] to perform breadth-first or depth-first searching. Implement [`Scoreable`] as well to perform heuristically guided search space exploration. Finally, additionally implement [`CostSearchable`] to perform A* based search exploration. Pass them to [`Searcher`] to create an iterator that will search for a solution.
//!
//! [`Searcher`] requires that you specify a `Manager` type that determines the strategy, return result, and optimization of the search algorithm. Choose one of the searchers defined in the hierarchy of the [`search`] module to fit your individual needs.
//!
//! * Implement [`Scoreable`] to utilize the `guided` search strategy based managers, which will prioritize searching states with a lower associated score first. Additionally, implement [`CostSearchable`] to make use of the A* based search managers in the `a_star` module. If implementing [`Scoreable`] is too complex or unnecessary for your use case, then you may use the `unguided` search managers, which explore the space naively in a depth-first or breadth-first manner, toggleable by a flag on the manager itself.
//! * Use a `route` based manager to yield results consisting of the sequence of steps taken from the starting state to the ending state. Use a `no_route` manager to just yield the solution state alone. Route based managers require that your state type implement [`Clone`].
//! * Implement [`Eq`] + [`std::hash::Hash`] + [`Clone`] for your [`Searchable`] type to benefit from prior explored state checking optimization using a `hashable` manager; if youre unable to, then use an `unhashable` manager, which does not require these additional bounds, but will likely explore the space much less efficiently unless cyclic traversal is not an inherent property of your search space.
//!
//! When implementing [`Scoreable`], make sure that lower scoring states are closer to a solution.
//!
//! ```
//! use space_search::*;
//! use std::{vec, hash::Hash};
//!
//! #[derive(Clone, Debug, PartialEq, Eq, Hash)]
//! struct Pos(i32, i32);
//!
//! impl Searchable for Pos {
//! fn next_states(&self) -> impl Iterator<Item = Self> {
//! let &Pos(x, y) = self;
//! [
//! Pos(x - 1, y),
//! Pos(x, y - 1),
//! Pos(x + 1, y),
//! Pos(x, y + 1),
//! ].into_iter()
//! }
//! }
//!
//! impl SolutionIdentifiable for Pos {
//! fn is_solution(&self) -> bool {
//! let &Pos(x, y) = self;
//! x == 5 && y == 5
//! }
//! }
//!
//! let mut searcher: Searcher<search::unguided::no_route::hashable::Manager<_>, _> = Searcher::new(Pos(0, 0));
//! assert_eq!(searcher.next(), Some(Pos(5, 5)));
//! ```
use std::collections::VecDeque;
pub mod search;
/// Basic trait for depth-first and breadth-first search space exploration.
///
/// Implement this + [`SolutionIdentifiable`] for your state type to perform search-space exploration.
pub trait Searchable: Sized {
/// Yield all adjacent explorable states reachable from this state.
fn next_states(&self) -> impl Iterator<Item = Self>;
}
/// Trait that allows a state to be identified as a solution.
///
/// Implement this + [`Searchable`] for your state type to perform search-space exploration.
pub trait SolutionIdentifiable {
/// Return `true` if this state is a solution state.
fn is_solution(&self) -> bool;
}
/// Trait for search space exploration guided by a heuristic.
///
/// Implement this + [`Searchable`] + [`SolutionIdentifiable`] to perform heuristically-guided search-space exploration.
///
/// New states are explored in the order of
/// lowest-scoring first, biasing the search exploration in the direction of a solution. Ensure the scores
/// returned by [`Scoreable::score`] are decreasing with the proximity to a solution.
pub trait Scoreable {
/// Type used to represent a state's score.
/// Common types can be [`i32`], [`usize`], an ordered float type, or your own type implementing [`Ord`].
type Score: Ord;
/// Score function used for heuristic exploration. New states are explored in the order of
/// lowest-scoring first; ensure the scores
/// returned by this function decrease with the proximity to a solution.
fn score(&self) -> Self::Score;
}
/// Trait for search space exploration guided by a cost function & heuristic.
///
/// Implement this + [`Scoreable`] + [`SolutionIdentifiable`] to perform A* guided search-space exploration.
///
/// [`Searchable`] is automatically implemented if this trait is implemented.
pub trait CostSearchable: Scoreable + Sized {
/// Yield all adjacent explorable states reachable from this state, paired with the associated cost
/// of traversing from the current state each new state.
fn next_states_with_costs(&self) -> impl Iterator<Item = (Self, Self::Score)>;
}
// this doesnt work unfortunately :(
// we can only have one blanket impl or the other
// /// Marker trait to auto-implement [`CostSearchable`] for any type that already implements [`Scoreable`] + [`Searchable`]; the cost
// /// is assumed to be 1 for all states returned by [`Searchable::next_states`].
// pub trait CostSearchableForSearchable {}
// impl<T> CostSearchable for T
// where
// T: Scoreable + Searchable + CostSearchableForSearchable,
// T::Score: One,
// {
// fn next_states_with_costs(&self) -> impl Iterator<Item = (Self, Self::Score)> {
// self.next_states().map(|s| (s, T::Score::one()))
// }
// }
impl<T> Searchable for T
where
T: CostSearchable,
{
fn next_states(&self) -> impl Iterator<Item = Self> {
self.next_states_with_costs().map(|(s, _)| s)
}
}
/// Internal.
///
/// Used to represent states paired with their scores in guided exploration managers.
struct OrderedSearchable<T, C> {
state: T,
score: C,
}
impl<S> From<S> for OrderedSearchable<S, S::Score>
where
S: Scoreable,
{
fn from(state: S) -> Self {
let score = state.score();
OrderedSearchable { state, score }
}
}
impl<S> From<StateParent<S>> for OrderedSearchable<StateParent<S>, S::Score>
where
S: Scoreable,
{
fn from(pair: StateParent<S>) -> Self {
let score = pair.state.score();
OrderedSearchable { state: pair, score }
}
}
impl<T, C> PartialEq for OrderedSearchable<T, C>
where
C: PartialEq,
{
fn eq(&self, other: &Self) -> bool {
self.score == other.score
}
}
impl<T, C> Eq for OrderedSearchable<T, C> where C: Eq {}
impl<T, C> PartialOrd for OrderedSearchable<T, C>
where
C: PartialOrd,
{
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
other.score.partial_cmp(&self.score)
}
}
impl<T, C> Ord for OrderedSearchable<T, C>
where
C: Ord,
{
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.score.cmp(&self.score)
}
}
/// Internal.
///
/// Used to represent states with no additional context in solution-only yielding managers.
pub struct NoContext<S>(S);
impl<S> AsRef<S> for NoContext<S> {
fn as_ref(&self) -> &S {
&self.0
}
}
/// Internal.
///
/// Used to represent states with the added context of their parent state
/// in solution-route yielding managers.
#[derive(Clone)]
pub struct StateParent<S> {
state: S,
parent: Option<usize>,
}
impl<S> AsRef<S> for StateParent<S> {
fn as_ref(&self) -> &S {
&self.state
}
}
/// Internal.
///
/// Used to represent states with the added context of their
/// cumulative rolling cost for A* based managers.
pub struct StateCumulativeCost<S, C> {
state: S,
cumulative_cost: C,
}
impl<S, C> AsRef<S> for StateCumulativeCost<S, C> {
fn as_ref(&self) -> &S {
&self.state
}
}
/// Internal.
///
/// Used to represent states with the added context of their parent state &
/// cumulative rolling cost for A* based solution route-yielding managers.
#[derive(Clone)]
pub struct StateParentCumulativeCost<S, C> {
state: S,
parent: Option<usize>,
cumulative_cost: C,
}
impl<S, C> AsRef<S> for StateParentCumulativeCost<S, C> {
fn as_ref(&self) -> &S {
&self.state
}
}
impl<S, C> From<StateParentCumulativeCost<S, C>> for StateParent<S> {
fn from(
StateParentCumulativeCost { state, parent, .. }: StateParentCumulativeCost<S, C>,
) -> Self {
StateParent { state, parent }
}
}
/// Internal.
///
/// Trait abstracting all exploration managers' common functionality.
pub trait ExplorationManager {
type State;
type YieldResult;
type FringeItem: AsRef<Self::State>;
type CurrentStateContext;
type NextStatesIterItem;
fn initialize(initial_state: Self::State) -> Self;
fn pop_state(&mut self) -> Option<Self::FringeItem>;
fn prepare_result_from(&self, item: Self::FringeItem) -> Self::YieldResult;
fn valid_state(&mut self, item: &Self::FringeItem) -> bool;
fn place_state(&mut self, item: Self::FringeItem);
fn register_current_state(&mut self, item: &Self::FringeItem) -> Self::CurrentStateContext;
fn prepare_state(
&self,
context: &Self::CurrentStateContext,
state: Self::NextStatesIterItem,
) -> Self::FringeItem;
fn next_states_iter(
current_state: &Self::State,
) -> impl Iterator<Item = Self::NextStatesIterItem>;
}
/// State space exploration iterator.
///
/// Create an instance of this to explore a search space.
pub struct Searcher<M> {
pub manager: M,
}
impl<M> Searcher<M> {
/// Create a new search iterator from an initial state.
pub fn new(initial_state: M::State) -> Self
where
M: ExplorationManager,
{
Self {
manager: M::initialize(initial_state),
}
}
/// Create a new search iterator from a default initial state.
pub fn new_with_default() -> Self
where
M: ExplorationManager,
M::State: Default,
{
Self::new(Default::default())
}
}
impl<M> Iterator for Searcher<M>
where
M: ExplorationManager,
M::State: SolutionIdentifiable,
{
type Item = M::YieldResult;
fn next(&mut self) -> Option<Self::Item> {
loop {
let current_state = self.manager.pop_state()?;
if current_state.as_ref().is_solution() {
return Some(self.manager.prepare_result_from(current_state));
}
let context = self.manager.register_current_state(¤t_state);
for item in M::next_states_iter(current_state.as_ref()) {
let new_item = self.manager.prepare_state(&context, item);
if self.manager.valid_state(&new_item) {
self.manager.place_state(new_item);
}
}
}
}
}
fn prepare_result_from_state_parent_map<S>(
parents: &[StateParent<S>],
StateParent {
mut state,
parent: mut maybe_parent_index,
}: StateParent<S>,
) -> Vec<S>
where
S: Clone,
{
let mut result = VecDeque::new();
while let Some(parent_index) = maybe_parent_index {
result.push_front(state);
let StateParent {
state: new_state,
parent: new_parent_index,
} = parents
.get(parent_index)
.expect("Parent state will always exist if parent index exists")
.clone();
state = new_state;
maybe_parent_index = new_parent_index;
}
result.push_front(state);
result.into()
}